Lately I have been having fun solving the AdventOfCode. I mainly used Haskell to solve each day so I can learn a bit about Haskell and as a byproduct VIM as well.
It was my first try to solve Day 7 using Ruby, and I wanted to find an elegant, idiomatic, short way to do it...
Before we start
Try it out, and if you like it let Eric know!
Exploring the problem
SPOILER ALERT: Yes, we are going to talk about Day 7 and how to implement the solution. Feel free to do it on your own first.
The problem describes a circuit board with instructions to apply signals to circuits using bitwise logic operations.
The operations are:
- 123 -> x means that the signal 123 is provided to wire x. - x AND y -> z means that the bitwise AND of wire x and wire y is provided to wire z. - p LSHIFT 2 -> q means that the value from wire p is left-shifted by 2 and then provided to wire q. - NOT e -> f means that the bitwise complement of the value from wire e is provided to wire f. Other possible gates include OR (bitwise OR) and RSHIFT (right-shift).
I implemented the solution in Haskell and found out that not only the parsing was the challenge but also the fact that you get a list of instructions that can be in any order, so some instructions when evaluated may result in having no signal (no value).
For example, let's consider the following sequence of instructions:
lx -> a 456 -> lx
When evaluating the first instruction, the wire
lx has no signal yet, so it has to be reevaluated later.
Of course you could create an evaluation tree but that seemed a bit too much for the problem at hand. So I decided to do the following:
- Parse instructions into commands
- Repeat evaluating commands until all pass
- Return the value of wire "a" from the board
The classy way
As soon as I read about instructions my mind started to race thinking about parsing and patterns.
My first thought was I could use the Interpreter Pattern to build a hierarchy of classes to evaluate expressions. But it seemed like an overkill.
Therefore, I decided to use classes to represent each command:
Each class has two methods with clear responsibilities:
parse(token1, token2, token3..., wire)Class factory method that parses the command and returns an instance of the command.
wireIt(board)Instance method that evaluates the command to assign the result of the operation to the target wire.
The constructor of the class stores the operands and target wire.
parse factory method receives the expected tokens. If the
cmd token matches the string
"AND" then returns an instance of
Abstracting the board
Evaluating the command was more complex because the values could be undefined. Some kind of validation was necessary.
I started using a
Hash as a CircuitBoard and then checking if the values were defined. It got a bit more complicated when I realized I had to parse values, because I could get
lx AND lb and also
1 AND ll.
Inspired by my Haskell solution I thought that a class that implements a short circuit evaluation could be very useful. That way, if one of the involved values was not defined the whole command was undefined.
To simplify board access and evaluation I created a
Board class that handles the assignment plus the lookup.
assign method takes a block that gets evaluated if all the values are defined, otherwise it is ignored.
This simplifies things quite a bit. Now the
wireIt implementation only applies the operation when all the values are defined:
Parsing instructions into commands
To parse the string I created a
parse method that splits the instruction into tokens (words) and finds a parsing factory method with the same amount of parameters that returns an actual instance of the command.
This is similar to a chain of responsibility where the parser tries to parse the instruction. If the parser cannot do it then the parser passes the instruction to the next parser in the chain until one of them succeeds. If no parser succeeds,
nil is returned.
The main loop
The last bit of the exercise is to keep evaluating all commands until there are no failing commands left.
You can see the complete source here.
The Ruby way
After finishing the implementation using classes I started to wonder what would be more idiomatic to Ruby.
Classes are fine, but I wanted to explore the dynamic aspect of Ruby and use
Instead of having a
Class factory method to parse, I declared
parse_xxx functions that return a string to be evaluated later for the expected command.
parse function now uses the
parse_xxx functions instead. The parse chooses the function that has the same amount of parameters as the tokens in the instructions and also returns a string with the expression to be evaluated.
The main loop
The main loop is very similar to the main loop of the classy version with the difference that to get the actual value,
eval is called for every command. If the command succeeds, the evaluation will return some kind of number.
The solution seems simpler than using classes. The strings make each command quite transparent.
Probably, even the parsing could be combined into one function and reduce the amount of functions in general.
You can see the complete solution here.
The functional way
After the Classy and Ruby way I wanted to see if I could be a bit more functional.
The approach this time was to parse the instruction into a
lambda that will evaluate the actual command.
I decided to reuse the
Board class from the first solution to make the value evaluation easier and implement a short circuit when a value is not yet defined.
Parsing instructions into commands
Third time’s the charm! I reduced the amount of parsing functions by having a binary parsing function that uses a hash to decide which operation to apply.
The hash lookup decides which operation to use.
parse function is similar to the Ruby way:
The main loop
Instead of using
call method is used on each
lambda to evaluate the command.
You can see the entire solution here.
The version I like the most is the
eval version because it is simple and straightforward.
The second best option, in my opinion, is the functional version because it uses the bitwise logic operators as functions.
Last but not least is the classy version. Using instances of classes does not seem to be necessary for this exercise because all parameters can be captured when creating the
lambda closure for each instruction.
Which one is would you choose?