This part took the most time till now. It presents the user with a small DSL which has to be solved because little Bobby Tables cannot solve it.
My first thought was to solve it by Algebraic Data Types since the operations and data are essentially recursive and pattern matching would have helped here too. But instead of jumping from one language to another, I decided to go ahead with C# right now.
The solution I came up with was recursive in nature and initially I
thought of using a
Wire class to abstract away the details – A wire
would have a signal and would interact with other =Wire=s using And, Or,
Shift, etc. operations. The initial approach I was thinking of required
the evaluations of actual
Signal values to be deferred since the wires
are defined in random manner in the input file. The correct approach (in
hindsight, anyway) was to use
Lazy<int> as the holder of the evaluated
Since we need a mapping of wires to their signals, a
Dictionary<string, int> made sense, but that would mess up the lazy
evaluation of operations, so I had to change it to
Dictionary<string, string> with the values being evaluated recursively
just when these were to be used. This was also going to be the
environment which held the entire structure.
There were two other classes which would be required: A
convert the input to an intermediate form and fill the Environment, and
Evaluator to evaluate the expression by reading the values defined
in the environment.
Initially the Parser was fat because it was trying to both parse and
minimise the string-expressions, but that approach would have been
wasteful. After some refactoring, almost all of the code was moved from
Parser simply split the input string and pushed it into the environment:
During this time, I also removed the laziness from
Wire because the
strings could be evaluated on need basis anyway.
Evaluator did the heavy lifting of evaluating the string-expressions.
Now initially I was returning a
Wire but that posed problems with the
final normalised expressions since these were supposed to be
The initial code was like:
So I changed the code to return
int instead of
Wire. Now the
expressions were evaluated and the operations were performed at the
point. This totally removed the dependency on the
Now at this point the sample/testing code provided on the website was
working perfectly but the actual test input was not. There was some sort
of infinite recursion happening (as noted by
Writeline calls). These
calls were also happening when I was returning
Wire instead of
but the problem of not being able to return
int was bigger at that
point than looking at this recursion.
All the test cases at this point were passing, even with some nested
input so I was not able to understand what really could be the problem.
Moreover, the problem was with the simplest expressions of type:
19345 -> b and others. It kept me confused for close to an hour.
I thought of just deleting everything and starting from scratch, but since this problem was in my mind over the weekend, I knew it would be difficult to switch the context and come up with a wildly different solution. And I knew that the solution was going to be similar to what I had right now – recursively parse and evaluate expressions.
Anyhow, I went for a walk, came back and started looking at the code, and then it struck me! The dictionary was populated the first time, and the values never got updated. Therefore, any expression which had been calculated was essentially thrown away. If it was part of another expression, it kept getting recalculated with the normalised/reduced value never used.
Finally the code became:
And I came out of the infinite loop! The code is present at github and the Evaluator requires a bit of cleanup, but I think that can wait ;)
Author Tushar Tyagi
LastMod Nov 1, 2016