DEV Community

Cover image for Adapter Array
Robert Mion
Robert Mion

Posted on

3 2

Adapter Array

Advent of Code 2020 Day 10

Try the simulator for Part 2 using NullDev's algorithm

Simulator of NullDev's Part 2 algorithm

Task: Solve for X where X =

  1. The product of the count of 1- and 3-integer differences between sorted jolt measures
  2. The total number of distinct ways you can arrange the adapters

Example input

16
10
15
5
1
11
7
19
6
12
4
Enter fullscreen mode Exit fullscreen mode

It represents:

  • A collection of adapters
  • Each of their output joltage

Part 1

  1. Confusion, then clarity, then confidence
  2. Writing a working algorithm

Confusion, then clarity, then confidence

  • Confusion: The introductory sentences of this puzzle made me concerned that I'd have no idea where to begin
  • Clarity: The walkthrough using the example input helped me understand what the rules of this puzzle were
  • Confidence: I knew immediately how I would solve it algorithmically - and thankfully my algorithm worked!

Writing a working algorithm

Process the input into a sorted array of numbers

Insert two values: one at the beginning and another at the end

Accumulate a 3-element array representing tallies for each 1-, 2- and 3-integer difference between each subsequent value

Return the product of the integers tallying all 1- and 3-integer differences
Enter fullscreen mode Exit fullscreen mode

Here's a visualization of my algorithm:

Part 1 algorithm visualization

Part 2

  1. I should have seen that coming
  2. I thought I figured it out
  3. I knew it was that simple!
  4. I had to see how it worked

I should have seen that coming

  • When Part 1 feels easy - to me! - it is often a sign that Part 2 is a test of speed...which I'm often unequipped to solve
  • Given the 1, 2 and 3-integer differences, it should have been clear that Part 2 would be a test of 'how many possible arrangements?'

I thought I figured it out

Using the first example input as reference, the numbers in order are:

1, 4, 5, 6, 7, 10, 11, 12, 15, 16, 19
Enter fullscreen mode Exit fullscreen mode

My faulty logic followed this path toward a solution:

Legend:
0 numbers in-between = 1
1 number in-between  = 2
2 numbers in-between = 4

1 - 4:   0 -> 1
4 - 7:   2 -> 4
7 - 10:  0 -> 1
10 - 12: 1 -> 2
12 - 15: 0 -> 1
15 - 16: 0 -> 1
16 - 19: 0 -> 1

1 * 4 * 1 * 2 * 1 * 1 * 1
4 * 2
8
Enter fullscreen mode Exit fullscreen mode

Sadly, using this formula on the second example produced ~2000, not 19208.

I knew it was that simple!

Thankfully, my go-to JavaScript solver, NullDev, wrote an elegant, sub-5-line solution that I felt compelled to fully understand...using simulation!

Create step, a 1-element array containing the value 1
For i from 0 to the maximum value in the sorted array of numbers from the input
  Set j to i + 1
  While the number at location j in the sorted array is less than or equal to i + 3
    Set the item at location j in step equal to the sum of the item at location i in step and either the item at location j in step or 0
    Increment j
Return the last value in step
Enter fullscreen mode Exit fullscreen mode

I was confused about how NullDev's algorithm worked when reasoning about it in my head.

Even after using console.log at the end to show the filled step array, I still didn't see what it was doing in each iteration.

I knew I needed to simulate each iteration.

I had to see how it worked

  • Re-factoring NullDev's code into if...else clauses instead of combination of for and while loops wasn't too difficult
  • The result is a simulator that renders a list which grows taller and always shows the last value at the top
  • It finally helped me realize how NullDev's algorithm goes '3 steps forward, 2 steps back' in a way to continually double each value

Try the simulator for Part 2 using NullDev's algorithm

Simulator of NullDev's Part 2 algorithm

Seeing NullDev's solution showed me that I was 'on to something' in my 1-2-4 doubling logic. Though, clearly my approach was too shallow.

I may not have solved Part 2, but I had fun noodling around with this puzzle and simulating another solver's algorithm.

Sentry image

See why 4M developers consider Sentry, “not bad.”

Fixing code doesn’t have to be the worst part of your day. Learn how Sentry can help.

Learn more

Top comments (0)

👋 Kindness is contagious

Please leave a ❤️ or a friendly comment on this post if you found it helpful!

Okay