Skip to content

Latest commit

 

History

History
234 lines (225 loc) · 7.35 KB

2019.01.org

File metadata and controls

234 lines (225 loc) · 7.35 KB

Day 01

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-2019-01)
  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"))
(unless (find-package :series)
  (ql:quickload "series"))

Create package for this day

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

Input

A file containing a series of numbers (one per line). Each represents the mass of a spacecraft module.

(defun read-input (file)
  (iter (for line in-file file using #'read)
        (collect line)))
(defparameter *input*
  (read-input "input/01.txt"))

Part 1

Given the mass from the inputs, calculate the fuel required. Sum up the amount of fuel for all modules.

(defun calc-fuel (mass)
  (- (floor mass 3) 2))
(defun solve-a (list)
  (loop for l in list
     sum (calc-fuel l)))
(defun problem-a () (format t "Problem 01 A: ~a~%" (solve-a *input*)))

I had explored Series in the past but not gotten far, just didn’t have suitable problems to play with. I saw a Haskell solution and realized that Series allowed for a similarly compact, yet clear, solution. Here it is:

(time (series:collect-sum (series:map-fn t #'calc-fuel (series:scan-file "input/01.txt"))))

Part 2

Recursively apply the fuel calculation in order to account for the mass of the added fuel. If the calculated fuel is 0 or less, then return the total.

(defun recursive-fuel (mass &optional (total 0))
  (let ((fuel (calc-fuel mass)))
    (cond ((plusp fuel) (recursive-fuel fuel (+ fuel total)))
          (t total))))
(defun solve-b (input)
  (loop for m in input
     sum (recursive-fuel m)))

(defun problem-b () (format t "Problem 01 B: ~a~%" (solve-b *input*)))

Putting it all together



<<read-input>>
<<calc-fuel>>
<<recursive-fuel>>


<<initialize>>
<<structs>>
<<functions>>
<<input>>
<<problem-a>>
<<problem-b>>
(problem-a)
(problem-b)


Answer


Problem 01 A: 3278434
Problem 01 B: 4914785



Test Cases


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

(test non-recursive
  (is (= 2 (calc-fuel 12)))
  (is (= 2 (calc-fuel 14)))
  (is (= 654 (calc-fuel 1969)))
  (is (= 33583 (calc-fuel 100756))))

(test recursive
  (is (= 2 (recursive-fuel 12)))
  (is (= 2 (recursive-fuel 14)))
  (is (= 966 (recursive-fuel 1969)))
  (is (= 50346 (recursive-fuel 100756))))

(run! 'aoc.2019.01)


Test Results


Running test suite AOC.2019.01
 Running test NON-RECURSIVE ....
 Running test RECURSIVE ....
 Did 8 checks.
    Pass: 8 (100%)
    Skip: 0 ( 0%)
    Fail: 0 ( 0%)



Thoughts


floor


The next morning I realized floor takes two parameters. This was
  also pointed out by Reddit user phil_g. So instead of:


(- (floor (/ m 3)) 2)


It can be written as:


(- (floor m 3) 2)


Tail recursion


From a quickness of writing perspective, recursive-fuel was not tail
  recursive. I’ve added an optional parameter to store the total and
  pass that to the recursive call. This doesn’t really impact this
  problem, but it’s a better style. Here’s the original:


(defun recursive-fuel (mass)
  (let ((fuel (calc-fuel mass)))
    (if (<= fuel 0) 0
        (+ fuel (recursive-fuel fuel)))))


Input handling


I am reusing the template I put together for 2018 (my first year of
  participation, though I’ve gone back and done some puzzles from prior
  years). At midnight, I’d forgotten how I handled reading the input
  file and had to throw in an extra parse-integer call because of
  it. The original:


(defun read-input (file)
  (iter (for line in-file file using #'read-line)
        (collect (parse-integer line))))


However, with that form of iteration the <read> function can be
  specified to be anything. read is the better function than
  read-line, it will read and parse lisp objects from text files. In
  this case, it will correctly convert the text in the file to an
  integer. This is another small change, but it’s a useful
  one. Hopefully I won’t forget how to use my template tomorrow.


Testing


I’ve added tests using the examples from the problem statement. I
  should have put these in first, but this was a simpler problem so I
  didn’t bother. For more complex problems this is the first thing I do
  after I have a solution sketch in place.


Reproducibility


I realized while reviewing the code that I’d failed to include a
  reference to the block titled recursive-fuel. Oops. This was fine
  for me last night because I’d manually compiled the function via C-c
  C-c into the lisp image. But if this were run in a clean image, it
  would’ve failed since the function would be undefined.


if v cond


I have a preference for cond, but apparently I’m out of practice on
  writing lisp. I made a change to recursive-fuel so that it uses cond
  rather than if. It’s not important when there are really only two
  options, but I prefer this style.


plusp/minusp


I originally had something like:


(if (<= fuel 0) ...)


This is really the case of:


(if (not (plusp fuel)) ...)


It’s a bit more idiomatic, and less error prone (I’d accidentally
  typed greater-than-or-equal the first time, coding at midnight is
  dangerous). As part of my clean up I’ve swapped the conditions (to
  take the case that fuel is positive first) and changed the conditional
  expression to use cond instead of if.