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
- sort.awk outputs the sorted input file by merging it with the sorted dependencies using the
FNR == NRtrick.
- solve.rb evaluates the sorted input sequentially and outputs the final value on each circuit.
Usage example, finding the value on the circuit
./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.