advent-of-code/2018-12-11.lisp -rw-r--r-- 2.8 KiB View raw
                                                                                
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
(defpackage "AOC/11" (:use "CL"))
(in-package "AOC/11")

(defun power-level (x y serial-number)
  (let ((rack-id (+ x 10)))
    (- (floor (mod (* (+ (* rack-id y) serial-number) rack-id) 1000) 100) 5)))

(defun fill-grid (size serial-number)
  (let ((grid (make-array (list size size))))
    (loop for x from 0 below size
          do (loop for y from 0 below size
                   for rack-id = (+ x 11)
                   do (setf (aref grid x y)
                            (power-level (1+ x) (1+ y) serial-number))))
    grid))

(defun print-grid (grid)
  (loop for y from 0 below (array-dimension grid 1)
        do (format t "~&~{~a ~}~%" (loop for x from 0 below (array-dimension grid 0) collect (aref grid x y)))))

(defun sum-subgrid (grid x y)
  (loop for y from (1- y) below (+ y 2)
        sum (loop for x from (1- x) below (+ x 2) sum (aref grid x y))))

(defun find-best (grid)
  (loop for y from 1 to (- (array-dimension grid 1) 2)
        with max = 0 and max-x and max-y
        do (loop for x from 1 to (- (array-dimension grid 0) 2)
                 ;; this could be more efficient by only adding the new cells, but … it’s a puzzle
                 for power = (sum-subgrid grid x y)
                 when (> power max)
                   do (setf max power
                            max-x x
                            max-y y))
        finally (return (list max-x max-y))))

(defun solution-1 ()
  (destructuring-bind (x y)
      (find-best (fill-grid 300 9005))
    (format t "~a,~a" x y)))

(defun sum-dynamic-subgrid (grid x y size)
  (loop for y from (1- y) below (+ y (1- size))
        sum (loop for x from (1- x) below (+ x (1- size)) sum (aref grid x y))))

(defun find-dynamic-best (grid)
  (loop for size from 1 to 300
        with max = 0 and max-x and max-y and max-size
        for start = (get-universal-time)
        do (loop for y from 1 to (- (array-dimension grid 1) (1- size))
                 do (loop for x from 1 to (- (array-dimension grid 0) (1- size))
                          ;; this could be more efficient by only adding the new cells, but … it’s a puzzle
                          for power = (sum-dynamic-subgrid grid x y size)
                          when (> power max)
                            do (setf max power
                                     max-x x
                                     max-y y
                                     max-size size)))
           ;; I cheated and just observed that the max stopped
           ;; increasing; it takes nearly 18 minutes to run on my computer
        do (format t "~&~a: ~a ~a ~a (~a secs)" size max-x max-y max-size (- (get-universal-time) start))
        finally (return (list max-x max-y max-size))))

(defun solution-2 ()
  (destructuring-bind (x y size)
      (find-dynamic-best (fill-grid 300 9005))
    (format t "~a,~a,~a" x y size)))