Advent of Code, day 7

Day7.fs

module Day7

open System
open System.Collections.Generic

type InputValue =
    | IntValue of uint16
    | Wire of string

type Gate =
    | Value of InputValue
    | Not of InputValue
    | Or of InputValue * InputValue
    | And of InputValue * InputValue
    | LShift of InputValue * uint16
    | RShift of InputValue * uint16

type Instruction =
    {
        GateString : string
        OutputTo : string
    }

type Operation =
    {
        Gate : Gate
        OutputTo : string
    }

let (|LiteralInt|_|) s =
    match UInt16.TryParse(s) with
    | (true, i) -> Some(i)
    | _ -> None

let (|WireName|_|) (s : string) =
    if (s.Length = 1 || s.Length = 2) && (String.forall Char.IsLetter s) then
        Some(s)
    else
        None

let (|WireNameOrLiteralInt|_|) s =
    match s with
    | LiteralInt(i) -> Some(IntValue(i))
    | WireName(w) -> Some(Wire(w))
    | _ -> None

let WireCircuit instructions =
    let state = new Dictionary<string, uint16>()

    let parseInstructionString lineNumber (ins : string) =
        let opPos = ins.IndexOf("->")
        if opPos <= 0 || opPos = ins.Length - 2 then
            failwith (sprintf "Invalid command on line %i: %s" lineNumber ins)

        let gate = (ins.[..opPos-1]).Trim().ToLower()
        let wire = ins.[opPos+2..].Trim().ToLower()
        let outputTo = match wire with
                       | WireName w -> w
                       | _ -> failwith (sprintf "Invalid wire on line %i: %s" lineNumber wire)

        { GateString = gate; OutputTo = outputTo }

    let tokenize (s : string) =
        s.Split([|' '|], System.StringSplitOptions.RemoveEmptyEntries)

    let getGate lineNumber tokens = 
        match tokens with
        | [| LiteralInt(i) |] -> Value(IntValue(i))
        | [| WireName(w) |] -> Value(Wire(w))
        | [| "not"; WireNameOrLiteralInt(iv) |] -> Not(iv)
        | [| WireNameOrLiteralInt(w1); "or"; WireNameOrLiteralInt(w2) |] -> Or(w1, w2)
        | [| WireNameOrLiteralInt(w1); "and"; WireNameOrLiteralInt(w2) |] -> And(w1, w2)
        | [| WireNameOrLiteralInt(w); "lshift"; LiteralInt(i) |] -> LShift(w, i)
        | [| WireNameOrLiteralInt(w); "rshift"; LiteralInt(i) |] -> RShift(w, i)
        | _ -> failwith (sprintf "Invalid gate definition on line %i: %A" lineNumber tokens)

    let parseInstruction lineNumber (ins : Instruction) =
        let gate = getGate lineNumber (tokenize ins.GateString)
        { Gate = gate; OutputTo = ins.OutputTo }

    let getIsInputValueAvailable iv =
        match iv with
        | IntValue iv -> true
        | Wire w -> state.ContainsKey(w)

    let getAreInputsSignalled operation = 
        match operation.Gate with
        | Value(iv) -> getIsInputValueAvailable iv
        | Not(iv) -> getIsInputValueAvailable iv
        | Or(iv1, iv2) -> (getIsInputValueAvailable iv1) && (getIsInputValueAvailable iv2)
        | And(iv1, iv2) -> (getIsInputValueAvailable iv1) && (getIsInputValueAvailable iv2)
        | LShift(iv, _) -> getIsInputValueAvailable iv
        | RShift(iv, _) -> getIsInputValueAvailable iv

    let getInputValue iv =
        match iv with
        | IntValue(v) -> v
        | Wire(w) -> state.[w]

    let wireUp op =
        let value = match op.Gate with
                    | Value(iv) -> getInputValue iv
                    | Not(iv) -> ~~~(getInputValue iv)
                    | Or(iv1, iv2) -> (getInputValue iv1) ||| (getInputValue iv2)
                    | And(iv1, iv2) -> (getInputValue iv1) &&& (getInputValue iv2)
                    | LShift(iv, shiftBy) -> (getInputValue iv) <<< int32(shiftBy)
                    | RShift(iv, shiftBy) -> (getInputValue iv) >>> int32(shiftBy)

        state.[op.OutputTo] <- value

    let operations = instructions 
                     |> List.mapi parseInstructionString
                     |> List.mapi parseInstruction

    while not(state.ContainsKey("a")) do
        for o in operations do
            if getAreInputsSignalled o then
                wireUp o

    printfn "All values:"

    state 
    |> Seq.sortBy(fun kvp -> kvp.Key)
    |> Seq.map(fun kvp -> sprintf "%s: %i" kvp.Key kvp.Value)
    |> Seq.iter(fun s -> printfn "%s" s)

    printfn ""
    printfn "Answer: %i" state.["a"]

Some small things about style, which are mostly my very personal opinion, but maybe you find some of it helpful:

As mentioned on Twitter the other day, generally leave out parentheses wherever you can (there are certainly exceptions, of course); one of the nice properties in F# is that it does with much less of them, which helps declutter the code. Take the LiteralInt pattern for example:

let (|LiteralInt|_|) s =
    match UInt16.TryParse s with
    | true, i -> Some i
    | _ -> None

I have recently started putting if, then and else on individual lines (if the whole thing isn't short enough for a single line) to better reflect the structure of the construct. I asked about this on Twitter a while back, and this was suggested a number of times; the "traditional" form that you used still seems to be the more common one, though.

let (|WireName|_|) (s : string) =
    if (s.Length = 1 || s.Length = 2) && (String.forall Char.IsLetter s)
    then Some s
    else None

While I generally don't pipe for just calling a single function, when calling a higher order function with a "qualifier" or "selector" function and a "proper" argument, I find it more understandable to pipe in the actual argument. When I read String.forall Char.IsLetter s, it took me a moment to make sense of those three pieces (which in this case was in part due to the fact that both functions involved aren't among the most commonly used in everyday F#). s |> String.forall Char.IsLetter makes it clearer that String.forall Char.IsLetter forms the function and s is the argument.

Also, you can generally leave out new in F# (which I think is a godsend, because new is the most annoying and redundant thing of all in C#, outside using anonymous types). You will only get a compiler warning with IDisposable implementations, saying you should put it in to make it clear that the object is disposable.

A very, very small thing: For method calls, I always put the parentheses directly after the identifier, as in C#, but for functions, I always give them a space, even if the argument needs to be parenthesized. There's one place in the code in particular:

state 
|> Seq.sortBy (fun kvp -> kvp.Key)
|> Seq.map (fun kvp -> sprintf "%s: %i" kvp.Key kvp.Value)
|> Seq.iter (fun s -> printfn "%s" s)

In this case, none of the functions is "complete" with just the lambda; it's always just the first argument for a two-argument function, and leaving out the space is inconsistent with cases where the "selector" function is a named function instead of a lambda.

An interesting thing is that you consistently start the "expression body" on a new line when declaring a function, but always on the same line when just binding a value, even when a pipe chain or a pattern match follows. The point of this is immediately obvious, but it will require pushing columns around should you ever decide to rename a value (or maybe turn a simple value binding into a function).