Arithmetic Golf: Reach 2011

This is an 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.

• 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.

• Is the new total always <total> <op> <digit>, or can it be <digit> <op> <total>?
– J B
Aug 28, 2011 at 10:59
• @J B Always <total> <op> <digit>. I'll update the description to make it clearer. Aug 28, 2011 at 11:01
• 'Your program should run in a "reasonable" amount of time.' Should this not be properly specified? It seems you just want to prevent the brute-force solution, but there are other algorithms that also take quite a long time. Is 10 minutes per hole on a normal dual-core ok? An hour? The whole time from finishing the program till 09-10-2011 for the entire course, when running on a state-of-the-art mainframe? — And as for the non-randomness, is this just for being repeatable? Certainly, we may use a pseudo-random generator with a fixed seed? Or do you really want no Monte-Carlo? Aug 29, 2011 at 0:29
• @leftaroundabout I'm not sure how to properly specify what "reasonable" is without a standard environment. I suppose that since I'll be testing these on ideone, it should run to completion there, which I think means a maximum of 15 seconds per hole. Also, the non-randomness is indeed just for verifiability. You may use a PRNG with a fixed seed, since that should result in the same output every time. Aug 29, 2011 at 0:41
• @migimaru With larger number of paths it is 39 strokes less with a runtime of 150s for the complete course. Still hole 16 smashes my arithmetic golfer. Sep 12, 2011 at 17:16

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.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 {

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.

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 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)
neighbours=neighbours.drop(1)
if(neighbours.size==0)
{
neighbours=getNeighbours(xnow,ynow,c)
neighbours=neighbours.drop(1)
if(neighbours.size==0)
{
exit=true
}
else
{
c(ynow)(xnow)=0
}
}
else
{
c(ynow)(xnow)=0
}
if(!exit)
{
}
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. :-)