Riddler: Can you solve the not-so-corn maze?

I love AWK and I’ve written about it before……here.

I’m still coming up to speed on the language “R”, but often read the R-bloggers website. A recent post had an article about solving a maze, Riddler: Can you solve the not-so-corn maze?

I worked through the solution provided by Joshua Cook which is easier to read on his website. Honestly, the R solution was a bit beyond me atm, but I was curious about the runtime which was around 40 seconds on my macbook (not counting the graphing).

Like Jon Bentley, my go to language for testing algorithms is generally AWK, so I set out to solve it with using a language I’m more familiar with first. My premise was that his solution created an array of almost 10,000 objects and most were discarded. The following script only creates an array of valid edges and the script runs in about 100ms on my macbook. Granted, it doesn’t do the graphing (which is really cool actually).

Anyway, this was a just-for-fun post..  How would you solve it in your go-to language?

#!/bin/bash
#
# @(#) not-so-corn - solve a maze problem
#
# Description
#   The number in each box tells you how many spaces up, down,
#   left or right you must move. (no diagonal moves)
#   starting at six in the bottom left corner (10,1),
#     can you make your way to the zero at 7,3?
#
############################################################################
debug=false  # make this true to see all output


cat << "EoM" |
# row,column
start 10,1
finish 7,3
6 2 1 3 6 1 7 7 4 3
2 3 4 5 7 8 1 5 2 3
1 6 1 2 5 1 6 3 6 2
5 3 5 5 1 6 7 3 7 3
1 2 6 4 1 3 3 5 5 5
2 4 6 6 6 2 1 3 8 8
2 4 0 2 3 6 5 2 4 6
3 1 7 6 2 3 1 5 7 7
6 1 3 6 4 5 4 2 2 7
6 7 5 7 6 2 4 1 9 1
EoM

awk '
BEGIN { SUBSEP="," }
BEGIN { depthfound=20 }

/^#/ { next }
!NF  { next }
/start/  { start=$2; next }
/finish/ { finish=$2; next }

start && finish {  # gather the data
  # print
  columns = NF
  rows++
  for (col=1; col<=NF; col++)
    matrix[rows,col] = $col
}

# process - recursive function to find the paths
function process(from,      p,i, prevstack) {
  if (depth >= depthfound) {   # both of these variables are global
    # print "TOO DEEP"
    return 1
  }

  prevstack = stack

  if (from == finish) {
    print "SUCCESS", depth, stack
    depthfound=depth
    return 0
  }

  # else
  if (split(path[from],p)) { # should be at least one
    for (i in p) {
      if (from SUBSEP p[i] in seen) { # loop detection
        # printf "SEEN: %s:%s\n", from, p[i]
        return 1
      }
      else {
        stack = stack " " from ":" p[i]
        seen[from,p[i]]++
        depth++
        process(p[i])   # recurse! --^
        stack = prevstack
        delete seen[from,p[i]]
        depth--
      }
    }
  }
}

function pathadjust(from, to) {   # create list of valid paths
  if (to in matrix)  path[from] = path[from] " " to
}

function listvalid(r,c,     t,val) {
  val = matrix[r,c]
  pathadjust(r SUBSEP c, r-val SUBSEP c)
  pathadjust(r SUBSEP c, r+val SUBSEP c)
  pathadjust(r SUBSEP c, r SUBSEP c-val)
  pathadjust(r SUBSEP c, r SUBSEP c+val)
}

# print the matrix and update the path[] array
function printall(r,c) {
  for (r=1; r <= columns; r++) {
    for (c=1; c <= rows; c++) {
      if (r SUBSEP c in matrix) {
        listvalid(r,c)              # update path[]
        printf " %2d", matrix[r,c]
      }
    }
    printf "\n"
  }
}

END {
  printall()
  # list valid paths
  # for (i in path)
  #   printf "matrix[%s]=%d  -->%s\n", i, matrix[i],path[i]
  process(start)
}' |

(
  $debug  &&
    cat ||
    tail -1 | sed 's/SUCCESS [0-9]* *//' | tr ' ' '\n' | cat -n
)

There are other interesting problems to solve on the FiveThirtyEight website.