Some Assembly Required

readme.md

Advent of Code Day 7: Some Assembly Required

Strategy: Sort the input file topologically by the circuits' dependencies and then evaluate it sequentially instead of using a recursive solution.

The easiest way to sort a file topologically is with tsort(1), so we should build a set of small tools around it. Will need tools to sort the input file, and then another tool to evaluate the sorted file.

• deps.awk outputs the dependency graph of the circuits in the way tsort(1) understands.
• sort.awk outputs the sorted input file by merging it with the sorted dependencies using the FNR == NR trick.
• solve.rb evaluates the sorted input sequentially and outputs the final value on each circuit.

Usage example, finding the value on the circuit a:

./deps.awk < input | tsort | tac | ./sort.awk input - | ./solve.pl | grep '^a '

The solver is the meat of the program, so it makes sense to do it in a comfortable language. Can swap solve.pl for solve.rb. Similarities between them are interesting but highlight Ruby's heritage.

The pipeline is equivalent to monolith.rb but requires less programmer effort. The pipeline is a couple tools with a total of 7 lines of AWK and 15 lines of Perl (or ~30 lines of Ruby), compared to ~80 lines of Ruby in the monolith.

deps.awk

#!/usr/bin/env awk -f
/^[a-z]+ -> [a-z]+$/ { print $3, $1 }
/^[a-z]+ (AND|OR) [a-z]+ -> [a-z]+$/ { print $5, $3; print $5, $1 }
/^[0-9]+ (AND|OR) [a-z]+ -> [a-z]+$/ { print $5, $3 }
/^[a-z]+ (LSHIFT|RSHIFT) [0-9]+ -> [a-z]+$/ { print $5, $1 }
/^NOT [a-z]+ -> [a-z]+$/ { print $4, $2 }

monolith.rb

require 'set'
require 'tsort'

class Hash
  include TSort

  alias tsort_each_node each_key

  def tsort_each_child(node, &block)
    fetch(node).each(&block)
  end
end

deps = Hash.new { |h, k| h[k] = Set.new }
lines = []

ARGF.each do |line|
  if line =~ /^([a-z]+) -> ([a-z]+)$/
    deps[$1] ||= Set.new
    deps[$2].add $1
  elsif line =~ /^\d+ (?:and|or) ([a-z]+) -> (\w+)$/i
    deps[$1] ||= Set.new
    deps[$2].add $1
  elsif line =~ /^([a-z]+) (?:and|or) ([a-z]+) -> (\w+)$/i
    deps[$1] ||= Set.new
    deps[$2] ||= Set.new
    deps[$3].add $1
    deps[$3].add $2
  elsif line =~ /^(\w+) (?:lshift|rshift) \d+ -> (\w+)$/i
    deps[$1] ||= Set.new
    deps[$2].add $1
  elsif line =~ /^not (\w+) -> (\w+)$/i
    deps[$1] ||= Set.new
    deps[$2].add $1
  end
  lines.push line
end

weights = Hash[deps.tsort.each_with_index.collect { |v, i| [v, i] }]
weights.default = 0
circuit = {}
circuit.default = 0

lines.sort_by { |line|
  if line =~ /^([a-z]+) -> \w+$/
    weights[$1]
  elsif line =~ /^\d+ -> (\w+)$/
    weights[$1]
  elsif line =~ /^([a-z]+) (?:and|or) (\w+) -> \w+$/i
    [weights[$1], weights[$2]].max
  elsif line =~ /^\d+ (?:and|or) (\w+) -> (\w+)$/i
    weights[$1]
  elsif line =~ /^(\w+) (?:lshift|rshift) \d+ -> \w+$/i
    weights[$1]
  elsif line =~ /^not (\w+) -> \w+$/i
    weights[$1]
  else
    0
  end
}.each do |line|
  if line =~ /^(\d+) -> ([a-z]+)$/
    circuit[$2] = $1.to_i
  elsif line =~ /^([a-z]+) -> ([a-z]+)$/
    circuit[$2] = circuit[$1]
  elsif line =~ /^(\d+) (and|or) (\w+) -> (\w+)$/i
    case $2.downcase
    when 'and'
      circuit[$4] = $1.to_i & circuit[$3]
    when 'or'
      circuit[$4] = $1.to_i | circuit[$3]
    end
  elsif line =~ /^([a-z]+) (and|or|lshift|rshift) (\w+) -> (\w+)$/i
    case $2.downcase
    when 'and'
      circuit[$4] = circuit[$1] & circuit[$3]
    when 'or'
      circuit[$4] = circuit[$1] | circuit[$3]
    when 'lshift'
      circuit[$4] = (circuit[$1] << $3.to_i) & 0xffff
    when 'rshift'
      circuit[$4] = (circuit[$1] >> $3.to_i) & 0xffff
    end
  elsif line =~ /^not (\w+) -> (\w+)$/i
    circuit[$2] = ~circuit[$1].to_i & 0xffff
  end
end

circuit.each do |k, v|
  puts "#{k} #{v}"
end

solve.pl

#!/usr/bin/env perl -Wln
BEGIN { our $circuit = {} }
if (/^(\d+) -> ([a-z]+)$/) { $circuit{$2} = $1 }
elsif (/^([a-z]+) -> ([a-z]+)$/) { $circuit{$2} = $circuit{$1} }
elsif (/^(\d+) (AND|OR) (\w+) -> (\w+)$/) {
  if ($2 eq 'AND') { $circuit{$4} = $1 & $circuit{$3} }
  elsif ($2 eq 'OR') { $circuit{$4} = $1 | $circuit{$3} }
}
elsif (/^([a-z]+) (AND|OR|LSHIFT|RSHIFT) (\w+) -> (\w+)$/) {
  if ($2 eq 'AND') { $circuit{$4} = $circuit{$1} & $circuit{$3} }
  elsif ($2 eq 'OR') { $circuit{$4} = $circuit{$1} | $circuit{$3} }
  elsif ($2 eq 'LSHIFT') { $circuit{$4} = ($circuit{$1} << $3) & 0xffff }
  elsif ($2 eq 'RSHIFT') { $circuit{$4} = ($circuit{$1} >> $3) & 0xffff }
}
elsif (/^NOT (\w+) -> (\w+)$/) { $circuit{$2} = ~$circuit{$1} & 0xffff }
END { print "$_ $circuit{$_}" for (keys %circuit); }

solve.rb

#!/usr/bin/env ruby -n
BEGIN {
  circuit = {}
  circuit.default = 0
}

if ~/^(\d+) -> ([a-z]+)$/
  circuit[$2] = $1.to_i
elsif ~/^([a-z]+) -> ([a-z]+)$/
  circuit[$2] = circuit[$1]
elsif ~/^(\d+) (and|or) (\w+) -> (\w+)$/i
  case $2.downcase
  when 'and'
    circuit[$4] = $1.to_i & circuit[$3]
  when 'or'
    circuit[$4] = $1.to_i | circuit[$3]
  end
elsif ~/^([a-z]+) (and|or|lshift|rshift) (\w+) -> (\w+)$/i
  case $2.downcase
  when 'and'
    circuit[$4] = circuit[$1] & circuit[$3]
  when 'or'
    circuit[$4] = circuit[$1] | circuit[$3]
  when 'lshift'
    circuit[$4] = (circuit[$1] << $3.to_i) & 0xffff
  when 'rshift'
    circuit[$4] = (circuit[$1] >> $3.to_i) & 0xffff
  end
elsif ~/^not (\w+) -> (\w+)$/i
  circuit[$2] = ~circuit[$1].to_i & 0xffff
end

END {
  circuit.each { |k,v| puts "#{k} #{v}" }
}

sort.awk

#!/usr/bin/env awk -f
FNR == NR { split($0, wire, " -> "); expr[wire[2]] = $0; next }
$1 in expr { print expr[$1] }