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.

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:

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:

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:

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:

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:

auto res = [gamma, epsilon].fold!"b.to!int(2) * a"(a);

Full solution

[(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:

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:

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:

auto result = rate!'1'(input) * rate!'0'(input);

Full solution

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
}