Arithmetic Golf: Reach 2011

Question

This is an ai-player challenge. Your goal is to reach the number 2011 as quickly as possible, or to get as close to it as you can.

Rules:

• A "hole" consists of a rectangular grid of digits (0-9).
• Your total starts at 0.
• You may start at any digit on the grid. This is your first "stroke."
• For each subsequent stroke, you may move to any immediately adjacent digit (up, left, down, right). However, you may not move to a digit that you have used before.
• With each stroke, you will use your current total and the digit at your current position as operands (the total is always the first operand), and apply one of the four basic arithmetic operations (+ - * /). The result will become your new total.
• If your total becomes 2011, your score for the course is the number of strokes.
• If you have no more valid moves, your score is your current number of strokes + your total's distance from 2011.
• You may also choose at any time to stop, and your score will be your current number of strokes + your total's distance from 2011.

Input:

• You will read in a file containing data for each "hole." Alternatively, you may accept the input through stdin or an equivalent.
• Each hole will consist of H rows of W digits, for a grid of size WxH. H and W may vary per hole.
• The holes will be separated by a single blank line.
• In the spirit of golf, the competition will consist of 18 holes, but your program should be able to handle any number of them.

Output:

• For each hole, your program should output the position of the starting digit. The position should be given as (row, col) where the top-left is (0, 0).
• For each stroke, your program should output the chosen operation, the current digit, and the resulting total.
• At the end of each hole, whether you reach 2011 or not, your program should output your number of strokes and your score for the hole (usually the same as the number of strokes).
• For testing purposes, you may also find it helpful to output your path on each board indicating which digits were used. However, you will not be required to provide this output for the competition.

Notes:

• For any given hole, your program should always start at the same position and choose the same route (i.e., no random choices). The starting position does not need to be the same for every hole.
• The total is not limited to the integers. That is, if you divide 4023 by 2, your total would become 2011.5, and you would still be .5 away from the goal.
• Your program should run in a "reasonable" amount of time.
• For purposes of verifiability, your program should be runnable on an online interpreter such as ideone.com.
• The winner is the program that has the lowest overall score for the entire course. If there is a tie, the tying programs will play a new course, hole-for-hole, with the lowest scorers advancing until there is only one winner. If there is still a tie after the tiebreaker course, the program submitted first will win.

Deadline:

• The current deadline for this competition is September 10, 2011. This deadline may be extended, depending on interest.

Sample input:

14932875921047
60438969014654
56398659108239
90862084187569
94876198569386
14897356029523

Sample output:

Start: (3, 7)
+4=4
*9=36
*9=324
*6=1944
+9=1953
+8=1961
+8=1969
+9=1978
+6=1984
+8=1992
+8=2000
+8=2008
+4=2012
-1=2011
Strokes: 14
Score: 14

14932875921047
6043....014654
563..65.108239
90..208.187569
94.76198569386
...97356029523

Sample output (compact):

Start: (3, 7)
+4=4 *9=36 *9=324 *6=1944 +9=1953 +8=1961 +8=1969 +9=1978 +6=1984 +8=1992 +8=2000 +8=2008 +4=2012 -1=2011
Strokes: 14   Score: 14

Sample input:

0346092836
1986249812
3568086343
5509828197
4612486355
3025745681
7685047124
2098745313

Sample output:

Start: (4, 7)
+3=3
*6=18
*5=90
+7=97
*5=485
*4=1940
+7=1947
+8=1955
+9=1964
+8=1972
+6=1978
+7=1985
+3=1988
+4=1992
+5=1997
+5=2002
+5=2007
+3=2010
+1=2011
Strokes: 19
Score: 19

0346092836
.986249812
..68086343
..09828197
.61248..55
.02574.681
...504.124
20.....313

Sample input:

9876
5432
1098
7654
3210

Sample output:

Start: (2, 2)
+9=9
*8=72
*4=288
*5=1440
+6=1446
+7=1453
+3=1456
+2=1458
+1=1459
Strokes: 9
Score: 561

9876
5432
10..
....
....

Sample input:

39857205
74493859
02175092
54239112
39209358
34568905

Sample output:

Start: (0, 0)
+3=3
*7=21
*4=84
*4=336
-1=335
*2=670
/3=(670/3)
*9=2010
+1=2011

