Robert Munyer is "Fastest Codeslinger of 2009"

Wow, that is some ugly code. If I've ever seen a program that needed 10 or 15 minutes of cleanup, it's that one.

A few minutes after the contest, Jim pointed out (correctly) that the use of "sort" is useless. It would be useful if, for example, we wanted the distance of a diagonal step to count as √2 times the distance of a vertical or horizontal step.

Speaking of a Useless Use of Sort... is everyone here familiar with UUOC? If not, it's worth a google.

(ns maze
	(:use clojure.set))

(def simple-board-string
".###..###
..###..##
..####.##
.#####.#.
..####.#.
#......#.
#.#####..")

(def panic-drafta-board-string
"..........................................#....................................
########...#######..##....##.####.#########...#############....................
##.....##.##.....##.###...##.####....##..............###.......................
##.....##.##.....##.####..##..##.....##................########................
##.....##.##.....##.##.##.##.##......##..........#####....#....................
##.....##.##.....##.##..####.........##.....####..........#....................
##.....##.##.....##.##...###.........##........###############################.
########...#######..##....##.........##............#...........................
...................................................#..........#######..........
.........###########################################...........................
.....................................................##########################
####################################################...........................
.....................................................##########################
########.....###....##....##.####..######.....####.############################
##.....##...##.##...###...##..##..##....##....####.............................
##.....##..##...##..####..##..##..##..........####.............................
########..##.....##.##.##.##..##..##...........##..............................
##........#########.##..####..##..##...........................................
##........##.....##.##...###..##..##....##....####.............................
##........##.....##.##....##.####..######.....####.............................
.........................#........................#############################
........#########################################.......#######################
...............................................................................
.#############################################################################.
..###########################################################################..
...########################################################################..##
....######################################################################..###
.....####################################################################..####
......##################################################################.......
.......################################################################....####
........##############################################################...######
.........############################################################...#######
.###################################################################...........
...............................................................................
.##############################################################################
...............................................................................
##############################################################################.
...............................................................................
.##############################################################################
...............................................................................")

(defn cartesian-product [seq1 seq2]
	(mapcat 
		(fn [x1] 
			(map 
				(fn [x2] (list x1 x2)) 
				seq2))
		seq1))

; make board from string where obstacles are '#' and empty spaces are '.'
; board is set of allowed positions as [x y]
(defn board-and-goal-from-string [s]
	(let 
		[rows (filter not-empty (map (fn [s] (.trim s)) (.split s "\n")))
		 num-rows (count rows)
		 num-cols (count (first rows))]
		[(set
			(filter
				(fn [pos] 
					(= \. 
						(nth
							(nth rows (- (first pos) 1))
							(- (second pos) 1))))
				(cartesian-product 
					(range 1 (+ 1 num-rows)) 
					(range 1 (+ 1 num-cols)))))
		 [num-rows num-cols]]))

(defn board-from-string [s]
	(get (board-and-goal-from-string s) 0))
	
(defn goal-from-string [s]
	(get (board-and-goal-from-string s) 1))

(def simple-board (board-from-string simple-board-string))

(def simple-goal (goal-from-string simple-board-string))

(def panic-drafta-board (board-from-string panic-drafta-board-string))

(def panic-drafta-goal (goal-from-string panic-drafta-board-string))

(defn maze-step [start]
	(map 
		(fn [direction] (map + start direction))
		(cartesian-product [-1 0 1] [-1 0 1])))

(defn maze-search 
	([old-paths allowed-states goal-state]
		(when (not (empty? old-paths))
			(let [next-path (first old-paths)
			      next-state (first next-path)
			      new-states (filter (fn [s] (contains? allowed-states s)) (maze-step next-state))]
				(if (= goal-state next-state)
					(reverse next-path)
					(recur
						(concat
							(rest old-paths)
							(map (fn [s] (cons s next-path)) new-states))
						(difference allowed-states (set new-states))
						goal-state)))))
	([allowed-states goal-state]
		(maze-search [[[1 1]]] allowed-states goal-state)))

(def simple-result 
	(maze-search 
		simple-board 
		simple-goal))
		
(def panic-drafta-result 
	(maze-search 
		panic-drafta-board 
		panic-drafta-goal))

(defn mis-step? [path board goal]
	(cond 
		(empty? path)	nil
		(not (contains? board (first path))) (first path)
		:default (recur (rest path) board goal)))

(defn contains-start? [path board goal]
	(= [1 1] (first path)))

(defn contains-goal? [path board goal]
	(contains? (set path) goal))

(defn long-step? [path board goal]
	(when (and (first path) (second path))
		(if (contains? (set (maze-step (first path))) (second path))
			(recur (rest path) board goal)
			[(first path) (second path)])))

(defn solution-mistake [path board goal]
	(cond
		(not (contains-start? path board goal)) {:include-start [1 1]}
		(not (contains-goal? path board goal)) {:include-goal goal}
		(mis-step? path board goal) {:mis-step (mis-step? path board goal)}
		(long-step? path board goal) {:long-step (long-step? path board goal)}
		(> (count path) (count (maze-search board goal))) {:solution-too-long (count path)}))

(def simple-result-skip-start
	'((2 1) (3 1) (4 1) (5 2) (6 3) (6 4) (6 5) (6 6) (6 7) (7 8) (7 9)))

(def simple-result-skip-goal
	'([1 1] (2 1) (3 1) (4 1) (5 2) (6 3) (6 4) (6 5) (6 6) (6 7) (7 8)    ))

(def simple-result-mis-step
	'([1 1] (2 1) (3 1)   (4 2)   (5 2) (6 3) (6 4) (6 5) (6 6) (6 7) (7 8) (7 9)))

(def simple-result-skip-mid
	'([1 1] (2 1) (3 1) (4 1)     (6 3) (6 4) (6 5) (6 6) (6 7) (7 8) (7 9)))

(def simple-result-inefficient
	'([1 1] (2 1) (3 1) (4 1) (5 1) (6 2) (6 3) (6 4) (6 5) (6 6) (6 7) (7 8) (7 9)))

#!/usr/bin/env python

###  Parse input into sideways 2-dim list. I.e., Element x,y is at maze[y][x]
#
#  E.g., "..#\n#.#\n" will become [ ['.', '.', '#'], ['#', '.', '#'] ]
#
# BUGS: The maze must be well formed. The Y coordinate increases downward

from sys import argv
maze = [list(l.strip()) for l in open(argv[1])]	# Parsing was the easy part.

W = len(maze[0])	# Width of maze (characters in first row)
H = len(maze)		# Height of maze (number of rows)

def valid(x,y):		# Check coordinate within maze rectangle
  return (
    0 <= x < W and
    0 <= y < H)

def moves(x,y): return (# Returns octuple of coordinates one move from (x,y).
  (x+0,y+1), (x+0,y-1),	#   NOTE:  Some may be outside rectangular maze.
  (x+1,y-1), (x+1,y+0),	#          Others may be blocked by '#'.
  (x+1,y+1), (x-1,y-1),
  (x-1,y+0), (x-1,y+1))
  
def move(X,Y):		# Add neighbors of X,Y to queue and mark with cost.
  global queue		# Queue is global fifo of points
  c = maze[Y][X]+1	# It costs one step to move from here to there

  for x,y in moves(X,Y):	# Loop through neighbors of (X,Y):
    if (valid(x,y) and 		#   If not outsize maze and
    maze[y][x] == '.'):		#   haven't already been there,
      queue.append((x,y))	#     put neighbor onto end of queue
      maze[y][x] = c		#     change cost from '.' to number of steps.


# First loop floods maze and labels each point with the cost (number of 
# moves) for the rat to reach it.

queue = [(0,0)]		# Rat starts in upper-left corner
maze[0][0] = 0 		# Flood maze and replace each reachable '.' with the
while queue:		# 'cost' to reach it from upper left corner.
  x,y = queue.pop(0)	# Remove lowest-cost point from *head* of queue
  move(x,y)		#   visit, add neighbors to *tail* of queue
  
# We got the above code written when Robert announced his program had found
# the solution. We got the above code *debugged* by the time Eric verified
# our hopes were dashed and Robert had won.
#
# By the time I got home, Marly had broken up move(X,Y) into three separate
# functions (as you see it now) to make two of them useful for the following
# function, and was just finishing the second loop that actually accumulates
# the *backward* path into a list.
#
# I did some housekeeping and added comments and code to handle the case when 
# no path exists.

def retrace(X,Y):	# Return a neighbor of X,Y one step closer to start
  c = maze[Y][X]-1	# Cost of neighbor that's one step closer
  for x,y in moves(X,Y):# Loop through neighbors of (X,Y)
    if (valid(x,y) and 	#   If inside maze and
    maze[y][x] == c): 	#   exactly one step closer to start,
      return x,y	#     return another step backward

# Second loop starts at the endpoint and marches back toward the start.

x,y = W-1, H-1  		# The rat's endpoint, the lower-right corner
if type(maze[y][x]) != int:	# Defends against no-solution case	
  quit("no solution")
  
# We started at (0,0), but in ratspeak, that's (1,1).  The solution demands
# ratspeak, so we'll just add 1,1 to each solution point.
  
steps = [(x+1,y+1)]		# First step back is last step out
while x or y:			# Until back at (0,0):
  x,y = retrace(x,y)		#   Take a step back
  steps.append((x+1,y+1))	#   Add new location to list

steps.reverse()			# Change backward path to forward
print len(steps),"points:",	# Print number, list of points rat visits
print steps		

This is a GIF animation that shows the maze being solved. The colors were chosen to suggest a wildfire spreading through a forest.

The last frame is a solution of the maze (in fact, it includes every solution) because each burned cell has little arrowheads pointing back to the cells that ignited it.

The rat only needs to follow arrowheads, and he's guaranteed to get out after visiting the least possible number of cells.

(Hmm... I don't see a way to upload the GIF files. I'll send 'em to Clint.)