Advent of Code (Day 7)

Check out out day 7 here.

This was an interesting challenge that had a tower (aka tree) of programs (aka nodes) structure. Each program had a name, weight, and pointed to other programs.

From the description:

Your input has the name (weight) and references (if present) in a text file like this:

pbga (66)
xhth (57)
ebii (61)
havc (66)
ktlj (57)
fwft (72) -> ktlj, cntj, xhth
qoyq (66)
padx (45) -> pbga, havc, qoyq
tknk (41) -> ugml, padx, fwft
jptl (61)
ugml (68) -> gyxo, ebii, jptl
gyxo (61)
cntj (57)

The tower ultimately looks like something like this.

         ugml - ebii
       /      \
      |         jptl
      |         pbga
     /        /
tknk --- padx - havc
     \        \
      |         qoyq
      |         ktlj
       \      /
         fwft - cntj

Challenge One

You had to find the root program, ie, the only program that isn’t referenced by another program.

Half the work was parsing through the input to get to the data, but the other step that was difficult was thinking about how to handle the modeling and referencing.

Thinking of the program model

Here is a nice version of what I came up with at the time; the real version looked like crap and I was racing through the challenge like a dummy… I loved it.

class Program
  def initialize(name, weight, references)
    # ...

if we just initialized each program, we can collect all the references and then just select the one program that isn’t one of the references. In my Program, the @references variable was just an array of strings of the names of the other programs being referenced.

referenced_programs = {|prog| prog.reference}.flatten
root = {|prog| !referenced_programs.include?}.first


Parsing the data

ktlj (57)
fwft (72) -> ktlj, cntj, xhth
qoyq (66)

Given the input liked like this, I iterated through each line and chopped the hell out of the strings.

input ='input.txt').split("\n")! { |program| program.split(' -> ') }

initial_programs = []

input.each do |(name_weight, references)|
  references = []
  references = references.split(', ') if references
  name, weight = name_weight.split(' ')
  weight = weight[1..-2].to_i
  programs << [name, weight, references}

Then I just took the initial_programs array and initialized a bunch of programs

class Program
  attr_accessor :name, :weight, :references

  def initialize(name, weight, references)
    @name = name
    @weight = weight
    @references = references

  # other stuff here ...
end! do |(name, weight, references)|, weight, references)

With all our programs initialized, it was a piece of cake.

Challenge Two

For this one, there were programs that were imballenced, meaning that references that didn’t all have the same total weight (self.weight, and weight of all the references up to that point in the tower). Here is where understanding the tree structure helped. I just needed a way to get find a program from it’s name. Program.find(name) # => program, and a bit of recursion.

def tree_weight
  if references.size == 0
    @tree_weight = self.weight
    tree_weights = do |name|

    @tree_weight = tree_weights.inject(:+) + self.weight

Anyway, my blog writing time is up so I’m going to bed. Happy holidays! Get me on twitter if you had any ?’s. @Jason_Data