Day 7 of the Advent of Code challenge was perhaps the hardest so far. I came up with two different solutions, one with a rather hacky “retrying aggregate”, and the other with a recursive function memoizing the results in a dictionary. It was even a challenge trying to explain how I’d done it without the video going on too long, so hope this makes at least some sense.

My “retrying aggregate” approach in C#. Basically the idea is that if we can’t wire up a gate yet because we don’t have all its inputs, then we’ll put it to the back of the queue and try again later.

``````void Main()
{
var startState = new Dictionary<string, ushort>();
Func<string, ushort> eval = x =>
Char.IsLetter(x) ?  startState[x] : ushort.Parse(x);

Func<string[], ushort> assign = x => eval(x);
Func<string[], ushort> and = x => (ushort) (eval(x) & eval(x));
Func<string[], ushort> or = x => (ushort) (eval(x) | eval(x));
Func<string[], ushort> lshift = x => (ushort) (eval(x) << eval(x));
Func<string[], ushort> rshift = x => (ushort) (eval(x) >> eval(x));
Func<string[], ushort> not = x => (ushort) (~eval(x));

Func<string[], Func<string[], ushort>> selector = x =>
{
if (x == "->") return assign;
else if (x == "AND") return and;
else if (x == "OR") return or;
else if (x == "LSHIFT") return lshift;
else if (x == "RSHIFT") return rshift;
else if (x == "NOT") return not;
x.Dump();
throw new InvalidDataException(\$"Unrecognised command {string.Join(" ", x)}");
};

.Select(i => i.Split(' '))
.Select(i => new { Target = i.Last(), Action = selector(i), Params = i })
/* .Aggregate(startState, (acc, next) =>
{
acc[next.Target] = next.Action(next.Params);
return acc;
})*/

.RetryingAggregate(startState, (acc, next) =>
{
acc[next.Target] = next.Action(next.Params);
return acc;
})
.OrderBy(d => d.Key)
.Dump();

}
static class MyExtensions
{
public static TAcc RetryingAggregate<TAcc, TSource>(this IEnumerable<TSource> source, TAcc seed, Func<TAcc, TSource, TAcc> selector)
{
var retries = new Queue<TSource>(source);
while (retries.Count > 0)
{
TSource item = retries.Dequeue();
bool success = false;
try
{
seed = selector(seed, item);
success = true;
}
catch (KeyNotFoundException)
{
}
if (!success)
retries.Enqueue(item);
}
return seed;
}
}
``````

A different C# approach, storing the instructions in a dictionary, evaluating with a recursive function and memoizing the results.

``````Dictionary<string, string[]> instructions = new Dictionary<string, string[]>();
void Main()
{

instructions = realInstructions
.Select(i => i.Split(' '))
.ToDictionary(i => i.Last());
EvalInput("a").Dump(); // 3176

instructions = realInstructions
.Select(i => i.Split(' '))
.ToDictionary(i => i.Last());
instructions["b"] = new string[] { "3176", "->", "b" };
EvalInput("a").Dump(); // 14710
}

ushort EvalInput(string input)
{
Func<string, ushort> eval = x =>
Char.IsLetter(x) ? EvalInput(x) : ushort.Parse(x);
Func<string[], ushort> assign = x => eval(x);
Func<string[], ushort> and = x => (ushort)(eval(x) & eval(x));
Func<string[], ushort> or = x => (ushort)(eval(x) | eval(x));
Func<string[], ushort> lshift = x => (ushort)(eval(x) << eval(x));
Func<string[], ushort> rshift = x => (ushort)(eval(x) >> eval(x));
Func<string[], ushort> not = x => (ushort)(~eval(x));

var ins = instructions[input];
//\$"{input}:{String.Join(" ",ins)}".Dump();
ushort value;
if (ins == "->") value = assign(ins);
else if (ins == "AND") value = and(ins);
else if (ins == "OR") value = or(ins);
else if (ins == "LSHIFT") value = lshift(ins);
else if (ins == "RSHIFT") value = rshift(ins);
else if (ins == "NOT") value = not(ins);
else throw new InvalidDataException("Unrecognised command");
instructions[input] = new string[] { value.ToString(), "->", input };
return value;

}
``````

Finally, as usual I turned my solution into F#. I actually chose the `RetryingAggregate` approach, apart from for F# I got rid of the ugly catching on exception so I called it `deferAggregate`. Due to the time it took me to solve day 7, the F# version didn’t get quite as much refactoring as it deserved, but once again I did attempt to make use of some F# specific features like discriminated unions and pattern matching rather than doing a straight port from C#.

``````let realInstructions = "day7.txt" |> File.ReadAllLines

type arg =
| Constant of uint16
| Wire of string

type action =
| Assign of arg
| LShift of arg * arg
| RShift of arg * arg
| And of arg * arg
| Or of arg * arg
| Not of arg

type command = action * string

let parseArg (a:string) =
if Char.IsLetter (a.) then Wire a else Constant (uint16 a)

let parseCommand (c:string) =
let parts = c.Split(' ')
let toArg n = parseArg parts.[n]

let action =
match parts. with
| "->" -> Assign (toArg 0)
| "AND" -> And (toArg 0, toArg 2)
| "OR" -> Or (toArg 0, toArg 2)
| "LSHIFT" -> LShift (toArg 0, toArg 2)
| "RSHIFT" -> RShift (toArg 0, toArg 2)
| _ -> Not (toArg 1)
(action, parts |> Seq.last)

let evalCommand (state:Dictionary<string,uint16>) (action,target) =
let canEvalArg a = match a with | Constant _ -> true | Wire w -> state.ContainsKey(w)
let evalArg a = match a with | Constant n -> n | Wire w -> state.[w]

let canEvalAction =
match action with
| Assign a | Not a -> (canEvalArg a)
| And (a,b) | Or (a,b) | LShift (a,b) | RShift (a,b) -> (canEvalArg a) && (canEvalArg b)

if canEvalAction then
let result =
match action with
| Assign a -> evalArg a
| Not a -> ~~~ (evalArg a)
| And (a,b) -> (evalArg a) &&& (evalArg b)
| Or (a,b)  -> (evalArg a) ||| (evalArg b)
| LShift (a,b) -> (evalArg a) <<< int (evalArg b)
| RShift (a,b) -> (evalArg a) >>> int (evalArg b)
Some result
else
None

let deferAggregate commands =
let queue = new Queue<command>()
commands |> Seq.iter (fun c -> queue.Enqueue (c))
let state = new Dictionary<string,uint16>()
while queue.Count > 0 do
let c = queue.Dequeue()
let r = evalCommand state c
match r with | Some n -> state.[snd c] <- n | None -> queue.Enqueue(c)
state

let endState =
realInstructions
|> Seq.map parseCommand
|> deferAggregate

endState.["a"]
|> Dump

let endState2 =
realInstructions
|> Seq.map (fun i -> if i.TrimEnd().EndsWith("-> b") then "3176 -> b" else i)
|> Seq.map parseCommand
|> deferAggregate

endState2.["a"]
|> Dump
``````
Want to learn more about LINQ? Be sure to check out my Pluralsight course More Effective LINQ.