Solving Advent of Code 2020 - Day 10
Tags: adventofcode, competitiveprogramming, codingpuzzle, dotnet
Published: 2020-12-11 00:14:04

---
published: true
title: Solving Advent of Code 2020 - Day 10
description: My solutions to Day 10 of Advent of Code 2020
canonical_url: https://eduherminio.github.io/blog/solving-aoc-2020-day-10/
cover_image: https://dev-to-uploads.s3.amazonaws.com/i/iadjbdo8ssj43c8913aw.PNG
tags: adventofcode, competitiveprogramming, codingpuzzle, dotnet
---

## Why Day 10

Not only I've found [Day 10 of this year's Advent of Code](https://adventofcode.com/2020/day/10) 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](https://adventofcode.com/2020/day/10) 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:

```csharp
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:

```txt
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:

```txt
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](https://twitter.com/ericwastl), 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:

```txt
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:

```csharp

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](https://github.com/eduherminio/AoC2020/blob/main/src/AoC_2020/Day_10.cs).

----

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](https://www.reddit.com/r/adventofcode/comments/ka9pc3/2020_day_10_part_2_suspicious_factorisation/gf969fr/) some mathematical concepts behind the puzzle.
- Some examples of implementations that follow that idea or similar ones are:
  - [In JavaScript](https://github.com/rubnvp/advent-of-code-2020/blob/main/day-10/main.js) by [Rubén Valseca](https://github.com/rubnvp).
  - [In Kotlin](https://github.com/erikiva/advent-of-code/blob/master/2020/src/dev/erikiva/aoc2020/Day10.kt) by [Natalia Vidal](https://github.com/erikiva).
  - [In PHP](https://github.com/guillermoig/AoC2020/blob/main/src/AoC-D10/AoC-D10-02.php) by [Guillermo Ibáñez](https://github.com/guillermoig).
  - [In Python](https://github.com/jabadia/adventOfCode2020/blob/main/d10/d10p2.py) by [Javier Abadía](https://javierabadia.medium.com/advent-of-code-d%C3%ADa-10-d82063d9ab19).
  - [In JavaScript + memes](https://github.com/juananmuxed/adventofcode-2020/blob/master/days/10/problem10.js) by [Juan Antonio 'Muxed'](https://github.com/juananmuxed).
  - [In Rust](https://github.com/mariomka/AdventOfCode2020/blob/master/day10/src/lib.rs) by [Mario Juárez](https://github.com/mariomka).