円周上のCrossing ver.2, saihon2013さんのエレガントな解答を参考に書き直しました。

2013-09-28-crossing-v2.lisp

;;;; Last modified: 2013-11-29 20:18:09 tkych


;;====================================================================
;; 円周上のCrossing ver.2
;;====================================================================
;; - [円周上のCrossing 〜 横へな 2013.9.28 参考問題](http://nabetani.sakura.ne.jp/hena/ord14crosscircle/)
;; - [第14回オフラインリアルタイムどう書くの参考問題](http://qiita.com/Nabetani/items/66806c9dc14a96f2fd42)
;; - [saihon2013さんの解答: crossing.c](http://qiita.com/Nabetani/items/66806c9dc14a96f2fd42)


#| Memo: 計算量の違い

 - crossing ver.1: O(n^4), [2013-09-28-crossing.lisp](https://gist.github.com/tkych/7691226)のプログラム
   ver.2と比べ、実行速度は約１０倍、メモリ使用量が約１０分の１
   Evaluation took:
     0.003 seconds of real time
     0.004000 seconds of total run time (0.004000 user, 0.000000 system)
     133.33% CPU
     7,126,716 processor cycles
     32,560 bytes consed

 - crossing ver.2: O(n^2), このファイルのプログラム
   ver.1と比べ、実行速度が約１０分の１、メモリ使用量は約１０倍
   Evaluation took:
     0.000 seconds of real time
     0.000000 seconds of total run time (0.000000 user, 0.000000 system)
     100.00% CPU
     774,304 processor cycles
     326,016 bytes consed


 現在（2013年）、メモリはチープなので、ver.2の方が良いプログラムだと思う（実行環境にも依るが）。
 また、ver.2のメモリ使用量は工夫すれば減らせるはず（宣言を入れたり、配列をビットで置き換えたり、lisp以外の言語を用いる等々）。

|#


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

(in-package :cl-user)
(defpackage :crossing-points (:use :cl))
(in-package :crossing-points)


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

(defun main (input)
  (let ((num-labels (length input))
        (num-points 0))
    (loop :for start :from 0 :below num-labels
          :for label := (char input start)
          :for num-lines := 0
          :with tmp-line-count := (make-array num-labels
                                              :element-type t :initial-element 0)
          :for line-count := (copy-seq tmp-line-count)
          :do (loop :for end :from (1+ start) :below num-labels
                    :do (when (char= label (char input end))
                          (incf (svref tmp-line-count end))
                          (incf num-points num-lines))
                        (incf num-lines (svref line-count end))))
    (write-to-string num-points)))


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

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

(time
 (progn
   (=>? (main "aabbca1bcb") "14")    
   (=>? (main "111ZZZ") "0")    
   (=>? (main "v") "0")    
   (=>? (main "ww") "0")    
   (=>? (main "xxx") "0")    
   (=>? (main "yyyy") "1")    
   (=>? (main "zzzzz") "5")    
   (=>? (main "abcdef") "0")    
   (=>? (main "abcaef") "0")    
   (=>? (main "abbaee") "0")    
   (=>? (main "abcacb") "2")    
   (=>? (main "abcabc") "3")    
   (=>? (main "abcdabcd") "6")    
   (=>? (main "abcadeabcade") "23")    
   (=>? (main "abcdeedcba") "0")    
   (=>? (main "abcdeaedcba") "8")    
   (=>? (main "abcdeaedcbad") "16")    
   (=>? (main "QQQQXXXX") "2")    
   (=>? (main "QwQQmQXmXXwX") "14")    
   (=>? (main "111222333") "0")    
   (=>? (main "aaAAaA") "4")    
   (=>? (main "121232313") "12")    
   (=>? (main "1ab1b") "1")    
   (=>? (main "abcdefbadcfe") "12")    
   (=>? (main "abxcdefbadcfex") "14")    
   (=>? (main "dtnwtkt") "0")    
   (=>? (main "mvubvpp") "0")    
   (=>? (main "moggscd") "0")    
   (=>? (main "kzkjzpkw") "2")    
   (=>? (main "fbifybre") "1")    
   (=>? (main "rrrfjryki") "1")    
   (=>? (main "wrbbdwsdwtx") "2")    
   (=>? (main "vvucugvxbvgx") "9")    
   (=>? (main "ojkjzyasjwbfjj") "5")    
   (=>? (main "ggffyuxnkyypifff") "5")    
   (=>? (main "vcgtcqlwrepwvkkogl") "4")    
   (=>? (main "xeqtmmgppwcjpcisogxbs") "4")    
   (=>? (main "lukltpeucrqfvcupnpxwmoj") "6")    
   (=>? (main "zpzswlkkoqwwndwpfdpkhtzgtn") "31")    
   (=>? (main "bkfeflagfvluelududqjcvfyvytfw") "45")    
   (=>? (main "rvqbhfmcjjqlpqzulzerxgyowiwrfkmhw") "26")    
   (=>? (main "qyxvpdtoeexbqsethwjwmqszcxxjnsdoeaet") "144")    
   (=>? (main "rjmsgmswhcolmpbhmpncziymydyalrcnevsrespj") "133")    
   (=>? (main "oxetnyjzjbysnwktfwzndlejfndsqeetsnjvsicyjehd") "395")    
   (=>? (main "wzvddnddzogywcqxbyvagbzmsmtcmrrlbnebmvhaemjouaqim") "219")    
   (=>? (main "karhphxcxqgsyorhusbumbqzocuzvnwzwcpxgsksrviihxrgsrhji") "461")    
   (=>? (main "oxgbononhqdxzmkysgijwvxljpaazmgkurkpffeuwywwuyxhyfkicgyzyc") "441")    
   (=>? (main "sdgsrddwsrwqthhdvhrjhgtxwgurgyiygtktgtughtogzaqmcafkljgpniddsvb") "1077")    
   (=>? (main "qemhecchkgzhxmdcsltwhpoyhkapckkkzosmklcvzkiiucrvzzznmhjfcdumuflavxik") "1711")    
   (=>? (main "ffqmsirwpxrzfkbvmmfeptkbhnrvfcywthkwkbycmayhhkgvuyecbwwofwthlmzruphrcujwhr") "2440")
   ))


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