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, 31 [here](https://adventofcode.com/2021/day/3). 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, 98 > start with the full list of binary numbers from your diagnostic report and 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[0]) { 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[0]) { 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 ```