The lost pawn problem

Question

The lost pawn problem

After the chess game ended, a surviving pawn was left behind enemy lines. let's help him find the shortest way back home.

The original problem describes a nXn "chess" board, and a function f: {1,..,n-1}X{1,..,n}X{-1,0,1} => R+ of weights. the goal is to find the best path from some square in the buttom line, to some other square in the top line, where the possible moves are: left-up,up,right-up, and you may not exit the board.

The problem is relatively easy to solve in O(n^2) using dynamic programming, but this is codegolf, and we don't care about useless stuff like running time complexity...

The Problem

input: a 3-dimentional array (or some other collection of your choice, received through stdin, or as a function argument), corresponding to a regular chess board, exactly in size: 7X8X3 (#linePasses X #rowSize X #movesPerPass) containing non-negative integers. the moves cost from some position (i,j) where i is the row index, and j is the column index, are:

• a[i][j][0] for the cost to travel up-left to square (i+1,j-1), or graphically: \.
• a[i][j][1] for the cost to travel up to square (i+1,j), or graphically: |.
• a[i][j][2] for the cost to travel up-right to square (i+1,j+1), or graphically: /.

you may assume it will not contain a path that sums greater than MAX_INT.

output: an 8X8 ascii output showing the best (shortest, i.e. minimum sum of weights) path (if there is more than 1 optimal result, you may show an arbitrary path of your choice). the path is drawn bottom to top, where in each line, the character corresponding to the pawn's position in the path, is the one it about to make. e.g. if the pawn is about to move up-left from column 3 (to column 2), the you should draw:

#?######
##\#####

where ? should be replaced with the next move. final position needs to be drawn as X.

Examples

input:

[
  [[1,1,1],[1,1,1],[0,1,1],[1,1,1],[1,1,1],[1,1,1],[1,1,1],[1,1,1]],
  [[1,1,1],[1,0,1],[1,1,1],[1,1,1],[1,1,1],[1,1,1],[1,1,1],[1,1,1]],
  [[1,1,1],[1,1,0],[1,1,1],[1,1,1],[1,1,1],[1,1,1],[1,1,1],[1,1,1]],
  [[1,1,1],[1,1,1],[1,1,0],[1,1,1],[1,1,1],[1,1,1],[1,1,1],[1,1,1]],
  [[1,1,1],[1,1,1],[1,1,1],[1,0,1],[1,1,1],[1,1,1],[1,1,1],[1,1,1]],
  [[1,1,1],[1,1,1],[1,1,1],[1,0,1],[1,1,1],[1,1,1],[1,1,1],[1,1,1]],
  [[1,1,1],[1,1,1],[1,1,1],[0,1,1],[1,1,1],[1,1,1],[1,1,1],[1,1,1]]
]

output:

##X#####
###\####
###|####
###|####
##/#####
#/######
#|######
##\#####

input:

[
  [[41,27,38],[12,83,32],[50,53,35],[46,32,26],[55,89,82],[75,30,87],[2,11,64],[8,55,22]],
  [[56,21,0],[83,25,38],[43,75,63],[56,60,77],[68,55,89],[99,48,67],[94,30,9],[62,62,58]],
  [[23,18,40],[24,47,61],[96,45,72],[71,6,48],[75,63,98],[93,56,51],[23,31,30],[49,34,99]],
  [[20,47,42],[62,79,72],[32,28,44],[68,61,55],[62,39,57],[4,17,49],[97,85,6],[91,18,12]],
  [[51,50,11],[32,39,56],[12,82,23],[33,88,87],[60,55,22],[29,78,14],[70,11,42],[63,94,67]],
  [[75,64,60],[27,79,86],[70,72,56],[55,45,32],[95,67,12],[87,93,98],[81,36,53],[38,22,93]],
  [[31,80,50],[77,71,22],[59,46,86],[64,71,53],[41,19,95],[62,71,22],[92,80,41],[26,74,29]]
]

output:

######X#
#####/##
####/###
#####\##
#####|##
######\#
######|#
#######\

this is code-golf, so shortest code wins.

play fair. no loopholes...

EDIT:

Iv'e written an un-golfed straight forward solution in scala you can look at. There's also a site you can play with scala code on-line: scalakata (just copy&paste the gist to scalakata, and hit the play button)

Answer 1

Q: 199 Bytes

f:{m::x;n::{@/[+/-1 0 1_\:/:(x;m[y;;|!3]);0 2;(0W,),{x,0W}]};i:*<*|r:{&/n[x;y]}\[8#0;!7];  s:{-1+{*<x}'+n[y;z]}\[();(,8#0),-1_r;!7];j:i,{x+y x}\[i;|s];-1(@[8#"#";;:;]'[j;"X","/|\\"1+s'[|!7;-1_j]]);}

NOTES

• Q interpreter (kx.com) free for non-commertial use (versions for Windows, Linux, Mac)
• This solution uses inner core of Q (internally named k4), so we need a scripting file with k extension, or interactive interpreter in k mode (\ command at first prompt). By contrast, 'verbose' (legible) version of the language requires script with q extension, and is the default mode at interactive interpreter.

TEST

f ((1 1 1; 1 1 1; 0 1 1; 1 1 1; 1 1 1; 1 1 1; 1 1 1; 1 1 1)
   (1 1 1; 1 0 1; 1 1 1; 1 1 1; 1 1 1; 1 1 1; 1 1 1; 1 1 1)
   (1 1 1; 1 1 0; 1 1 1; 1 1 1; 1 1 1; 1 1 1; 1 1 1; 1 1 1)
   (1 1 1; 1 1 1; 1 1 0; 1 1 1; 1 1 1; 1 1 1; 1 1 1; 1 1 1)
   (1 1 1; 1 1 1; 1 1 1; 1 0 1; 1 1 1; 1 1 1; 1 1 1; 1 1 1)
   (1 1 1; 1 1 1; 1 1 1; 1 0 1; 1 1 1; 1 1 1; 1 1 1; 1 1 1)
   (1 1 1; 1 1 1; 1 1 1; 0 1 1; 1 1 1; 1 1 1; 1 1 1; 1 1 1))

##X#####
###\####
###|####
###|####
##/#####
#/######
#|######
##\#####

f ((41 27 38; 12 83 32; 50 53 35; 46 32 26; 55 89 82; 75 30 87;  2 11 64;  8 55 22)
   (56 21  0; 83 25 38; 43 75 63; 56 60 77; 68 55 89; 99 48 67; 94 30  9; 62 62 58)
   (23 18 40; 24 47 61; 96 45 72; 71  6 48; 75 63 98; 93 56 51; 23 31 30; 49 34 99)
   (20 47 42; 62 79 72; 32 28 44; 68 61 55; 62 39 57;  4 17 49; 97 85  6; 91 18 12)
   (51 50 11; 32 39 56; 12 82 23; 33 88 87; 60 55 22; 29 78 14; 70 11 42; 63 94 67)
   (75 64 60; 27 79 86; 70 72 56; 55 45 32; 95 67 12; 87 93 98; 81 36 53; 38 22 93)
   (31 80 50; 77 71 22; 59 46 86; 64 71 53; 41 19 95; 62 71 22; 92 80 41; 26 74 29))

######X#
#####/##
####/###
#####\##
######\#
######|#
######|#
#######\

EXPLANATION

For ilustration purpose, we assume second test (matrix ((41 27 38; 12 83 32; ....)

We transform original matrix (m at code level): instead of orginimal matriz with a triplet for each coordinate, we define matrix for left, up, and right displacements. Left matrix contains 7x7 values (we drop first column), Up matrix 7x8, and right matrix 7x7 (we frop last column).

left                           up                         right
12 50 46 55 75 2  8       27 83 53 32 89 30 11 55     38 32 35 26 82 87 64
83 43 56 68 99 94 62      21 25 75 60 55 48 30 62     0  38 63 77 89 67 9 
24 96 71 75 93 23 49      18 47 45 6  63 56 31 34     40 61 72 48 98 51 30
62 32 68 62 4  97 91      47 79 28 61 39 17 85 18     42 72 44 55 57 49 6 
32 12 33 60 29 70 63      50 39 82 88 55 78 11 94     11 56 23 87 22 14 42
27 70 55 95 87 81 38      64 79 72 45 67 93 36 22     60 86 56 32 12 98 53
77 59 64 41 62 92 26      80 71 46 71 19 71 80 74     50 22 86 53 95 22 41

To calculate final position we need to evaluate minimum-cost path. We assume initial cost 0 0 0 0 0 0 0 0 (cost to arrive at each column of first row), and iterates with each next row. At each column i, we calculate three values:

• cost of previous i+1 value plus left[i+1]. We drop first component of cost (shifts and alineates columns to add) and sum component to component

• cost of previous i value plus up[i]. We sum component to component

• cost of previous i-1 value plus right[i-1]. We drop last component of cost (shifts and alineates columns to add) and sum component to component

To calculate minimum we complete left cost prepending infinite and right cost appending infinite: with 3 vectors of eight components, calculate minimum component to component. Resulting value is the base cost for new iteration

For first iteration we obtain values (0W is infinite in Q)

0W 12 50 46 55 75 2  8
27 83 53 32 89 30 11 55
38 32 35 26 82 87 64 0W

and calculates minimum of each column

27 12 35 26 55 30 2 8

After all iterations, we have the minimum cost to arrive to each square (assuming row 0 at top, 7 at bottom). We are only interested in last column, but i draw all intermediate results for ilustrative purposes

0   0   0   0   0   0   0   0
27  12  35  26  55  30  2   8
27  37  78  82  110 78  11  70
45  61  123 88  173 129 34  104
87  123 151 143 212 133 40  122
98  155 163 176 234 147 51  185
158 182 219 208 246 234 87  207
208 204 265 261 265 256 128 233

Now we found minimum value at last row (128, at column 6). That's the end of the path (X character in ouput).

We repeat cost calculation again, but now we annotate the direction from we obtain each minimum (wich of the 3 values used to calculate minimum is the selected value).

\|/|\///
\\\\\/|/
\\\|//|/
\\|\//|/
\\|//|\/
\\//|\|/
\|/|/|\/

We reverse rows, put 'X' at pos 6, and preserves only path that ends at column 6 (the others are substituted by #)

######X#
#####/##
####/###
#####\##
######\#
######|#
######|#
#######\