等差数列, http://qiita.com/Nabetani/items/c206fbc645c255cb7de6

2013-06-01-sequence-of-numbers.lisp

;;;; Last modified: 2013-12-16 20:02:30 tkych


;;====================================================================
;; 等差数列
;;====================================================================
;; - [等差数列 〜 横へな 2013.6.1 参考問題](http://nabetani.sakura.ne.jp/hena/ord11arithseq/)
;; - [第11回オフラインリアルタイムどう書くの参考問題](http://qiita.com/Nabetani/items/c206fbc645c255cb7de6)


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

(in-package :cl-user)
(defpackage :sequence-of-numbers (:use :cl))
(in-package :sequence-of-numbers)


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

(defun character->number (char)
  (or (digit-char-p char)
      (- (char-code char) #.(- (char-code #\a) 10))))

(defun number->character (number)
  (or (digit-char number)
      (code-char (+ number #.(- (char-code #\a) 10)))))

;; "012abku" -> (0 1 2 10 11 20 30)
(defun string->numbers (string)
  (map 'list #'character->number string))

;; (0 1 2 10 11 20 30) -> "012abku"
(defun numbers->string (numbers)
  (map 'string #'number->character numbers))

;; (length-sequence 1 3 '(2 4 6 7 8 9)) => 3   ; (1 4 7)
(defun length-sequence (start diff numbers)
  "`numbers'から得られる等差数列（初項`start'、 公差`diff'）の長さを返す。
注：`numbers'に初項は含まれていない。"
  (loop :for i :from 1
        :while (find (+ start (* diff i)) numbers)
        :finally (return (1+ i))))

(defun main (input)
  (labels ((rec (numbers longest)
             (if (null numbers)
                 longest
                 (destructuring-bind (x0 . xs0) numbers
                   (rec xs0
                        (max longest
                             (loop :for (x1 . xs1) :on xs0
                                   :for diff := (- x1 x0)
                                   :maximize (length-sequence x1 diff xs1))))))))
    (write-to-string
     (rec (string->numbers input) 1))))


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

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

(progn
  (=>? (main "12345abcz") "5")
  (=>? (main "012abku") "4")
  (=>? (main "01245689cdeghik") "6")
  (=>? (main "0") "1")
  (=>? (main "m") "1")
  (=>? (main "01") "2")
  (=>? (main "az") "2")
  (=>? (main "0az") "2")
  (=>? (main "0ak") "3")
  (=>? (main "05ak") "3")
  (=>? (main "01349acdrsuv") "2")
  (=>? (main "01245789efgipqstux") "3")
  (=>? (main "0123456789abcdefghijklmnopqrstuvwxyz") "36")
  (=>? (main "02468acegikmoqsuwy") "18")
  (=>? (main "0369cfilorux") "12")
  (=>? (main "048cgkosw") "9")
  (=>? (main "05afkpuz") "8")
  (=>? (main "0123456789abcdefghjklmnopqrstuvwxyz") "18")
  (=>? (main "0123456789bcdefghijklmopqrstuvwxyz") "12")
  (=>? (main "0156abfgklpquv") "7")
  (=>? (main "0167cdijopuv") "6")
  (=>? (main "0178eflmst") "5")
  (=>? (main "0189ghopwx") "5")
  (=>? (main "019aijrs") "4")
  (=>? (main "012567abcfghklmpqruvw") "7")
  (=>? (main "012678cdeijkopquvw") "6")
  (=>? (main "012789efglmnstu") "5")
  (=>? (main "01289aghiopqwxy") "5")
  (=>? (main "0129abijkrst") "4")
  (=>? (main "01235678abcdfghiklmnpqrsuvwx") "7")
  (=>? (main "01236789cdefijklopqruvwx") "12")
  (=>? (main "0123789aefghlmnostuv") "5")
  (=>? (main "012389abghijopqrwxyz") "5")
  (=>? (main "01239abcijklrstu") "4")
  (=>? (main "368acdknouvz") "4")
  (=>? (main "369chikmnopqruwx") "6")
  (=>? (main "05689cdefghijklmnopqrstvwy") "18")
  (=>? (main "2489abdeiklrsuvwz") "4")
  (=>? (main "678bhijklnpqrsuvwxyz") "6")
  (=>? (main "1246cfjkopquxz") "5")
  (=>? (main "123459abcefhilmotuvx") "6")
  (=>? (main "02578acdefikmopqsuvwxz") "8")
  (=>? (main "135abdefghijlopstuwz") "7")
  (=>? (main "0126789fgjnotuvxy") "5")
  (=>? (main "2345678defjkmnoqrtvwxy") "7")
  (=>? (main "02568bdemnostw") "5")
  (=>? (main "145689bdfhilnqrstvwxz") "6")
  (=>? (main "4aghjrtuvwxyz") "7")
  (=>? (main "158achklmqstwy") "3")
  (=>? (main "012346abceghjknortv") "5")
  )


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