adventofcode/src/2017/day03.lisp at master · iamFIREcracker/adventofcode · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
(defpackage :aoc/2017/03 #.cl-user::*aoc-use*)
(in-package :aoc/2017/03)

(defstruct (spiral-gen (:constructor make-spiral-gen%))
  storage
  last
  last-pos
  dir)

(defun make-spiral-gen (&aux (storage (make-hash-table)))
  "Create a spiral sequence generator configured as below:

    ...   ...
    .1.   .C.
    ...   ..^

  `LAST`     = 1
  `LAST-POS` = #C(1 -1)
  `DIR`      = #C(0  1)

  This might look a little weird, but if you look at how SPIRAL-GEN-NEXT work,
  you will realize this is required so that:

  - `2` will be placed on `LAST-POS` + `DIR` (to the right of `1`)
  - `DIR` will be rotated counter-clockwise (facing the center)
  "
  (hash-table-insert storage #C(0 0) 1)
  (make-spiral-gen% :storage storage
                    :last 1
                    :last-pos #C(1 -1)
                    :dir #C(0 1)))

(defun spiral-gen-next (gen)
  "Generate successive values of the spiral sequnce, returning the last position
  used, as well as the last value.

  To recap, a SPIRAL-GEN has the following properties:

  - `STORAGE`: used to keep track of already visited cells
  - `LAST`: the last value used
  - `LAST-POS`: where `LAST` was last placed inside `STORAGE`
  - `DIR`: where to check for an empty cell

  The idea is _simple_:

  - if `LAST-POS` + `DIR` is empty, use that and rotate `DIR` counter-clockwise
  (facing the center of the spiral)
  - if `LAST-POS` + `DIR` is *not* empty, temporarily rotate `DIR` clockwise and
  use `LAST-POS` + `DIR-TEMP`

  Example:

  Suppose we just placed number 2 on the grid:

    ...   ...
    .12   .C<
    ...   ...

  `LAST`     = 2
  `LAST-POS` = #C( 1 0)
  `DIR`      = #C(-1 0)

  `LAST-POS` + `DIR` is already occupied, so we temporarily rotate `DIR`
  clockwise place `3` in `LAST-POS` + `DIR-TEMP`, and move on (leaving `DIR`
  unchanged).

    ..3   ..<
    .12   .C.
    ...   ...

  `LAST`      = 3
  `LAST-POST` = #C( 1 1)
  `DIR`       = #C(-1 0)

  This time, `LAST-POS` + `DIR` is not occupied, so we place `4` there, and then
  rotate `DIR` clockwise.

    .43   .v.
    .12   .C.
    ...   ...

  `LAST`      = 4
  `LAST-POST` = #C(0  1)
  `DIR`       = #C(0 -1)

  And so on, and so forth.
  "
  (with-slots (storage last last-pos dir) gen
    (let* ((next (1+ last))
           (next-pos-busy (gethash (+ last-pos dir) storage))
           (next-pos (+ last-pos (if next-pos-busy (complex-rotate-cw dir) dir)))
           (next-dir (if next-pos-busy dir (complex-rotate-ccw dir))))
      (setf (gethash next-pos storage) next
            (spiral-gen-last gen) next
            (spiral-gen-last-pos gen) next-pos
            (spiral-gen-dir gen) next-dir)
      (values (spiral-gen-last-pos gen)
              (spiral-gen-last gen)))))

(define-solution (2017 3) (data read-integer)
  (values
    (loop
      :with gen = (make-spiral-gen)
      :for (pos n) = (multiple-value-list (spiral-gen-next gen))
      :when (= n data) :return (manhattan-distance #C(0 0) pos))
    (loop
      :with gen = (make-spiral-gen)
      :with grid = (make-hash-table)
      :initially (hash-table-insert grid #C(0 0) 1)
      :for (pos) = (multiple-value-list (spiral-gen-next gen))
      :for value = (reduce #'+ (adjacents pos :include-diagonal T)
                           :key (partial-1 #'gethash _ grid 0))
      :when (> value data) :return value
      :do (hash-table-insert grid pos value))))

(define-test (2017 3) (419 295229))