Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Solution for http://www.lispology.com/show?ZXE It takes advantage from the fact that when moving backwards there is only one possible move.
;; From: http://www.lispology.com/show?ZXE
;; A General solution
(defpackage #:tweet-maze
(:use #:cl))
(in-package #:tweet-maze)
(defun read-maze (string-description)
(loop :for index :from 0
:for char :across string-description
:collect (cons index (digit-char-p char))))
(defun short-list (x y)
(< (length x) (length y)))
(defun links-to (target maze)
(loop :for (position . stride) :in maze
:when (and (/= stride 0)
(member target (list (+ position stride)
(- position stride))
:test #'=))
:collect position))
(defun find-path (maze)
(let (solutions)
(labels ((%find-path (current-position target-position maze path)
(let ((positions (links-to current-position maze)))
(dolist (new-position positions)
(cond ((= target-position new-position)
(push (cons new-position path)
solutions))
;; To prevent following cycles.
((member new-position path :test #'=) 'dead-end)
(t (%find-path new-position
target-position
maze
(cons new-position path))))))))
(%find-path (length maze)
0
maze
nil))
;; Just in case there are multiple solutions
(sort solutions #'short-list)))
(find-path (read-maze "7347737258493420"))
(find-path (read-maze "2649572484342750"))
(defvar *tweet-maze*
'((0 . 7)
(1 . 3)
(2 . 4)
(3 . 7)
(4 . 7)
(5 . 3)
(6 . 7)
(7 . 2)
(8 . 5)
(9 . 8)
(10 . 4)
(11 . 9)
(12 . 3)
(13 . 4)
(14 . 2)
(15 . 0))
"The maze to solve. (index . movement)")
(defun links-to (target maze)
(dolist (square maze)
(destructuring-bind (position . stride) square
(when (and (/= stride 0)
(member target (list (+ position stride)
(- position stride))
:test #'=))
(return position)))))
(defun solve (position path)
(cond ((zerop position) (cons position path))
(t (solve (links-to position *tweet-maze*) (cons position path)))))
(solve 15 nil)
;; (0 7 5 8 3 10 14 12 15)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.