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.

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.