If you have a lisp installation, emacs, org-mode, and org-babel support for lisp installed you can run this by:
- Starting slime (
M-x slime) - Typing
C-c C-cin the block initialize. - In the repl type
(in-package :aoc-2018-11) - Typing
C-c C-cin the block answers
(unless (find-package :cl-ppcre)
(ql:quickload "cl-ppcre"))
(unless (find-package :iterate)
(ql:quickload "iterate"))
(unless (find-package :parseq)
(ql:quickload "parseq"))
(unless (find-package :fiveam)
(ql:quickload "fiveam"))<<packages>>
(defpackage :aoc-2018-11
(:use :common-lisp
:iterate
:parseq
:fiveam)
(:export :problem-a
:problem-b))
(in-package :aoc-2018-11)(defparameter *input* 1133)There’s a 300x300 grid of fuel cells. Can select any 3x3 region. Want the region with the largest total power. The region is identified by its top left coordinate (NB: top left of grid is (1,1)).
The power level in a given fuel cell can be found through the following process:
- Find the fuel cell’s rack ID, which is its X coordinate plus 10.
- Begin with a power level of the rack ID times the Y coordinate.
- Increase the power level by the value of the grid serial number (your puzzle input).
- Set the power level to itself multiplied by the rack ID.
- Keep only the hundreds digit of the power level (so 12345 becomes 3; numbers with no hundreds digit become 0).
- Subtract 5 from the power level.
(defun power-level (x y grid-id)
(let* ((rack-id (+ x 10))
(power-level (+ (* rack-id y) grid-id)))
(setf power-level (* power-level rack-id))
(- (mod (floor (/ power-level 100)) 10) 5)))Alright, so now we need the coordinates for the maximal region.
(defun sum-square (x y grid &optional (size 3))
(iter outer
(for i from x to (+ x (1- size)))
(iter (for j from y to (+ y (1- size)))
(in outer
(sum (aref grid i j))))))
(defun max-square (grid &optional (size 3))
(iter outer
(for x from 1 to (- 300 (1- size))) ;; stop short so we don't
;; go out of bounds
(iter (for y from 1 to (- 300 (1- size)))
(let ((power (sum-square x y grid size)))
(in outer
(finding (list x y size power) maximizing power))))))(defun make-power-grid (grid-id)
(let ((grid (make-array '(301 301))))
(iter (for x from 1 to 300)
(iter (for y from 1 to 300)
(setf (aref grid x y) (power-level x y grid-id))))
grid))(defun problem-a () (format t "Problem 11 A: ~a~%" (max-square (make-power-grid *input*))))Same basic code, but we can now adjust the size of the grid. This time we want to return all 3 parameters: x,y,size.
I’ve extended the code above to take an optional size parameter, defaulting to 3 so I didn’t have to adjust my main test functions below.
(defun best-size (grid)
(iter (for size from 1 to 20)
(let ((best (max-square grid size)))
(finding best maximizing (fourth best)))))The above is a cheat. It was taking too long so I printed out each potential best as they were found. The best was negative by size 25, at which point it wasn’t going to improve again. I saw that 14 was the max and just used it above to get the printout below. I should revisit this and figure out how to make it run faster. I believe that I can reduce the total grid size by creating partial sums along the way (so that at size 300 it’s just adding the 300th rows and columns to location (1,1)). But I’m not sure how to code that up right now.
(defun problem-b () (format t "Problem 11 B: ~a~%" (best-size-fast (summed-area-table (make-power-grid *input*)))))<<power-level>>
<<max-square>>
<<best-size>>
<<make-power-grid>>
<<summed-area-table>>
<<area-sum>>
<<max-square-fast>>
<<best-size-fast>><<initialize>>
<<functions>>
<<input>>
<<problem-a>>
<<problem-b>>
(problem-a)
(problem-b)Problem 11 A: (235 14 3 31) Problem 11 B: (237 227 14 108)
For example, to find the power level of the fuel cell at 3,5 in a grid with serial number 8:
- The rack ID is 3 + 10 = 13.
- The power level starts at 13 * 5 = 65.
- Adding the serial number produces 65 + 8 = 73.
- Multiplying by the rack ID produces 73 * 13 = 949.
- The hundreds digit of 949 is 9.
- Subtracting 5 produces 9 - 5 = 4.
- So, the power level of this fuel cell is 4.
Here are some more example power levels:
- Fuel cell at 122,79, grid serial number 57: power level -5.
- Fuel cell at 217,196, grid serial number 39: power level 0.
- Fuel cell at 101,153, grid serial number 71: power level 4.
(def-suite aoc.2018.11)
(in-suite aoc.2018.11)
(test power-level-test
(is (= 4 (power-level 3 5 8)))
(is (= -5 (power-level 122 79 57)))
(is (= 0 (power-level 217 196 39)))
(is (= 4 (power-level 101 153 71))))
(run! 'aoc.2018.11)Running test suite AOC.2018.11
Running test POWER-LEVEL-TEST ....
Did 4 checks.
Pass: 4 (100%)
Skip: 0 ( 0%)
Fail: 0 ( 0%)
OK, so there’s an algorithm out there called Summed-area table which is pretty much exactly what I was trying to think of last night.
(defun summed-area-table (table)
(let ((result (make-array (array-dimensions table) :initial-element 0)))
(setf (aref result 0 0) (aref table 0 0))
(iter (for x from 1 below (first (array-dimensions result)))
(setf (aref result x 0)
(+ (aref result x 0) (aref table (1- x) 0))))
(iter (for y from 1 below (second (array-dimensions result)))
(setf (aref result 0 y)
(+ (aref result 0 y) (aref table 0 (1- y)))))
(iter (for x from 1 below (first (array-dimensions result)))
(iter (for y from 1 below (second (array-dimensions result)))
(setf (aref result x y)
(+ (aref result (1- x) y)
(aref result x (1- y))
(- (aref result (1- x) (1- y)))
(aref table x y)))))
result))
(defun print-array (array)
(iter (for x from 0 below (first (array-dimensions array)))
(iter (for y from 0 below (second (array-dimensions array)))
(format t "~A " (aref array x y)))
(format t "~%")))The next thing we need is the sum of a region. The table generated above gives us a relatively fast way of doing that.
Pass in the same kind of coordinates that we want for the answer (specify the upper left corner of the range). This function will convert properly but does no bounds checking. Give it bad coordinates and size and it’ll bring you to the debugger.
(defun area-sum (table x y size)
(let* ((lr (complex (+ x size -1) (+ y size -1)))
(ur (- lr (complex 0 size)))
(ll (- lr size))
(ul (- lr (complex size size))))
(- (+ (aref table (realpart lr) (imagpart lr))
(aref table (realpart ul) (imagpart ul)))
(+ (aref table (realpart ur) (imagpart ur))
(aref table (realpart ll) (imagpart ll))))))NB: From now on I’m following phil_g’s lead and using complex numbers to represent all 2D coordinates. It’s just so much more convenient.
(defun max-square-fast (grid &optional (size 3))
"Unlike the original, this one requires a summed-area table version of the battery grid."
(iter outer
(for x from 1 to (- 300 (1- size))) ;; stop short so we don't
;; go out of bounds
(iter (for y from 1 to (- 300 (1- size)))
(let ((power (area-sum grid x y size)))
(in outer
(finding (list x y size power) maximizing power))))))(let ((grid (summed-area-table (make-power-grid 1133))))
(max-square-fast grid 3))| 235 | 14 | 3 | 31 |
(let ((grid (summed-area-table (make-power-grid 1133))))
(max-square-fast grid 14))| 237 | 227 | 14 | 108 |
Now that we know that the max-square-fast works, lets try making the actual search function.
(defun best-size-fast (grid)
(iter (for size from 1 to 300)
(let ((best (max-square-fast grid size)))
(finding best maximizing (fourth best)))))I’ve updated Problem B above to use this function so it can now actually run through all 300 sizes without testing my patience. For fun, here’s the timing output for it.
(let ((*trace-output* *standard-output*))
(time (problem-b)))Problem 11 B: (237 227 14 108) Evaluation took: 1.687 seconds of real time 1.696096 seconds of total run time (1.673423 user, 0.022673 system) [ Run times consist of 0.103 seconds GC time, and 1.594 seconds non-GC time. ] 100.53% CPU 5,222,992,208 processor cycles 1,741,533,200 bytes consed