(defparameter *sample-input*
  "(2,0)
 e se se sw  s
 s nw nw  n  w
ne  s  h  e sw
se  n  w ne sw
ne nw nw  n  n"
  "Challenge input.")

(defun parse-coord-string (coord)
  "Convert an (X, Y) coordinate pair into a list consisting of (X Y)."
  (with-input-from-string (coord-stream (substitute #\Space #\, coord))
	(read coord-stream)))

(defun split-seq (splitp seq)
  "Split SEQ into chunks based on SPLITP."
  (loop
	 for beg = (position-if-not splitp seq)
	 then (position-if-not splitp seq :start (1+ end))
	 for end = (and beg (position-if splitp seq :start beg))
	 if beg collect (subseq seq beg end)
	 while end))

(defun 2d-array-find (item arr &key (test #'eql))
  "Returns a list of (X Y) coordinates if ITEM is found in ARR."
  (loop named outer-loop
	 for y below (array-dimension arr 0) do
	   (loop for x below (array-dimension arr 1)
	      if (funcall test (aref arr y x) item)
	      do (return-from outer-loop (list x y)))))

(defun points-that-could-reach-coord (arr coord)
  (destructuring-bind (coord-x coord-y) coord
	(loop for y below (array-dimension arr 0) nconc
	     (loop
		for x below (array-dimension arr 1)
		for dir = (aref arr y x)
		for x-delta = (- x coord-x)
		for y-delta = (- y coord-y)
		if (or (and (zerop x-delta)
			    (or (and (string= dir "s")
				     (minusp y-delta))
				(and (string= dir "n")
				     (plusp y-delta))))
		       (and (zerop y-delta)
			    (or (and (string= dir "e")
				     (minusp x-delta))
				(and (string= dir "w")
				     (plusp x-delta))))
		       (and (= (abs x-delta) (abs y-delta))
			    ; PLUSP and MINUSP ensure that neither is ZEROP
			    (or (and (string= "se" dir) (minusp y-delta) (minusp x-delta))
				(and (string= "sw" dir) (minusp y-delta) (plusp x-delta))
				(and (string= "ne" dir) (plusp y-delta) (minusp x-delta))
				(and (string= "nw" dir) (plusp y-delta) (plusp x-delta)))))
		collect (list x y)))))

(defun arrayify-maze (maze)
  (let ((maze-list (mapcar (lambda (x)
				 (split-seq (lambda (y) (char= #\Space y)) x))
			       maze)))
	(make-array (list (length maze-list)
			  (length (car maze-list)))
		    :initial-contents maze-list)))

(defun solve-maze (maze destination start-point)
  (labels ((%solve-maze (maze destination point-list potential-points)
		 (cond ((equal destination (car point-list))
			point-list)
		       ((null potential-points)
			nil)
		       ((null (car point-list))
			(%solve-maze maze
				     destination
				     (cdr point-list)
				     (cdr potential-points)))
		       (t
			(%solve-maze maze
				     destination
				     (cons (car potential-points) point-list)
				     (remove-if (lambda (x) (member x point-list :test #'equal))
						(points-that-could-reach-coord maze (car potential-points))))))))
	(%solve-maze maze destination (list start-point)
		     (points-that-could-reach-coord maze start-point))))

(defun show-map-solution (in)
  (destructuring-bind (start-coord &rest maze)
	  (split-seq (lambda (x) (char= #\Newline x)) in)
	(let* ((start-coord (parse-coord-string start-coord))
	       (maze-array (arrayify-maze maze))
	       (home-pos (2d-array-find "h" maze-array :test #'string=)))
	  (format t "~{(~{~d~^, ~})~%~}"
		  (solve-maze maze-array start-coord home-pos)))))

(show-map-solution *sample-input*)