Solving Advent of Code 2020 - Day 10

Why Day 10

Not only I've found Day 10 of this year's Advent of Code challenging, but also I've come up with a particular enough solution that I'd like to share (and document!) somewhere.

Problem rules

I strongly encourage you to read the full puzzle description if you aren't familiar with it, here I'm just gonna try to extract problem the restrictions with no amazing elves story behind:

• We're given a list of integers, each of one representing the output joltage supported by a different joltage adapter.

Sample input: 16 10 15 5 1 11 7 19 6 12 4

• Each one of our adapters can take an input joltage up to 3 jolts lower than its rating while still producing its rated output joltage (quite shocking, right?).

• We need to use our adapters to connect a charging outlet (0 jolts) to our device (3 jolts more than the highest of our adapters).

Warming up: part 1

Let's assume we use all our adapters chained one after the other: between each one of them there will be a joltage difference.

What is the number of 1-jolt differences multiplied by the number of 3-jolt differences?

The approach for this part is relatively simple:

• Sorting the input in ascending order.
• Creating two counters: number of 1-jolt differences and number of 3-jolt differences.
• Looping through our ordered list, comparing each item with the previous one and incrementing the relevant counter consequently. The initial 'previous' value is 0.
• Incrementing the 3-jolt counter by one, since that's a known problem restriction.

The solution asked is the product of both counters.

Something similar to:

public string Solve_1()
{
    var ascendingInput = File.ReadAllLines("input.txt").Select(int.Parse).OrderBy(_ => _).ToList();

    var ones = 0;
    var threes = 0;

    var previous = 0;
    for (int i = 0; i < ascendingInput.Count; i++)
    {
        var current = ascendingInput[i];

        if (current - previous == 1)
        {
            ++ones;
        }
        else
        {
            ++threes;
        }

        previous = current;
    }

    ++threes;   // Last connection is highest adapter + 3 jolts

    return $"{ones * threes}";
}

The real challenge: part 2

How many different ways are there to arrange your adapters, not necessarily using them all?

As the problem hints ("there must be more than a trillion valid ways to arrange them!"), trying to brute-force all the possible sequences may not be the ideal approach.

We're going to follow a different one: finding which adapters are optional, and based on that, trying to deduct how many different ways of arranging our adapters are there.

Finding optional adapters

First things first, let's try to identify those parameters that are optional:

Statement 1:

Given   Three consecutive adapters (A <= B <= C)
When    A and C have a voltage difference of three or less jolts
Then    B is optional

That one was easy, right?

Optional adapters and bifurcations

How does having an optional adapter exactly affect the number of possible ways of arranging our sequence? Let's see:

Statement 2:

Given   Given any sequence of adapters [N-Z] (N < O < ... < Z)
When    The first adapter is optional (and could be removed)
Then    The number of possible arrangements of the sequence [N-Z]
          is twice the number of possible arrangements in the subsequence [O-Z] (O < ... < Z):
          all the arrangements in [O-Z] plus the same arrangements preceded by N.

Sounds good, right? Maybe too good to be true.

Using the examples to find our mistake

If both statements were right:

• The solution to the example 1, with three optional adapters, would be 2^3 = 8, which is correct.
• The solution to the example 2, with fifteen optional adapters, would be 2^15 = 32.768, which is not correct.

Let's have a look at the failing example, more specifically at the first group of lines:

(0), 1, 2 ... 42, 45, 46, 47, 48, 49, (52)

(0), 1, 2 ... 42, 45, 46, 47, 49, (52)

(0), 1, 2 ... 42, 45, 46, 48, 49, (52)

(0), 1, 2 ... 42, 45, 46, 49, (52)

(0), 1, 2 ... 42, 45, 47, 48, 49, (52)

...

Eric Wastl, AoC creator, could have provided us with any random arrangements (there were 19208 different ways of using the adapters for this example), but these specific ones seem to follow a certain pattern. Let's try to see what is it.

(0), 1, 2 ... 42, 45, 46, 47, 48, 49, (52) → Complete sequence

(0), 1, 2 ... 42, 45, 46, 47, {}, 49, (52) → Missing 48

(0), 1, 2 ... 42, 45, 46, {}, 48, 49, (52) → Missing 47

(0), 1, 2 ... 42, 45, 46, {}, {}, 49, (52) → Missing 47 and 48

(0), 1, 2 ... 42, 45, {}, 47, 48, 49, (52) → Missing 46

Let's continue ourselves:

(0), 1, 2 ... 42, 45, {}, {}, 48, 49, (52) → Missing 46 and 47`

(0), 1, 2 ... 42, 45, {}, 47, {}, 49, (52) → Missing 46 and 48`

