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=100 } /^#/ { 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.