It's the 16th of December here, so let's do one small recap of my experiences from the last eleven days of Advent of Code. Since there are a lot of challenges here, I'll just do some commentary and not really present all solutions. I'll provide a repository later where you'll be able to find all of my solutions.
Day 5 was asking to decode a binary format that was used to represent boarding pass codes for seats in a fictional plane. There were quite a lot of clues that this was the case, so it was quite simple to write down a solution that parsed the codes given into binary numbers. Then for part two the task was to find a missing step in the numbering.
All in all it was a quite easy challenge for day 5.
In day 6 the task was to count unique items in a group for the first part and then count common elements in slightly different groups. As the description shows it was quite easy as well and took little time to implement.
Day 7 was the first challenging day for me, and it really helped me to remember some graph concepts that I had forgotten. The first problem is asking to do calculate the nodes in a connected component of a graph the represents how bags are to be inserted in each other. A recursive solution with associative lists worked fine for the first part.
In part 2 the question was how many bags are to be contained in ours, given rules for what the bag shall contain. A DFS for the directed graph was then implemented in order to discover all the nodes and count them. This was quite an interesting day.
At the eight day the challenge was around parsing and executing a pseudo language with jumps and an accumulator. For the first part there was an infinite loop to be discovered, which I did by keeping the history of executed commands. If one was called twice the program was surely lead to run forever.
For part 2 we had the information that two kinds of instructions were flipped, and that was the issue that produced the infinite loop. So I checked the pairs that could be swapped and if the resulting instructions would create a finishing program.
In all this day was not that difficult, but needed some tricks.
The challenge here was to find a number in a sequence that was the sum of two numbers in another group. Since we had the two sum algorithm from day 1, it was easy to modify it so to check if some number is or not a two sum in a given group. Then we had to find a range in the same group that had the sum of the number found in part one. This was solved by starting with each element of the group and calculating the sum of the sub-groups starting with it till the wanted sum was found or the sum exceeded it.
Here the first part was quite easy, in calculating the number of differences that where three or ones in a sequence of numbers. The second part though wanted to calculate all the permutations that would work with the rule that a number had to be followed by one that was from 1 to 3 units bigger. This required a dynamic programming solution backtracking in the numbers and counting the possible arrangements for each element.
Day 11 was a problem similar to Conway's Game of Life. The implementation I did was not the most performant, since it kept the whole board of positions in memory but it worked well enough in the end. Part 2 needed just a modification of what was considered neighboring between the positions and was interesting to implement.
Moving a ship given some coordinates and then adding a waypoint to the whole ordeal. Quite nice challenge and reminded me of some of the graphics manipulation like rotating points around others etc. I used Lisp's structs to express the ship and waypoint which to lead to simple but rather verbose code.
This day's challenge was mostly around number theory and the part 2 even required the implementation of the Chinese Remainder Theorem to solve. I was happy to do so and have it reminded, after so many years that I last used it.
More low level stuff in day 14, as the problem was around masking and memory positions. The bit level functions of Lisp proved really helpful, especially the boole function. Part two was also quite interesting as it introduced a floating bit, i.e. a bit that can take all possible values.
The elf game of day 15 was not really a challenge, and my implementation with a hash list happily responded even for the second part that demanded 30 million iterations. Given that the whole solution was:
(defparameter input '((20 . 1) (0 . 2) (1 . 3) (11 . 4) (6 . 5) (3 . 6))) (defparameter starting-input (loop :for i :in input :with a := (make-hash-table) :do (setf (gethash (car i) a) (cdr i)) :finally (return a))) (defun calculate-next-number-v2 (prev alist turn) (let ((cell (gethash prev alist))) (if cell (- turn cell) 0))) (defun elf-game-v2 (turn starting-alist) (labels ((iter (acc prev past-alist) (if (= turn (1+ acc)) (calculate-next-number-v2 prev past-alist acc) (iter (1+ acc) (calculate-next-number prev past-alist acc) (progn (setf (gethash prev past-alist) acc) past-alist))))) (let ((starting-turn (hash-table-count starting-alist))) (remhash 3 starting-alist) (iter starting-turn 3 starting-alist))))
it was probably the day for which I wrote the least code.
Day 16 challenged me more than it should. The first part was quite trivial, but for the second part we needed to map some number positions to rules, given the data-set we were given. I was anxious that I would need backtracking but in the end part 2 was simpler than I anticipated. I think I did take some questionable choices to be honest:
(ql:quickload :cl-ppcre) (defun get-file (filename) (with-open-file (stream filename) (loop :for line := (read-line stream nil) :while line :collect line))) (defparameter file (get-file "input16.txt")) (defparameter test (get-file "test16.txt")) (defparameter rule-scanner (ppcre:create-scanner "(?:.+: )(\\d+)(?:-)(\\d+)(?: or )(\\d+)(?:-)(\\d+)")) (defparameter rules (loop :for line :in file :when (ppcre:scan rule-scanner line) :collect (ppcre:register-groups-bind ((#'parse-integer min1) (#'parse-integer max1) (#'parse-integer min2) (#'parse-integer max2)) (rule-scanner line) (list (cons min1 max1) (cons min2 max2))))) (defparameter rules-functions (mapcar (lambda (x) (lambda (y) (or (and (>= y (car (first x))) (<= y (cdr (first x)))) (and (>= y (car (second x))) (<= y (cdr (second x))))))) rules)) (defparameter nearby-tickets (loop :for line :in file :with start := nil :when start :collect (mapcar #'parse-integer (ppcre:split "," line)) :when (string= line "nearby tickets:") :do (setf start t))) ;;; part 1 (defun apply-rules (rules ticket) (labels ((iter (numbers acc) (if (endp numbers) acc (iter (cdr numbers) (if (not (some (lambda (x) (funcall x (car numbers))) rules)) (cons (car numbers) acc) acc))))) (iter ticket '()))) (defun calculate-error-rate (rules tickets) (labels ((iter (tickets acc) (if (endp tickets) acc (iter (cdr tickets) (append (apply-rules rules (car tickets)) acc))))) (reduce #'+ (iter tickets '())))) ;;; part 2 (defparameter cleaned-nearby-tickets (loop :for ticket :in nearby-tickets :unless (apply-rules rules-functions ticket) :collect ticket)) (defun apply-rules-v2 (rules ticket) (loop :for rule :in rules :for rule-position :from 1 :with result = '() :do (loop :for number :in ticket :for number-position :from 1 :unless (funcall rule number) :do (setf result (cons `(,rule-position . ,number-position) result))) :finally (return result))) (defun viable-positions (rules tickets) (let ((exclusions (loop :for i :from 1 :upto (length rules) :collect (mapcar #'cdar (delete-if-not (lambda (x) (= (caar x) i)) (mapcar (lambda (x) (apply-rules-v2 rules x)) tickets)))))) (loop :for exl :in exclusions :with result := '() :with availabe-positions := (loop :for i :from 1 :to (length rules) collect i) :collect (loop :for i :in availabe-positions :when (not (member i exl)) :collect i)))) (defun map-positions-to-rules (rules tickets) (loop :with viable-positions := (viable-positions rules tickets) :with result-array := (make-array (length rules)) :do (loop :for pos :in viable-positions :for i :from 0 :if (= (length pos) 1) :do (let ((target (car pos))) (setf (aref result-array i) target) (setf viable-positions (mapcar (lambda (x) (remove target x)) viable-positions)))) :when (not (find 0 result-array)) :return result-array)) (defparameter my-ticket (mapcar #'parse-integer (ppcre:split "," "97,101,149,103,137,61,59,223,263,179,131,113,241,127,53,109,89,173,107,211"))) (defun calculate-part2 (rules tickets my-ticket) (let ((rules-array (map-positions-to-rules rules tickets))) (loop :for i :from 0 :upto 5 :with product := 1 :do (setf product (* product (nth (1- (aref rules-array i)) my-ticket))) :finally (return product))))
Not all solutions are created equal, but at least this year I feel I will stay up and running with the challenges and will complete them on time. Still 9 days to go.