 # git

My personal website source code

zet-4-aoc-2021-03.md (8017B)

```      1 ---
2 title: 'Zettelkasten #4: Solution in D for Advent of Code 2021, Day 3'
3 date: '2021-12-04T00:08:00+01:00'
4 tags: ['zettelkasten', 'zet', 'dlang', 'aoc', 'aoc2021', 'adventofcode']
5 description: "This post describes, in detail, my solution in the D programming
6 language for the 3rd puzzle of the Advent of Code 2021."
7 ---
8
9 ## The challenge
10
11 > The submarine has been making some odd creaking noises, so you ask it to
12 > produce a diagnostic report just in case.
13 >
14 > The diagnostic report (your puzzle input) consists of a list of binary
15 > numbers which, when decoded properly, can tell you many useful things about
16 > the conditions of the submarine. The first parameter to check is the power
17 > consumption.
18 >
19 > You need to use the binary numbers in the diagnostic report to generate two
20 > new binary numbers (called the gamma rate and the epsilon rate). The power
21 > consumption can then be found by multiplying the gamma rate by the epsilon
22 > rate.
23 >
24 > [...]
25 >
26 > Use the binary numbers in your diagnostic report to calculate the gamma rate
27 > and epsilon rate, then multiply them together. What is the power consumption
28 > of the submarine? (Be sure to represent your answer in decimal, not binary.)
29
30 You can read the challenge more in depth,
32
33 ## Part 1
34
35 To make the problem easier to look at, we can think that the input data is a
36 matrix of 0s and 1s and we work with the transposed version of the matrix to
37 calculate the bit criteria. To transpose a range of ranges in D you can use
38 `transposed` template:
39
40 ```d
41 auto tmatrix = input.transposed;
42 ```
43
44 As the problem dictates, the criteria is to select the most common bit for each
45 column (in this case, each row, due to the matrix transposition). To do this,
46 we shall sort and group the bits, which in practice counts the number of 0s and
47 1s in our array. We then convert the group (array of tuples) to an associative
48 array, but that is just purely for code aesthetics:
49
50 ```d
51 auto g = tmatrix.sort.group.assocArray;
52 ```
53
54 To extract the common bits you just need to compare the counter and select the
55 common bit accordingly. We can solve this with a simple map and a ternary
56 operator:
57
58 ```d
59 auto gamma = g.map!"a['0'] > a['1'] ? '0' : '1'";
60 ```
61
62 We now have the encoded version of gamma value. To find epsilon, we just flip
63 each bit. We can also use a map and a ternary operator to that job:
64
65 ```d
66 auto epsilon = gamma.map!"a == '0' ? '1' : '0'";
67 ```
68
69 To calculate the result we just decode the values to decimal and multiply them.
70 To decode to decimal, you can use `to!int(<base>)` from `std.conv`, where
71 `<base>` is the numeric base of the input value. Here I used a `fold` instead
72 of repeating two `to` calls:
73
74 ```d
75 auto res = [gamma, epsilon].fold!"b.to!int(2) * a"(a);
76 ```
77
78 ### Full solution
79
80 ```d
81 [(cast(char[][])stdin.byLine().map!"a.to!string".array) // input
82     .transposed.map!array                               // transpose matrix
83     .map!`a.dup.sort.group.assocArray`                  // sort & group bits
84     .map!"a['0'] > a['1'] ? '0' : '1'".array]           // extract common bit
85     .map!(b => [b, b.map!"a == '0' ? '1' : '0'".array]) // flip bits for gamma & epsilon
86     .front.fold!"b.to!int(2) * a"(1).writeln;           // decode & multiply gamma & epsilon
87 ```
88
89 ## Part 2
90
91 > Next, you should verify the life support rating, which can be determined by
92 > multiplying the oxygen generator rating by the CO2 scrubber rating.
93
94 > Both the oxygen generator rating and the CO2 scrubber rating are values that
95 > can be found in your diagnostic report - finding them is the tricky part.
96 > Both values are located using a similar process that involves filtering out
97 > values until only one remains. Before searching for either rating value,
99 > consider just the first bit of those numbers. Then:
100 >
101 > - Keep only numbers selected by the bit criteria for the type of rating value
102 >   for which you are searching. Discard numbers which do not match the bit
103 >   criteria.
104 > - If you only have one number left, stop; this is the rating value for which
105 >   you are searching.
106 > - Otherwise, repeat the process, considering the next bit to the right.
107 >
108 > The bit criteria depends on which type of rating value you want to find:
109 >
110 > - To find oxygen generator rating, determine the most common value (0 or 1)
111 >   in the current bit position, and keep only numbers with that bit in that
112 >   position. If 0 and 1 are equally common, keep values with a 1 in the
113 >   position being considered.
114 > - To find CO2 scrubber rating, determine the least common value (0 or 1) in
115 >   the current bit position, and keep only numbers with that bit in that
116 >   position. If 0 and 1 are equally common, keep values with a 0 in the
117 >   position being considered.
118 >
119 > [...]
120 >
121 > Use the binary numbers in your diagnostic report to calculate the oxygen
122 > generator rating and CO2 scrubber rating, then multiply them together. What
123 > is the life support rating of the submarine? (Be sure to represent your
124 > answer in decimal, not binary.)
125
126 I got impressed with the second part, as it is quite big, although not too
127 complicated, just more restrictive bit criteria and more rules for each
128 criteria.
129
130 To facilitate comprehension and avoid code duplication, I decided to create a
131 rate function to calculate the rate for oxygen and CO2. The rate calculation
132 needs similar approaches to the first part, although, each iteration is
133 dependent of the previous one, so you need to recalculate the bit counter for
134 each state.
135
136 To the basic iteration logic you will need to recalculate the counter which
137 includes transpose the state matrix, sort and group the bits of each column
138 (row, for transposed matrix). You will also need to add a stop condition when
139 only one value is present in the state matrix. The basic logic will end up
140 being something like this:
141
142 ```d
143 auto rate(char[][] input) {
144     auto ret = input;                                 // state matrix
145     foreach(n, _; input) {
146         auto b = ret.dup.transposed.map!array         // transpose matrix
147             .map!`a.dup.sort.group.assocArray`.array; // sort & group bits
148         if(ret.length == 1) break;                    // stop on one bitarray
149     }
150     return ret.front.to!int(2);                       // decode bits
151 }
152 ```
153
154 To add the bit criteria and filter the values we can use the `filter` template
155 along with a comparison with a ternary operator:
156
157 ```d
158 auto newState = oldState.filter!(f =>                                     // filter result
159             (b[n]['1'] >= b[n]['0'] ? c : (c == '0' ? '1' : '0')) == f[n] // bit criteria
160         ).array;
161 ```
162
163 More in detail, `b` will include the transposed and grouped bits, `n` is the
164 column position and `c` is the bit criteria corresponding to the desired rate,
165 which will be a template parameter, in our case. Now we just need to add this
166 filter in the loop and we have a working rate function. To calculate the final
167 result, we just instantiate each rate template and multiply the results:
168
169 ```d
170 auto result = rate!'1'(input) * rate!'0'(input);
171 ```
172
173 ### Full solution
174
175 ```d
176 int rate(char c)(char[][] input) {
177     auto ret = input;
178     foreach(n, _; input) {
179         auto b = ret.dup.transposed.map!array                             // transpose matrix
180             .map!`a.dup.sort.group.assocArray`.array;                     // sort & group bits
181         ret = ret.filter!(f =>                                            // filter result
182             (b[n]['1'] >= b[n]['0'] ? c : (c == '0' ? '1' : '0')) == f[n] // bit criteria
183         ).array;
184         if(ret.length == 1) break;                                        // stop on one bitarray
185     }
186     return ret.front.to!int(2);                                           // decode bits
187 }
188
189 void main() {
190     auto i = cast(char[][])stdin.byLine().map!(to!string).array;          // input
191     writeln(rate!'1'(i) * rate!'0'(i));                                   // calculate result
192 }
193 ```
```