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 LINQ Best Practices. ``let (|Matches|) pattern =  let rgx = Regex (pattern, RegexOptions.Compiled)  fun input -> [for m in rgx.Matches input -> [for g in m.Groups -> g.Value]]let (|Int32|_|) str = match System.Int32.TryParse str with true, value -> Some value | _ -> Nonelet (|UInt16|_|) str = match System.UInt16.TryParse str with true, value -> Some value | _ -> Nonetype Signal =  Value  of uint16| Var    of string| Not    of string| LShift of string * int| RShift of string * int| And    of string * string| Or     of string * stringlet common =  System.IO.File.ReadAllLines "day07.txt"  |> Seq.fold (fun acc -> function    Matches "(.+) -> (.+)" [[_; value; key]] ->    Map.add key      (match value with        Matches "^\d+\$"          [[UInt16 value]] -> Value value      | Matches "^[a-z]+\$"       [[var]]          -> Var var      | Matches "NOT ([a-z]+)"   [[_; var]]       -> Not var      | Matches "(.+) (.+) (.+)" binary           ->        match binary with          [[_; var ; "LSHIFT"; Int32 value]] -> LShift (var, value)        | [[_; var ; "RSHIFT"; Int32 value]] -> RShift (var, value)        | [[_; var1; "AND"   ; var2]]        -> And (var1, var2)        | [[_; var1; "OR"    ; var2]]        -> Or (var1, var2)        | _ -> failwith ""      | _ -> failwith "")      acc    | _ -> failwith "") (Map.add "1" <| Value 1us <| Map.empty)let extract =  let rec aux cont key map =    match Map.find key map with      Value value          -> cont (value, map)    | Var var              -> aux (fun (value, map) -> cont (value, Map.add key (Value value) map)) var map    | Not var              -> aux (fun (value, map) -> let value = ~~~value in cont (value, Map.add key (Value value) map)) var map    | LShift (var, offset) -> aux (fun (value, map) -> let value = value <<< offset in cont (value, Map.add key (Value value) map)) var map    | RShift (var, offset) -> aux (fun (value, map) -> let value = value >>> offset in cont (value, Map.add key (Value value) map)) var map    | And (var1, var2)     -> aux (fun (value1, map1) -> aux (fun (value2, map2) -> let value = value1 &&& value2 in cont (value, Map.add key (Value value) map2)) var2 map1) var1 map    | Or (var1, var2)      -> aux (fun (value1, map1) -> aux (fun (value2, map2) -> let value = value1 ||| value2 in cont (value, Map.add key (Value value) map2)) var2 map1) var1 map  aux idlet part1 () = common |> extract "a" |> fstlet part2 () = common |> Map.add "b" (Value <| part1 ()) |> extract "a" |> fst`` 