text:
Asymmetrical KOTH: Catch the Cat (Catcher Thread)
UPDATE:
The gist-files are updated (including new submissions) as the Controller.java did not catch Exceptions (only errors). It does now catch errors and exceptions and also prints them.
This challenge consists of two threads, this is the catcher thread, the cat thread can be found here.
The controller can be downloaded here.
This is an asymmetrical KOTH: Each submission is either a cat or a catcher. There are games between each pair of each a cat and a catcher. The cats and the catchers have separate rankings.
Catcher
There is a cat on a hexagonal grid. Your task is to catch it as fast as possible. Every turn, you can place a water bucket on one grid cell in order to prevent the cat from being able to go there. But the cat is not (perhaps) that dumb, and whenever you place a bucket, the cat will move to another grid cell. Since the grid is hexagonal, the cat can go in 6 different directions. Your goal is to surround the cat with water buckets, the faster the better.
Cat
You know the catcher wants to catch you by placing water buckets around you. Of course you try to evade, but as you are a lazy cat (as cats are) you exactly take one step at the time. This means you cannot stay on the same place you, but you have to move to one of the six surrounding spots. Whenever you see that the catcher placed a new water bucket you go to another cell. Of course you try to evade as long as possible.
Grid
The grid is hexagonal, but as we do not have hexagonal data structures, we take a 11 x 11 square 2d array and mimic the hexagonal 'behavior' that the cat can only move in 6 directions:

The topology is toroidal, that means if you step on a cell 'outside' of the array, you will just be transferred to the corresponding cell on the other side of the array.
Game
The cat starts out at given position in the grid. The catcher can do the first move, then the cat and its catcher alternate moves until the cat is caught. The number of steps is the score for that game. The cat tries to get a score as great as possible, the catcher tries to get a score as low as possible. The average sum over all the games you participated in will be the score of your submission. There are two separate rankings, one for the cat, one for the catchers.
Controller
The given controller is written in Java. As a catcher or a cat you each have to each complete implement a Java class (there are already some primitive examples) and place it in the players package (and update the list of cats/catchers in the Controller class), but you also may write additional functions within that class. The controller comes with each two working examples of simple cats/catcher classes.
The field is a 11 x 11 2D- int array that stores the values of the current states of the cells. If a cell is empty, it has value 0, if there is a cat it has value -1 and if there is a bucket there is a 1.
There are a few given functions you can use: isValidMove()/isValidPosition() are for checking whether your move (cat) / position (catcher) is valid.
Each time it is your turn, your function takeTurn() is called. The argument contains the a copy of the current grid an has methods like read(i,j) for reading the cell at (i,j), as well as isValidMove()/ isValidPosition() that checks the validity of your answer. This also manages the wrapping over of the toroidal topology, that means even if the grid is only 11 x 11, you still can access the cell (-5,13).
The method should return a int array of two elements, which represent possible moves. For the cats these are {-1,1},{0,1},{-1,0},{1,0},{0,-1},{1,-1} which represent the relative position of where the cat wants to go, and the catchers return the absolute coordinates of where they want to place a bucket {i,j}.
If your method produces an invalid move, your submission will be disqualified. The move is considered as invalid, if at your destination is already a bucket or the move is not allowed / destination already occupied (as a cat), or if there is already a bucket/cat (as a catcher). You can check that before hand with the given functions.
Your submission should work reasonably fast. If your method takes longer than 200ms for each step it will also be disqualified. (Preferably much less...)
The programs are allowed to store information between the steps.
Submissions

You can make as many submissions as you want.
Please do not significantly alter submissions you've already submitted.
Please each submissions in a new answer.
Each submission should preferably have it's unique name.
The submission should consist of the code of your class as well as a description that tells us how your submission works.
You can write the line <!-- language: lang-java --> before your source code in order to get automatic syntax highlighting.

Scoring
All cats will compete against all catchers the same number of times. I'll try to update the current scores frequently, the winners will be determined when the activity has decreased.
This challenge is inspired by this old flash game
Thanks @PhiNotPi for testing and giving some constructive feedback.
Current Scores (100 Games per pairing)

Name (Catcher)
Score
Rank
Author

RandCatcher
191674
8
flawr

StupidFill
214246
9
flawr

Achilles
76820
6
The E

Agamemnon
74844
5
The E

CloseCatcher
54920
4
randomra

ForwordCatcher
94246
7
MegaTom

Dijkstra
46500
2
TheNumberOne

HexCatcher
48832
3
randomra

ChoiceCatcher
43828
1
randomra

Name (Cat)
Score
Rank
Author

RandCat
77928
7
flawr

StupidRightCat
81794
6
flawr

SpiralCat
93868
5
CoolGuy

StraightCat
82452
9
CoolGuy

FreeCat
106304
3
randomra

RabidCat
77770
8
cain

Dijkstra's Cat
114670
1
TheNumberOne

MaxCat
97768
4
Manu

ChoiceCat
113356
2
randomra

What program makes the animations?

The animation is just the GUI (when starting the controller you have to set PRINT_STEPS = true , more detailed settings in the file MyFrame.java). Then I recorded this with LICEcap and edited it with GIMP. If you have further questions just ask!

If you add user input to the controller, it could make a nice software with the GUI and the bots already written. It would be also interesting to see how much can humans crack/abuse the specific bot strategies.

Also, can my bot keep information from the previous match to try to find a better move-sequence against the same bot?  I suppose not because it gets better the more rounds you do. It would also have to guess if it is playing against a new bot, so the running order would matter too.

@randomra Oh, that is indeed a fun idea, I see if I could do that today or tomorrow! No you can only store information within the same game (until the cat is caught), but not across multiple games. But I think that this would be another whole different challenge=)

@flawr Your last edit on hexcatcher messed up the code considerably.

Why is the scores of the cats un-ordered?

Both the cats and the catchers are in the order of submission=)

Achilles
Achilles isn't too bright but he is ruthlessly efficient. First he stops the cat from using the wrap around of the board, then he divides the board into two. Then he keeps on dividing the part of the board the cat is in into half until the cat is trapped.
Demonstration RandCat vs Achilles

package players;
/**
 * @author The E
 */
import main.*;

public class Achilles implements Catcher
{
    public Achilles() {

    }
    @Override
    public String getName() {

        return "Achilles";
    }

    @Override
    public int[] takeTurn(Field f) {
        try{
        if(f.read(0, f.SIZE-1)!=Field.BUCKET)
        {
            //Make the first line

            for(int j = 0; j<f.SIZE; j++)
            {
                if(f.read(0, j) == Field.EMPTY)
                {
                    return new int[]{0,j};
                }
            }
            return WasteGo(f);

        }
        else if (f.read(f.SIZE-1, 0)!=Field.BUCKET)
        {
            //Make the second line
            for(int i = 0; i<f.SIZE; i++)
            {
                if(f.read(i, 0) == Field.EMPTY)
                {
                    return new int[]{i,0};
                }
            }
            //The cat got in the way
            for(int j = 0; j<f.SIZE; j++)
            {
                if(f.read(1, j) == Field.EMPTY)
                {
                    return new int[]{1,j};
                }
            }
            return WasteGo(f);
        }
        else
        {
            return TrapCat(1,1,f.SIZE-1, f.SIZE-1, false, f);

        }
        }
        catch (Exception e)
        {
            return WasteGo(f);
        }
    }
    private int[] TrapCat(int i1, int j1, int i2, int j2, Boolean direction, Field f) {
        for(int a = 0; a<f.SIZE+10; a++)
        {
            if(direction)
            {

                int height = j2-j1+1;
                int row = j1 + height/2;
                for(int i = i1; i<=i2; i++)
                {
                    if(f.read(i, row)==Field.EMPTY)
                    {
                        return new int[]{i,row};
                    }
                }

                    //Done that Row
                    //Find cat
                    if(f.findCat()[1]>row)
                    {
                        //he's above the line
                        j1 = row+1;
                        direction = !direction;
                        //return TrapCat(i1, row+1, i2, j2, !direction, f);
                    }
                    else
                    {
                        //he's below the line
                        j2 = row - 1;
                        direction = !direction;
                        //return TrapCat(i1, j1, i2, row-1, !direction, f);
                    }

            }
            else
            {
                int bredth = i2-i1+1;
                int column = i1 + bredth/2;
                //Continue making the line
                for(int j = j1; j<=j2; j++)
                {
                    if(f.read(column,j)==Field.EMPTY)
                    {
                        return new int[]{column,j};
                    }
                }

                    //Done that Column
                    //Find cat
                    if(f.findCat()[0]>column)
                    {
                        //he's right of the line
                        i1 = column + 1;
                        direction = !direction;
                        //return TrapCat(column+1, j1, i2, j2, !direction, f);
                    }
                    else
                    {
                        //he's left of the line
                        i2 = column -1;
                        direction = !direction;
                        //return TrapCat(i1, j1, column-1, j2, !direction, f);
                    }

            }
        }
        return WasteGo(f);
    }
    private int[] WasteGo(Field f) {
        for (int i = 0; i<f.SIZE;i++)
        {
            for(int j=0;j<f.SIZE;j++)
            {
                if(f.read(i,j)==Field.EMPTY)
                {
                    return new int[]{i,j};
                }
            }
        }
        //Something drastic happened
        return new int[]{0,0};
    }

}

Well which one is it now, Achilles or Hector? (Or someone with a dissiociative identity disorder?=)

@flawr Achilles, lol I changed the name half way through (it's more apt to name the catcher Achilles and the cat Hector) but forgot to change the java - it's what happens when you program after tea :(

But Hector would rather be a dogs name=) Thanks for your submission works great. I hope you do not mind that I also include the 'preamble' in your code.

Yeah no problem. Hector does sound like a dogs name...

I just ran a simulation (10000 games for each pairing) and Achilles was disqualified, due to repeated StackOverflowError. I think the recursion did not end: http://pastebin.com/9n6SQQnd

I think because of my wrong error/exception handling you migh not have noticed this, so I'm trying to improve my Controller.

@flawr OK I think I've removed that bug- no longer uses recursion instead I've used a for loop (which has exactly the same effect as recursion but I can limit how long it goes on for) and I've added an emergency try/catch to waste the go if something goes drastically wrong. No Exceptions with 100,000 games so looking positive :)

Agamemnon
Agamemnon splits the cats area in half with a vertical line until the cat only has a strip of width 2 to move in, at which point he traps the cat.
Agamemnon vs RandCat:

package players;
/**
 * @author The E
 */
import main.*;

    public class Agamemnon implements Catcher {
        boolean up = true;
        @Override
        public String getName() {
            return "Agamemnon";
        }

        @Override
        public int[] takeTurn(Field f) {
            //First Make Line in column 1
            for(int j = 0; j<f.SIZE; j++)
            {
                if(f.read(0, j)==Field.EMPTY)
                {
                    return new int[]{0,j};
                }
            }
            //Then in column SIZE/2
            for(int j = 0; j<f.SIZE; j++)
            {
                if(f.read(f.SIZE/2, j)==Field.EMPTY)
                {
                    return new int[]{f.SIZE/2,j};
                }
            }
            //Then work out where the cat is
            int left, right;
            int cati = f.findCat()[0];
            if(cati<f.SIZE/2)
            {
                left = 1;
                right = f.SIZE/2-1;
            }
            else
            {
                left = f.SIZE/2+1;
                right = f.SIZE-1;
            }
            while(right-left>1)
            {
                //If the cat is not in a two width column
                //Split the area the cat is in in half
                int middleColumn = (left+right)/2;
                for(int j = 0; j<f.SIZE; j++)
                {
                    if(f.read(middleColumn, j)==Field.EMPTY)
                    {
                        return new int[]{middleColumn,j};
                    }
                }
                //If we got here we had finished that column
                //So update left and/or right
                if(cati<middleColumn)
                {
                    //he's left of the middle Column
                    right = middleColumn - 1;
                }
                else
                {
                    //he's right of the middle Column
                    left = middleColumn+1;
                }
                //Repeat
            }
            //Otherwise try to trap the cat
            //Make a line up and down on the opposite side of the cat
            int catj = f.findCat()[1];
            if(left!=right){
                if(cati==left)
                {
                    if(f.read(right, catj)==Field.EMPTY)
                    {
                        return new int[]{right, catj};
                    }
                    if(f.read(right, catj-1)==Field.EMPTY)
                    {
                        return new int[]{right, catj-1};
                    }
                    if(f.read(right, catj+1)==Field.EMPTY)
                    {
                        return new int[]{right, catj+1};
                    }

                }
                else
                {
                    if(f.read(left, catj)==Field.EMPTY)
                    {
                        return new int[]{left, catj};
                    }
                    if(f.read(left, catj-1)==Field.EMPTY)
                    {
                        return new int[]{left, catj-1};
                    }
                    if(f.read(left, catj+1)==Field.EMPTY)
                    {
                        return new int[]{left, catj+1};
                    }

                }
            }
            //Alternate between above and below
            if(up)
            {
                up = !up;
                if(f.read(cati, catj+1)==Field.EMPTY)
                {

                    return new int[]{cati, catj+1};
                }
            }
            up = !up;
            if(f.read(cati, catj-1)==Field.EMPTY)
            {

                return new int[]{cati, catj-1};
            }
            return WasteGo(f);
        }

        private int[] WasteGo(Field f) {
            for (int i = 0; i<f.SIZE;i++)
            {
                for(int j=0;j<f.SIZE;j++)
                {
                    if(f.read(i,j)==Field.EMPTY)
                    {
                        return new int[]{i,j};
                    }
                }
            }
            //Something drastic happened
            return new int[]{0,0};
        }
    }

This catcher does consistently better than Achilles and I think he's different enough to warrant a new answer.

Very nice solution, I was sure Achilles was close to optimal, but now I think even Agamemnon could be improved slightly=)

