# Problem Solving with Advent of Code

> Last updated: 2016-12-16

The Seattle.rb Study Group has been doing [Advent of Code](http://adventofcode.com/2016). 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](http://adventofcode.com/2016/day/14). I chose this one because it is similar to [Problem 5](http://adventofcode.com/2016/day/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](https://www.youtube.com/watch?v=cZW-Y37R4B0) 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](http://www.regular-expressions.info/backref.html) in my regular expression. The syntax for that is `\1`. I use [rubular.com](http://www.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).

Please enable JavaScript to view the [comments powered by Disqus.](https://disqus.com/?ref_noscript)

 ![Aja Hammerly](/img/traditionalheadshot.jpg)

Aja Hammerly

Seattle, WA

### library\_books Series Index 

- [Developer Relations](/series#developer-relations)4
- [Machine Learning Basics](/series#machine-learning-basics)3
- [Battleship](/series#battleship)5
- [Talks I Love](/series#talks-i-love)6
- [Algorithms with Auntie Aja](/series#algorithms-with-auntie-aja)3
- [Ruby and GCP](/series#ruby-and-gcp)5
- [Playing with Data](/series#playing-with-data)3
- [Kubernetes & Rails](/series#kubernetes-rails)3
- [Learn To Code Resources](/series#learn-to-code-resources)3
- [Testing Anti-Patterns](/series#testing-anti-patterns)5