Advent of Code Day 7 Solved in C# and F#

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[0]) ?  startState[x] : ushort.Parse(x);
    
    Func<string[], ushort> assign = x => eval(x[0]);
    Func<string[], ushort> and = x => (ushort) (eval(x[0]) & eval(x[2]));
    Func<string[], ushort> or = x => (ushort) (eval(x[0]) | eval(x[2]));
    Func<string[], ushort> lshift = x => (ushort) (eval(x[0]) << eval(x[2]));
    Func<string[], ushort> rshift = x => (ushort) (eval(x[0]) >> eval(x[2]));
    Func<string[], ushort> not = x => (ushort) (~eval(x[1]));
    
    Func<string[], Func<string[], ushort>> selector = x =>
    {
        if (x[1] == "->") return assign;
        else if (x[1] == "AND") return and;
        else if (x[1] == "OR") return or;
        else if (x[1] == "LSHIFT") return lshift;
        else if (x[1] == "RSHIFT") return rshift;
        else if (x[0] == "NOT") return not;
        x.Dump();
        throw new InvalidDataException($"Unrecognised command {string.Join(" ", x)}");
    };
    
    File.ReadAllLines("day7.txt")
        .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()
{

    var realInstructions = File.ReadAllLines("day7.txt");

    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[0]) ? EvalInput(x) : ushort.Parse(x);
    Func<string[], ushort> assign = x => eval(x[0]);
    Func<string[], ushort> and = x => (ushort)(eval(x[0]) & eval(x[2]));
    Func<string[], ushort> or = x => (ushort)(eval(x[0]) | eval(x[2]));
    Func<string[], ushort> lshift = x => (ushort)(eval(x[0]) << eval(x[2]));
    Func<string[], ushort> rshift = x => (ushort)(eval(x[0]) >> eval(x[2]));
    Func<string[], ushort> not = x => (ushort)(~eval(x[1]));

    var ins = instructions[input];
    //$"{input}:{String.Join(" ",ins)}".Dump();
    ushort value; 
    if (ins[1] == "->") value = assign(ins);
    else if (ins[1] == "AND") value = and(ins);
    else if (ins[1] == "OR") value = or(ins);
    else if (ins[1] == "LSHIFT") value = lshift(ins);
    else if (ins[1] == "RSHIFT") value = rshift(ins);
    else if (ins[0] == "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.[0]) 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.[1] 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