L-intersection, http://qiita.com/Nabetani/items/4c60f10b73812e86441c

2013-01-11-L-intersecton.lisp

;;;; Last modified: 2013-12-20 20:13:17 tkych


;;====================================================================
;; L-intersection
;;====================================================================
;; - [L-intersection 〜 横へな 2013.1.11の参考問題](http://nabetani.sakura.ne.jp/hena/ord6lintersection/)
;; - [オフラインリアルタイムどう書く第6回の参考問題](http://qiita.com/Nabetani/items/4c60f10b73812e86441c)


#| 解説

 例：(main "23-94-28,89-06-51") => "11"


1. ビット(整数)に変換 (parse)

   "23-94-28" -> #b0000000100
                   0000000100
                   0000000100
                   0000000100
                   1111111100
                   1111111100
                   0000000000
                   0000000000
                   0000000000

   "89-06-51" -> #b0111111111
                   0111111111
                   0111111111
                   0111111111
                   0111100000
                   0111100000
                   0111100000
                   0111100000
                   0111100000
                   0000000000

   注：変換後のビットは上下左右が対称のものとなるが、すべてのLが同様に変換されるので、最終結果には影響しない。

2. ビットアンド (logand)

   #b000000000000000010000000001000000000100000000010011111111001111111100000000000000000000000000000000
&) #b111111111011111111101111111110111111111011110000001111000000111100000011110000001111000000000000000
--------------------------------------------------------------------------------------------------------
   #b000000000000000010000000001000000000100000000000001111000000111100000000000000000000000000000000000

3. 1の数を数える (logcount)

   #b000000000000000010000000001000000000100000000000001111000000111100000000000000000000000000000000000
   -> 11

|#


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

(in-package :cl-user)
(defpackage :L-intersection (:use :cl))
(in-package :L-intersection)


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

(defun coord->pos (x1 x2) (+ x1 (* 10 x2)))

(defun ones (s1 s2 e1 e2 bits)
  (loop :with size := (- e1 s1 -1)
        :with end := (coord->pos e1 e2)
        :for start :from (coord->pos s1 s2) :by 10
        :until (< end start)
        :do (setf bits (dpb #xfff (byte size start) bits)))
  bits)

(defun to-bits (a1 a2 b1 b2 c1 c2)
  (cond
    ((< c1 b1)
     (cond ((< b2 c2) ;「
            (ones a1 a2 c1 c2 (ones a1 a2 b1 b2 0)))
           ((< c2 b2) ; 7
            (ones b1 c2 a1 b2 (ones c1 a2 a1 c2 0)))
           (t (error "invalid input"))))
    ((< b1 c1)
     (cond ((< c2 b2) ; 」
            (ones b1 b2 a1 a2 (ones c1 c2 a1 b2 0)))
           ((< b2 c2) ; L
            (ones a1 c2 c1 a2 (ones a1 b2 b1 c2 0)))
           (t (error "invalid input"))))
    (t (error "invalid input"))))

(defun parse (input)
  (destructuring-bind
      (x1 x2 y1 y2 z1 z2 u1 u2 v1 v2 w1 w2)
      (map 'list #'digit-char-p (remove #\- (remove #\, input)))
    (values (to-bits x1 x2 y1 y2 z1 z2)
            (to-bits u1 u2 v1 v2 w1 w2))))

(defun main (input)
  (multiple-value-bind (bits1 bits2) (parse input)
    (write-to-string (logcount (logand bits1 bits2)))))


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

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

(progn
  (=>? (main "23-94-28,89-06-51") "11")
  (=>? (main "11-84-58,02-73-69") "40")
  (=>? (main "18-41-86,77-04-32") "26")
  (=>? (main "81-88-23,64-58-14") "0")
  (=>? (main "31-29-07,41-87-69") "0")
  (=>? (main "83-13-40,18-10-94") "1")
  (=>? (main "77-80-92,21-72-38") "2")
  (=>? (main "57-70-91,55-19-08") "3")
  (=>? (main "18-22-75,66-80-91") "4")
  (=>? (main "51-93-78,54-49-06") "5")
  (=>? (main "58-70-96,17-43-76") "6")
  (=>? (main "58-07-12,58-82-93") "7")
  (=>? (main "41-29-07,35-95-88") "8")
  (=>? (main "88-26-60,42-29-07") "9")
  (=>? (main "18-40-85,34-40-91") "10")
  (=>? (main "36-60-96,53-96-89") "11")
  (=>? (main "51-39-02,44-98-69") "12")
  (=>? (main "48-06-20,76-04-42") "13")
  (=>? (main "85-29-18,26-50-93") "14")
  (=>? (main "27-50-91,43-29-07") "15")
  (=>? (main "57-06-20,48-60-91") "16")
  (=>? (main "52-98-89,21-76-67") "17")
  (=>? (main "67-12-40,45-80-92") "18")
  (=>? (main "47-03-10,26-30-82") "19")
  (=>? (main "74-28-06,21-86-37") "20")
  (=>? (main "65-01-20,73-39-05") "21")
  (=>? (main "17-72-86,36-50-94") "22")
  (=>? (main "51-29-07,77-15-41") "23")
  (=>? (main "33-98-39,82-16-02") "24")
  (=>? (main "75-05-10,37-81-96") "25")
  (=>? (main "72-58-06,48-80-96") "26")
  (=>? (main "81-67-16,21-91-59") "27")
  (=>? (main "13-96-57,24-96-79") "28")
  (=>? (main "57-04-32,51-18-06") "29")
  (=>? (main "88-03-52,28-41-86") "30")
  (=>? (main "78-04-61,13-86-49") "31")
  (=>? (main "58-12-20,27-50-85") "32")
  (=>? (main "61-19-05,71-68-15") "33")
  (=>? (main "63-29-16,18-31-83") "34")
  (=>? (main "16-50-91,32-98-79") "35")
  (=>? (main "82-17-03,38-40-81") "36")
  (=>? (main "72-48-04,11-98-39") "37")
  (=>? (main "77-05-10,28-50-62") "38")
  (=>? (main "38-50-91,11-86-57") "39")
  (=>? (main "87-05-10,13-97-69") "40")
  (=>? (main "11-86-49,22-98-89") "44")
  (=>? (main "11-97-69,12-86-67") "46")
  (=>? (main "11-95-69,71-49-05") "47")
  (=>? (main "28-31-92,13-98-79") "48")
  )

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