But the following one isn't a valid sequence:

(0), 1, 2 ... 42, 45, {}, {}, {}, 49, (52) → Missing 46, 47 and 48

If we iterate over the optional adapters from the right (48 > 47 > 46 ...), we see that:

• Initially, the number of valid arrangements is one (the whole sequence).

(0), 1, ... 49, (52)

• The first optional adapter, 48, duplicates the number of valid arrangements in the sequence, which was initially 1 and is 2 afterwards.

(0), 1, 2 ... 47, {48}, 49, (52)

(0), 1, 2 ... 47, {}, 49, (52)

• The second one, 47, duplicates the number of valid arrangements in the sequence, which was initially 2 and is 4 afterwards.

(0), 1, 2 ... 46, {47}, 48, 49, (52)

(0), 1, 2 ... 46, {47}, 49, (52)

(0), 1, 2 ... 46, {}, 48, 49, (52) [new]

(0), 1, 2 ... 46, {}, 49, (52) [new]

• The third one, 46, can't duplicate the number of valid arrangements in the sequence, because those combinations where neither 46, 47 and 48 are included are invalid.

(0), 1, 2 ... 45, {46}, 47, 48, 49, (52)

(0), 1, 2 ... 45, {46}, 47, 49, (52)

(0), 1, 2 ... 45, {46}, 48, 49, (52)

(0), 1, 2 ... 45, {46}, 49 (52)

(0), 1, 2 ... 45, {}, 47, 48, 49, (52) [new]

(0), 1, 2 ... 45, {}, 47, 49, (52) [new]

(0), 1, 2 ... 45, {}, 48, 49, (52) [new]

(0), 1, 2 ... 45, {}, 49, (52) [new]

Analyzing all the cases we checked that 46 can only provide another extra 0.75n, increasing the total by 1.75 rather than duplicating it.

We can also validate that mathematically:

If 47 provides n combinations:

• 46 was supposed to provide another n ones, to reach 2n in total.

However, it will only be able to provide part of them: another xn combinations, being x the number of 47 and 48 combinations where at least one of those optional adapters are present.

• 50% of the combinations provided by 47 didn't include the 47 adapter itself, that is 0.5n.
• 48 provided 0.5n combinations, and half of them didn't included 48. That is 0.25n

That means that x, or the number of combinations that include either 47 or 48, is 0.5n + 0.25n = 0.75n.

This rule can be generalized to (at least) any optional adapter that is used immediately before another 2 optional adapters, which is enough to solve our problem.

So, fixing Statement 2, we get:

Given   Given any sequence of adapters [N-Z] (N < O < P < ... < Z)
When    The first adapter is optional (and could be removed)
Then    The number of possible arrangements of the sequence [N-Z] is:
          a/ 1.75 2x the number of arrangements in the subsequence [O-Z]
             when the first two adapters in [O-Z] are also optional
          b/ 2x the number of arrangements in the subsequence [O-Z]
             otherwise

Implementation

Putting together both statements, we can implement the solution to the part 2 like this:

public string Solve_2()
{
    var descendingInput = File.ReadAllLines("input.txt").Select(int.Parse).OrderByDescending(_ => _).ToList();

    ulong totalNumberOfWays = 1;

    IEnumerable<int> GetOptionalAdapters()
    {
        for (int i = 1; i < descendingInput.Count - 1; ++i)
        {
            if (descendingInput[i - 1] - descendingInput[i + 1] <= 3)   // Statement 1
            {
                yield return descendingInput[i];
            }
        }
    }

    var optionalParametersList = GetOptionalAdapters().ToList();

    foreach (var optionalAdapter in optionalParametersList)
    {
        totalNumberOfWays += optionalParametersList.Contains(optionalAdapter + 1) && optionalParametersList.Contains(optionalAdapter + 2)
            ? 3 * totalNumberOfWays / 4     // Statement 2
            : totalNumberOfWays;
    }

    return totalNumberOfWays.ToString();
}

All the code shown here was taken from my Advent of Code 2020 repository.

Disclaimer: this way of resolving the puzzle is not necessarily the best one. As a matter of a fact, it's not.

• You can read here some mathematical concepts behind the puzzle.
• Some examples of implementations that follow that idea or similar ones are:
  • In JavaScript by Rubén Valseca.
  • In Kotlin by Natalia Vidal.
  • In PHP by Guillermo Ibáñez.
  • In Python by Javier Abadía.
  • In JavaScript + memes by Juan Antonio 'Muxed'.
  • In Rust by Mario Juárez.