Advent of Code 2020, Day 10 in Ruby

Question

I'm an amateur programmer making a career change into web development. I've found Advent of Code challenges are great way to sharpen my skills. I've cleaned up this solution for Day 10, 2020 as much as I know how.

Here's a link to the description of the problem and my solution on GitHub. I've also summarized the problem and attached my code below.

Part 1:

Begin with a list of unique ordered integers, called "joltage adapters." Find the difference between each adjacent pair of integers, and count up how many differences of 1 and how many differences of 3 there are. What is the product of the differences of 1 and differences of 3?

For example, examine the adapter list [0, 3, 4, 5, 7, 10, 13]. There are 2 differences of 1 and 3 differences of 3, making the answer 6.

Part 2:

We can connect "joltage adapters" into chains if their difference is 3 or less. For example, 8 can connect to 7, 6, or 5, but not 4. A chain of valid connections might look like:

15 => 14 => 12 => 11 => 9 => 8 => 5 => 4 => 3 => 1 => 0

Here's the question: given a list of "joltage adapters," how many valid chains can we make? As a constraint, chains must start with the greatest adapter in the list and end with the smallest.

I'm simplifying a few things in this description (for example: we always add the "outlet" and the "device" to the list with values of 0 and the highest value plus three), but it hopefully will be enough to understand the code.

The answers for part 1 and part 2 are 2380 and 48358655787008. My solution for part 2 uses both memorization and recursion. I make regular use of hashes throughout.

Here is my solution:

class Adapter_Array

    def initialize(filepath)
        @adapters = load_adapters(filepath)
    end

    def load_adapters(filepath)
        adapters = File.readlines(filepath, chomp: true)
            .map(&:to_i)
            .sort
        add_charger_and_device(adapters)
    end

    def add_charger_and_device(adapters)
        adapters.dup
            .unshift(0)
            .push(adapters.last + 3)
    end

    def part_1_answer
        jolt_differences[1] * jolt_differences[3]
    end

    def jolt_differences
        return @count if @count

        @count = Hash.new(0)
        @adapters.each_with_index do |adapter, i|
            next if is_charger?(adapter)
            prev_adapter = @adapters[i-1]
            @count[adapter - prev_adapter] += 1
        end
        @count
    end

    def part_2_answer
        ways_to_reach_charger(@adapters.last)
    end

    def ways_to_reach_charger(adapter)
        @memorized_ways = { 0 => 1 } unless @memorized_ways
        return @memorized_ways[adapter] if @memorized_ways[adapter]
        
        @memorized_ways[adapter] = lower_jolt_connections(adapter)
            .sum { |connection| ways_to_reach_charger(connection) }
    end

    def lower_jolt_connections(adapter)
        return [] if is_charger?(adapter)

        connections = []
        i = (to_index(adapter) - 1)
        potential_connection = @adapters[i]
        while valid_connection?(adapter, potential_connection) && i >= 0
            connections << potential_connection
            i -= 1
            potential_connection = @adapters[i]
        end
        connections
    end

    def valid_connection?(adapter_1, adapter_2)
        (adapter_1 - adapter_2).abs <= 3
    end

    def to_index(adapter)
        return @adapter_to_index_hash[adapter] if @adapter_to_index_hash

        @adapter_to_index_hash = Hash.new
        @adapters.each_with_index do |an_adapter, i|
            @adapter_to_index_hash[an_adapter] = i
        end
        @adapter_to_index_hash[adapter]
    end

    def is_charger?(adapter)
        adapter.zero?
    end

end

aa = Adapter_Array.new("input.txt")
puts aa.part_1_answer
puts aa.part_2_answer

And here is my input:

153
69
163
123
89
4
135
9
124
74
141
132
75
3
18
134
84
15
61
91
90
98
99
51
131
166
127
77
106
50
22
70
43
28
41
160
44
117
66
60
76
17
138
105
97
161
116
49
104
169
71
100
16
54
168
42
57
103
1
32
110
48
12
143
112
82
25
81
148
133
144
118
80
63
156
88
47
115
36
2
94
128
35
62
109
29
40
19
37
122
142
167
7
147
121
159
87
83
111
162
150
8
149

Answer 1

Advent of Code is a good idea to improve your coding skills. Good luck with switching careers. Here are some improvements.

Snake_Case vs CamelCase

In Ruby, modules and classes use CamelCase. You class name should be AdapterArray. Speaking of that, the class name is also not very speaking, maybe you can come up with something more descriptive?

Loading file in class

I personally would not load the file in the class but outside and just pass in the array. The advantage of this is that you can write tests easier.

class AdapterArray
  attr_reader :filepath

  def initialize(adapter_list)
    @adapter_list = adapter_list.sort
  end
end

adapter_list = File.readlines(filepath, chomp: true).map(&:to_i)
AdapterArray.new(adapter_list)

# in your tests you can do now
AdapterArray.new([10, 5, 1])

Magic value

A magic value are unique values with unexplained meaning or multiple occurrences which could (preferably) be replaced with named constants. In your code, e.g. the 1 and 3 are magic value you should give a name with extracting to a constant / method.

CHARGER_VALUE = 0

def adapter_list_with_charger_and_device
  adapters.unshift(CHARGER_VALUE).push(device_value)
end

def device_value
  adapter_list.last + 3
end

https://en.wikipedia.org/wiki/Magic_number_(programming)

JoltDifferences

Good idea to memoize this! I would maybe think about splitting it into two methods and use ||= instead of the guard clause.

def jolt_differences
  @jolt_differences ||= fetch_jolt_differences
end

def fetch_jolt_differences
  Hash.new(0).tap do |result|
    @adapters.each_with_index do |adapter, i|
      next if is_charger?(adapter)

      prev_adapter = @adapters[i-1]
      result[adapter - prev_adapter] += 1
    end
  end
end

Use attr_readers instead of instance variable

Instead of accessing the instance variables directly you should use attribute readers.

class AdapterArray
  attr_reader :adapter_list

  def my_method
    adapter_list # same as @adapter_list
  end
end

# to_index method Your to_index function can be simplified with a group_by. Also the name is not really reflecting what it does, I would name it something like adapters_grouped_by_index.

def adapters_grouped_by_index
      @adapters_grouped_by_index ||= adapters_with_charger_and_device.group_by.with_index { |_, i| i }
end

adapters_grouped_by_index[adapter]

tap method

I often see you using a pattern where you have a result object and then return it at the end of the method.

def some_method
  connections = [] # e.g. connection

  # do something with connection
  # connection << 1

  connections
end

You could replace this pattern with the tap method.

[].tap |connections|
  connections << 1
end

https://medium.com/aviabird/ruby-tap-that-method-90c8a801fd6a

or equals

Instead of a conditional assignment you can use a ||= (or equals)

@memorized_ways = { 0 => 1 } unless @memorized_ways

# vs

@memorized_ways ||= { 0 => 1 }

https://stackoverflow.com/questions/995593/what-does-or-equals-mean-in-ruby

Convention memoization value

It is a convention that the variable holding a memoized value has the same name as the method, sometimes prefixed with an underscore.

def jolt_differences
  return @count if @count

  @count = Hash.new(0)
  @adapters.each_with_index do |adapter, i|
      next if is_charger?(adapter)
      prev_adapter = @adapters[i-1]
      @count[adapter - prev_adapter] += 1
  end
  @count
end

This should really be @jolt_differences (or @_jolt_differences) instead of @count.

def jolt_differences
  return @jolt_differences if @count

  @jolt_differences = Hash.new(0)
  @adapters.each_with_index do |adapter, i|
      next if is_charger?(adapter)
      prev_adapter = @adapters[i-1]
      @jolt_differences[adapter - prev_adapter] += 1
  end
  @jolt_differences