Yes, Agamemnon has a much better end game trapping algorithm than Achilles, but I'm pretty sure there are some tweaks... Now I'll try and work on a cat :)

@flawr very tiny tweak added to speed up catching in some special cases, this doesn't affect the animation here (elthough I think it might affect SpiralCat's animation)

Question!  What happens if you're about to close a line, but the cat is standing in the last spot?

@Mr.Llama it starts making the next line as if that line had been filled (ie. the cat was in fact a bucket)- not the most effective use of a turn but happens very rarely that it doesn't really matter- the cat has to then move away on its next turn so I can place my bucket there

HexCatcher
If the catcher can get the cat in the inside of a big hexagon with 3 units sides where the corners of the hexagon are already occupied by buckets, the catcher can keep the cat in this area and catch him. The hexagon looks like this:

This is what HexCatcher tries to achieve. It mentally tiles the field with these big hexagons in a way that each corner cell is part of 3 big hexagons.
If there is a chance to keep the cat in the current area by connecting two corners next to the cat, the bot will do that. (E.g. in the image if the cat is at 7,5 we choose 7,6 even if only the 6,6 and 8,5 cells are occupied yet.)
If the previous is not an option we chooses to play a corner which is a part of the area where the cat is. If all such corners are already chosen (like in the image) we choose a cell next to the cat.
Multiple small improvements are possible such as handling wrap-around better (the tiling breaks there) or doing the last couple moves optimally. I might do some of these. If it is not allowed, I will just append it (out of competition) for the ones interested.
DijkstrasCat vs HexCatcher:

package players;
/**
 * @author randomra
 */
import main.Field;

public class HexCatcher implements Catcher {
    public String getName() {
        return "HexCatcher";
    }

    final int[][] o = { { -1, 1 }, { 0, 1 }, { -1, 0 }, { 1, 0 }, { 0, -1 },
            { 1, -1 } };// all valid moves
    final int[][] t = { { -2, 2 }, { 0, 2 }, { -2, 0 }, { 2, 0 }, { 0, -2 },
            { 2, -2 } };// all valid double moves in one direction
    final int[][] h = { { -1, 2 }, { -2, 1 }, { -1, -1 }, { 1, -2 }, { 2, -1 },
            { 1, 1 } };// all valid moves in not one direction
    int opp = 0;

    public int[] takeTurn(Field f) {
        int[] p = f.findCat();
        // center of the hexagon the cat is in
        int[] c = { ((int) p[0] / 3) * 3 + 1, ((int) p[1] / 3) * 3 + 1 };
        // change priority of catching direction at every turn
        opp = 1 - opp;

        // check missing corner piece next to cat
        for (int i = 0; i < 6; i++) {
            int ind = (i + opp * 3) % 6;
            boolean close = false;
            for (int k = 0; k < 6; k++) {
                if (c[0] + h[ind][0] == p[0] + o[k][0]
                        && c[1] + h[ind][1] == p[1] + o[k][1]) {
                    close = true;
                }
            }
            if (f.read(c[0] + h[ind][0], c[1] + h[ind][1]) == 0 && close) {
                return new int[] { c[0] + h[ind][0], c[1] + h[ind][1] };
            }
        }
        // cut off escape route if needed
        for (int i = 0; i < 6; i++) {
            int ind = (i + opp * 3) % 6;
            if (f.read(c[0] + o[ind][0], c[1] + o[ind][1]) == -1
                    && f.read(c[0] + t[ind][0], c[1] + t[ind][1]) == 0) {
                return new int[] { c[0] + t[ind][0], c[1] + t[ind][1] };
            }
        }
        // check any missing corner piece in the area
        for (int i = 0; i < 6; i++) {
            int ind = (i + opp * 3) % 6;
            if (f.read(c[0] + h[ind][0], c[1] + h[ind][1]) == 0) {
                return new int[] { c[0] + h[ind][0], c[1] + h[ind][1] };
            }
        }
        // choose an empty cell next to the cat
        for (int i = 0; i < 6; i++) {
            int ind = (i + opp * 3) % 6;
            if (f.read(p[0] + o[ind][0], p[1] + o[ind][1]) == 0) {
                return new int[] { p[0] + o[ind][0], p[1] + o[ind][1] };
            }
        }
        return null;
    }
}

Dijkstra
He doesn't like cats very much (:v{  >
FreeCat vs Dijkstra (needs updated):

package players;

import main.Controller;
import main.Field;

import java.util.*;

/**
 * @author TheNumberOne
 *
 * Catches the cat.
 */

public class Dijkstra implements Catcher{

    private static final int[][][] CACHE;

    static {
        CACHE = new int[Controller.FIELD_SIZE][Controller.FIELD_SIZE][2];
        for (int x = 0; x < Controller.FIELD_SIZE; x++){
            for (int y = 0; y < Controller.FIELD_SIZE; y++){
                CACHE[x][y] = new int[]{x,y};
            }
        }
    }

    private static final int[][] possibleMoves = {{-1,1},{0,1},{-1,0},{1,0},{0,-1},{1,-1}};
    @Override
    public String getName() {
        return "Dijkstra";
    }

    @Override
    public int[] takeTurn(Field f) {
        long startTime = System.nanoTime();

        final int[] theCat = f.findCat();
        int[] bestMove = {-1,1};
        int[] bestOpenness = {Integer.MAX_VALUE, 0};
        List<int[]> possiblePositions = new ArrayList<>();
        for (int x = 0; x < 11; x++){
            for (int y = 0; y < 11; y++){
                int[] pos = {x,y};
                if (f.isValidPosition(pos)){
                    possiblePositions.add(pos);
                }
            }
        }
        Collections.sort(possiblePositions, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return distance(o1, theCat) - distance(o2, theCat);
            }
        });
        for (int i = 0; i < possiblePositions.size() && System.nanoTime() - startTime < Controller.MAX_TURN_TIME/2; i++){
            int[] pos = possiblePositions.get(i);
            int before = f.field[pos[0]][pos[1]];
            f.placeBucket(pos);
            int[] openness = openness(theCat, f, true);
            if (openness[0] < bestOpenness[0] ||
                    (openness[0] == bestOpenness[0] &&
                            (openness[1] > bestOpenness[1])
                    )
                    ){
                bestOpenness = openness;
                bestMove = pos;
            }
            f.field[pos[0]][pos[1]] = before;
        }
        return bestMove;
    }

    /**
     *
     * @param pos The pos to calculate the openness of.
     * @param f The field to use.
     * @return Two integers. The first integer represents the number of reachable hexagons.
     * The second integer represents how strung out the squares are relative to the pos.
     */
    public static int[] openness(int[] pos, Field f, boolean catZeroWeight){
        Map<int[], Integer> lengths = new HashMap<>();
        PriorityQueue<int[]> open = new PriorityQueue<>(10,new Comparator<int[]>() {
            Map<int[], Integer> lengths;
            @Override
            public int compare(int[] o1, int[] o2) {
                return lengths.get(o1) - lengths.get(o2);
            }
            public Comparator<int[]> init(Map<int[], Integer> lengths){
                this.lengths = lengths;
                return this;
            }
        }.init(lengths));
        Set<int[]> closed = new HashSet<>();
        lengths.put(pos, catZeroWeight ? 0 : 6 - pointsAround(pos, f).size());
        open.add(pos);
        while (open.size() > 0){
            int[] top = open.remove();
            if (closed.contains(top)){
                continue;
            }
            closed.add(top);
            int l = lengths.get(top);
            List<int[]> pointsAround = pointsAround(top, f);

            for (ListIterator<int[]> iter = pointsAround.listIterator(); iter.hasNext();){
                int[] point = iter.next();
                if (closed.contains(point)){
                    iter.remove();
                }
            }

            for (int[] p : pointsAround){
                int length = l + 7 - pointsAround(p, f).size();
                if (lengths.containsKey(p)){
                    length = Math.min(length, lengths.get(p));
                }
                lengths.put(p, length);
                open.add(p);
            }
        }
        int sum = 0;
        for (int integer : lengths.values()){
            sum += integer;
        }
        return new int[]{lengths.size(),sum};
    }

    public static int distance(int[] p1, int[] p2){
        p2 = Arrays.copyOf(p2, 2);
        while (p2[0] < p1[0]){
            p2[0] += 11;
        }
        while (p2[1] < p2[0]){
            p2[1] += 11;
        }
        int lowestDistance = 0;
        for (int dx = 0; dx == 0; dx -= 11){
            for (int dy = 0; dy == 0; dy -= 11){
                lowestDistance = Math.min(lowestDistance,Math.min(Math.abs(p1[0]-p2[0]-dx),Math.min(Math.abs(p1[1]-p2[1]-dy),Math.abs(p1[0]+p1[1]-p2[0]-dx-p2[1]-dy))));
            }
        }
        return Math.min(Math.abs(p1[0]-p2[0]),Math.min(Math.abs(p1[1]-p2[1]),Math.abs(p1[0]+p1[1]-p2[0]-p2[1])));
    }

    public static int[] normalize(int[] p){
        return CACHE[(p[0]%11+11)%11][(p[1]%11+11)%11];
    }

    public static List<int[]> pointsAround(int[] p, Field f){
        int[] cat = f.findCat();
        List<int[]> locations = new ArrayList<>();
        for (int[] move : possibleMoves){
            int[] location = normalize(new int[]{p[0]+move[0], p[1] + move[1]});
            if (f.isValidPosition(location) || Arrays.equals(cat, location)){
                locations.add(location);
            }
        }
        return locations;
    }
}

How he tries to catch the cat:
He analyzes all squares of the board and tries to find the square that minimizes the openness of the board, and maximizes how much the board is strung out; in relation to the cat. The openness and stringiness of a board are computed using a modification of his famous algorithm.
Openness:
The openness of a board relative to a position is the number of reachable positions from that position.
Stringiness:
The stringiness of a board relative to a position is the sum of the distances between the reachable positions and the position.
With last update:
Now, he is much better at catching FreeCat and his own cat all cats. Unfortunately, he is also much worse at catching the crazy uncooperative cats. He could be improved by detecting if the cat is one of the crazy ones and then acting as CloseCatcher.
Bug fixed.

