積み木の水槽, http://qiita.com/Nabetani/items/936e7885f4c607472060

2013-09-06-block-water-tank.lisp

;;;; Last modified: 2014-01-04 23:01:02 tkych


;;====================================================================
;; 積み木の水槽
;;====================================================================
;; - [積み木の水槽 〜 横へな 2013.9.6](http://nabetani.sakura.ne.jp/hena/ord13blocktup/)
;; - [第13回オフラインリアルタイムどう書くの問題](http://qiita.com/Nabetani/items/936e7885f4c607472060)


;;--------------------------------------------------------------------
;; Package
;;--------------------------------------------------------------------

(in-package :cl-user)

(eval-when (:compile-toplevel :load-toplevel :execute)
  (ql:quickload :split-sequence))

(defpackage :block-water-tank
  (:use :cl)
  (:import-from :split-sequence :split-sequence))

(in-package :block-water-tank)


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

;; "83141310145" -> ((8 3 1 4 1 3 1) (1 4 5))
(defun parse (input)
  (split-sequence 0 (map 'list #'digit-char-p input)))

;; (8 3 1 4 1 3 1) -> 6
(defun count-water (tank)
  (labels
      ((rec (tank count)
         (if (null (cddr tank))
             count
             (destructuring-bind (left . rest) tank
               (rec rest
                    (+ count
                       (loop :for top :downfrom left :above (first rest)
                             :when (position top rest :test #'<=)
                               :collect it :into acc
                             :finally (return (reduce #'+ acc)))))))))
    (rec tank 0)))

(defun main (input)
  (loop :for tank :in (parse input)
        :collect (count-water tank) :into acc
        :finally (return (write-to-string (reduce #'+ acc)))))


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

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

(progn
  (=>? (main "83141310145169154671122") "24")    
  (=>? (main "923111128") "45")    
  (=>? (main "923101128") "1")    
  (=>? (main "903111128") "9")    
  (=>? (main "3") "0")    
  (=>? (main "31") "0")    
  (=>? (main "412") "1")    
  (=>? (main "3124") "3")    
  (=>? (main "11111") "0")    
  (=>? (main "222111") "0")    
  (=>? (main "335544") "0")    
  (=>? (main "1223455321") "0")    
  (=>? (main "000") "0")    
  (=>? (main "000100020003121") "1")    
  (=>? (main "1213141516171819181716151413121") "56")    
  (=>? (main "712131415161718191817161514131216") "117")    
  (=>? (main "712131405161718191817161514031216") "64")    
  (=>? (main "03205301204342100") "1")    
  (=>? (main "0912830485711120342") "18")    
  (=>? (main "1113241120998943327631001") "20")    
  (=>? (main "7688167781598943035023813337019904732") "41")    
  (=>? (main "2032075902729233234129146823006063388") "79")    
  (=>? (main "8323636570846582397534533") "44")    
  (=>? (main "2142555257761672319599209190604843") "41")    
  (=>? (main "06424633785085474133925235") "51")    
  (=>? (main "503144400846933212134") "21")    
  (=>? (main "1204706243676306476295999864") "21")    
  (=>? (main "050527640248767717738306306596466224") "29")    
  (=>? (main "5926294098216193922825") "65")    
  (=>? (main "655589141599534035") "29")    
  (=>? (main "7411279689677738") "34")    
  (=>? (main "268131111165754619136819109839402") "102")
  )


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