Instantly share code, notes, and snippets.

@jdp /deps.awk
Last active Jan 28, 2016

Embed
What would you like to do?
Some Assembly Required

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.

#!/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 }
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
#!/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); }
#!/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}" }
}
#!/usr/bin/env awk -f
FNR == NR { split($0, wire, " -> "); expr[wire[2]] = $0; next }
$1 in expr { print expr[$1] }
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment