;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*)