0 Comments Posted in:

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
Want to learn more about LINQ? Be sure to check out my Pluralsight course More Effective LINQ. I'm also speaking on LINQ at Techorama Netherlands 2018 on 3rd October, so I'd love to see you there if you can make it.
Vote on HN