(ql:quickload '(fiveam uiop arrows))

(defun elf-coordinates (filename)
  (let ((coord (make-hash-table :test #'equal)))
    (with-open-file (input filename)
      (loop for line = (read-line input nil nil)
            and y from 0
            while line
            do (loop for point across line
                     and x from 0
                     when (eq point #\#)
                       do (setf (gethash (cons x y) coord) t))))
    coord))

(defun bounding-box (elf-coordinates)
  (loop for k being the hash-key of elf-coordinates
        minimize (car k) into minx
        minimize (cdr k) into miny
        maximize (car k) into maxx
        maximize (cdr k) into maxy
        finally (return (list minx miny maxx maxy))))

(defparameter *moves*
  (vector (vector (cons -1 -1) (cons  0 -1) (cons  1 -1))   ;; North
          (vector (cons -1  1) (cons  0  1) (cons  1  1))   ;; South
          (vector (cons -1 -1) (cons -1  0) (cons -1  1))   ;; West
          (vector (cons  1 -1) (cons  1  0) (cons  1  1)))) ;; East

(defun draw (elves)
  (with-output-to-string (out)
    (destructuring-bind (minx miny maxx maxy) (bounding-box elves)
      (loop for y from miny to maxy
            do (princ #\Newline out)
               (loop for x from minx to maxx
                     do (princ (if (gethash (cons x y) elves)
                                   #\# #\.) out))))))

(defun pair-add (a b)
  (cons (+ (car a) (car b))
        (+ (cdr a) (cdr b))))

(defun test-move (dir elf others)
  (loop for next-dir across dir
        never (gethash (pair-add elf next-dir) others)))

(defun all-moves (step elves)
  (let ((next-places (make-hash-table :test #'equal)))
    (loop for elf being the hash-key of elves
          do
             (let ((options (loop for dirs below 4
                                  collect (arrows:-> (aref *moves* (mod (+ dirs step) 4))
                                                     (test-move elf elves)))))
               (unless (or (notany #'null options) ;; all free don't move
                           (every #'null options)) ;; all blocked don't move
                 (let ((prop
                         (arrows:->
                          (aref *moves* (mod (+ (position t options) step) 4))
                          (aref 1)
                          (pair-add elf))))
                   (setf (gethash prop next-places)
                         (cons elf (gethash prop next-places)))))))
    next-places))

(defun move-elves! (next-places elves)
  (loop for target being the hash-key of next-places using (hash-value source)
        when (null (cdr source)) ;; no conflicts on target
          do (remhash (car source) elves)
             (setf (gethash target elves) t)))

(defun empty-ground (elves)
  (destructuring-bind (minx miny maxx maxy) (bounding-box elves)
    (- (* (1+ (- maxx minx))
          (1+ (- maxy miny)))
       (hash-table-count elves))))

(defun solver (elves limit)
  (loop for step from 0 below limit
        for moves = (all-moves step elves)
        while (plusp (hash-table-count moves))
        do (move-elves! moves elves)
        finally (return step)))

(defun part1 (filename)
  (let ((elves (elf-coordinates filename)))
    (solver elves 10)
    (empty-ground elves)))

(fiveam:test solutions
  (fiveam:is (= 110  (part1 "eg-in")))
  (fiveam:is (= 4052 (part1 "input")))
  (fiveam:is (= 20 (1+ (solver (elf-coordinates "eg-in") 1000))))
  (fiveam:is (= 978 (1+ (solver (elf-coordinates "input") 1000)))))
eight: 125%; }
td.linenos .normal { color: #37474F; background-color: #263238; padding-left: 5px; padding-right: 5px; }
span.linenos { color: #37474F; background-color: #263238; padding-left: 5px; padding-right: 5px; }
td.linenos .special { color: #607A86; background-color: #263238; padding-left: 5px; padding-right: 5px; }
span.linenos.special { color: #607A86; background-color: #263238; padding-left: 5px; padding-right: 5px; }
.highlight .hll { background-color: #2C3B41 }
.highlight { background: #263238; color: #EEFFFF }
.highlight .c { color: #546E7A; font-style: italic } /* Comment */
.highlight .err { color: #FF5370 } /* Error */
.highlight .esc { color: #89DDFF } /* Escape */
.highlight .g { color: #EEFFFF } /* Generic */
.highlight .k { color: #BB80B3 } /* Keyword */
.highlight .l { color: #C3E88D } /* Literal */
.highlight .n { color: #EEFFFF } /* Name */
.highlight .o { color: #89DDFF } /* Operator */
.highlight .p { color: #89DDFF } /* Punctuation */
.highlight .ch { color: #546E7A; font-style: italic } /* Comment.Hashbang */
.highlight .cm { color: #546E7A; font-style: italic } /* Comment.Multiline */
.highlight .cp { color: #546E7A; font-style: italic } /* Comment.Preproc */
.highlight .cpf { color: #546E7A; font-style: italic } /* Comment.PreprocFile */
.highlight .c1 { color: #546E7A; font-style: italic } /* Comment.Single */
.highlight .cs { color: #546E7A; font-style: italic } /* Comment.Special */
.highlight .gd { color: #FF5370 } /* Generic.Deleted */
.highlight .ge { color: #89DDFF } /* Generic.Emph */
.highlight .ges { color: #FFCB6B } /* Generic.EmphStrong */
.highlight .gr { color: #FF5370 } /* Generic.Error */
.highlight .gh { color: #C3E88D } /* Generic.Heading */
.highlight .gi { color: #C3E88D } /* Generic.Inserted */
.highlight .go { color: #546E7A } /* Generic.Output */
.highlight .gp { color: #FFCB6B } /* Generic.Prompt */
.highlight .gs { color: #FF5370 } /* Generic.Strong */
.highlight .gu { color: #89DDFF } /* Generic.Subheading */
.highlight .gt { color: #FF5370 } /* Generic.Traceback */
.highlight .kc { color: #89DDFF } /* Keyword.Constant */
.highlight .kd { color: #BB80B3 } /* Keyword.Declaration */
.highlight .kn { color: #89DDFF; font-style: italic } /* Keyword.Namespace */
.highlight .kp { color: #89DDFF } /* Keyword.Pseudo */
.highlight .kr { color: #BB80B3 } /* Keyword.Reserved */
.highlight .kt { color: #BB80B3 } /* Keyword.Type */
.highlight .ld { color: #C3E88D } /* Literal.Date */
.highlight .m { color: #F78C6C } /* Literal.Number */
.highlight .s { color: #C3E88D } /* Literal.String */
.highlight .na { color: #BB80B3 } /* Name.Attribute */
.highlight .nb { color: #82AAFF } /* Name.Builtin */
.highlight .nc { color: #FFCB6B } /* Name.Class */
.highlight .no { color: #EEFFFF } /* Name.Constant */
.highlight .nd { color: #82AAFF } /* Name.Decorator */
.highlight .ni { color: #89DDFF } /* Name.Entity */
.highlight .ne { color: #FFCB6B } /* Name.Exception */
.highlight .nf { color: #82AAFF } /* Name.Function */
.highlight .nl { color: #82AAFF } /* Name.Label */
.highlight .nn { color: #FFCB6B } /* Name.Namespace */
.highlight .nx { color: #EEFFFF } /* Name.Other */
.highlight .py { color: #FFCB6B } /* Name.Property */
.highlight .nt { color: #FF5370 } /* Name.Tag */
.highlight .nv { color: #89DDFF } /* Name.Variable */
.highlight .ow { color: #89DDFF; font-style: italic } /* Operator.Word */
.highlight .pm { color: #89DDFF } /* Punctuation.Marker */
.highlight .w { color: #EEFFFF } /* Text.Whitespace */
.highlight .mb { color: #F78C6C } /* Literal.Number.Bin */
.highlight .mf { color: #F78C6C } /* Literal.Number.Float */
.highlight .mh { color: #F78C6C } /* Literal.Number.Hex */
.highlight .mi { color: #F78C6C } /* Literal.Number.Integer */
.highlight .mo { color: #F78C6C } /* Literal.Number.Oct */
.highlight .sa { color: #BB80B3 } /* Literal.String.Affix */
.highlight .sb { color: #C3E88D } /* Literal.String.Backtick */
.highlight .sc { color: #C3E88D } /* Literal.String.Char */
.highlight .dl { color: #EEFFFF } /* Literal.String.Delimiter */
.highlight .sd { color: #546E7A; font-style: italic } /* Literal.String.Doc */
.highlight .s2 { color: #C3E88D } /* Literal.String.Double */
.highlight .se { color: #EEFFFF } /* Literal.String.Escape */
.highlight .sh { color: #C3E88D } /* Literal.String.Heredoc */
.highlight .si { color: #89DDFF } /* Literal.String.Interpol */
.highlight .sx { color: #C3E88D } /* Literal.String.Other */
.highlight .sr { color: #89DDFF } /* Literal.String.Regex */
.highlight .s1 { color: #C3E88D } /* Literal.String.Single */
.highlight .ss { color: #89DDFF } /* Literal.String.Symbol */
.highlight .bp { color: #89DDFF } /* Name.Builtin.Pseudo */
.highlight .fm { color: #82AAFF } /* Name.Function.Magic */
.highlight .vc { color: #89DDFF } /* Name.Variable.Class */
.highlight .vg { color: #89DDFF } /* Name.Variable.Global */
.highlight .vi { color: #89DDFF } /* Name.Variable.Instance */
.highlight .vm { color: #82AAFF } /* Name.Variable.Magic */
.highlight .il { color: #F78C6C } /* Literal.Number.Integer.Long */</style><div class="highlight"><pre><span></span>O....#....
O.OO#....#
.....##...
OO.#O....O
.O.....O#.
O.#..O.#.#
..O..#O..O
.......O..
#....###..
#OO..#....
</pre></div>