Advent of Code - Year 2015, Day 07

Problem statement: http://adventofcode.com/2015/day/7

Part A

This is a really interesting problem statement. Technically, this puzzle falls into a computer science topic known as a dependency graph. This is type of problem is found in many areas of programming, and knowing how to identify this can help with finding a good solution to the problem at hand. Find out more here.

At first, you might think that you can evaluate the inputs in order and calculate the answer. However, the actual puzzle input provides the circuit definitions out of order, to prove that we are able to emulate the circuit board, and not just evaluate the statements as we parse them.

Now, there are three primary ways to solve this problem. First, we can use an iterative method whereby we foreach over all of the circuit definitions and attempt to calculate the value of each wire. If we are unable to evaluate the wire because one of the inputs has not been calculated, then we skip it. We do this repeatedly until we have evaluated every wire. Pseudo code here:

int numWires = wires.Length;  
var wireValues = new Dictionary<string, ushort>();  
while (wireValues.Count < numWires)  
    foreach (var w in wires)
        if (inputsCalculated(w))
            wireValues[w.output] = calculateWire(w);

The biggest problem with this method is that it checks each wire more than once, and how many times we do so would depend on how deep the dependency tree is. This can create performance problems, and definitely creates more work than is absolutely necessary. In the worst case scenario, where the dependency graph is completely linear (A->B->C->D, etc.), each wire will be visited as many times as there are wires. The other two ways to solve this both only evaluate each wire once.

The second way we can solve this dependency graph would be using a subscription model, or "top-down" approach. Alternatively, it can be referred to as doing the calculations "eagerly". In this solution, we would set up each wire to have a list of wires that need to know when the value of this wire changes. Then we trigger the wires that have constant value and recursively evaluate the related wires until all changes have been propagated. This model requires more framework to build it, but is very effective in an environment where inputs are changed on a regular to rapid basis and the outputs always need to be kept up to date; when a value is changed, only the objects that depend on it are evaluated. Pseudo code:

struct Wire { string Output; List<string> DependentUpon; ushort? Value; List<Wire> DependentWires; }  
Dictionary<string, Wire> wires = ParseInput().ToDictionary(w => w.Output);  
foreach (var w in wires)  
    foreach (var s in w.DependentUpon)
        wires[s].DependentWires.Add(w);

foreach (var w in wires.Where(w => w.Value.HasValue))  
    w.Evaluate();

// recursively evaluate each wire
void Wire.Evaluate()  
{
    var parentValues = DependentUpon.Select(s => wires[s].Value.Value);
    this.Value = CalculateValue(parentValues);
    foreach (var dw in w.DependentWires)
        dw.Evaluate();
}

The third way we can solve this puzzle is with an actual dependency graph, or the "bottom-up" approach. This method is also called doing the calculations "lazily". Instead of having each wire subscribe to the wires it is dependent upon, it simply records the dependencies. Evaluation of the value is delayed until it is absolutely needed. This can be useful when the calculation of each node is expensive, and we don't need to know each value all of the time. Also, this method is much easier to code. The downside to this method is that each value can only be calculated once, or you must use a propagation method such as option #2 above to invalidate the values so that future requests for the data know that the value must be recalculated. Pseudo code:

struct Wire { string Output; List<string> DependentUpon; ushort? Value; }  
Dictionary<string, Wire> wires = ParseInput().ToDictionary(w => w.Output);  
ushort Wire.GetValue()  
{
    var parentValues = DependentUpon.Select(s => wires[s].GetValue());
    this.Value = CalculateValue(parentValues);
}

Part B

Depending on if you used method 2 or method 3 above, this can be easy or difficult to include in the calculations. If method 3 is used, either invalidation must be used, or all of the definitions must be re-evaluated, so that the model is fresh for a new round of calculation. Before clearing the model, the value for wire A must be saved, and once the model is cleared, the definition for wire B must be set to the saved value. Once this is done, A may be re-evaluated.

If method 2 is used, wire B may simply be reset to the value calculated in wire A; this change will be provided to each dependent wire until wire A is "automagically" updated to the new value.

Regex

    @"^\s*(
        (?<assign>\w+) |
        (?<not>NOT\s+(?<not_arg>\w+)) |
        ((?<arg1>\w+)\s+(?<command>AND|OR|LSHIFT|RSHIFT)\s+(?<arg2>\w+))
    )
    \s*->\s*
    (?<dest>\w+)\s*$",

This regex is a bit more complicated than the previous ones, so I broke it out over multiple lines. I specified an option that allows the parser to ignore the whitespace in the string, and I will provide definition for the whitespace (\s+) where needed. Easy parts first. \s*->\s*: \s says that I want a whitespace character. This can be a space, a tab, or in some cases, even a new-line. Here, * says that I want any of the preceding value as many times as it exists, but if it doesn't exist, then I don't care. \s*->\s* would successfully match "->" or " -> ".

(?<dest>\w+)\s*$ - I've already explained how (?<dest>...) works. The \w inside means that I want any character that would go into an identifier, so letters [a-z] both upper and lower case, numbers [0-9], and the underscore _. Since I know that the destination for any wire definition is a string, \w+ is the appropriate way to select them. $ at the end means that I only want this regex to match if I can match it at the end of the string. For example: (?<dest>\w+)\s*$ would match "abc", or "123 " (matching the spaces due to \s*), but it would not match "xyz @", because there must be nothing between either the word or the spaces following the word and the end of the string, and @ is not a word character.

I've already explained how the | operator works, so the first half of the string should be straight forward: I want to match either: a) an identifier and only an identifier, and place this identifier in the named group assign; b) NOT followed by at least one space followed by an identifier, and place this identifier in the named group not_arg; or c) an identifier (labeled arg1) followed by one of the allowed commands: AND, OR, LSHIFT, or RSHIFT, followed by a second identifier (labeled arg2).

Finally, at the beginning of the definition you'll notice a ^, which works the same as the $ except to say that matching must start at the beginning of the string. Any definition which opens with ^ and closes with $ must match the entire string instead of matching part of the string. For example: @abc? would be successfully matched by \w+ for the abc part, but would not be matched by ^\w+$, since there are non-word characters between abc and the beginning and end of the string.

C#

source
Since we are only evaluating the wires twice (part A and part B), and it is easier to write the code, I used method 3. Instead of using ushort?, I used Lazy<ushort>. The nice thing about the Lazy<> object is that it accepts a function that defines how to obtain the stated value, but doesn't execute the function immediately. Once the value is requested, it evaluates the function and then caches the final value, so that the function doesn't have to be run again.

Notice that because of the simplicity of the model, the wire definitions only have to be evaluated once in ResetWires(); once the lines are parsed, the wires can be placed into the dictionary. The bottom up subscriptions are automatic. However, ResetWires() has to be run twice, once for each part, because the definitions have to be reset to ensure that the new value for wire B are propagated properly to all dependent wires.

F#

source
The F# version very closes resembles the C# version. The main thing I would like to note is how much cleaner the match syntax is than the switch (_) { } syntax.

Turner's Turns

Part A

Part B

Regex

C#

F#