Advent Of Code 2022 - Day 05

The input can be separated into two parts. Moves and crates. Starting with the easier one, moves, we see how scanf-like parsing would be very nice here. Alas, it doesn't exist in F#. A hackier solution is to split each line into words, convert them to integers (which will fail for the words), select only the ones for which conversion succeeds and put them into a nice data structure.

type Move = {
    Count: int;
    Src: int;
    Dst: int;
}

let parseMoveLine (line: string) =
    match line.Split(" ") |> Array.choose parseIntOpt with
    | [|count;src;dst|] -> { Count = count; Src = src - 1; Dst = dst - 1 }
    | _ -> failwith $"Failed to parse move line: {line}"

The crates are more annoying, mostly because not all stacks have the same height. You cannot visually see it, but thankfully the lines with missing crates are not truncated. They have the same length as the other lines.

Each spot is represented by three characters. A missing crate is represented by three spaces. A crate has the form [identifier] and finally a stack identifier is just a number surrounded by spaces. We don't have to parse the stack identifiers, but we also won't run into any problems if we just identify them as crates.

Each of the individual pieces is separated from the others with a space. There are various ways to hack together a parser for this. My way was to replace the three spaces representing an empty crate with [-], then remove all occurrences of [ and ] and finally split on space, removing empty entries.

let parseContainerLine (line: string) =
    line.Replace("    ", " [-]")
        .Replace("[", " ")
        .Replace("]", " ")
        .Split(" ", StringSplitOptions.RemoveEmptyEntries)

We aren't there yet. This gives us horizontal lists of crates, but we need vertical ones. Taking a hint from myself from earlier this Advent of Code and wanting to move on to solve the actual problem I hacked something together with mutation. I determined the amount of stacks, made an array of that width seeded with empty lists and built the stacks one line at a time. We have to start at the last line, because we want the tops to be the heads of the list.

let parseContainerLines (lines: string list) =
    let asSegments = lines |> List.map parseContainerLine
    let len = Array.length asSegments[0]
    let stacks = Array.init len (fun _ -> [])
    let filledStacks =
        List.foldBack (fun (elt: string array) stacks ->
            let mutable x = stacks
            for i = 0 to len - 1 do
                x <- (Array.updateAt i (elt[i] :: stacks[i]) x)
            x) asSegments stacks
    Array.map (List.reject ((=) "-")) filledStacks

Not pretty, but it works. We have to end by removing the crates with "-" as their identifier, because those were used as placeholders for missing crates.

With the parsing solved we can now solve the problem: perform moves on the stacks of crates in order to determine which crates end up on top of each stack after the set of moves has been completed.

Lists in F# behave like stacks. It's cheap to add/remove items at the front. Since the problem statement says that we can only move one crate at a time, that's exactly what we do. We take the first item of the source stack and prepend it to the destination stack. Once again with mutation because I couldn't really wrap my head around mapping / folding.

let step (move: Move) (stacks: string list array) =
    let mutable newStacks = stacks
    for i = 0 to move.Count - 1 do
        let container = List.head newStacks[move.Src]
        newStacks <- Array.updateAt move.Dst (container :: newStacks[move.Dst]) newStacks
        newStacks <- Array.updateAt move.Src (List.tail newStacks[move.Src]) newStacks
    newStacks

Getting the tops and glueing it all together is an exercise for the reader.

The loop in the first step function may hide it, but step and step2 are nearly identical. We can remove the loop from step and instead reverse the set of N crates taken from the front of the source list.

If the only difference is reverse or not reverse we can turn step into a higher order function, passing a transformation function as we go.

let step reorder (move: Move) (stacks: string list array) =
    let mutable newStacks = stacks
    let containers = List.take move.Count newStacks[move.Src] |> reorder
    newStacks <- Array.updateAt move.Src (List.skip move.Count newStacks[move.Src]) newStacks
    newStacks <- Array.updateAt move.Dst (List.append containers newStacks[move.Dst]) newStacks
    newStacks

The worst offenders are step and parseContainerLines, but I also had mutation in my original solve:

let solve1 (input: string list) =
    let (stacks, moves) = parseInput input
    let mutable mutableStacks = stacks
    for move in moves do
        mutableStacks <- step move mutableStacks
    getTopOfStacks mutableStacks

We begin by removing the mutation in step. While we're at it, we will also reorder the arguments so that we can pass step as an argument to List.fold. That way we can also fix the mutation in solve.

let step reorder (stacks: string list array) move =
    let containers = List.take move.Count stacks[move.Src] |> reorder
    stacks
    |> Array.updateAt move.Src (List.skip move.Count stacks[move.Src])
    |> Array.updateAt move.Dst (List.append containers stacks[move.Dst])

[<AocSolver(2022, 5, Level = 1)>]
let solve1 (input: string list) =
    let (stacks, moves) = parseInput input
    moves
    |> List.fold step stacks
    |> getTopOfStacks

Like many for-loops and a mutating variable, we can get rid of that in parseContainerLines by transforming it into a List.fold:

let parseContainerLines (lines: string list) =
    let asSegments = lines |> List.map parseContainerLine
    let len = Array.length asSegments[0]
    let stacks = Array.init len (fun _ -> [])
    let filledStacks =
        List.foldBack (fun (elt: string array) stacks ->
            [0..len-1]
            |> List.fold (fun stacks i -> Array.updateAt i (elt[i] :: stacks[i]) stacks) stacks)
            asSegments stacks
    Array.map (List.reject ((=) "-")) filledStacks

It turns out that F# has a built-in function for transposing a list of lists. It's conveniently called transpose and makes our life a lot easier.

let parseContainerLines (lines: string list) =
    lines
    |> List.map parseContainerLine
    |> List.transpose
    |> List.toArray
    |> Array.map (List.reject ((=) "-"))

Gone is the nested unreadable fold.

The above changes make the code a lot better, but all things considered the parsing code is still hacky. We can do better. And we should.

FParsec is a parser combinator library for F# and we'll use it to make the parsing for this problem significantly nicer.

Once again, the input consists of two parts. This time we'll work top to bottom.