end

private

Make all methods except part_1_answer and part_2_answer private as they should only accessed from inside the class.

By the way, I would also think about better names for these methods.

Answer 2

Problem 1

Often the key to getting a good solution is to find the right methods to use. For this problem there are two: Enumerable#each_cons and Enumerable#tally¹.

def product_of_freq_of_1_and_3(adapters)  
  freq = adapters.each_cons(2).map { |x,y| y-x }.tally
  freq[1].to_i * freq[3].to_i
end

adapters = [0, 3, 4, 5, 7, 10, 13]

product_of_freq_of_1_and_3 adapters
  #=> 6
product_of_freq_of_1_and_3 [0, 1, 10, 20]
  #=> 0
product_of_freq_of_1_and_3 [0, 1, 3, 4, 5, 6, 9, 10, 11, 14, 15]
  #=> 14

Note that if freq has no key 1, freq[1].to_i #=> nil.to_i => 0. Same for the key 3. See NilClass#to_i. One could alternatively write freq.fetch(1, 0) * freq.fetch(3, 0). See Hash#fetch.

The steps are as follows.

enum = adapters.each_cons(2)
  #=> #<Enumerator: [0, 3, 4, 5, 7, 10, 13]:each_cons(2)>

We can see the values that will be generated by this enumerator and passed to tally by converting it to an array:

enum.to_a
  #=> [[0, 3], [3, 4], [4, 5], [5, 7], [7, 10], [10, 13]]

Continuing,

arr = enum.map { |x,y| y-x }
  #=> [3, 1, 1, 2, 3, 3]
freq = arr.tally
  #=> {3=>3, 1=>2, 2=>1}
freq[1].to_i * freq[3].to_i
  #=> 2 * 3 => 6

You'll see that I defined no classes, accessors or instance variables. This seems to be a standalone problem, so a single method using local variables would seem to suffice.

Problem 2

Suppose:

joltage_adapters = [23, 22, 20, 15, 14, 12, 8, 5, 4, 3, 1, 0]

I understand a chain of adapters is an array of the form

chain = joltage_adapters[i, n]

for some integer n that satisfies

2 <= n <= joltage_adapters.size

and some i that satisfies

0 <= i < joltage_adapters.size - n

and for all j, i <= j < n,

chain[j] - chain[j+1] <= 3

For example, three chains in joltage_adapters would be joltage_adapters[0, 3] #=> [23, 22, 20], joltage_adapters[3, 2] #=> [15, 14] and joltage_adapters[9, 3] #=> [3, 1, 0]. [12, 8, 5] is not a chain because it does not satisfy the last condition above (12 - 8 > 3). Neither is [8] a chain because it does not have at least 2 elements.

As a first step, let's use Enumerable#slice_when to partition the elements of joltage_adapters into groups:

adapter_groups = joltage_adapters.slice_when { |x,y| x - y > 3 }
  #=> #<Enumerator: #<Enumerator::Generator:0x00007fb736118f10>:each>

We can see the objects that will be generated by this enumerator by converting it to an array.

adapter_groups.to_a
   #=> [[23, 22, 20], [15, 14, 12], [8, 5, 4, 3, 1, 0]]

Chains can be constructed within each of these three arrays but no chain can begin in one array and continue on to the next, because the difference between the last element of one array (e.g., 20) and the first element of the next (e.g., 15) is always greater than 3. Moreover, the number of chains that can be formed in each of the three arrays depends only on the size of the array. For example, it will be the same for [8, 5, 4, 3, 1, 0] as it would be for [ 8, 7, 5, 4, 2, 0], because the difference between successive integers never more than 3.

For the array

arr = [5, 4, 3, 1, 0]

we can compute the number of chains recursively:

• 0 chains in [0]
• 1 chain in [1, 0]:
  • [1, 0]
