算术高尔夫: Reach 2011

Question

这是一个艾博挑战。你的目标是尽快达到2011年的数字，或者尽可能接近它。

规则：

• 一个“洞”由一个数字(0-9)的矩形网格组成。
• 你的总数从0开始。
• 你可以从网格上的任何数字开始。这是你第一次“中风”
• 对于随后的每一次笔划，您都可以移动到任何相邻的数字(上、左、下、右)。但是，您可能不会移动到以前使用过的数字。
• 对于每一笔，您将使用当前总计和当前位置的数字作为操作数(总和始终是第一个操作数)，并应用四个基本算术操作之一(+ -* /)。结果将成为你的新的总数。
• 如果你的总数变成2011年，你的成绩是笔画的数量。
• 如果您没有更有效的移动，您的分数是您当前的笔画数+您的总距离从2011年。
• 你也可以选择在任何时候停止，你的分数将是你目前的笔画次数+你的总距离从2011年开始。

输入：

• 您将在一个包含每个“孔”数据的文件中读取。或者，您可以通过stdin或等效的方式接受输入。
• 每个孔将由H行W位数组成，用于尺寸为WxH的网格。H和W可能随孔而变。
• 这些洞将用一条空白行隔开。
• 本着高尔夫的精神，比赛将由18个洞组成，但你的项目应该能够处理任何数量的洞。

输出：

• 对于每个洞，你的程序应该输出起始数字的位置。位置应为(row, col)，左上角为(0, 0).
• 对于每一笔，您的程序应该输出所选择的操作、当前数字和结果总数。
• 在每个洞的末尾，无论你是否到达2011年，你的程序都应该输出你的笔画数和洞的得分(通常与笔画数相同)。
• 出于测试目的，您可能还会发现，在指示使用了哪些数字的每块板上输出路径也是有帮助的。然而，您将不需要为竞争提供此输出。

备注：

• 对于任何给定的漏洞，您的程序应该始终从相同的位置开始，并选择相同的路径(即，没有随机选择)。每个洞的起始位置不需要相同。
• 总数不限于整数。也就是说，如果你把4023除以2，你的总数就会变成2011.5，而你仍然是离目标很远的.5。
• 你的程序应该在“合理”的时间内运行。
• 为了实现可验证性，您的程序应该可以在在线解释器(如ideone.com )上运行。
• 优胜者是在整个课程中总成绩最低的项目。如果有一个平局，平局将发挥一个新的过程，洞对洞，与最低得分前进，直到只有一个赢家。如果在比赛结束后还有一场平局，那么先提交的方案就会赢。

截止日期：

• 本次比赛的截止日期是2011年9月10日。这一期限可能会被延长，这取决于利息。

示例输入：

14932875921047
60438969014654
56398659108239
90862084187569
94876198569386
14897356029523

示例输出：

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

示例输出(紧凑)：

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

示例输入：

0346092836
1986249812
3568086343
5509828197
4612486355
3025745681
7685047124
2098745313

示例输出：

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

示例输入：

9876
5432
1098
7654
3210

示例输出：

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

示例输入：

39857205
74493859
02175092
54239112
39209358
34568905

示例输出：

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

结果

不幸的是，只有两名选手，但我会公布结果。

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

课程的前半部分由大致“正常”的洞组成，大部分是随机产生的。下半场更有挑战性，因为洞里有更多的“沙坑”(特别是0)。

**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

使用的课程可以在巴斯丁上找到。

@Howard:由于对ideone的限制，我以较低的路径数运行了您的程序。如果您的完整版本给出了显著不同的结果，让我知道的分数和程序的相对运行时间。

Answer 1

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

Java这是我第一次就这个问题提交意见。我不知道这是否符合ai-player的资格，因为这更像是“人为的笨拙”。也许我可以做得更好，但我认为在大多数网格上很难打败它。 程序只是采用一个非常复杂而聪明的算法计算出的路径和操作(不，它不是随机的;-)每次它都会给出相同的结果，并将它们进行比较以找到最佳的路径和操作。 必须输入STDIN。您可以看到运行这里的示例(注意:路径减少的数量)。 以上孔的输出为 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 下面给出了程序本身(它使用了大量的静态声明-不要在家里尝试)。 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(); } } } 编辑:刚刚做了一个小的性能优化。如果一条路径的长度已经超过了目前为止的最佳得分，我们就不需要再走这条路了。

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
    }
}

我把它整理了一下，修正了一个错误，这个bug让相同的数字不止一次地被用于添加，并且我已经满足了(我以前没有发现)以多个洞作为输入的要求。

算法相当简单：

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

在ideone.com中运行：

输入

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

输出

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

和霍华德的老虎伍兹相比，我的周末高尔夫选手一定很满足。:-)