ハニカム歩き, http://qiita.com/Nabetani/items/55641767510c2f9f235f

2013-05-10-honeycomb-walk.lisp

;;;; Last modified: 2013-12-01 21:19:28 tkych


;;====================================================================
;; ハニカム歩き
;;====================================================================
;; - [ハニカム歩き 〜 横へな 2013.5.10](http://nabetani.sakura.ne.jp/hena/ord10haniwa/)
;; - [第10回オフラインリアルタイムどう書くの問題](http://qiita.com/Nabetani/items/55641767510c2f9f235f)


;;--------------------------------------------------------------------

(in-package :cl-user)
(defpackage :honeycomb (:use :cl))
(in-package :honeycomb)


;;--------------------------------------------------------------------
;; Main
;;--------------------------------------------------------------------

;; brute force

(defparameter *honeycomb* (make-hash-table))

(defstruct (unit (:conc-name nil))
  label
  (next (make-array 6 :element-type '(or null unit) :initial-element nil)))

(defun add-unit-to-honeycomb (label &rest next-units)
  (let ((unit (or (gethash label *honeycomb*)
                  (make-unit :label label))))
    (dotimes (i 6)
      (let ((next (nth i next-units)))
        (when next
          (setf (aref (next unit) i)
                (or (gethash next *honeycomb*)
                    (make-unit :label next))))))
    (setf (gethash label *honeycomb*) unit)
    T))

(add-unit-to-honeycomb #\A #\B #\C #\D #\E #\F #\G)
(add-unit-to-honeycomb #\B #\H #\I #\C #\A #\G #\S)
(add-unit-to-honeycomb #\C #\I #\J #\K #\D #\A #\B)
(add-unit-to-honeycomb #\D #\C #\K #\L #\M #\E #\A)
(add-unit-to-honeycomb #\E #\A #\D #\M #\N #\O #\F)
(add-unit-to-honeycomb #\F #\G #\A #\E #\O #\P #\Q)
(add-unit-to-honeycomb #\G #\S #\B #\A #\F #\Q #\R)
(add-unit-to-honeycomb #\H #\T #\U #\I #\B #\S #\k)
(add-unit-to-honeycomb #\I #\U #\V #\J #\C #\B #\H)
(add-unit-to-honeycomb #\J #\V #\W #\X #\K #\C #\I)
(add-unit-to-honeycomb #\K #\J #\X #\Y #\L #\D #\C)
(add-unit-to-honeycomb #\L #\K #\Y #\Z #\a #\M #\D)
(add-unit-to-honeycomb #\M #\D #\L #\a #\b #\N #\E)
(add-unit-to-honeycomb #\N #\E #\M #\b #\c #\d #\O)
(add-unit-to-honeycomb #\O #\F #\E #\N #\d #\e #\P)
(add-unit-to-honeycomb #\P #\Q #\F #\O #\e #\f #\g)
(add-unit-to-honeycomb #\Q #\R #\G #\F #\P #\g #\h)
(add-unit-to-honeycomb #\R #\j #\S #\G #\Q #\h #\i)
(add-unit-to-honeycomb #\S #\k #\H #\B #\G #\R #\j)
(add-unit-to-honeycomb #\T nil nil #\U #\H #\k nil)
(add-unit-to-honeycomb #\U nil nil #\V #\I #\H #\T)
(add-unit-to-honeycomb #\V nil nil #\W #\J #\I #\U)
(add-unit-to-honeycomb #\W nil nil nil #\X #\J #\V)
(add-unit-to-honeycomb #\X #\W nil nil #\Y #\K #\J)
(add-unit-to-honeycomb #\Y #\X nil nil #\Z #\L #\K)
(add-unit-to-honeycomb #\Z #\Y nil nil nil #\a #\L)
(add-unit-to-honeycomb #\a #\L #\Z nil nil #\b #\M)
(add-unit-to-honeycomb #\b #\M #\a nil nil #\c #\N)
(add-unit-to-honeycomb #\c #\N #\b nil nil nil #\d)
(add-unit-to-honeycomb #\d #\O #\N #\c nil nil #\e)
(add-unit-to-honeycomb #\e #\P #\O #\d nil nil #\f)
(add-unit-to-honeycomb #\f #\g #\P #\e nil nil nil)
(add-unit-to-honeycomb #\g #\h #\Q #\P #\f nil nil)
(add-unit-to-honeycomb #\h #\i #\R #\Q #\g nil nil)
(add-unit-to-honeycomb #\i nil #\j #\R #\h nil nil)
(add-unit-to-honeycomb #\j nil #\k #\S #\R #\i nil)
(add-unit-to-honeycomb #\k nil #\T #\H #\S #\j nil)

(defun goto (state step)
  (let ((unit (gethash state *honeycomb*)))
    (aref (next unit) step)))

(defun main (input)
  (with-output-to-string (s)
    (princ #\A s)
    (loop :for step :across input
          :with state := #\A
          :do (let ((next (goto state (digit-char-p step))))
                (if next
                    (progn
                      (princ (label next) s)
                      (setf state (label next)))
                    (princ #\! s))))))


;;--------------------------------------------------------------------
;; Tests
;;--------------------------------------------------------------------

(defun =>? (got expected)
  (assert (string= got expected)))

(progn
  (=>? (main "135004") "ACDABHS")
  (=>? (main "1") "AC")
  (=>? (main "33333120") "AENc!!b!M")
  (=>? (main "0") "AB")
  (=>? (main "2") "AD")
  (=>? (main "3") "AE")
  (=>? (main "4") "AF")
  (=>? (main "5") "AG")
  (=>? (main "4532120") "AFQPOEMD")
  (=>? (main "051455") "ABSHSj!")
  (=>? (main "23334551") "ADMb!cdeO")
  (=>? (main "22033251") "ADLKLa!ML")
  (=>? (main "50511302122") "AGSjkTHTU!VW")
  (=>? (main "000051") "ABHT!!!")
  (=>? (main "1310105") "ACDKJW!V")
  (=>? (main "50002103140") "AGSk!HU!IVIU")
  (=>? (main "3112045") "AEDKYXKC")
  (=>? (main "02021245535") "ABCIJW!JIHBS")
  (=>? (main "014204") "ABIBCIB")
  (=>? (main "255230") "ADAGAEA")
  (=>? (main "443501") "AFPefgQ")
  (=>? (main "022321") "ABCKLZ!")
  (=>? (main "554452") "AGRh!!Q")
  (=>? (main "051024") "ABSHTUH")
  (=>? (main "524002") "AGAFGSB")
  (=>? (main "54002441132") "AGQRjSRhRSGA")
  (=>? (main "11010554312") "ACJV!!UTkSHI")
  (=>? (main "23405300554") "ADMNEFOFGRi!")
  (=>? (main "555353201") "AGRih!gPQG")
  (=>? (main "22424105") "ADLMabaLD")
  (=>? (main "11340202125") "ACJKDCKJX!!J")
  (=>? (main "4524451") "AFQFPf!P")
  (=>? (main "44434234050") "AFPf!!e!!Pgh")
  (=>? (main "00554040132") "ABHk!j!i!jRG")
  (=>? (main "3440403") "AEOePfgf")
  (=>? (main "111130") "ACJW!XW")
  (=>? (main "21133343125") "ADKXYZ!a!Z!L")
  (=>? (main "353511") "AEFOPFA")
  (=>? (main "22204115220") "ADLZYLY!KY!X")
  (=>? (main "03013541") "ABABICBGB")
  (=>? (main "101344") "ACIVJCA")
  (=>? (main "2432541") "ADENbNdN")
  (=>? (main "45332242015") "AFQPedc!!NME")
  (=>? (main "215453") "ADKCAGF")
  (=>? (main "45540523454") "AFQh!i!RQg!!")
  (=>? (main "42434302545") "AFEOd!!ONOef")
  )

;;====================================================================