Skip to content

Instantly share code, notes, and snippets.

@jakergrossman

jakergrossman/aoc2015-17.lsp

Last active December 14, 2021 23:38
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save jakergrossman/30d4c7ba5ad2b33e0f4d2184e5fec0bd to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save jakergrossman/30d4c7ba5ad2b33e0f4d2184e5fec0bd to your computer and use it in GitHub Desktop.
Download ZIP
Solution to Day 17 of 2015's Advent of Code. A variation of the Subset Sum problem.
Raw
aoc2015-17.lsp
; Day 17: No Such Thing as Too Much
; https://adventofcode.com/2015/day/17
; https://adventofcode.com/2015/day/17/input
(defun get-lines (filename)
(with-open-file (stream filename)
(loop :for line = (read-line stream nil nil)
:while line
:collect line)))
; Find every way to hold `volume` units with `containers`
(defun discover (containers volume &optional used-containers)
(let ((next-container (car containers)))
(cond
((eq 0 volume) (list used-containers))
((null containers) nil)
((> next-container volume) (discover (cdr containers) volume used-containers))
(t (append (discover (cdr containers) (- volume next-container) (cons next-container used-containers))
(discover (cdr containers) volume used-containers))))))
(defun answer (&optional (file #P"input.txt") (volume 150))
(let* ((containers (mapcar #'parse-integer (get-lines file)))
(p1-comb (discover containers volume))
(min-containers (reduce #'min (mapcar #'length p1-comb)))
(p2-comb (remove-if-not (lambda (x) (eq (length x) min-containers)) p1-comb)))
(format t "Part 1: ~d~%" (length p1-comb))
(format t "Part 2: ~d~%" (length p2-comb))))
(answer)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment