Part 1:

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.

Steps:

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 values.

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 Parser to convert the input to an intermediate form and fill the Environment, and an 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 to Evaluator.

Parser simply split the input string and pushed it into the environment:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

    public void Parse(string instruction) {

        var parts = instruction.Split(new string[]{"->"}, StringSplitOptions.RemoveEmptyEntries);

        if (parts.Length != 2) {
            throw new ArgumentException("The instruction provided is malformed");
        }
        else {
            _environment.Add(parts[1].Trim(), parts[0].Trim());
        }
    }
}

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 int.

The initial code was like:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

public Wire Evaluate(string key) {
   ...
   if (instruction.Contains("AND")) {
       var r = Regex.Match(instruction, binaryPattern);
       if (r.Success && r.Groups.Count == 4) {
           var leftOperand = r.Groups[1].Value;
           var rightOperand = r.Groups[3].Value;

           var leftWire = Evaluate(leftOperand);
           var rightWire = Evaluate(rightOperand);
           return leftWire.And(rightWire, "result");
       }
}

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 Wire class.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

public int Evaluate(string key) {
   ...
   if (instruction.Contains("AND")) {
       var r = Regex.Match(instruction, binaryPattern);
       if (r.Success && r.Groups.Count == 4) {
           var leftOperand = r.Groups[1].Value;
           var rightOperand = r.Groups[3].Value;

           var leftWire = Evaluate(leftOperand);
           var rightWire = Evaluate(rightOperand);
           return leftWire & rightWire;
       }
}

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 int 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:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

public int Evaluate(string key) {
   ...
   if (instruction.Contains("AND")) {
       var r = Regex.Match(instruction, binaryPattern);
       if (r.Success && r.Groups.Count == 4) {
           var leftOperand = r.Groups[1].Value;
           var rightOperand = r.Groups[3].Value;

           var leftWire = Evaluate(leftOperand);
           var rightWire = Evaluate(rightOperand);
           var result = leftWire & rightWire;
           _environment[key] = result;
           return result;
       }
}

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 ;)