;gnu clisp 2.49

(defvar *input-text*
    (list ".###..#......###..#...#"
          "#.#..#.##..###..#...#.#"
          "#.#.#.##.#..##.#.###.##"
          ".#..#...####.#.##..##.."
          "#.###.#.####.##.#######"
          "..#######..##..##.#.###"
          ".##.#...##.##.####..###"
          "....####.####.#########"
          "#.########.#...##.####."
          ".#.#..#.#.#.#.##.###.##"
          "#..#.#..##...#..#.####."
          ".###.#.#...###....###.."
          "###..#.###..###.#.###.#"
          "...###.##.#.##.#...#..#"
          "###.##.#..##...#..#.#.#"
          "###..###..##.##..##.###"
          "###.###.####....######."
          ".###.#####.#.#.#.#####."
          "##.#.###.###.##.##..##."
          "##.#..#..#..#.####.#.#."
          ".#.#.#.##.##########..#"
          "#####.##......#.#.####."))

(defvar *test-1-text*
    (list ".#..#"
          "....."
          "#####"
          "....#"
          "...##"))

(defun parse-input (lines)
    (let ((points nil))
        (loop for s in lines
              for j from 0
              do (loop for c across s
                       for i from 0
                       when (char= (code-char 35) c)
                       do (push (complex i j) points)))
         points))

(defvar *input* (parse-input *input-text*))

(defun slope (p1 p2)
    (let ((x (- (realpart p1) (realpart p2)))
          (y (- (imagpart p1) (imagpart p2))))
         (cond
             ((zerop y) 1)
             ((zerop x) #C(0 1))
             ((and (< x 0) (< y 0) (complex (/ (- x) (gcd x y)) (/ (- y) (gcd x y)))))
             (t (complex (/ x (gcd x y)) (/ y (gcd x y)))))))

(defun in-line (p1 p2 p3)
    (integerp (/ (- p3 p1) (slope p1 p2))))

(defun left-of (p1 p2 slope)
"Returns T if P1 is left of P2, or above in the case of a slope of 0."
    (< 0 (/ (- p1 p2) slope)))

;; (let* ((points (list #C(1 0) #C(4 0) #C(0 2) #C(1 2) #C(2 2) #C(3 2) #C(4 2) #C(4 3) #C(3 4) #C(4 4)))
;;       (visibility (make-hash-table)))
(defun best-visibility (points)
    (let ((visibility (make-hash-table)))
         (loop for p1 in points
               do (let ((visited (make-hash-table)))
                       (loop for p2 in points
                             unless (or (gethash p2 visited) (= p1 p2))
                             do (let ((s (slope p1 p2))
                                      (ps (remove-if-not (lambda (p3) (or (= p1 p3) (= p2 p3) (in-line p1 p2 p3))) points)))
                                     (loop for p in (cons p2 ps)
                                           do (setf (gethash p visited) t))
                                     (multiple-value-bind (left right)
                                         (reduce (lambda (partition p3)
                                                         (list (or (first partition) (left-of p3 p1 s))
                                                               (or (second partition) (not (left-of p3 p1 s)))))
                                                 (cons p2 ps)
                                                 :initial-value (list nil nil))
                                         (setf (gethash p1 visibility) (+ (gethash p1 visibility 0)
                                                                          (if left 1 0)
                                                                          (if right 1 0))))))))
         (maphash (lambda (k v)
                          (format t "~a -> ~a~%" k v))
                  visibility)
         (loop for v being the hash-values of visibility
               maximizing v)))

(print (best-visibility *input*))
(print *input*)