Can confirm it works so far, but by far the slowest but one of the best so far I think. Needs 134 seconds for 100 games against RandCat while doing a total of only 4406 moves! I think I'm gonna have to let my pc run overnight in one of the next days... Can you tell us a bit mor on how it works?

@flawr Added a description.

Still doesn't work for me. Gives me one error: error: cannot infer type arguments for PriorityQueue<> on this line PriorityQueue<int[]> open = new PriorityQueue<>(new Comparator<int[]>() {.

@CoolGuy Are you using java 6? I think you need to update your JDK.

@CoolGuy You can also put an int[] between the two empty diamonds after PriorityQueue.

Tried PriorityQueue<int[]> open = new PriorityQueue<>(new Comparator<int[]>() { and PriorityQueue<int[]> open = new PriorityQueue<int[]>(new Comparator<int[]>() {. The former gave this error and the latter gave error: no suitable constructor found for PriorityQueue(Comparator<int[]>). My javac version is 1.7.0_51 and java version is 1.7.0_71.And This gives "Your Java version: Version 7 Update 71"

Okay, just looked at the documentation, that constructor wasn't added until 1.8 apparently. Fixing right now.

Finally, it worked! Nice cat & catcher ,BTW. +1 :-)

CloseCatcher
Chooses one of the positions where the cat could step in the next step. It chooses the one which would give the most possible paths after 3 steps for the cat if it would move there and the field wouldn't change.
Code is almost identical to my Cat entry, FreeCat, which chooses the direction in a very similar way.
SpiralCat vs CloseCatcher:

package players;
/**
 * @author randomra
 */

import main.Field;
import java.util.Arrays;

public class CloseCatcher implements Catcher {
    public String getName() {
        return "CloseCatcher";
    }

    final int[][] turns = { { -1, 1 }, { 0, 1 }, { -1, 0 }, { 1, 0 },
            { 0, -1 }, { 1, -1 } };// all valid moves
    final int turnCheck = 3;

    public int[] takeTurn(Field f) {

        int[] pos = f.findCat();
        int[] bestMove = { 0, 1 };
        int bestMoveCount = -1;
        for (int[] t : turns) {
            int[] currPos = { pos[0] + t[0], pos[1] + t[1] };
            int moveCount = free_count(currPos, turnCheck, f);
            if (moveCount > bestMoveCount) {
                bestMoveCount = moveCount;
                bestMove = t;
            }
        }
        int[] bestPos = { pos[0] + bestMove[0], pos[1] + bestMove[1] };
        return bestPos;
    }

    private int free_count(int[] pos, int turnsLeft, Field f) {
        if (f.isValidPosition(pos) || Arrays.equals(pos, f.findCat())) {
            if (turnsLeft == 0) {
                return 1;
            }
            int routeCount = 0;
            for (int[] t : turns) {
                int[] currPos = { pos[0] + t[0], pos[1] + t[1] };
                int moveCount = free_count(currPos, turnsLeft - 1, f);
                routeCount += moveCount;
            }
            return routeCount;
        }
        return 0;
    }

}

Nice +1. CloseCatcher easily captures StraightCat

ForwordCatcher
Places a bucket in front of the cat, or if that is taken, places behind.
RabidCat vs ForwordCatcher:

package players;

import main.Field;
import java.util.Arrays;

public class ForwordCatcher implements Catcher {
    public String getName() {
        return "ForwordCatcher";
    }

    private int[] lastPos = {0,0};

    public int[] takeTurn(Field f) {
        int[] temp = lastPos;
        int[] pos = f.findCat();
        lastPos = pos;
        int[] Move = {pos[0]*2-temp[0], pos[1]*2-temp[1]};
        if(f.isValidPosition(Move)){return Move;}
        if(f.isValidPosition(temp)){return temp;}
        Move[0] = pos[0];Move[1] = pos[1]+1;
        return Move;
    }
}

There are quite a few errors, which lead me to the assumption that you did not test your program. Please fix those...

@flawr fixed. sorry about the errors. I did not test it and my Java is not to good.

Nice, so far everything runs smoothely, but I am still unsure whether it will always produce valid moves=)

@flawr The space behind a cat will always be empty for the catcher :)

ChoiceCatcher
Uses the same scoring mechanism as my ChoiceCat entry. There is a little modification which helps to choose relevant cells at the first few steps as ChoiceCat doesn't care about the first few buckets as it doesn't see them as threat.
ChoiceCatcher seems to score considerably better than the current catchers.
ChoiceCat vs ChoiceCatcher:

package players;
/**
 * @author randomra
 */
import java.util.Arrays;

import main.Field;

public class ChoiceCatcher implements Catcher {

    private class Values {
        public final int size;
        private double[][] f;

        Values(int size) {
            this.size = size;
            f = new double[size][size];
        }

        public double read(int[] p) {
            int i = p[0];
            int j = p[1];
            i = (i % size + size) % size;
            j = (j % size + size) % size;
            return f[i][j];
        }

        private double write(int[] p, double v) {
            int i = p[0];
            int j = p[1];
            i = (i % size + size) % size;
            j = (j % size + size) % size;
            return f[i][j] = v;
        }
    }

    final int[][] turns = { { -1, 1 }, { 0, 1 }, { 1, 0 }, { 1, -1 },
            { 0, -1 }, { -1, 0 } };// all valid moves CW order
    final int stepCheck = 5;

    public String getName() {
        return "ChoiceCatcher";
    }

    @Override
    public int[] takeTurn(Field f) {
        int[] bestPos = null;
        double bestPosValue = Double.MAX_VALUE;
        for (int i = 0; i < f.SIZE; i++) {
            for (int j = 0; j < f.SIZE; j++) {
                if (f.read(i, j) == Field.EMPTY) {
                    Field myField = new Field(f);
                    myField.placeBucket(new int[] { i, j });
                    double posValue = catTurnValue(myField);
                    if (posValue < bestPosValue) {
                        bestPosValue = posValue;
                        bestPos = new int[] { i, j };
                    }
                }
            }
        }
        return bestPos;
    }

    private double catTurnValue(Field f) {

        int[] pos = f.findCat();
        double[] values = new double[6];
        int count=0;
        for (int[] t : turns) {
            int[] currPos = { pos[0] + t[0], pos[1] + t[1] };
            double moveValue = movePosValue(currPos, f);
            values[count++]=moveValue;
        }
        Arrays.sort(values);
        return values[5];
    }

    private double movePosValue(int[] pos, Field f) {

        Values v = new Values(f.SIZE);

        for (int ring = stepCheck; ring >= 0; ring--) {
            for (int phase = 0; phase < 2; phase++) {
                for (int sidepos = 0; sidepos < Math.max(1, ring); sidepos++) {
                    for (int side = 0; side < 6; side++) {
                        int[] evalPos = new int[2];
                        for (int coord = 0; coord < 2; coord++) {
                            evalPos[coord] = pos[coord] + turns[side][coord]
                                    * sidepos + turns[(side + 1) % 6][coord]
                                    * (ring - sidepos);
                        }
                        if (phase == 0) {
                            if (ring == stepCheck) {
                                // on outmost ring, init value
                                v.write(evalPos, -1);
                            } else {
                                v.write(evalPos, posValue(evalPos, v, f));
                            }
                        } else {
                            // finalize position value for next turn
                            v.write(evalPos, -v.read(evalPos));
                        }
                    }
                }
            }
        }

        return -v.read(pos);
    }

    private double posValue(int[] pos, Values v, Field f) {
        if (f.read(pos[0], pos[1]) == Field.BUCKET) {
            return 0;
        }
        int count = 0;
        int maxRoutes = 2;
        double[] product = new double[6];
        for (int[] t : turns) {
            int[] tPos = new int[] { pos[0] + t[0], pos[1] + t[1] };
            if (v.read(tPos) > 0) {
                product[count] = 1 - 1 / (v.read(tPos) + 1);
                count++;
            }
        }
        Arrays.sort(product);
        double fp = 1;
        for (int i = 0; i < Math.min(count, maxRoutes); i++) {
            fp *= product[5 - i];
        }
        double fp2 = 1;
        for (int i = 0; i < Math.min(count, 6); i++) {
            fp2 *= product[5 - i];
        }
        double retValue = Math.min(count, maxRoutes) + fp;
        double retValue2 = Math.min(count, 6) + fp2;
        return -retValue - retValue2 / 1000000;
    }

}

RandCatcher
This was made just for testing the controller and just randomly places the buckets (very inefficiently).
package players;

import main.Field;

public class RandCatcher implements Catcher {
    public String getName(){
        return "RandCatcher";
    }
    public int[] takeTurn(Field f){
        int[] pos = {0,0};
        do {
            pos[0] = (int) (Math.random()*f.SIZE);
            pos[1] = (int) (Math.random()*f.SIZE);
        } while( f.isValidPosition(pos)==false );
        return pos;
    }

}

StupidFillCatcher
This was made just for testing the controller. It just fills up column by column until the cat is caught.
package players;

import main.Field;

public class StupidFillCatcher implements Catcher {
    public String getName(){
        return "StupidFillCatcher";
    }
    public int[] takeTurn(Field f){
        for(int i=0; i < f.SIZE; i++){
            for(int j=0; j < f.SIZE; j++){
                if(f.isValidPosition(new int[] {i,j})){
                    return new int[] {i,j};
                }
            }
        }
        return new int[] {0,0};
    }

}


text:
Supersonic domino tilings
Task
Write a program that reads three integers m, n either from STDIN or as command-line arguments, prints all possible tilings of a rectangle of dimensions m × n by 2 × 1 and 1 × 2 dominos and finally the number of valid tilings.
Dominos of an individual tiling have to be represented by two dashes (-) for 2 × 1 and two vertical bars (|) for 1 × 2 dominos. Each tiling (including the last one) has to be followed by a linefeed.
For scoring purposes, you also have to accept a flag from STDIN or as command line argument that makes your program print only the number of valid tilings, but not the tilings itself.
Your program may not be longer than 1024 bytes. It has to work for all inputs such that m × n ≤ 64.
(Inspired by Print all domino tilings of 4x6 rectangle.)
Example
$ sdt 4 2
----
----

||--
||--

|--|
|--|

--||
--||

||||
||||

5
$ sdt 4 2 scoring
5

Scoring
Your score is determined by the execution time of your program for the input 8 8 with the flag set.
To make this a fastest code rather than a fastest computer challenge, I will run all submissions on my own computer (Intel Core i7-3770, 16 GiB PC3-12800 RAM) to determine the official score.
Please leave detailed instructions on how to compile and/or execute your code. If you require a specific version of your language's compiler/interpreter, make a statement to that effect.
I reserve the right to leave submissions unscored if:

There is no free (as in beer) compiler/interpreter for my operating system (Fedora 21, 64 bits).
Despite our efforts, your code doesn't work and/or produces incorrect output on my computer.
Compilation or execution take longer than an hour.
Your code or the only available compiler/interpreter contain a system call to rm -rf ~ or something equally fishy.

Leaderboard
I've re-scored all submissions, running both compilations and executions in a loop with 10,000 iterations for compilation and between 100 and 10,000 iterations for execution (depending on the speed of the code) and calculating the mean.
These were the results:
User          Compiler   Score                              Approach

jimmy23013    GCC (-O0)    46.11 ms =   1.46 ms + 44.65 ms  O(m*n*2^n) algorithm.
steveverrill  GCC (-O0)    51.76 ms =   5.09 ms + 46.67 ms  Enumeration over 8 x 4.
jimmy23013    GCC (-O1)   208.99 ms = 150.18 ms + 58.81 ms  Enumeration over 8 x 8.
Reto Koradi   GCC (-O2)   271.38 ms = 214.85 ms + 56.53 ms  Enumeration over 8 x 8.

Why not make this a GOLF contest? :(

No, I mean a GOLF challenge.

If you had suggested that in the sandbox, I might have. That would have saved my CPU and me a lot of work...

@user23013: No, the results do not have to be sorted. I'll edit the question.

I'm slightly confused. What I got is that every domino type (- or |) must appear at least twice. But then why is there no -||-? Or is it that the side-dominos (-) must always appear consecutively? Some more examples would be nice, too...

@kirbyfan64sos The way I understand it, there's only one type of domino, which you can rotate. If it's horizontal, it looks like this: --. If it's vertical, it is two |, one below the other.

@RetoKoradi That makes sense. Thanks!

isn't this going to be I/O-limited?

@feersum: Possibly. I assumed this would take a lot longer. Shows how much I know about writing fast code. :/

@feersum I'm worried about that, too. Redirecting to /dev/null will cut out part of the I/O overhead. But you still have to generate strings, and it seems likely that this could take much longer than finding the solutions. An alternative might have been to only count the solutions, without having to output them.

Do we have to check for the case where m*n is odd? E.g. for 9x7, there are no solutions.

@RetoKoradi: Your code has to work for odd mn, which means it should print nothing.

Unfortunately our concerns were correct. My initial implementation uses almost 99% of the time for output. Finding the solutions for the 8x6 size is under 10 ms on a modest laptop. At least if I got it right... Do you want to share how many solutions there are? Does the number start with a 1 and end with 89?

@Dennis If I were you I would re-post this challenge using the GOLF scoring method - right now it's kinda useless since it just becomes an I/O contest.

@RetoKoradi: As you already know by now, there are 167089 tilings for 8x6. Sorry for not answering earlier.

@orlp: Given how unfamiliar I am with GOLF (and assembly in general, I might add), I'm not sure I should be the one to do that. At least not right now. You're more than welcome to though.

Your challenge is not bad. The problem is that our top coders are too strong. My solution that checks validity of rows and columns stays near 1 minute for 6x8.

I think the best strategy now is to use assembly, and try to get a binary file less than 1024 bytes, to get rid of the complication time.

C
A straightforward implementation...
#include<stdio.h>
int a,b,c,s[65],l=0,countonly;
unsigned long long m=0;
char r[100130];
void w(i,x,o){
    int j,k;
    j=(1<<b)-1&~x;
    if(i<a-1){
        s[i+1]=j;
        w(i+1,j,1);
        for(k=j&j/2&-o;j=k&-k;k&=~j)
            w(i,x|3*j,j);
    }
    else if((j/3|j/3*2)==j)
        if(countonly)
            m++;
        else{
            if(c==b)
                for(k=0;k<b;r[k++,l++]=10)
                    for(j=0;j<a;j++)
                        r[l++]=45+79*!((s[j]|s[j+1])&(1<<k));
            else
                for(j=0;j<a;r[j++,l++]=10)
                    for(k=0;k<b;k++)
                        r[l++]=124-79*!((s[j]|s[j+1])&(1<<k));
            r[l++]=10;
            if(l>=100000){
                fwrite(r,l,1,stdout);
                l=0;
            }
        }
}

int main(){
    scanf("%d %d %d",&a,&b,&countonly);
    c=b;
    if(a<b){a^=b;b^=a;a^=b;}
    s[0]=s[a]=0;
    w(0,0,1);
    if(countonly)
        printf("%llu\n",m);
    else if(l)
        fwrite(r,l,1,stdout);
}

The cheating version
#include<stdio.h>
#include<string.h>
int a,b,c,s[65],l=0,countonly;
unsigned long long m=0,d[256];
char r[100130];
void w2(){
    int i,j,k,x;
    memset(d,0,sizeof d);
    d[0]=1;
    j=0;
    for(i=0;i<a-1;i++){
        for(k=1;k<(1<<(b-1));k*=2)
            for(x=0;x<(1<<(b-2));x++)
                d[(x+x/k*k*3+k*3)^j]+=d[(x+x/k*k*3)^j];
        j^=(1<<b)-1;
    }
    for(x=0;x<(1<<b);x++)
        if((x/3|x/3*2)==x)
            m+=d[x^((1<<b)-1)^j];
    printf("%llu\n",m);
}

void w(i,x,o){
    int j,k;
    j=(1<<b)-1&~x;
    if(i<a-1){
        s[i+1]=j;
        w(i+1,j,1);
        for(k=j&j/2&-o;j=k&-k;k&=~j)
            w(i,x|3*j,j);
    }
    else if((j/3|j/3*2)==j){
        if(c==b)
            for(k=0;k<b;r[k++,l++]=10)
                for(j=0;j<a;j++)
                    r[l++]=45+79*!((s[j]|s[j+1])&(1<<k));
        else
            for(j=0;j<a;r[j++,l++]=10)
                for(k=0;k<b;k++)
                    r[l++]=124-79*!((s[j]|s[j+1])&(1<<k));
        r[l++]=10;
        if(l>=100000){
            fwrite(r,l,1,stdout);
            l=0;
        }
    }
}

int main(){
    scanf("%d %d %d",&a,&b,&countonly);
    c=b;
    if(a<b){a^=b;b^=a;a^=b;}
    s[0]=s[a]=0;
    if(countonly)
        w2();
    else{
        w(0,0,1);
        if(l)
            fwrite(r,l,1,stdout);
    }
}

Explanation of the faster algorithm
It scans from left to right, and maintain the state d[i][j], where:

i is in [0,m), which means the current column.
j is a bit vector of size n, where the bit would be 1 if the corresponding position in column i is already occupied before starting working on this column. I.e. it is occupied by the right half of a --.
d[i][j] is the total number of different tilings.

Then say e[i][j] = the sum of d[i][k] where you can put vertical dominoes base on k to form a j. e[i][j] would be the number of tilings where each 1 bit in j is occupied by anything but the left half of a --. Fill them with -- and you'll get d[i+1][~j] = e[i][j]. e[m-1][every bit being 1] or d[m][0] is the final answer.
A naive implementation will get you the time complexity somewhere near g[n]=2*g[n-1]+g[n-2] = O((sqrt(2)+1)^n) (already fast enough if n=m=8). But you can instead firstly loop for each possible domino, and try to add it to every tiling that can have this domino added, and merge the result to the original array d (like the algorithm for the Knapsack problem). And this becomes O(n*2^n). And everything else are implementation details. The whole code runs in O(m*n*2^n).

@Dennis You probably want to start a poll to change it.

@Dennis Not sure increasing the size would have helped much. While it increases the computation time substantially, it also produces about 100 times more output. Relatively speaking, the amount of output is actually larger.

1st version Execution: 0.286 s Compilation: 0.053 s Sum: 0.339 s 2nd version Execution: 0.002 s Compilation: 0.061 s Sum: 0.063 s (What did just happen here?)

@Dennis It used another algorithm in O(mn2^n) if the flag is set.

@Dennis Was it the spirit of the rule change that a completely different algorithm could be used for the scoring run? I figured that it would still have to enumerate the solutions, and only skip the output. Then again, I didn't think that it would be possible to calculate the count orders of magnitude faster. That sounds intriguing. I would definitely love to see an explanation of how this works.

@RetoKoradi: I can't say this is what I had in mind, because I didn't even consider the possibility...

@jimmy23013: To be clear, there would be no way of actually generating the output from within w2()? The line that updates d looks like d[(x+x/k*k*3)^j] and d[(x+x/k*k*3+k*3)^j] both represent a certain set of outputs, but frankly I don't really know what is going on.

@Dennis Right. d[x]+=d[y] adds two counts together, and there will be d[y]+=d[x] later, so each of the d isn't for a single tiling. So adding generation code will be complex. (It's not impossible, if you think each count is a tree containing duplicated nodes, but it would be a much worse idea than my original code.) Explanations of the algorithm will be added soon.

Execution: 190 ms Compilation: 68 ms Sum: 258 ms (-O1 seems to be the sweet spot. I've tried all optimization levels.)

C
After a round of optimizations, and adapted for the modified rules:
typedef unsigned long u64;

static int W, H, S;
static u64 RM, DM, NSol;
static char Out[64 * 2 + 1];

static void place(u64 cM, u64 vM, int n) {
  if (n) {
    u64 m = 1ul << __builtin_ctzl(cM); cM -= m;

    if (m & RM) {
      u64 nM = m << 1;
      if (cM & nM) place(cM - nM, vM, n - 1);
    }

    if (m & DM) {
      u64 nM = m << W;
      vM |= m; vM |= nM; place(cM - nM, vM, n - 1);
    }
  } else if (S) {
    ++NSol;
  } else {
    char* p = Out;
    for (int y = 0; y < H; ++y) {
      for (int x = 0; x < W; ++x) { *p++ = vM & 1 ? '|' : '-'; vM >>= 1; }
      *p++ = '\n';
    }
    *p++ = '\0';
    puts(Out);
    ++NSol;
  }
}

int main(int argc, char* argv[]) {
  W = atoi(argv[1]); H = atoi(argv[2]); S = (argc > 3);

  int n = W * H;
  if (n & 1) return 0;

  for (int y = 0; y < H; ++y) {
    RM <<= W; RM |= (1ul << (W - 1)) - 1;
  }
  DM = (1ul << (W * (H - 1))) - 1;

  place(-1, 0, n >> 1);
  printf("%lu\n", NSol);

  return 0;
}

I started bumping into the length limit of 1024 characters, so I had to reduce the readability somewhat. Much shorter variable names, etc.
Build instructions:
> gcc -O2 Code.c

Run with solution output enabled:
> ./a.out 8 8 >/dev/null

Run with only solution count:
> ./a.out 8 8 s

Some comments:

With the larger test example, I do want optimization now. While my system is different (Mac), around -O2 seems to be good.
The code has gotten slower for the case where output is generated. This was a conscious sacrifice for optimizing the "count only" mode, and for reducing the code length.
There will be a few compiler warnings because of missing includes and external declarations for system functions. It was the easiest way to get me to below 1024 characters in the end without making the code totally unreadable.

Also note that the code still generates the actual solutions, even in "count only" mode. Whenever a solution is found, the vM bitmask contains a 1 for the positions that have a vertical bar, and a 0 for positions with a horizontal bar. Only the conversion of this bitmask into ASCII format, and the actual output, is skipped.

@Dennis New version. Execution should be unchanged, but compilation faster. If we need to optimize for compile time, we don't need no system headers!

@Dennis Updated for new scoring, and for a round of optimizations. Note that I do want optimization now, something like -O2 should be good.

Execution: 256 ms Compilation: 65 ms Sum: 321 ms (-O2 seems to be the sweet spot. I've tried all optimization levels.)

C
The concept is to first find all possible arrangements of horizontal dominoes in a row, store them in r[] and then organize them to give all possible arrangements of vertical dominoes.
The code for positioning the horizontal dominoes in a row is modified from this answer of mine: https://codegolf.stackexchange.com/a/37888/15599. It's slow for the wider grids but that isn't a problem for the 8x8 case.
The innovation is in the way the rows are assembled. If the board has an odd number of rows it is turned through 90 degrees in the input parsing, so it now has an even number of rows. Now I place some vertical dominoes across the centreline. Because of symmetry, if there are c ways of arranging the remaining dominoes in the bottom half, there must also be c ways of arranging the remaining dominoes in the top half, meaning that for a given arrangement of vertical dominoes on the centreline, there are c*c possible solutions. Therefore only the centreline plus one half of the board is analysed when the program is required to print only the number of solutions.
f() builds the table of possible arrangements of horizontal dominoes, and scans through the possible arrangements of vertical dominoes on the centreline. it then calls recursive function g() which fills in the rows. If printing is required, function h() is called to do this.
g() is called with 3 parameters. y is the current row and  d is the direction (up or down) in which we are filling the board from the centre outwards. x contains a bitmap indicates the vertical dominoes that are incomplete from the previous row. All possible arrangements of dominoes in a row from r[] are tried. In this array, a 1 represents a vertical domino and a pair of zeroes a horizontal domino. A valid entry in the array must have at least enough 1's to finish any incomplete vertical dominoes from the last row: (x&r[j])==x. It may have more 1's which indicates that new vertical dominoes are being started. For the next row, then, we need only the new dominoes so we call the procedure again with x^r[j].
If an end row has been reached and there are no incomplete vertical dominoes hanging of the top or bottom of the board x^r[j]==0 then the half has been succesfully completed. If we are not printing, it is sufficient to complete the bottom half and use c*c to work out the total number of arrangements. If we are printing, it will be necessary to complete also the top half and then call the printing function h().
CODE
unsigned int W,H,S,n,k,t,r[1<<22],p,q[64];
long long int i,c,C;

//output: ascii 45 - for 0, ascii 45+79=124 | for 1
h(){int a;
  for(a=n;a--;a%W||puts(""))putchar(45+(q[a/W]>>a%W)%2*79);
  puts("");
}

g(y,d,x){int j;
  for(j=0;j<p;j++)if((x&r[j])==x){
    q[y]=r[j];
    if(y%(H-1)==0){
       (x^r[j])==0?
        y?c++,S||g(H/2-1,-1,i):h()
       :0;
    }else{
      g(y+d,d,x^r[j]);
    }

  }
}

e(z){int d;
  for(d=0;z;d++)z&=z-1;return n/2+1+d&1;
}

f(){
  //k=a row full of 1's
  k=(1ULL<<W)-1;

  //build table of possible arrangements of horizontal dominoes in a row;
  //flip bits so that 1=a vertical domino and save to r[]
  for(i=0;i<=k;i++)(i/3|i/3<<1)==i?r[p++]=i^k:0;

  //for each arrangement of vertical dominoes on the centreline, call g()
  for(i=0;i<=k;i++)e(i)?c=0,g(H/2,1,i),C+=c*c:0;
  printf("%llu",C);
}

main(int argc, char* argv[]) {
  W = atoi(argv[1]); H = atoi(argv[2]); S = (argc > 3);
  1-(n=W*H)%2?
      H%2?W^=H,H^=W,W^=H,t=1:0,f()
    :puts("0");

}

Note that input with an odd number of rows and even number of columns is turned though 90 degrees in the parsing phase. If this is unacceptable, the printing function h() can be changed to accomodate it. (EDIT: not required, see comments.)
EDIT: A new function e() has been used to check the parity of i (i.e the number of dominoes straddling the centreline.) The parity of i (the number of half-dominoes on the centreline protruding into each half of the board) must be the same as the oddness of the total number of spaces in each half (given by n/2) because only then can the dominoes fill all available space. This edit eliminates half the values of i and therefore makes my program approximately twice as fast.

Execution: 18 ms Compilation: 50 ms Sum: 68 ms (-O0 was the sweet spot for the total. Other options slowed down compilation.)

This either never terminates, or at least takes a very long time, for input 32 2 s. I stopped it after about 15 minutes.

@RetoKoradi indeed, yet 2 32 s runs almost instantly. The scanning through all possible vertical dominoes is extremely wasteful for the H=2 case, because in fact we already have all necessary info in r[]. I'm very pleased with the official time for 8 8 s Here's a patch for the case you mention:  if(H==2){C=p;if(!S)for(i=0;i<p;i++)q[0]=q[1]=r[i],h();}else for(i=0;i<=k;i++)c=0,g(H/2,1,i),C+=c*c; As you can see this snippet will run instantly for H=2  with the flag set. The overall runtime is then limited by the building of r[] which certainly has room for improvement.

For completeness here's the patch for turning the output the right way up, if required: if(t)for(a=n;a--;a%H||puts(""))putchar(124-(q[a%H]>>a/H)%2*79);else for(a=n;a--;a%W||puts(""))putchar(45+(q[a/W]>>a%W)%2*79); Codelength is still well below 1000 bytes and impact on compile time should be minimal. I didn't include these patches last night as I was too tired.

I meant to comment on that last night, but I forgot. Since the scoring is done on a square, I'm not going to insist on a particular order.

Out of curiosity: Would it be possible to apply your approach recursively if the number of rows is a power of 2?

@Dennis while there may be mileage in splitting the board into sections & analysing each separately, I'm not sure there's anything special about powers of 2. With 4 or 8 slices, the top&bottom ones would have 1 clean edge but the others wouldn't. So it might work just as well with 6. Exploiting symmetry more may help. For example analyse 1 quadrant, list all possible tilings by the overlaps on their inner "ragged" edge, then combine them like a 4 piece jigsaw. Symmetry is used to reduce complexity of computational fluid dynamics. You can study 1/4 or 1/2 of a round object instead of the whole

@Dennis I have just done a new edit that should make the program twice as fast. Let me know the official time!

Execution: 10 ms Compilation: 53 ms Sum: 63 ms (-O0) Tied to the millisecond! I'll rerun the test this weekend (with a lot more iterations) to see if I can determine a winner. When I wrote up this challenge, I expected to measure execution time in minutes, not milliseconds...

I've re-scored all submissions, determining the most favorable optimization levels and compiling and executing the fast answers 10,000 times. All timings appear lower than before since I timed the entire loop and divided by the number of iterations. Your answer turned out to be a just a tad slower than Jimmy's. Let me know if you make any improvements.

@Dennis Thanks for checking thoroughly. I think I'll leave it now. I expected to win with my last edit, but I didn't reckon on the compile time increasing by 3ms with respect to my original answer. Jimmy's answer is better on both run time and compile time. In fact if I reduced my run time to zero he would still beat me! It was interesting to see different approaches, which these domino questions have always produced.

source: Stack Exchange

license: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/3.0/

sort: votes


text:
Cryptographic hash golf

This contest is over.
Due to the nature of cops-and-robbers challenges, the cops challenge becomes a lot easier when the interest in the associated robbers challenge has diminished. Therefore, while you can still post hash functions, your answer will not get accepted or form part of the leaderboard.

This challenge is a search for the shortest implementation of a hash function that is collision resistant, i.e., it should be infeasible to find two different messages with the same hash.
As a cop, you try to invent and implement a hash function finding the best compromise between code size and collision resistance. Use too many bytes and another cop will outgolf you!
As a robber, you try to foil the cops' attempts by cracking their functions, proving that they are unsuitable. This will force them to use more bytes to strengthen their algorithms!
Cops challenge
Task
Implement a cryptographic hash function H : I -> O of your choice, where I is the set of all non-negative integers below 2230 and O is the set of all non-negative integers below 2128.
You can either implement H as an actual function that accepts and returns a single integer, a string representation of an integer or an array of integers or a full program that reads from STDIN and prints to STDOUT in base 10 or 16.
Scoring

H that it has to resist the robbers challenge defined below.
If a robber defeats your submission in the first 168 hours after posting it, it is considered cracked.
The implementation of H should be as short as possible. The shortest uncracked submission will be the winner of the cops challenge.

Additional rules

If you implement H as a function, please provide a wrapper to execute the function from within a program that behaves as explained above.
Please provide at least three test vectors for your program or wrapper (example inputs and their corresponding outputs).
H can be your novel design (preferred) or a well-known algorithm, as long as you implement it yourself. It is forbidden to use any kind in-built hash function, compression function, cipher, PRNG, etc.
Any built-in commonly used to implement hashing functions (e.g., base conversion) is fair game.
The output of your program or function must be deterministic.
There should be a free (as in beer) compiler/interpreter that can be run on a x86 or x64 platform or from within a web browser.
Your program or function should be reasonably efficient and has to hash any message in I below 2219 in less than a second.
For edge cases, the (wall) time taken on my machine (Intel Core i7-3770, 16 GiB of RAM) will be decisive.
Given the nature of this challenge, it is forbidden to change the code of your answer in any way, whether it alters the output or not.
If your submission has been cracked (or even if it hasn't), you can post an additional answer.
If your answer is invalid (e.g., it doesn't comply with the I/O specification), please delete it.

Example

Python 2.7, 22 bytes
def H(M):
 return M%17

Wrapper
print H(int(input()))

Robbers challenge
Task
Crack any of the cops' submissions by posting the following in the robbers' thread: two messages M and N in I such that H(M) = H(N) and M ≠ N.
Scoring

Cracking each cop submissions gains you one point. The robber with the most points wins.
In the case of a tie, the tied robber that cracked the longest submission wins.

Additional rules

Every cop submission can only be cracked once.
If a cop submission relies on implementation-defined or undefined behavior, you only have to find a crack that works (verifiably) on your machine.
Each crack belongs to a separate answer in the robbers' thread.
Posting an invalid cracking attempt bans you from cracking that particular submission for 30 minutes.
You may not crack your own submission.

Example

Python 2.7, 22 bytes by user8675309
1

and
18

Leaderboard
Safe submissions

CJam, 21 bytes by eBusiness
C++, 148 bytes by tucuxi
C++, 233(?) bytes by Vi.

Uncracked submissions
You can use this Stack Snippet to get a list of not yet cracked answers.

function g(p){$.getJSON('//api.stackexchange.com/2.2/questions/51068/answers?page='+p+'&pagesize=100&order=desc&sort=creation&site=codegolf&filter=!.Fjs-H6J36w0DtV5A_ZMzR7bRqt1e',function(s){s.items.map(function(a){var h=$('
').html(a.body).children().first().text();if(!/cracked/i.test(h)&&(typeof a.comments=='undefined'||a.comments.filter(function(b){var c=$('
').html(b.body);return /^cracked/i.test(c.text())||c.find('a').filter(function(){return /cracked/i.test($(this).text())}).length>0}).length==0)){var m=/^\s*((?:[^,(\s]|\s+[^-,(\s])+)\s*(?:[,(]|\s-).*?([0-9]+)/.exec(h);$('
').append($('').append($('').text(m?m[1]:h).attr('href',a.link)),$('').text(m?m[2]:'?'),$('').append($('').text(a.owner.display_name).attr('href',a.owner.link))).appendTo('#listcontent');}});if(s.length==100)g(p+1);});}g(1);
table th, table td {padding: 5px} th {text-align: left} .score {text-align: right} table a {display:block}
<link rel="stylesheet" type="text/css" href="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b">

Language	Length	User

If a hash function erroneously returns numbers greater than 2^128-1, does that invalidate the submission, or would we simply take the result modulo 2^128?

@MartinBüttner: Yes, you'd have to take the result modulo 2^128.

I may have been unclear with my first question. I mean if someone actually submits code that doesn't take the modulo, is that acceptable (and the robbers condition becomes "H(M) = H(N) (mod 2^128) and M ≠ N") or is it the cop's responsibility to ensure output is in range (which would mean submissions that don't ensure this are invalid).

I understood, but I didn't express myself very well. The cop submission has to provide an integer in O, so you'd have to take the result modulo 2^128 in your code.

Can I implement a function which takes in a string representing the argument in base 10 or 16, or am I required to accept it as a number argument if I use a function?

@algorithmshark: String representations are fine.

Is it cheating to just return I?

@Scimonster Doesn't meet the requirements (up to 2^30 bits of input, 128 bits of output)

So you cannot compete with a language does not support 128 bit (even more 2^30 bit) integers?

@flawr: As stated in the question, you can represent I and O as arrays of integers, For O, you can choose 1 128-bit integer, 128 1-bit integers or anything in between.

Doesn't cops and robbers usually go the other way around?

Where is some Python2 answer I was trying to crack (about circular bitshift)? It suddenly disappeared.

@Vi. I deleted it because it doesn't conform to the runtime requirements. In fact, I can't compete at all because the runtime requirements are way too strict. Both Pyth and Python are too slow for this challenge. Having to process 130 kilobytes byte-by-byte in less than a second in a slow language is just not possible.

@haneefmubarak This interpretation of cops and robbers is sort of my fault (because I wrote the first challenge assigning the roles this way round). I've first come across the phrase in internet-security capture-the-flag games, where the cops secure a machine (and the flag in the form of some secret) and the robbers break in to steal it. The metaphor I had in mind was along those lines.

@orlp: Byte-by-byte being the key here. A block size of 16 bits should solve the speed problem. A block size of 128 bytes would even work with your exec statement. But I don't want the challenge to be too restrictive, so I've changed the speed rule. It only requires integers below 2^(2^19) under one second now.

Surely if you want to win this, you should be writing in APL? en.wikipedia.org/wiki/APL_(programming_language)

Perhaps we could have a rule that submissions must include example hashes, it is quite annoying to have to run the submitters chosen programming language in order to have a result to compare ones cracking implementation against.

@eBusiness: I had that rule in the original draft, but since the crack has to work only on some computer, I edited out. The question now requires at least three test vectors.

@Dennis Thank you for organizing this, it was great fun! (And a big time sink.)

CJam, 21 bytes
1q3*{i+_E_#*^26_#)%}/

Takes a string of bytes as input.
In pseudocode:
hash = 1
3 times:
    for i in input:
        hash = hash + i
        hash = hash xor hash * 14^14
        hash = hash mod (26^26 + 1)
output hash

Example hashes:
"" (empty string) -> 1
"Test" -> 2607833638733409808360080023081587841
"test" -> 363640467424586895504738713637444713
It may be a bit on the simple side, the output range is only a little more than 122 bits, the triple iteration strengthening is already a bit broken as it does exactly the same thing every time, so input that hash to 1 in the first iteration will be a full break. But it is short, and there is no fun in being too safe.

Is there an accompanying C version like in the other CJam post?

@Vi. No, not yet at least. I never dabbled with bigint in C, is there a standard library for that?

GMP?

@Vi. Sorry, I'm not going to go on a library safari for this, you'll have to reimplement it in whatever language/library you wish to use for cracking.

Here: http://pastebin.com/SDzA3JK4

For the record, this takes 838 ms for 2 2 19 # ( on my machine, making it fast enough to comply with the rules.

This submission has remained uncracked for over 168 hours and is now safe.

so .... is this Caesar shifting with substitusion by many rounds ?

@Agawa001 Why would you think so? And no.

@eBusiness hashing is another form of substitution (as long as it is reversible) , and the information hash(i-1) is used to calculate hash(i) , so there is shifting + substitution ,

@Agawa001 You are getting your terminology mixed up. It is a triple-pass sponge function hash algorithm. A Caesar cipher is one specific encryption algorithm with no inner state.

Python, 109 bytes [cracked, and again]
def f(n,h=42,m=2**128):
 while n:h+=n&~-m;n>>=128;h+=h<<10;h^=h>>6;h%=m
 h+=h<<3;h^=h>>11;h+=h<<15;return h%m

I tried implementing Jenkins' one-at-a-time function as-is, with the only difference being the seed and the number of bits.
Fun fact: Apparently Perl used the Jenkins' hash at some point.
Wrapper
print(f(int(input())))

Examples
>>> f(0)
12386682
>>> f(1)
13184902071
>>> f(2**128-1)
132946164914354994014709093274101144634
>>> f(2**128)
13002544814292
>>> f(2**128+1)
13337372262951
>>> f(2**(2**20))
290510273231835581372700072767153076167

Cracked.

Even more cracked (preimage attack).

C++, 148 bytes
typedef __uint128_t U;U h(char*b,U n,U&o){U a=0x243f6a8885a308d,p=0x100000001b3;for(o=a;n--;)for(U i=27;--i;){o=(o<>(128-i));o*=p;o^=b[n];}}

__uint128_t is a GCC extension, and works as expected. The hash is based on iterating FNV hash (I've borrowed their prime, although a is the first digits of Pi in hex) with a sha1-like rotation at the start of each iteration. Compiling with -O3, hashing a 10MB file takes under 2 seconds, so there is still margin for upping the iterations in the inner loop - but I'm feeling generous today.
De-uglified (changed variable names, added comments, whitespace and a pair of braces) for your cracking pleasure:
typedef __uint128_t U;
U h(char* input, U inputLength, U &output){
    U a=0x243f6a8885a308d,p=0x100000001b3;
    for(output=a;inputLength--;) {   // initialize output, consume input
        for(U i=27;--i;) {                          // evil inner loop
            output = (output<>(128-i)); // variable roll
            output *= p;                            // FNV hash steps
            output ^= input[inputLength];
        }
    }
    // computed hash now available in output
}

Golfing suggestions are welcome (even if I don't get to improve the code based on them).
edit: fixed typos in de-uglified code (golfed version remains unchanged).

o seems to be uninitialized. Where output is declared? Or maybe o is output?

The same for n. Have you actually checked the "de-uglified" code to run?

Started the bruteforcer...

Even 3-round version is not easy.

@Vi. Fixed de-uglified version -- sorry for not checking it better.  I'm proud of that inner loop; U i=81;i-=3 could have been even more vile, without significant runtime costs.

What do the d and b3 integer suffixes mean? I don't know C well, so I'm trying to translate it. Also, how are you using a 16-bit datatype when the input can have up to 134,217,728 bytes?

@LegionMammal978 d and b3 are not suffixes, just part of the hex. char is 8-bit.  char * is a pointer to a char (or in this case, an array of chars), and can be treated like an array (see input[inputLength]).

@g.rocket Hex fail... I know  most of the syntax, though, such as pointers and chars.

@LegionMammal978 I was just pointing out that what you called a "16-bit datatype" was actually an array of 8-bit datatypes.  I might have misunderstood which you were referring to as the "16-bit datatype."

@g.rocket Thanks, meant 16-byte and forgot that it's just for the output... Also, do the for loops stop at 1 or 0?

for-loops stop when the center condition is false;  for( init ; cond ; post ) body is roughly equivalent to init ; while( cond ) { body ;  post }

@tucuxi I know, it's just that I was confused from the pre- and post-decrements (I know what they are.)

This submission has remained uncracked for over 168 hours and is now safe.

C++, 182 characters (+ about 51 characters of boilerplate)
h=0xC0CC3051F486B191;j=0x9A318B5A176B8125;char q=0;for(int i=0;i<l;++i){char w=buf[i];h+=((w<<27)*257);j^=(h+0x5233);h+=0xAA02129953CC12C3*(j>>32);j^=(w+0x134)*(q-0x16C552F34);q=w;}

Boilerplate:
void hash(const unsigned char* buf, size_t len, unsigned long long *hash1, unsigned long long *hash2)
{
    unsigned long long &h=*hash1;
    unsigned long long &j=*hash2;
    size_t l = len;
    const unsigned char* b = buf;

    // code here
}

Runnable program with a golfed function
#include <stdio.h>

// The next line is 227 characters long
int hash(char*b,int l,long long&h,long long&j){h=0xC0CC3051F486B191;j=0x9A318B5A176B8125;char q=0;for(int i=0;i<l;++i){char w=b[i];h+=((w<<27)*257);j^=(h+0x5233);h+=0xAA02129953CC12C3*(j>>32);j^=(w+0x134)*(q-0x16C552F34);q=w;}}

int main() {
    char buf[1024];
    int l  = fread(buf, 1, 1024, stdin);
    long long q, w;
    hash(buf, l, q, w);
    printf("%016llX%016llX\n", q, w);
}

I think the function declaration etc. counts towards the character count.

@Ypnypn, counted characters in a golfed down function declaration.

What is the output hash? I am assuming it is  ((h<<64)|j).

Yes. Or just a pair of 64-bit numbers. I found out about __uint128_t only after implemeting this.

Tough to crack. If it lasts the night, I'll submit it as SHA-4
:-P

@tucuxi, It isn't broken by my bruteforcer in 10 hours (and counting). I don't think any 128-bit hash can be SHA-4. Actually I just mashed in some random constrants, arithmetic and bit operators together and tested it for collisions.

I had a hunch concerning sequences of 0x00 bytes (which are really quick to hash, since you can set w = q = 0 and there's no need to actually generate the sequences themselves). No luck there either.

Would it be okay if you posted some example runs? Also, what is the expected input format - a string of any characters, specifically digit characters 0-9, or...?

@Sp3000, Input is a byte buffer. Tests: "" -> C0CC3051F486B1919A318B5A176B8125, "\x00"-> DB768C65B8B6F0F2A50245424A6FB791", "A" -> DB768C65C0B6F0F2A50246E6CC0EBBDD, "ABC" -> 3312D717E8D481501F9FBC2DA342116A.

This submission has remained uncracked for over 168 hours and is now safe.

@Vi.: Could you please provide the full function (golfed boilerplate and all)?

@Dennis, https://gist.github.com/vi/248db6d2d2bdc26d66cc . Check the tests above.

I meant the golfed boilerplate. Since you claim a score of 233, that 233 byte code should be included in your answer.

@Dennis, Done.

CJam, 44 bytes [cracked]
lW%600/_z]{JfbDbGK#%GC#[md\]}%z~Bb4G#%\+GC#b

Input is in base 10.
CJam is slow. I hope it runs in 1 second in some computer...
Explanations
lW%600/            e# Reverse, and split into chunks with size 600.
_z                 e# Duplicate and swap the two dimensions.
]{                 e# For both versions or the array:
    JfbDb          e# Sum of S[i][j]*13^i*19^j, where S is the character values,
                   e# and the indices are from right to left, starting at 0.
    GK#%GC#[md\]   e# Get the last 32+48 bits.
}%
z~                 e# Say the results are A, B, C, D, where A and C are 32 bits.
Bb4G#%             e# E = the last 32 bits of A * 11 + C.
\+GC#b             e# Output E, B, D concatenated in binary.

Well, the two dimensional things seemed to be a weakness... It was intended to make some slow calculations faster at the beginning. But it cannot run in a second no matter what I do, so I removed the slow code finally.
It should be also better if I have used binary bits and higher bases.
C version
__uint128_t hash(unsigned char* s){
    __uint128_t a=0,b=0;
    __uint128_t ar=0;
    __uint128_t v[600];
    int l=0,j=strlen(s);
    memset(v,0,sizeof v);
    for(int i=0;i<j;i++){
        if(i%600)
            ar*=19;
        else{
            a=(a+ar)*13;
            ar=0;
        }
        if(i%600>l)
            l=i%600;
        v[i%600]=v[i%600]*19+s[j-i-1];
        ar+=s[j-i-1];
    }
    for(int i=0;i<=l;i++)
        b=b*13+v[i];
    a+=ar;
    return (((a>>48)*11+(b>>48))<<96)
        +((a&0xffffffffffffull)<<48)
        +(b&0xffffffffffffull);
}

Could you please add a description? Not everyone knows CJam.

@orlp Edited...

This takes 0.4 s on my computer, so it's well within the allowed range.

What is A, B, C and so on? Some matrices? Which dimensions? Can it be easily implemented in C?

A and B are the last 80 bits of the result using the original dimension order. A is 32 bit, to the left of B, which is 48 bit. C and D are similar but using the swapped dimension order. They are numbers. Changed the matrix to S to reduce confusion.

(I though about using my collision detector on this, but incompatibility with C is a stopper)

@Vi. I think the only problem (if a C code doesn't match the result) would be the initial step of splitting the reversed base 10 string, and aligning with the rightmost digit. Others are straightforward.

Slowness of the hash (or slowness of CJam startup) protects the it from being brufeforced.

Started the bruteforcer...

If input is in base 10, shouldn't 0 and 00 hash to the same value?

@squeamishossifrage Indeed it should be better have been in binary. But since I already specified it to be in decimal (due to some weakness I spotted before posting), let's say there is only one valid representation for each number, which doesn't have extra leading zeros.

The bruteforcer can't find anything in 35 CPU hours on i5..

Cracked, I believe.

Pyth, 8 Cracked
sv_`.lhQ

Try it online
A bit of a silly answer, I'll explain how it works because most people can't read Pyth. This takes the natural log of one plus the input, and then converts that to a string. That string is reversed, and then evaluated and then converted to an integer.
A python translation would look like:
import math
n = eval(input()) + 1
rev = str(math.log(n))[::-1]
print(int(eval(rev)))

Cracked?

Python 3, 216 bytes [cracked]
def f(m):
 h=1;p=[2]+[n for n in range(2,102)if 2**n%n==2];l=len(bin(m))-2;*b,=map(int,bin((l<<(l+25)//26*26)+m)[2:])
 while b:
  h*=h
  for P in p:
   if b:h=h*P**b.pop()%0xb6ee45a9012d1718f626305a971e6a21
 return h

Due to an incompatibility with the spec I can think of at least one slight vulnerability, but other than that I think this is at least brute-force proof. I've checked the first 10 million hashes, among other things.
In terms of golf this would be shorter in Python 2, but I've sacrificed some bytes for efficiency (since it's probably not going to win anyway).
Edit: This was my attempt at implementing the Very Smooth Hash, but unfortunately 128-bits was far too small.
Wrapper
print(f(int(input())))

Examples
>>> f(0)
2
>>> f(123456789)
228513724611896947508835241717884330242
>>> f(2**(2**19)-1)
186113086034861070379984115740337348649
>>> f(2**(2**19))
1336078

Code explanation
def f(m):
 h=1                                             # Start hash at 1
 p=[2]+[n for n in range(2,102)if 2**n%n==2]     # p = primes from 2 to 101
 l=len(bin(m))-2                                 # l = bit-length of m (input)
 *b,=map(int,bin((l<<(l+25)//26*26)+m)[2:])      # Convert bits to list, padding to
                                                 # a multiple of 26 then adding the
                                                 # bit-length at the front

 while b:                                        # For each round
  h*=h                                           # Square the hash
  for P in p:                                    # For each prime in 2 ... 101
   if b:h=(h*P**b.pop()                          # Multiply by prime^bit, popping
                                                 # the bit from the back of the list
           %0xb6ee45a9012d1718f626305a971e6a21)  # Take mod large number

 return h                                        # Return hash

An example of the padding for f(6):
[1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0]

(len 3)(------------------ 23 zeroes for padding -------------------------)(input 6)
       (---------------------------- length 26 total ------------------------------)

Cracked

C, 87 bytes [cracked]
This is the complete program; no wrapper required. Accepts binary input via stdin, and outputs a hexadecimal hash to stdout.
c;p;q;main(){while((c=getchar())+1)p=p*'foo+'+q+c,q=q*'bar/'+p;printf("%08x%08x",p,q);}

This only calculates a 64-bit hash, so I'm taking a bit of a gamble here.
In case anyone's wondering, the two constants 'foo+' and 'bar/' are the prime numbers 1718578987 and 1650553391.

Examples:
Ignores leading zeroes:
echo -ne '\x00\x00\x00\x00' |./hash
0000000000000000

Single-byte inputs:
echo -ne '\x01' |./hash
0000000100000001
echo -ne '\xff' |./hash
000000ff000000ff

Multi-byte inputs:
echo -ne '\x01\x01' |./hash
666f6f2dc8d0e15c
echo -ne 'Hello, World' |./hash
04f1a7412b17b86c

How would it behave with 'aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa' and 'aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa'?

I was going to remove the comment, since I found out for myself. But thanks a lot for the answer.

foo| (d5c9bef71d4f5d1b) and foo\ (d5c9bef71d4f5d1b) produce VERY similar hashes.

Try ~~, ~^ and ~\. They differ by 2. Everytime you add 1 bit, it adds 2 at position 8 and 16. By the way, how would ~~~~~~~~~~~~~ and ~~~~~~~~~~~~~\0 behave? (can't test the \0 on ideone.com)

What about ~~~~~~~~~~~~~ and ~~~~~~~~~~~~~\xFF? Since you add 1 to each char, \xFF should overlap to 0. Thus, p*'foo+'+q+c would be p*'foo+'+q+0, breaking your code.

Still different. I'm not incrementing c — check the parentheses.

Broke it!!! \x00 and \x00\x00!

Let us continue this discussion in chat.

Based on the chat comments, I believe this is still not cracked yet? Just double checking, because the upvoted comment might be confusing to those who are skimming for uncracked hashes.

@Sp3000 Not yet cracked

Cracked: http://codegolf.stackexchange.com/a/51174/7773

J - 39 bytes - cracked
Function taking a string as input and returning an integer < 2128. I am assuming we have to name our function to be valid, so drop another 3 chars from the count if we can submit anonymous functions.
H=:_8(".p:@+5,9:)a\(a=.(2^128x)&|@^/@)]

For those of you that don't read hieroglyphics, here's a rundown of what I'm doing.

a=.(2^128x)&|@^/@ This is a subroutine* which takes an array of numbers, and then treats it as a power tower, where exponentiation is taken mod 2128. By "power tower", I mean if you gave it the input 3 4 5 6, it would calculate 3 ^ (4 ^ (5 ^ 6)).
(".p:@+5,9:)a This function takes a string, converts it to the number N, and then calculates the (n+5)-th and (n+9)-th prime numbers, and then throws the a from before on it. That is, we find p(n+5) ^ p(n+9) mod 2128 where p(k) is the k-th prime.
H=:_8...\(a...)] Perform the above function on 8-character subblocks of the input, and then a all the results together and call the resulting hash function H. I use 8 characters because J's "k-th prime" function fails when p(k) > 231, i.e. k=105097564 is the largest safe k.

Have some sample outputs. You can try this yourself online at tryj.tk, but I really recommend doing this at home by downloading the interpreter from Jsoftware.
   H=:_8(".p:@+5,9:)a\(a=.(2^128x)&|@^/@)]
   H '88'
278718804776827770823441490977679256075
   H '0'
201538126434611150798503956371773
   H '1'
139288917338851014461418017489467720433
   H '2'
286827977638262502014244740270529967555
   H '3'
295470173585320512295453937212042446551
   30$'0123456789'  NB. a 30 character string
012345678901234567890123456789
   H 30$'0123456789'
75387099856019963684383893584499026337
   H 80$'0123456789'
268423413606061336240992836334135810465

* Technically, it's not a function in and of itself, it attaches to other functions and acts on their output. But this is a semantic issue of J, not a conceptual difference: the program flow is as I described it above.

Cracked

Java, 299 291 282 bytes, cracked.
import java.math.*;class H{public static void main(String[]a){BigInteger i=new java.util.Scanner(System.in).nextBigInteger();System.out.print(BigInteger.valueOf(i.bitCount()*i.bitLength()+1).add(i.mod(BigInteger.valueOf(Long.MAX_VALUE))).modPow(i,BigInteger.valueOf(2).pow(128)));}}

Does some operations on BigIntegers, then takes the result modulo 2128.

How do I run this? Ideone refuses to compile it.

You can run it on Ideone by renaming the class to "Main" or removing the first "public" keyword (but NOT the second one). Either one will work.

Cracked.

@SuperJedi224 Why not remove the first public yourself, saving 7 chars?

@immibis Because then I don't think it would work right on Eclipse. I'll try it though. EDIT: I guess it does. That's a surprise.

Python 3, 118 bytes [cracked]
def H(I):
    o=0;n=3;M=1<<128
    for c in I:i=ord(c);o=(o<<i^o^i^n^0x9bb90058bcf52d3276a7bf07bcb279b7)%M;n=n*n%M
    return o

Indentation is a single tab. Simple hash, haven't really tested it thoroughly yet.
Call as follows:
print(H("123456789"))

result: 73117705077050518159191803746489514685

How should the input integer be converted to a string to use in your algorithm?

@feersum base-10 string is what I tested. It doesn't use anything but ord(c) though, so really, any string will do :) (except things like nul chars, I think those make hash collisions really easy. So stick with a 0-9 string.)

Broke it:  http://codegolf.stackexchange.com/a/51160/41288. Started out by observing that strings like "10000" and "20000" produce very close hashes. Started to play around with more and more zeroes, and after 128 or so, any digit + k*4 zeroes repeats returns the same hash regardless of k.

@tucuxi Already thought it shouldn't bee too hard; glad that is wasn't trivial but that someone broke it anyway. Good work.

C++, 239 bytes
My very first code golf! [Please be gentle]
#define r(a,b) ((a<>(64-b)))
typedef uint64_t I;I f(I*q, I n, I&h){h=0;for(I i=n;--i;)h=r(h^(r(q[i]*0x87c37b91114253d5,31)*0x4cf5ad432745937f),31)*5+0x52dce729;h^=(h>>33)*0xff51afd7ed558ccd;h^=(h>>33)*0xc4ceb9fe1a85ec53;h^=(h>>33);}

Ungolfed version:
I f(I* q, I n, I& h) // input, length and output
{
    h = 0; // initialize hashes
    for (I i=n;--i;)
    {
        q[i] *= 0x87c37b91114253d5;
        q[i]  = rotl(q[i], 31);
        q[i] *= 0x4cf5ad432745937f;

        h ^= q[i]; // merge the block with hash

        h *= rotl(h, 31);
        h = h * 5 + 0x52dce729;
    }
    h ^= h>>33;
    h *= 0xff51afd7ed558ccd;
    h ^= h>>33;
    h *= 0xc4ceb9fe1a85ec53; // avalanche!
    h ^= h>>33;
}

Not the best hash, and definitely not the shortest code in existence. Accepting golfing tips and hoping to improve!
Wrapper
Probably not the best in the world, but a wrapper nonetheless
I input[500];

int main()
{
    string s;
    getline(cin, s);
    memcpy(input, s.c_str(), s.length());
    I output;
    f(input, 500, output);
    cout << hex << output << endl;
}

Looks solid, but with 64 bits, it may be subject to brute-forcing. There is about a 50% chance to find a collision in ~sqrt(n) tests (from among n total outputs);  2^32 tries is not that much for a modern pc.

Wrapper lacks header inclusions and in general leads to many equal hashes.

Provide some hash samples. For me both "3" and "33" lead to 481c27f26cba06cf (using this wrapper).

Cracked: http://codegolf.stackexchange.com/a/51215/41288 . I suspect right before @Vi. found out why so many hashes were equal.

Proper collision (without bug using): printf '33333333\x40\xF3\x32\xD6\x56\x91\xCA\x66' | ./hash7_ -> a4baea17243177fd; printf '33333333\x77\x39\xF3\x82\x93\xDE\xA7\x2F' | ./hash7_ -> a4baea17243177fd. The bruteforcer finds collisions here much faster compared to in other 64-bit hash here.

Much of the strength of multiplication in a hash relies on the multiplicative constants being prime; in this case, only 0xff51afd7ed558ccd happens to be a prime.

C, 128 bytes [cracked]
p;q;r;s;main(c){while((c=getchar())+1)p=p*'foo+'+s^c,q=q*'bar/'+p,r=r*'qux3'^q,s=s*'zipO'+p;printf("%08x%08x%08x%08x",p,q,r,s);}

This is more or less the same algorithm as my last effort (cracked by Vi.), but now has enough hamster wheels to generate proper 128-bit hashes.
The four prime constants in the code are as follows:
'foo+' = 1718578987
'bar/' = 1650553391
'qux3' = 1903523891
'zipO' = 2053730383

As before, this is a complete program with no need for a wrapper. The integer I is input via stdin as raw binary data (big-endian), and the hash O is printed in hex to stdout. Leading zeroes in I are ignored.
Examples:
echo -ne '\x00' |./hash
00000000000000000000000000000000
echo -ne '\x00\x00' |./hash
00000000000000000000000000000000
echo -ne '\x01' |./hash
00000001000000010000000100000001
echo -ne 'A' |./hash
00000041000000410000004100000041
echo -ne '\x01\x01' |./hash
666f6f2dc8d0e15cb9a5996fe0d8df7c
echo -ne 'Hello, World' |./hash
da0ba2857116440a9bee5bb70d58cd6a

Cracked http://codegolf.stackexchange.com/a/51216/101

Didn't your example show a collision right there (the first two)?

@mbomb007 No. The input is a number between 0 and 2^(2^30). 0x00 and 0x0000 are both equal to zero, so they produce the same output.

C, 122 bytes [cracked]
long long x,y,p;main(c){for(c=9;c|p%97;c=getchar()+1)for(++p;c--;)x=x*'[3QQ'+p,y^=x^=y^=c*x;printf("%016llx%016llx",x,y);}

Nested loops, half-assed LCGs, and variable swapping.  What's not to love?
Here's a ungolf'd version to play around with:
long long x,y,p;

int main(int c){
    // Start with a small number of iterations to
    //   get the state hashes good and mixed because initializing takes space
    // Then, until we reach the end of input (EOF+1 == 0)
    //   and a position that's a multiple of 97
    for (c=9;c|p%97;c=getchar()+1) {

        // For each input c(haracter) ASCII value, iterate down to zero
        for (++p;c--;) {

            // x will act like a LCG with a prime multiple
            //   partially affected by the current input position
            // The string '[3QQ' is the prime number 0x5B335151
            x=x*'[3QQ'+p;

            // Mix the result of x with the decrementing character
            y^=c*x;

            // Swap the x and y buffers
            y^=x^=y;
        }
    }

    // Full 128-bit output
    printf("%016llx%016llx",x,y);
    return 0;
}

This is a fully self-contains program that reads from STDIN and prints to STDOUT.
Example:
> echo -n "Hello world" | ./golfhash
b3faef341f70c5ad6eed4c33e1b55ca7

> echo -n "" | ./golfhash
69c761806803f70154a7f816eb3835fb

> echo -n "a" | ./golfhash
5f0e7e5303cfcc5ecb644cddc90547ed

> echo -n "c" | ./golfhash
e64e173ed4415f7dae81aae0137c47e5

In some simple benchmarks, it hashes around 3MB/s of text data.  The hash speed depends on the input data itself, so that should probably be taken into consideration.

Cracked: http://codegolf.stackexchange.com/a/51354/101

C, 134 bytes, Cracked
This is complete C program.
long long i=0,a=0,e=1,v,r;main(){for(;i++<323228500;r=(e?(scanf("%c",&v),e=v>'/'&&v<':',v):(a=(a+1)*7)*(7+r)));printf("0x%llx\n", r);}

What it does:
The idea is to take input as byte array and append pseudo random (but deterministic) bytes at the end to make the length equal to about 2230 (a bit more).
The implementation reads input byte by byte and starts using pseudo random data when it finds the first character that isn't a digit.
As builtin PRNG isn't allowed I implemented it myself.
There is undefined/implementation defined behavior that makes the code shorter (the final value should be unsigned, and I should use different types for different values).
And I couldn't use 128 bit values in C.
Less obfuscated version:
long long i = 0, prand = 0, notEndOfInput = 1, in, hash;

main() {
    for (; i++ < 323228500;) {
        if (notEndOfInput) {
            scanf("%c", &in);
            notEndOfInput = in >= '0' && in <= '9';
            hash = in;
        } else {
            prand = (prand + 1)*7;
            hash = prand*(7 + hash);
        }
    }
    printf("0x%llx\n", hash);
}

Cracked

PHP 4.1, 66 bytes [cracked]
I'm just warming up.
I hope you find this insteresting.
<?for($l=strlen($b.=$a*1);$i<40;$o.=+$b[+$i]^"$a"/$a,$i++);echo$o;

I've tried it numbers as large as 999999999999999999999999999.
The output seemed to be within the 2128 range.

PHP 4.1 is required because of the register_globals directive.
It works by automatically creating local variables from the session, POST, GET, REQUEST and cookies.
It uses the key a. (E.G.: access over http://localhost/file.php?a=<number>).
If you want to test it with PHP 4.2 and newer, try this:
<?for($l=strlen($b.=$a=$_REQUEST['a']*1);$i<40;$o.=+$b[+$i]^"$a"/$a,$i++);echo$o;

This version only works with POST and GET.

Example output:
0 -> 0000000000000000000000000000000000000000
9 -> 8111111111111111111111111111111111111111
9999 -> 8888111111111111111111111111111111111111
1234567890 -> 0325476981111111111111111111111111111111
99999999999999999999999999999999999999999999999999999999999999999999999999999999 -> 0111191111111111111111111111111111111111

(I assure you that there are numbers that produce the same hash).

Cracked: http://codegolf.stackexchange.com/a/51121/7773

Python 2.X - 139 bytes [[Cracked]]
This is quite similar to all the other (LOOP,XOR,SHIFT,ADD) hashes out here. Come get your points robbers ;) I'll make a harder one after this one is solved.
M=2**128
def H(I):
 A=[1337,8917,14491,71917];O=M-I%M
 for z in range(73):
  O^=A[z%4]**(9+I%9);O>>=3;O+=9+I**(A[z%4]%A[O%4]);O%=M
 return O

Wrapper (expects one argument in base-16 also known as hexadecimal):
import sys
if __name__ == '__main__':
 print hex(H(long(sys.argv[1], 16)))[2:][:-1].upper()

Cracked: http://codegolf.stackexchange.com/a/51180/36885

Also, I am not sure that this entry meets the OP's spec, since on my machine the function takes multiple seconds on large inputs.  For example, H(2**(2**10)) took around 8 or 9 seconds, while H(2**(2**12)) took around 29 seconds and H(2**(2**14)) took over two minutes.

You are absolutely right, I obviously should have tested the timing for larger inputs. Also, I appear to have forgot to run my own test after that shift was added. The original version was without shift (before posting) and it was passing my "no collisions in the first 100000 integers" test :/

Python 2.7 - 161 bytes [[Cracked]]
Well since I managed to change my first hash function into an useless version before posting it, I think I will post another version of a similar structure. This time I tested it against trivial collisions and I tested most of the possible input magnitudes for speed.
A=2**128;B=[3,5,7,11,13,17,19]
def H(i):
 o=i/A
 for r in range(9+B[i%7]):
  v=B[i%7];i=(i+o)/2;o=o>>v|o<<128-v;o+=(9+o%6)**B[r%6];o^=i%(B[r%6]*v);o%=A
 return o

Wrapper (not counted in the bytecount)
import sys
if __name__ == '__main__':
 arg = long(sys.argv[1].strip(), 16)
 print hex(H(arg))[2:][:-1].upper()

Run example (input is always a hexadecimal number):
$ python crypt2.py 1
3984F42BC8371703DB8614A78581A167
$ python crypt2.py 10
589F1156882C1EA197597C9BF95B9D78
$ python crypt2.py 100
335920C70837FAF2905657F85CBC6FEA
$ python crypt2.py 1000
B2686CA7CAD9FC323ABF9BD695E8B013
$ python crypt2.py 1000AAAA
8B8959B3DB0906CE440CD44CC62B52DB

Cracked.

Well done jimmy :)

Ruby, 90 Bytes
def H(s);i=823542;s.each_byte{|x|i=(i*(x+1)+s.length).to_s.reverse.to_i%(2**128)};i;end

A highly random hash algorithm I made up without looking at any real hashes...no idea if it is good. it takes a string as input.
Wrapper:
def buildString(i)
  if(i>255)
    buildString(i/256)+(i%256).chr
  else
    i.chr
  end
end
puts H buildString gets

Could you please provide the wrapper the question requires?

What's the input format? I tried with a number but it says comparison of String with 255 failed (ArgumentError).

H takes a string, Build string takes the number required by the OP and transforms it to a string.

I think you need a gets.to_i in the wrapper.

Cracked.

Mathematica, 89 bytes, cracked
Last@CellularAutomaton[(a=Mod)[#^2,256],{#~IntegerDigits~2,0},{#~a~99,128}]~FromDigits~2&

Not the shortest.

How do you run this without Mathematica? "There should be a free (as in beer) compiler/interpreter that can be run on a x86 or x64 platform or from within a web browser."

@MartinBüttner https://www.wolfram.com/mathematica/trial/

Cracked.

PHP, 79 Bytes (cracked. With a comment):
echo (('.'.str_replace('.',M_E*$i,$i/pi()))*substr(pi(),2,$i%20))+deg2rad($i);

This does alot of scary things via type-conversions in php, which makes it hard to predict ;) (or at least I hope so). It's not the shortest or most unreadable answer, however.
To run it you can use PHP4 and register globals (with ?i=123) or use the commandline:
php -r "$i = 123.45; echo (('.'.str_replace('.',M_E*$i,$i/pi()))*substr(pi(),2,$i%20))+deg2rad($i);"

The hash's output value looks floating-point. And It's the same for 3000000000000000000000000000000000000000000001 and 3000000000000000000000000000000000000000000000.

Python 2, 115 bytes [Cracked already!]
OK, here's my last effort. Only 115 bytes because the final newline isn't required.
h,m,s=1,0,raw_input()
for c in[9+int(s[x:x+197])for x in range(0,len(s),197)]:h+=pow(c,257,99**99+52)
print h%4**64

This is a complete program that inputs a decimal integer on stdin and prints a decimal hash value on stdout. Extra leading zeroes will result in different hash values, so I'll just assume that the input doesn't have any.
This works by stuffing 197-digit chunks of the input number through a modular exponentiation. Unlike some languages, the int() function always defaults to base 10, so int('077') is 77, not 63.
Sample outputs:
$ python hash.py <<<"0"
340076608891873865874583117084537586383

$ python hash.py <<<"1"
113151740989667135385395820806955292270

$ python hash.py <<<"2"
306634563913148482696255393435459032089

$ python hash.py <<<"42"
321865481646913829448911631298776772679

$ time python hash.py <<<`python <<<"print 2**(2**19)"`
233526113491758434358093601138224122227

real    0m0.890s   <-- (Close, but fast enough)
user    0m0.860s
sys     0m0.027s

It didn't use the order of blocks... Cracked.

Ugh. I give in :-(

C# - 393 bytes cracked
using System;class P{static void Main(string[]a){int l=a[0].Length;l=l%8==0?l/8:l/8+1;var b=new byte[l][];for(int i=0;i<l;i++){b[i]=new byte[8];};int j=l-1,k=7;for(int i=0;i<a[0].Length;i++){b[j][k]=Convert.ToByte(""+a[0][i],16);k--;if((i+1)%8==0){j--;k=7;}}var c=0xcbf29ce484222325;for(int i=0;i<l;i++){for(int o=0;o<8;o++){c^=b[i][o];c*=0x100000001b3;}}Console.WriteLine(c.ToString("X"));}}

Ungolfed:
using System;
class P
{
    static void Main(string[]a)
    {
      int l = a[0].Length;
      l = l % 8 == 0 ? l / 8 : l / 8 + 1;
      var b = new byte[l][];
      for (int i = 0; i < l; i++) { b[i] = new byte[8]; };
      int j = l-1, k = 7;
      for (int i = 0; i < a[0].Length; i++)
      {
        b[j][k] = Convert.ToByte(""+a[0][i], 16);
        k--;
        if((i+1) % 8 == 0)
        {
          j--;
          k = 7;
        }
      }
      var c = 0xcbf29ce484222325;
      for (int i = 0; i < l; i++)
      {
        for (int o = 0; o < 8; o++)
        {
          c ^= b[i][o];
          c *= 0x100000001b3;
        }
      }
      Console.WriteLine(c.ToString("X"));
    }
}

I have never touched cryptography or hashing in my life, so be gentle :)
It's a simple implementation of an FNV-1a hash with some array pivoting on the input. I am sure there is a better way of doing this but this is the best I could do.
It might use a bit of memory on long inputs.

Cracked: http://codegolf.stackexchange.com/a/51277/101 On top of having faulty padding, this is not a cryptographic hash, there is so many ways to break it.

all_licenses: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/3.0/