Skip to content

Latest commit

 

History

History
225 lines (220 loc) · 12.9 KB

2018.12.org

File metadata and controls

225 lines (220 loc) · 12.9 KB

Day 12

Executing this code

If you have a lisp installation, emacs, org-mode, and org-babel support for lisp installed you can run this by:

  1. Starting slime (M-x slime)
  2. Typing C-c C-c in the block initialize.
  3. In the repl type (in-package :aoc-2018-12)
  4. Typing C-c C-c in the block answers

Initial stuffs

Packages to load

(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"))

Create package for this day

<<packages>>
(defpackage :aoc-2018-12
  (:use :common-lisp
        :iterate
        :parseq
        :fiveam)
  (:export :problem-a
           :problem-b))
(in-package :aoc-2018-12)

Input

I’ve created structs below to contain the game and its rules. Each rule looks something like:

#..#. => #

So I split on the ' => ' with the left becoming the pattern to match against and the right being the result.

(defun get-initial (line)
  (ppcre:regex-replace-all "\\s+" (cadr (ppcre:split ":" line)) ""))
(defun get-rule (line)
  (let ((rule (ppcre:split " => " line)))
    (make-rule :pattern (car rule) :result (elt (cadr rule) 0))))
(defun get-rules (lines)
  (mapcar #'get-rule lines))
(defun parse-input (lines)
  (make-game :initial (get-initial (car lines))
             :rules (get-rules (cddr lines))
             :default #\.))
(defun read-input (file)
  (iter (for line in-file file using #'read-line)
        (collect line)))
(defparameter *input*
  (parse-input (read-input "input/12.txt")))

Part 1

This is a simple 1d cellular automata. For each pot (cell) determine whether it lives or dies per the list of rules (they are complete).

There are an infinite number of pots, each uniquely numbered. But the first element of the input is 0. Since I can’t access things at a negative position, I’m going to create a padded state variable with 100 ‘.’ characters on either side of the initial state and use an offset when computing the score later.

The question is what is the sum of the number of each pot with a plant in it at the end of generation 20. So if pot’s 0, 2, 10 have plants in them the score is 12.

(defun print-state (state generation offset)
  (format t "~d: ~a => ~d~%" generation state (score-game state offset)))
(defun score-game (state offset)
  (iter (for i from (- offset))
        (for c in-string state)
        (when (char= #\# c)
          (sum i))))
(defun apply-rules (string rules)
  (iter (for r in rules)
        (when (string= string (rule-pattern r))
          (return (rule-result r)))))
(defun next-state (state game)
  (let ((next (make-string (length state) :initial-element #\.)))
    (iter (for i from 2 below (- (length state) 2))
          (setf (elt next i)
                (apply-rules (subseq state (- i 2) (+ i 3)) (game-rules game))))
    next))
(defun run-game-print (game generations)
  (let* ((offset (length (game-initial game)))
         (state (make-string (* 3 offset) :initial-element #\.)))
    (setf (subseq state 100) (game-initial game))
    (iter (for generation from 0 to generations)
          (print-state state generation offset)
          (setf state (next-state state game)))))
(defun problem-a () (format t "Problem 12 A:~%") (run-game-print *input* 20))

Part 2

Now we need the score after 50,000,000,000 generations. That’s a lot of generations and I don’t have the patience for it. I have an idea though. Iterate until a steady state exists. That is, I’ll create the next generation and see if the same series of potted plants exist (but shifted). The score difference between the two generations can be multiplied by the number of generations remaining to hit 50,000,000,000.

Simpler, let’s just keep track of the score differences. Once it’s increasing by the same rate over 3 generation then we have our answer.

(defun run-game (game generations target-generation)
  (let* ((offset (length (game-initial game)))
         (state (make-string (* 2 offset generations) :initial-element #\.))
         (s0 (score-game state offset))
         (s1 (score-game state offset))
         (s2 (score-game state offset)))
    (setf (subseq state 100) (game-initial game))
    (iter (for generation from 0 below generations)
          (setf state (next-state state game))
          (setf s0 s1)
          (setf s1 s2)
          (setf s2 (score-game state offset))
          (when (= (- s2 s1) (- s1 s0))
                 (return (+ s2 (* (- s2 s1) (- target-generation generation 1))))))))
(defun problem-b () (format t "Problem 12 B: ~a~%" (run-game *input* 200 50000000000)))

Putting it all together

(defstruct game
  initial
  rules
  default)

(defstruct rule
  pattern
  result)
<<parse-input>>
<<read-input>>
<<print-state>>
<<score-game>>
<<next-state>>
<<run-game-print>>
<<run-game>>
<<initialize>>
<<structs>>
<<functions>>
<<input>>
<<problem-a>>
<<problem-b>>
(problem-a)
(problem-b)

Answer

Problem 12 A:
0: .....................................................................................................##..#.#..##..##..##...#####.#.....#..#..##.###.#.####......#.......#..###.#.#.##.#.#.###...##.###.#.................................................................................................... => 2455
1: .....................................................................................................#..#....##..##..##.##...#.##.#...##.##.#########.#...#....###.....##.#.####.#..###.#.##.##.#######.#................................................................................................... => 3081
2: ....................................................................................................##.###...#..##..####..###...##.##.###.###.#####.##.#####....#.#....####.#..##..#.####..##.###.###.##.#.................................................................................................. => 3169
3: ....................................................................................................#####.####.##..#.....#.#.##.###.###########.#.##.###.#..#..#...#......##..##..#..#....############.##.#................................................................................................. => 3033
4: ......................................................................................................#.###..##...###...#..#..#######.#######.###..######..##.#######.....#..##..##.###.....########.##.##.#................................................................................................ => 3396
5: .....................................................................................................#..##..##.##..#.####.##.#..###.###.###.####..#..##...#####.###..#...##.##..######.#......####.##.##.##.#............................................................................................... => 3244
6: ....................................................................................................##.##..####...#..#..##.##..#.############....##.##.##...#.####..####.###...#..##.##.#........##.##.##.##.#.............................................................................................. => 3027
7: ....................................................................................................###...#....####.##.####...#..#.########..#...###.##..###..#....#...####.####.####.##.#.......###.##.##.##.#............................................................................................. => 3189
8: .....................................................................................................#.#####......##.###...####.#..#.####...####..###...#.#..###..####....###..###..##.##.#.......###.##.##.##.#............................................................................................ => 3101
9: ....................................................................................................#..#.#..#.....#####.##....##..#..#...##......#.#.###....#.#..#....#....#..#.#..####.##.#.......###.##.##.##.#........................................................................................... => 2621
10: ...................................................................................................##.#....###......#.##..#...#..##.####.#.#....#..#.##.#..#....###..###..##.#....#...##.##.#.......###.##.##.##.#.......................................................................................... => 2810
11: ...................................................................................................###.#....#.#....#.....######.#####..###..#..##.#...##..###....#..#.#..####.#..####.###.##.#.......###.##.##.##.#......................................................................................... => 3277
12: ....................................................................................................###.#..#...#..###......##.###.#...#.#..##.####.##.#..#.#.#..##.#....#...##..#...######.##.#.......###.##.##.##.#........................................................................................ => 3135
13: .....................................................................................................###..######.#.#.#.....#######.###....#####..##.##..#..#...####.#..####.#..####...##.##.##.#.......###.##.##.##.#....................................................................................... => 3488
14: ......................................................................................................#..#..##.###.#..#......###.####.#.....#...####...##.####....##..#...##..#....##.###.##.##.#.......###.##.##.##.#...................................................................................... => 3193
15: .....................................................................................................##.##.########..###......####..##.#...####.....##.####...#...#..####.#..###...#######.##.##.#.......###.##.##.##.#..................................................................................... => 3601
16: .....................................................................................................###.###.####...#.#.#..........####.##.....#....####...########.#...##..#.#.##...###.##.##.##.#.......###.##.##.##.#.................................................................................... => 3484
17: ......................................................................................................########...###..#..#............##..#...###.......##...####.##.##.#..#..#...##..###.##.##.##.#.......###.##.##.##.#................................................................................... => 3298
18: ........................................................................................................####..##..#..##.###...........#..####..#.#......#.##....##.##.##..##.####.#..#.###.##.##.##.#.......###.##.##.##.#.................................................................................. => 3563
19: .............................................................................................................##..##.######.#.........##.#.....#...#....#....#...###.##...#####..##..#..####.##.##.##.#.......###.##.##.##.#................................................................................. => 3473
20: .............................................................................................................#..#####.##.##.#........###.#...#######..###..####..###..##...#...##..##.#...##.##.##.##.#.......###.##.##.##.#................................................................................ => 3738
Problem 12 B: 3900000002467

Test Cases

(def-suite aoc.2018.12)
(in-suite aoc.2018.12)

(run! 'aoc.2018.12)

Test Results

Thoughts