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.

 

One thought on “Riddler: Can you solve the not-so-corn maze?”

  1. Hey I am so glad I found your website, I really found you by accident,
    while I was browsing on Bing for something else, Regardless I am here now and
    would just like to say thank you for a incredible post and a
    all round exciting blog (I also love the theme/design), I don’t have time to read it all
    at the moment but I have bookmarked it and also added in your RSS
    feeds, so when I have time I will be back to read a lot more,
    Please do keep up the excellent job.

Leave a Reply

Your email address will not be published. Required fields are marked *

19 + seven =