.9857205
...93859
02.75092
54....12
39209358
34568905

Results

Unfortunately, there were only two contestants, but I'll post the results.

#1 - Howard (1881)
#2 - Gareth (5442)

The first half of the course consisted of roughly "normal" holes, generated mostly randomly. The second half was more challenging, as the holes contained more "sand traps" (sections deliberately filled with low numbers, especially 0s).

**Howard**
01) 5 - 5
02) 5 - 5
03) 6 - 6
04) 6 - 7
05) 6 - 7
06) 6 - 6
07) 5 - 5
08) 5 - 5
09) 6 - 6
10) 9 - 10
11) 5 - 8
12) 8 - 8
13) 6 - 7
14) 8 - 9
15) 7 - 12
16) 20 - 1665
17) 29 - 66
18) 30 - 44
Front 9) 52
Back  9) 1829
Full 18) 1881

**Gareth**
01) 9 - 10
02) 33 - 173
03) 8 - 8
04) 11 - 16
05) 7 - 84
06) 17 - 17
07) 9 - 10
08) 8 - 8
09) 15 - 15
10) 16 - 16
11) 12 - 32
12) 18 - 164
13) 34 - 335
14) 10 - 10
15) 26 - 447
16) 78 - 78
17) 1 - 2010
18) 1 - 2009
Front 9) 341
Back  9) 5101
Full 18) 5442

The course used can be found on pastebin.

@Howard: I ran your program with the lower number of paths due to limits on ideone. If your full version gives significantly different results, let me know the scores and the relative running time of the program.

Answer 1

Java - The Why-Not-Try-It-The-Easy-Way-Approach

Here is my first submission for this problem. I don't know if it qualifies for ai-player because it is more "artifical clumsiness". Maybe I can do better but I think it is hard to beat it on most grids.

