git

My personal website source code
Log | Files | Refs | Submodules | README | LICENSE

commit da89a53cbfb2defddee9f1e9eb27d5cc6abbbf58
parent ba46c4a60107dfc1d3e1a741f97f4a43f3521aeb
Author: Luís Ferreira <[email protected]>
Date:   Sat,  4 Dec 2021 01:55:39 +0000

posts: Add Zettelkasten 4

Signed-off-by: Luís Ferreira <[email protected]>

Diffstat:
Acontent/posts/zet-4-aoc-2021-03.md | 193+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
1 file changed, 193 insertions(+), 0 deletions(-)

diff --git a/content/posts/zet-4-aoc-2021-03.md b/content/posts/zet-4-aoc-2021-03.md @@ -0,0 +1,193 @@ +--- +title: 'Zettelkasten #4: Solution in D for Advent of Code 2021, Day 3' +date: '2021-12-02T19:02:00+01:00' +tags: ['zettelkasten', 'zet', 'dlang', 'aoc', 'aoc2021', 'adventofcode'] +description: "This post describes, in detail, my solution in the D programming +language for the 3rd puzzle of the Advent of Code 2021." +--- + +## The challenge + +> The submarine has been making some odd creaking noises, so you ask it to +> produce a diagnostic report just in case. +> +> The diagnostic report (your puzzle input) consists of a list of binary +> numbers which, when decoded properly, can tell you many useful things about +> the conditions of the submarine. The first parameter to check is the power +> consumption. +> +> You need to use the binary numbers in the diagnostic report to generate two +> new binary numbers (called the gamma rate and the epsilon rate). The power +> consumption can then be found by multiplying the gamma rate by the epsilon +> rate. +> +> [...] +> +> Use the binary numbers in your diagnostic report to calculate the gamma rate +> and epsilon rate, then multiply them together. What is the power consumption +> of the submarine? (Be sure to represent your answer in decimal, not binary.) + +You can read the challenge more in depth, +[here](https://adventofcode.com/2021/day/3). + +## Part 1 + +To make the problem easier to look at, we can think that the input data is a +matrix of 0s and 1s and we work with the transposed version of the matrix to +calculate the bit criteria. To transpose a range of ranges in D you can use +`transposed` template: + +```d +auto tmatrix = input.transposed; +``` + +As the problem dictates, the criteria is to select the most common bit for each +column (in this case, each row, due to the matrix transposition). To do this, +we shall sort and group the bits, which in practice counts the number of 0s and +1s in our array. We then convert the group (array of tuples) to an associative +array, but that is just purely for code aesthetics: + +```d +auto g = tmatrix.sort.group.assocArray; +``` + +To extract the common bits you just need to compare the counter and select the +common bit accordingly. We can solve this with a simple map and a ternary +operator: + +```d +auto gamma = g.map!"a['0'] > a['1'] ? '0' : '1'"; +``` + +We now have the encoded version of gamma value. To find epsilon, we just flip +each bit. We can also use a map and a ternary operator to that job: + +```d +auto epsilon = gamma.map!"a == '0' ? '1' : '0'"; +``` + +To calculate the result we just decode the values to decimal and multiply them. +To decode to decimal, you can use `to!int(<base>)` from `std.conv`, where +`<base>` is the numeric base of the input value. Here I used a `fold` instead +of repeating two `to` calls: + +```d +auto res = [gamma, epsilon].fold!"b.to!int(2) * a"(a); +``` + +### Full solution + +```d +[(cast(char[][])stdin.byLine().map!"a.to!string".array) // input + .transposed.map!array // transpose matrix + .map!`a.dup.sort.group.assocArray` // sort & group bits + .map!"a['0'] > a['1'] ? '0' : '1'".array] // extract common bit + .map!(b => [b, b.map!"a == '0' ? '1' : '0'".array]) // flip bits for gamma & epsilon + .front.fold!"b.to!int(2) * a"(1).writeln; // decode & multiply gamma & epsilon +``` + +## Part 2 + +> Next, you should verify the life support rating, which can be determined by +> multiplying the oxygen generator rating by the CO2 scrubber rating. + +> Both the oxygen generator rating and the CO2 scrubber rating are values that +> can be found in your diagnostic report - finding them is the tricky part. +> Both values are located using a similar process that involves filtering out +> values until only one remains. Before searching for either rating value, +> start with the full list of binary numbers from your diagnostic report and +> consider just the first bit of those numbers. Then: +> +> - Keep only numbers selected by the bit criteria for the type of rating value +> for which you are searching. Discard numbers which do not match the bit +> criteria. +> - If you only have one number left, stop; this is the rating value for which +> you are searching. +> - Otherwise, repeat the process, considering the next bit to the right. +> +> The bit criteria depends on which type of rating value you want to find: +> +> - To find oxygen generator rating, determine the most common value (0 or 1) +> in the current bit position, and keep only numbers with that bit in that +> position. If 0 and 1 are equally common, keep values with a 1 in the +> position being considered. +> - To find CO2 scrubber rating, determine the least common value (0 or 1) in +> the current bit position, and keep only numbers with that bit in that +> position. If 0 and 1 are equally common, keep values with a 0 in the +> position being considered. +> +> [...] +> +> Use the binary numbers in your diagnostic report to calculate the oxygen +> generator rating and CO2 scrubber rating, then multiply them together. What +> is the life support rating of the submarine? (Be sure to represent your +> answer in decimal, not binary.) + +I got impressed with the second part, as it is quite big, although not too +complicated, just more restrictive bit criteria and more rules for each +criteria. + +To facilitate comprehension and avoid code duplication, I decided to create a +rate function to calculate the rate for oxygen and CO2. The rate calculation +needs similar approaches to the first part, although, each iteration is +dependent of the previous one, so you need to recalculate the bit counter for +each state. + +To the basic iteration logic you will need to recalculate the counter which +includes transpose the state matrix, sort and group the bits of each column +(row, for transposed matrix). You will also need to add a stop condition when +only one value is present in the state matrix. The basic logic will end up +being something like this: + +```d +auto rate(char[][] input) { + auto ret = input; // state matrix + foreach(n, _; input[0]) { + auto b = ret.dup.transposed.map!array // transpose matrix + .map!`a.dup.sort.group.assocArray`.array; // sort & group bits + if(ret.length == 1) break; // stop on one bitarray + } + return ret.front.to!int(2); // decode bits +} +``` + +To add the bit criteria and filter the values we can use the `filter` template +along with a comparison with a ternary operator: + +```d +auto newState = oldState.filter!(f => // filter result + (b[n]['1'] >= b[n]['0'] ? c : (c == '0' ? '1' : '0')) == f[n] // bit criteria + ).array; +``` + +More in detail, `b` will include the transposed and grouped bits, `n` is the +column position and `c` is the bit criteria corresponding to the desired rate, +which will be a template parameter, in our case. Now we just need to add this +filter in the loop and we have a working rate function. To calculate the final +result, we just instantiate each rate template and multiply the results: + +```d +auto result = rate!'1'(input) * rate!'0'(input); +``` + +### Full solution + +```d +int rate(char c)(char[][] input) { + auto ret = input; + foreach(n, _; input[0]) { + auto b = ret.dup.transposed.map!array // transpose matrix + .map!`a.dup.sort.group.assocArray`.array; // sort & group bits + ret = ret.filter!(f => // filter result + (b[n]['1'] >= b[n]['0'] ? c : (c == '0' ? '1' : '0')) == f[n] // bit criteria + ).array; + if(ret.length == 1) break; // stop on one bitarray + } + return ret.front.to!int(2); // decode bits +} + +void main() { + auto i = cast(char[][])stdin.byLine().map!(to!string).array; // input + writeln(rate!'1'(i) * rate!'0'(i)); // calculate result +} +```