Problem Solving with Advent of Code

The Seattle.rb Study Group has been doing Advent of Code. I’ve been really enjoying it as a diversion from my holiday tasks. I’ve finished fourteen of the twenty-five problems at this point and thought it would be fun to do a walkthrough of how I approach these problems.

This is a walkthrough of Problem 14. I chose this one because it is similar to Problem 5 which I had already solved.

I start by reading through the problem statement and then creating a directory and downloading the data file. Then I create a test data file from the examples on the website. This problem had a single string as the data file so writing to a file might have been overkill, but I like having a consistent process.

After that, it is time to start coding. I use my solution to problem 5 as a starting point and copy over what is relevant. I know I need an increasing integer (i) and some sort of loop. I’m not sure what the exit condition for the loop should be so I’m using loop do for now. Here’s the skeleton of the solution.

require 'digest'

data = File.read(ARGV[0]).strip

i = 0

loop do
  digest = Digest::MD5.hexdigest "#{data}#{i}"

end

Now I need to figure out which digests meet the requirements in the problem. Here’s the problem statement.

A hash is a key only if:

It contains three of the same character in a row, like 777. Only consider the first such triplet in a hash.

And one of the next 1000 hashes in the stream contains that same character five times in a row, like 77777.

I remember from one of Nell Shamrell’s Talks that there’s a way to use a capture in subsequent match in a regex. A bit of googling tells me that that I want a back reference in my regular expression. The syntax for that is \1. I use rubular.com to test some regular expressions and figure out that I can use /(\w)\1\1/ to match three of the same character in a row. Plugging that into the code gives me this:

require 'digest'

data = File.read(ARGV[0]).strip

i = 0

loop do
  digest = Digest::MD5.hexdigest "#{data}#{i}"

  if digest =~ /(\w)\1\1/ then

  end
end

If I find a hash that matches the first condition I need to loop through the next 1000 indices to see if any of those have 5 of the same character in a row. I use $1 to get the matched character and multiply it by five. This gives me the string I need to find. Then using a range (1..1000) to generate the numbers 1 to 1000 I can check the next 1000 hashes to see if they contain that string. If one does I’ve found a valid key, and so I output i.

I know that I’m going to be generating the hash for the same string multiple times. To make my code faster I cache the MD5 hashes in a global variable called $hashes.

require 'digest'

data = File.read(ARGV[0]).strip

i = 0
$hashes = {}

loop do 
  $hashes[i] ||= Digest::MD5.hexdigest "#{data}#{i}"

  if $hashes[i] =~ /(\w)\1\1/ then
    to_find = $1 * 5

    (1..1_000).each do |j|
      $hashes[i + j] ||= Digest::MD5.hexdigest "#{data}#{i + j}"

      if $hashes[i + j].include? to_find then
        puts i 
        exit
      end
    end
  end
end

Now I run this code using the test input abc. After 10 seconds it doesn’t spit out an answer, so I’m pretty sure I have a bug. I double check the code and realize I’m not incrementing i. Oops! I add an incrementor and also add an array to track the indices I’ve found that meet the constraints. I’m doing this because the problem asks for the index for 64th valid key. I can use a while loop and this array instead of the infinite loop I had before.

require 'digest'

data = File.read(ARGV[0]).strip

passwords = []
$hashes = {}

i = 0

while passwords.length < 64 do
  $hashes[i] ||= Digest::MD5.hexdigest "#{data}#{i}"

  if $hashes[i] =~ /(\w)\1\1/ then
    to_find = $1 * 5

    (1..1_000).each do |j|
      $hashes[i + j] ||= Digest::MD5.hexdigest "#{data}#{i + j}"

      if $hashes[i + j].include? to_find then
        passwords << i
        break
      end
    end
  end

  i += 1   # IMPORTANT!
end

puts passwords.last

I run the code using the test data (abc) and verify my answer matches the example. Now I run the actual data, input my answer, and it is correct. Yay! Since I have a passing test I push my code.

I look the code over and I’m not really happy with it. The global variable is especially bad. I refactor and move all the password finding logic into a class. That lets me use a class variable for the cache instead of a global. I end up with this version which is longer but cleaner. The cleaned up version also leaves me in a good place to start the extension to this problem.

require 'digest'

class PasswordGenerator
  attr_accessor :password_indices

  def initialize salt
    @salt             =    salt
    @hashes           = {}
    @password_indices = []
  end

  def generate_n_passwords n
    n -= 1   # Fencepost
    return if password_indices[n]

    i = password_indices.last || 0

    until password_indices[n] do
      @hashes[i] ||= Digest::MD5.hexdigest "#{@salt}#{i}"

      if @hashes[i] =~ /(\w)\1\1/ then
        to_find = $1 * 5

        (1..1_000).each do |j|
          @hashes[i + j] ||= Digest::MD5.hexdigest "#{@salt}#{i + j}"

          if @hashes[i + j].include? to_find then
            @password_indices << i
            break
          end
        end
      end

      i += 1   # IMPORTANT!
    end
  end
end

salt = File.read(ARGV[0]).strip

pg = PasswordGenerator.new salt

pg.generate_n_passwords 64

puts pg.password_indices.last

I enjoy coding puzzles but walking through my thought process is harder than I expected. In order to write this post I had to record my screen while I worked. Here’s the recording if you’d like to watch the whole process (including my solution for the extension problem).

Aja Hammerly