The program just takes paths and operations calculated by a very complicated and clever algorithm (no, it's not random ;-) It will give you the same result every time) and compares all of them to find the best one.

Input must be given on STDIN. You can see the examples running here (note: number of paths reduced).

The output for above holes is

Start: (4, 0)
+9=9
*4=36
*8=288
*7=2016
-6=2010
Strokes: 5
Score: 6

Start: (3, 3)
+9=9
*8=72
*4=288
*7=2016
-5=2011
Strokes: 5
Score: 5

Start: (0, 2)
+7=7
*8=56
*4=224
-0=224
*9=2016
-5=2011
Strokes: 6
Score: 6

Start: (2, 3)
+7=7
*9=63
*4=252
*8=2016
-5=2011
Strokes: 5
Score: 5

The program itself is given below (it makes use of lots of static declarations - don't try this at home).

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Random;

public class Main {

    // DEBUG=true displays progress
    private static final boolean DEBUG = false;

    // Number of paths to try
    private static final int PATHS = 10000000;

    // Saves the number grid
    static int[][] grid;

    // start position
    static int startx;
    static int starty;

    // used digits and operations
    static int[] ns = new int[1024];
    static int[] ops = new int[1024];

    // current best score and output for this score
    static double bestScore;
    static String best;

    // a random number generator
    static Random random;

    public static void main(String[] args) throws IOException {
        BufferedReader cons = new BufferedReader(new InputStreamReader(System.in));

        String[] conLines = new String[1024];
        int numLines = 0;

        while (true) {
            String line = cons.readLine();
            if (line == null || line.isEmpty()) {
                // already some lines found
                if (numLines > 0) {
                    // prepare grid and run algorithm
                    prepareGrid(conLines, numLines);
                    findBest();
                    System.out.println(best);
                }
                numLines = 0;
            } else {
                conLines[numLines++] = line;
            }
            if (line == null)
                break;
        }
    }

    private static void findBest() {
        random = new Random(1);
        bestScore = 9999e99;
        for (int k = 0; k < PATHS; k++) {
            int sx = startx = random.nextInt(grid.length);
            int sy = starty = random.nextInt(grid[0].length);
            doStep(0, 1, 0, sx, sy);
        }
    }

    private static void doStep(int num, int den, int steps, int sx, int sy) {
        // consume the digit at the current position
        ns[steps] = grid[sx][sy];
        grid[sx][sy] = -1;

        // choose random operation and apply to total=num/den
        ops[steps] = num == 0 || ns[steps] == 0 ? random.nextInt(2) : random.nextInt(4);
        if (ops[steps] == 0) {
            num -= den * ns[steps];
        } else if (ops[steps] == 1) {
            num += den * ns[steps];
        } else if (ops[steps] == 2) {
            den *= ns[steps];
            int g = gcd(num, den);
            if (g > 1) {
                num /= g;
                den /= g;
            }
        } else if (ops[steps] == 3) {
            num *= ns[steps];
            int g = gcd(num, den);
            if (g > 1) {
                num /= g;
                den /= g;
            }
        }

        // calculate score for path up to now and save it if best
        double score = steps + 1 + Math.abs(2011 - num / (double) den);
        if (score < bestScore) {
            bestScore = score;
            best = String.format("Start: (%d, %d)\n", starty, startx);
            int nn = 0;
            int dn = 1;
            for (int k = 0; k <= steps; k++) {
                if (ops[k] == 0) {
                    nn -= dn * ns[k];
                } else if (ops[k] == 1) {
                    nn += dn * ns[k];
                } else if (ops[k] == 2) {
                    dn *= ns[k];
                    int g = gcd(nn, dn);
                    if (g > 1) {
                        nn /= g;
                        dn /= g;
                    }
                } else if (ops[k] == 3) {
                    nn *= ns[k];
                    int g = gcd(nn, dn);
                    if (g > 1) {
                        nn /= g;
                        dn /= g;
                    }
                }
                best += String.format(dn == 1 ? "%c%d=%d\n" : "%c%d=%d/%d\n", "-+/*".charAt(ops[k]), ns[k], nn, dn);
            }
            best += String.format("Strokes: %d\n", steps + 1);
            best += dn == 1 ? String.format("Score: %d\n", (int) (score + 0.05)) : String.format("Score: %f\n", score);
            if (DEBUG) {
                System.out.println(best);
                printGrid(grid);
                System.out.println();
            }
        }

        if (steps + 2 < bestScore) {
            // choose any direction and go on
            int dir = random.nextInt(4);
            int nx = sx;
            int ny = sy;
            int b = 0;
            while (b < 4) {
                if (dir == 0 && sx > 0 && grid[sx - 1][sy] >= 0) {
                    nx = sx - 1;
                    break;
                } else if (dir == 1 && sx < grid.length - 1 && grid[sx + 1][sy] >= 0) {
                    nx = sx + 1;
                    break;
                } else if (dir == 2 && sy > 0 && grid[sx][sy - 1] >= 0) {
                    ny = sy - 1;
                    break;
                } else if (dir == 3 && sy < grid[0].length - 1 && grid[sx][sy + 1] >= 0) {
                    ny = sy + 1;
                    break;
                }
                b++;
                dir++;
            }

            // if further step possible
            if (b < 4) {
                doStep(num, den, steps + 1, nx, ny);
            }
        }

        // put back the digit
        grid[sx][sy] = ns[steps];
    }

    // helper function calculating gcd
    private static int gcd(int a, int b) {
        while (b != 0) {
            int t = b;
            b = a % b;
            a = t;
        }
        return a;
    }

    // helper function reading the grid from an array of strings
    private static void prepareGrid(String[] data, int numLines) {
        grid = new int[data[0].length()][numLines];
        for (int y = 0; y < numLines; y++) {
            for (int x = 0; x < data[y].length(); x++) {
                grid[x][y] = (int) (data[y].charAt(x) - '0');
            }
        }
    }

    // helper function printing the grid
    private static void printGrid(int[][] grid) {
        for (int y = 0; y < grid[0].length; y++) {
            for (int x = 0; x < grid.length; x++) {
                System.out.print(grid[x][y] < 0 ? '.' : (char) ('0' + grid[x][y]));
            }
            System.out.println();
        }
    }
}

Edit: Just did a small performance optimization. We don't need to follow a path anymore if it's length already exceeds the best score found so far.

Answer 2

Scala

object Main
{
    def main(args:Array[String])
    {
        var input=io.Source.stdin.getLines.toArray

        while(!input.isEmpty)
        {
            var hole=input.takeWhile(_!="").map(_.map(x=>Integer.parseInt(x.toString)).toArray).toArray
            input=input.dropWhile(_!="")
            if(!input.isEmpty)
                input=input.tail

            var (height,width)=(hole.size,hole.head.size)
            var bestscore=10000000
            var bestrunoutput=""
            var currentval=0
            var output=""
            var exit=false
            var c:Array[Array[Int]]=Array(Array(0))
            var(steps,xnow,ynow)=(0,0,0)

            def getNeighbours(x:Int,y:Int,c:Array[Array[Int]]):Array[(Int,Int,Int)]=
                (for(a<- -1 to 1;b<- -1 to 1;if(Math.abs(a)!=Math.abs(b) && x+b>=0 && x+b<width && y+a>=0 && y+a<height)) yield (c(y+a)(x+b),x+b,y+a)).toArray.sortBy(_._1).reverse

            for(y<-0 until height;x<-0 until width)
            {
                c=hole.map(_.clone)
                exit=false
                steps=0
                xnow=x
                ynow=y

                currentval=c(ynow)(xnow)
                output="Start: ("+y+","+x+")\n+"+currentval+"="+currentval+"\n"
                while(!exit)
                {
                    var neighbours=getNeighbours(xnow,ynow,c)
                    while(neighbours.size>0 && (neighbours.head._1*currentval>2011 || neighbours.head._1<2))
                        neighbours=neighbours.drop(1)
                    if(neighbours.size==0)
                    {
                        neighbours=getNeighbours(xnow,ynow,c)
                        while(neighbours.size>0 && (neighbours.head._1+currentval>2011 || neighbours.head._1==0))
                            neighbours=neighbours.drop(1)
                        if(neighbours.size==0)
                        {
                            exit=true
                        }
                        else
                        {
                            currentval+=neighbours.head._1
                            c(ynow)(xnow)=0
                            output+="+"+neighbours.head._1+"="+currentval+"\n"
                        }
                    }    
                    else
                    {
                        currentval*=neighbours.head._1
                        c(ynow)(xnow)=0
                        output+="*"+neighbours.head._1+"="+currentval+"\n"
                    }
                    if(!exit)
                    {
                        xnow=neighbours.head._2
                        ynow=neighbours.head._3
                    }
                    steps+=1
                }
                output+="Strokes: "+steps+"\nScore: "+(steps+2011-currentval)+"\n"

                if(steps+2011-currentval<bestscore)
                {
                    bestscore=steps+2011-currentval
                    bestrunoutput=output
                }
            }

            println(bestrunoutput)
        }
        println
    }
}

I've tidied it up a little, fixed the bug that let the same number be used more than once for addition, and I've met the requirement (which I didn't spot before) to take multiple holes as input.

The algorithm is fairly simple:

For every possible start point:
    Find the highest value neighbour and try multiplying it
    If it's too high
        Try the next highest neighbour
        If there are no more neighbours
            Find the highest value neighbour and try adding it
            If it's too high
                Try the next highest neighbour
                If there are no more neighbours
                    End this attempt and calculate the score
Print out the attempt with the best score

Running in ideone.com:

Input

14932875921047
60438969014654
56398659108239
90862084187569
94876198569386
14897356029523

0346092836
1986249812
3568086343
5509828197
4612486355
3025745681
7685047124
2098745313

9876
5432
1098
7654
3210

39857205
74493859
02175092
54239112
39209358
34568905

Output

Start: (0,3)
+3=3
*9=27
*4=108
*3=324
*6=1944
+5=1949
+9=1958
+9=1967
+4=1971
+8=1979
+8=1987
+9=1996
+7=2003
+6=2009
+2=2011
Strokes: 15
Score: 15

Start: (6,6)
+7=7
*5=35
*4=140
*7=980
+8=988
+9=997
+8=1005
*2=2010
+1=2011
Strokes: 9
Score: 9

Start: (4,0)
+3=3
*7=21
*6=126
*5=630
+9=639
*3=1917
+7=1924
+8=1932
+9=1941
+5=1946
+4=1950
Strokes: 11
Score: 72

Start: (4,5)
+3=3
*9=27
*8=216
*9=1944
+9=1953
+5=1958
+7=1965
+9=1974
+5=1979
+8=1987
+9=1996
+4=2000
+7=2007
+3=2010
Strokes: 14
Score: 15

Looks like mine'll have to be content being weekend golf player compared to Howard's Tiger Woods. :-)