XY-Sort, http://qiita.com/Nabetani/items/7b08b0eb9ef84d7cfe49

2013-02-02-xy-sort.lisp

;;;; Last modified: 2013-11-29 23:59:01 tkych


;;====================================================================
;; XY-Sort
;;====================================================================
;; - [XY-Sort 〜 横へな 2013.2.2 の参考問題](http://nabetani.sakura.ne.jp/hena/ord7xysort/)
;; - [オフラインリアルタイムどう書く第7回の参考問題](http://qiita.com/Nabetani/items/7b08b0eb9ef84d7cfe49)


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

(in-package :cl-user)
(defpackage :xy-sort (:use :cl))
(in-package :xy-sort)


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

(defparameter *table* '((4 1 4 2 1 3)
                        (7 3 2 0 5 0)
                        (2 3 6 0 6 7)
                        (6 4 5 7 5 1)
                        (3 1 6 6 2 4)
                        (6 0 5 5 5 1)))

(defun transpose (table)
  (apply #'mapcar #'list table))

(defun sort-by-row (table i)
  (transpose (stable-sort (transpose table) #'< :key (lambda (col) (nth i col)))))

(defun sort-by-col (table i)
  (stable-sort (copy-seq table) #'< :key (lambda (row) (nth i row))))

;; Iteration
;; (defun main (input &optional (table *table*))
;;   (loop :for c :across input
;;         :do (if (upper-case-p c)
;;                 (setf table (sort-by-row table (- (char-code c) #.(char-code #\A))))
;;                 (setf table (sort-by-col table (- (char-code c) #.(char-code #\u)))))
;;         :finally (return (format nil "~{~D~}" (first table)))))

;; Recursion
(defun main (input &optional (table *table*))
  (let ((len (length input)))
    (labels ((rec (table i)
               (if (<= len i)
                   (format nil "~{~D~}" (first table))
                   (let ((c (char input i)))
                     (if (upper-case-p c)
                         (rec (sort-by-row table (- (char-code c) #.(char-code #\A)))
                              (1+ i))
                         (rec (sort-by-col table (- (char-code c) #.(char-code #\u)))
                              (1+ i)))))))
      (rec table 0))))


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

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

(progn
  (=>? (main "AvEx") "305027")
  (=>? (main "A") "112344")
  (=>? (main "C") "241413")
  (=>? (main "F") "134214")
  (=>? (main "u") "236067")
  (=>? (main "w") "732050")
  (=>? (main "y") "414213")
  (=>? (main "yx") "732050")
  (=>? (main "ux") "236067")
  (=>? (main "EF") "131424")
  (=>? (main "DF") "134124")
  (=>? (main "Au") "055165")
  (=>? (main "uA") "023667")
  (=>? (main "By") "234114")
  (=>? (main "yB") "114342")
  (=>? (main "yBy") "357020")
  (=>? (main "yByB") "350072")
  (=>? (main "AuBvCw") "131244")
  (=>? (main "FAuFBvFCw") "300527")
  (=>? (main "AuBv") "112344")
  (=>? (main "CwDx") "515056")
  (=>? (main "FzyE") "324114")
  (=>? (main "uAwDyB") "114324")
  (=>? (main "zExCvF") "073520")
  (=>? (main "uFxEv") "002357")
  (=>? (main "DyCwB") "076362")
  )

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