• 3 chains in [3, 1, 0]:
  • [3, 1] + 0 chains in [0] (1) +
  • [3, 1, 0] (1) +
  • [1, 0] (3 not in a chain) (1)
• 8 chains in [4, 3, 1, 0]:
  • [4, 3] + 1 chain in [1, 0] (2) +
  • [4, 3, 1] + 0 chains in [0] (1) +
  • [4, 3, 1, 0] (1) +
  • 3 chains in [3, 1, 0] (4 not in a chain) (3) +
  • 1 chain in [1, 0] (4 and 3 not in a chain) (1)
• 20 chains in [5, 4, 3, 1, 0]:
  • [5, 4] + 3 chains in [3, 1, 0] (4) +
  • [5, 4, 3] + 1 chain in [1, 0] (2) +
  • [5, 4, 3, 1] and 0 chains in [0] (1) +
  • [5, 4, 3, 1, 0] (1) +
  • 8 chains in [4, 3, 1, 0] (5 not in a chain) (8) +
  • 3 chains in [3, 1, 0] (5 and 4 not in a chain) (3) +
  • 1 chain in [1, 0] (5, 4 and 3 not in a chain) (1)

We can write a method to perform these calculation.

def nbr_chains(n)
  return 0 if n == 1
  return 1 if n == 2
  (n-3).downto(0)
       .each_with_object({ n=>0, n-1=>0, n-2=>1 }) do |i, nbr_from_index|
          nbr_from_index[i] =
            # chains beginning at index i
            ((i+1)..(n-1)).sum { |j| 1 + nbr_from_index[j+1] } +
            # chains beginning at index > i
            ((i+1)..(n-2)).sum { |j| nbr_from_index[j] }
        end[0]
end

nbr_chains([5, 4, 3, 1, 0].size)
  #=> 20 ({5=>0, 4=>0, 3=>1, 2=>3, 1=>8, 0=>20})
nbr_chains([23, 22, 20].size)
  #=>  3  ({3=>0, 2=>0, 1=>1, 0=>3})
nbr_chains([15, 14, 12].size)
  #=>  3  ({3=>0, 2=>0, 1=>1, 0=>3})
nbr_chains([8, 5, 4, 3, 1, 0].size)
  #=> 49 ({6=>0, 5=>0, 4=>1, 3=>3, 2=>8, 1=>20, 0=>49})

The hashes shown above are the final values of nbr_from_index before the value of 0 is extracted.

We therefore can count the number of chains with the following method.

def count_chains(joltage_adapters)
  joltage_adapters.slice_when { |x,y| x - y > 3 }
                  .sum { |a| nbr_chains(a.size) }
end

count_chains(joltage_adapters) #=> 55

^{1. tally made its debut in v2.7. To support earlier versions write freq = adapters.each_cons(2).with_object(Hash.new(0)) { |(x,y),h| h[y-x] += 1 }. See the form of Hash::new that takes a single argument (the default value) and no block.}

Answer 3

I'm an amateur programmer making a career change into web development.

Rather than give a detailed review of the existing code, I'll give you a succinct list of the advice I would have wanted to get at this stage, based on your code.

1. Avoid unnecessary abstractions. In particular....
2. Avoid unnecessary classes.
3. Avoid unnecessary helper methods.
4. Identify the essential algorithm, and strip away everything else to let that shine. In problem 1, it's just a map over differences. In problem 2, it's just a reduction of the sorted list.

# Read in the data.
d = DATA.readlines.map(&:to_i).sort.reverse
d = [0] + d + [d.last + 3]

# Part 1
diffs = d.each_cons(2).map { |a, b| a - b }
part1 = diffs.count(1) * diffs.count(3)

# Part 2
part2 = d.reduce({}) do |m, x|
  cnt = (1..3).map { |i| m[x+i] || 0 }.sum
  m.update(x => cnt == 0 ? 1 : cnt )
end.fetch(0)