Advent of Code 2021, Day 3
Our submarine adventure continues, we’ll need to parse some binary data after we fixed the navigation computer yesterday.
I was lazy today, so only Scheme solution. Lazy evaluation and what not.
Without further ado, here we go.
Here’s the problem we need to solve: we need to parse a matrix of binary numbers.
00100 11110 10110 10111 10101 01111 00111 11100 10000 11001 00010 01010
You know the drill by now. We’ll again first take care of the input. Since input is impure, we’ll hide it away in a function:
(define input (letrec ((input-file (open-input-file "Input.txt")) (str->bin (lambda (ls) (map (lambda (s) (map (lambda (n) (- n 48)) (map char->integer (string->list s)))) ls))) (R (lambda (ls) (let ((next (get-line input-file))) (if (eof-object? next) ls (R (cons next ls))))))) (str->bin (reverse (R '())))))
str->bin function is a bit awkward, three nested
maps is a bit ugly, but it works for now. We simply convert the string read from input into lists, then into integers. Now we have the input matrix as a list of list, where each list represents a row in the matrix.
Since we need to count the the number of
1’s in a column (you can think of it as some kind of parity check), we first transpose the input matrix:
(define transpose (lambda (ls) (apply map list ls)))
To calculate whether there’s more
1’s in a row, I employ a simple trick: I calculate the sum of a column. If that number is larger than half the total numbers in one row, then there are more
0’s. The functions
epsilon-rate simply inject a comparison function into
(define rate (lambda (f ls) (let* ((row-sums (map (lambda (l) (fold-right + 0 l)) ls)) (half-row-length (/ (length (car ls)) 2))) (map (lambda (x) (if (f x half-row-length) 1 0)) row-sums)))) (define gamma-rate (lambda (ls) (rate (lambda (x y) (> x y)) ls))) (define epsilon-rate (lambda (ls) (rate (lambda (x y) (< x y)) ls)))
We’ll also need a little helper function to convert binary numbers represented as a list back into integers:
(define bin->dec (lambda (ls) (letrec ((in (reverse ls)) (B (lambda (sum fac ls) (if (null? ls) sum (B (+ sum (* (car ls) fac)) (* fac 2) (cdr ls)))))) (B 0 1 in))))
Finally, we compose the solution for part 1, we calculate the gamma- and epsilon-rate for the transposed input matrix and return the product:
(define solution-part1 (let* ((transposed-input (transpose input)) (gamma (bin->dec (gamma-rate transposed-input))) (epsilon (bin->dec (epsilon-rate transposed-input)))) (* gamma epsilon)))
This returns the correct result of 4006064 for my input.
Part 2 is again a some kind of parity check. We need to filter numbers (the rows of the matrix) by frequency of
1’s in each column. If a column is mostly
1’s, all numbers with
1 at that bit are kept, discarded otherwise (and the same again for
I use a trick similar to the sum trick here. This time, I take each column and sort it first. Then I take the element at the half-length-of-list-nth position. Which ever number is more frequent in said column will be at that position:
🠓 00101 -> 00011 11101 -> 01111
I call this a bit awkwardly the
(define bit-max (lambda (ls) (let* ((bit-list (map car ls)) (bit-length (div (length bit-list) 2))) (car (list-tail (sort < bit-list) bit-length)))))
Now a set of small helper functions, all pretty self-explanatory:
(define toogle (lambda (x) (if (= x 1) 0 1))) (define bit-min (lambda (ls) (toogle (bit-max ls)))) (define nth-bit-max (lambda (n ls) (let ((bs (map (lambda (l) (list-tail l n)) ls))) (bit-max bs)))) (define nth-bit-min (lambda (n ls) (let ((bs (map (lambda (l) (list-tail l n)) ls))) (bit-min bs)))) (define nth-bit (lambda (n ls) (car (list-tail ls n))))
bit-min does the opposite of
bit-max and returns the least frequent bit value in a given list.
nth-bit-min return the most and least frequent bit value in the
nth column of a given matrix.
Now we can filter the input matrix by any arbitrary value (well, of two) that occurs most frequent in any column. The oxygen generator will filter by the most frequent bit value, the CO2 scrubber by the least frequent:
(define filter-by-nth-bit-f (lambda (f n ls) (let ((filter-bit (f n ls))) (filter (lambda (ls) (equal? filter-bit (nth-bit n ls))) ls)))) (define filter-by-nth-bit-max (lambda (n ls) (filter-by-nth-bit-f nth-bit-max n ls))) (define filter-by-nth-bit-min (lambda (n ls) (filter-by-nth-bit-f nth-bit-min n ls))) (define generator (lambda (f ls) (letrec ((R (lambda (n ls) (if (= (length ls) 1) (car ls) (R (+ n 1) (f n ls)))))) (R 0 ls)))) (define oxygen-generator (lambda (ls) (generator filter-by-nth-bit-max ls))) (define co2-scrubber (lambda (ls) (generator filter-by-nth-bit-min ls)))
And as always, we compose the solution:
(define solution-part2 (let ((oxygen-rating (bin->dec (oxygen-generator input))) (co2-rating (bin->dec (co2-scrubber input)))) (* oxygen-rating co2-rating)))
Again, the correct numbers for my input.
That was a rather inelegant solution. Oh, well.
That’s it for today. You can find all my solutions on my Github.
See you tomorrow.