Module aoc::year2020::day14

source ·
Expand description

§Docking Data

First we parse each mask into 2 u64 values, ones where a bit is set when there is a corresponding “1” in the mask and xs (plural of “x”) where a bit is set when there is a corresponding “X” in the mask. A bit will never be set in the same location in both ones and xs. For example:

    Mask: 000000000000000000000000000000X1001X
    ones: 000000000000000000000000000000010010
    xs:   000000000000000000000000000000100001

§Part One

The memory values are quite sparse, about 500 discrete values in a address range of about 65,000. This makes a FastMap a better choice than a large mostly empty array. Storing the correct value is a straightforward application of the problem rules, expressed as bitwise logic.

§Part Two

This part is subtly tricky to solve quickly. The maximum number of Xs in any mask is 9 which gives 2⁹ = 512 different memory addresses. A brute force solution will work, but there’s a much more elegant approach.

We treat each address and mask combination as a set. Then by using the inclusion-exclusion principle we can determine any overlaps with other sets and deduct the correct number of values.

For example:

    mask = 0000000000000000000000000000000001XX  // A
    mem[8] = 3
    mask = 00000000000000000000000000000000011X  // B
    mem[8] = 5
    mask = 000000000000000000000000000000000111  // C
    mem[8] = 7

Results in the following address sets:

   ┌──────────────┐A            Set A: 12 13 14 15
   │ 12 13        │             Set B: 14 15
   │ ┌─────────┐B │             Set C: 15
   │ │ 14      │  │
   │ │ ┌────┐C │  │
   │ │ │ 15 │  │  │
   │ │ └────┘  │  │
   │ └─────────┘  │
   └──────────────┘

Using the inclusion-exclusion principle the remaining size of A is: 4 (initial size) - 2 (overlap with B) - 1 (overlap with C) + 1 (overlap between B and C) = 2 If there were any quadruple overlaps we would add those, subtract quintuple, and so on until there are no more overlaps remaining.

To calculate the final answer we treat the value as the weight of the set, in this case: 2 * 3 + 1 * 5 + 1 * 7 = 18

The complexity of this approach depends on how many addresses overlap. In my input most addresses overlapped with zero others, a few with one and rarely with more than one. Benchmarking against the brute force solution showed that this approach is ~90x faster.

Structs§

Enums§

Functions§