DEV Community

Discussion on: Advent of Code 2020 Solution Megathread - Day 10: Adapter Array

Collapse
 
sleeplessbyte profile image
Derk-Jan Karrenbeld

I didn't really have fun today. My final solution in Ruby took way too long to get too and doesn't feel like an accomplishment. Rather it's a Dynamic Programming trick you just have to know or see, but not something to derive at logically or interestingly.

The grunt work is O(n), the sort is O(n log n), so sorting the input becomes the "limiting" factor. YMMV.

require 'benchmark'

adapters = File.readlines('input.txt').map(&:to_i).sort
maximum_jolt = adapters.last + 3
adapters.push(maximum_jolt)

=begin
# For the example input, here is what is being calculated:

target:  options                   => total options
     1:  only 1 option (0 + 1)     => 1
     4:  only 1 option (1 + 3)     => 1
     5:  only 1 option (4 + 1)     => 1
     6:  either 4 + 2 or 5 + 1     => 2
     7:  6 + 1 or 5 + 2 or 4 + 3   => 2 (6) + 1 (5) + 1 (4)
    10:  only 1 option (7 + 3)     => 4
    11:  only 1 option (10 + 1)    => 4
    12:  either 10 + 2 or 11 + 1   => 4 (10) + 4 (11)
    15:  only 1 option 12 + 3      => 8
    16:  only 1 option 15 + 1      => 8
    19:  only 1 option 16 + 3      => 8
    22:  only 1 option 19 + 3      => 8
=end

Benchmark.bm do |x|
  x.report(:part_1) do
    jolt_groups = adapters
      .each_with_index
      .map do |adapter, index|
        adapter - (index > 0 ? adapters[index - 1] : 0)
      end
      .group_by(&:itself)

    puts jolt_groups[1].length * jolt_groups[3].length
  end

  x.report(:part_2) do
    # Track the number of options to get to a target jolt value
    # and default to 0. The first jolt value is 0, and can only
    # be reached in one way.
    options = Hash.new(0)
    options[0] = 1

    adapters.each do |target_jolts|
      options[target_jolts] = [1, 2, 3]
        .sum { |difference| options[target_jolts - difference] }
    end

    puts options[maximum_jolt]
  end
end
Enter fullscreen mode Exit fullscreen mode
Collapse
 
nicklehmann profile image
Nick Lehmann

Hey, thank you very much! Could you give me a hint on how this "trick" is called?

Collapse
 
sleeplessbyte profile image
Derk-Jan Karrenbeld

Certainly. It's dynamic programming!

In this case, the problem can be broken down and simplified. We're not looking for the list of combinations. We are looking for the total number of options to build a valid connection between start (0) and end (max + 3).

For each adapter the following is true:

The number of paths to get to this adapter from the start is equal to the sum of the number of paths to get from the previous adapter to this one.

That means that this problem can be reduced. You can walk the list from start to end or end to start and only answer the question: paths to / paths from this adapter.

Storing the intermediate outcome is a typical dynamic programming this.

  • Determine number of paths between start and first adapter (always 1). Store it.
1:  only 1 option (0 + 1)     => 1
Enter fullscreen mode Exit fullscreen mode

Stored is the value 1 (ways to get to this index) on the index 1 (the joltage of the first adapter):

[1]
Enter fullscreen mode Exit fullscreen mode
  • Determine number of paths between the second - 1 and second - 2 adapters. This is the total number of paths from start to the second adapter. Store it.
4:  only 1 option (1 + 3)     => 1

4 - 1: 0
4 - 2: 0
4 - 3: 1
Enter fullscreen mode Exit fullscreen mode

Stored at index 4 (joltage) is the number of paths to this index: ways to joltage 4 - 3 plus ways to joltage 4 - 2 plus ways to joltage 4 - 1.

[1, 0, 0 , 0,1]
Enter fullscreen mode Exit fullscreen mode
  • Determine number of paths between the third - 1, third - 2 and third - 3 adapters. The sum is the total number of paths from start tot the third adapter. Store it.
5:  only 1 option (4 + 1)     => 1

5 - 1: 1
5 - 2: 0
5 - 3: 0
Enter fullscreen mode Exit fullscreen mode

Stored at index 5 (joltage) is the number of paths to this index: ways to joltage 5 - 3 plus ways to joltage 5 - 2 plus ways to joltage 5 - 1.

[1, 0, 0 , 0, 1, 1]
Enter fullscreen mode Exit fullscreen mode
  • Determine number of paths between the fourth - 1, fourth - 2 and fourth - 3 adapters. The sum is the total number of paths from start tot the fourth adapter. Store it.
6:  either 4 + 2 or 5 + 1     => 2

6 - 1: 1
6 - 2: 1
6 - 3: 0
Enter fullscreen mode Exit fullscreen mode

As you can see, here is where it becomes interesting. By storing the ways to get to a joltage in the array, when we need it's Γ©valuΓ©s, it doesn't need to calculate or worse, recalculate those values.

[1, 0, 0 , 0, 1, 1, 2]
Enter fullscreen mode Exit fullscreen mode

This is what is key in Dynamic Programming. You store intermediate results so that you don't need to do the work again. A classic example is solving Fibonacci.

You may want to solve it recursively, but the problem with doing that without memorisation step is that you'll be calculating the same values over and over. Instead, because each fib(n) equals fib(n-1) + fib(n-2), the pair input and output can reduce the recursive complexity of
O(2^n) to O(n). Each term is only considered once, instead of many many many times.

Thread Thread
 
nicklehmann profile image
Nick Lehmann • Edited

Oh wow, thank you very much πŸš€ Really didn't expect such a lengthy, comprehensible answer. So, thank you very much again! Just thought it's a special technique one could look up and practice but I guess I just have to look into dynamic programming again πŸ‘πŸ»

Thread Thread
 
sleeplessbyte profile image
Derk-Jan Karrenbeld

Yeah. Once you do a series of solutions using Dynamic Programming, you'll get a feel for it!

Thread Thread
 
honi profile image
Joni Bekenstein

Thanks for the clear explanation Derk-Jan Karrenbeld!

Here is my implementation in Python:

#!/usr/bin/env python3

import sys


if __name__ == '__main__':
    adapters = list(sorted(map(int, sys.stdin.read().strip().split('\n'))))
    adapters = [0] + adapters
    valid_arrangements = [1] * len(adapters)
    for index in range(1, len(adapters)):
        valid_arrangements[index] = sum(
            valid_arrangements[src_index]
            for src_index in range(max(0, index - 3), index)
            if adapters[index] - adapters[src_index] <= 3
        )
    print(valid_arrangements[-1])
Enter fullscreen mode Exit fullscreen mode