Advent Of Code 2022 - Day 03

Dec 03, 2022

It's December. Time for snow, slippery roads, hot chocolate and cozy fire places. Also time for Advent of Code. An advent calendar with small, daily programming puzzles, growing progressively more difficult.

Every year I participate in a programming language I did not use for Advent of Code before, in order to learn new ways of doing things and to challenge myself. This year, that language is F#.

Day 03: Rucksack Reorganisation

Summary: Given a list of strings, for each string find which characters are common to both the left half and the right half of the string. Convert those characters to a priority, [a..z] having priority 1..26 and [A..Z] having priority 27..52. Sum the priorites.

Example input:

aAccbB
BbaacC

In the string aAccbB the character c occurs on both sides. It has priority 3 points. In BbaacC the character a occurs on both sides. It has priority 1. Summing those priorities results in 4.

Find the full description here.

Some of the built-ins in F# make this problem relatively easy. Splitting a string exactly in half can be done by treating it as a list of characters and then using List's splitInto function which splits a list into n equal parts.

F# also has set operations built-in, which we can use to determine which character appears on both sides. Convert each side to a set and find the intersection.

We can then convert the intersection to priorities and sum them.

There's a small twist in the conversion to priorities. Typical programming problems that make you convert characters to integers, do so in ASCII order. In ASCII order, however, [a-z] comes after [A-Z]. So rather than going for the obvious (but wrong in this case) Convert.ToInt32(chr) - Convert.ToInt32('A') + 1 we have to check if the character is lowercase and math based on that.

All together, this is what it can look like. A very straight forward list of steps. It does the trick, but I don't like all the occurrences of List.map.

let convertToPrio itemType =
    if Char.IsLower itemType then Convert.ToInt32(itemType) - Convert.ToInt32('a') + 1
    else Convert.ToInt32(itemType) - Convert.ToInt32('A') + 27

let solve1 (input: string list) =
    input
    |> List.map List.ofSeq
    |> List.map (List.splitInto 2)
    |> List.map (List.map Set.ofList)
    |> List.map Set.intersectMany
    |> List.map Set.toList
    |> List.map (List.map convertToPrio)
    |> List.map List.sum
    |> List.sum

Part 2

Summary: In part two we have to take the list of strings and form groups of three. For each we have to find which character occurs in all three strings. Then we have to sum the same priority conversion for each group.

The idea is the same as part 1. We convert the strings into sets and find their intersection. Then we convert the intersection to priorities and sum them.

F#'s Set.intersectMany takes an arbitrary number of sets so once again the language helps us.

Feeling like there must be a better way than writing all those List.map's, I grouped a few of them a single function.

let solve2 (input: string list) =
    input
    |> List.map List.ofSeq
    |> List.map Set.ofList
    |> List.chunkBySize 3
    |> List.map (fun group ->
        group
        |> Set.intersectMany
        |> Set.toList
        |> List.map convertToPrio
        |> List.sum)
    |> List.sum

Improvements

Repeat after me: "Strings are Sequences." At least they are in F#. Which means that if you want to do something to the list of characters, rather than the string, you can use the Seq module without having to convert the string first. This may be obvious to many F# users, but wasn't to me. Instead, I would use Seq.toList first and then operate on the list.

In this particular case that means we can skip List.ofSeq and instead immediately use Set.ofSeq for part 2. In part 1 we did slightly more, but there, too, we can simplify.

input
|> List.map List.ofSeq
|> List.map (List.splitInto 2)
|> List.map (List.map Set.ofList)

// Becomes

input
|> List.map (Seq.splitInto 2)
|> List.map (Seq.map Set.ofSeq)

The `>>` operator

All those List.maps's I wasn't happy about can also be simplified. the >> operator combines functions. foo >> bar returns a function that first executes foo and then calls bar with the result.

input
|> List.map ((Seq.splitInto 2)
             >> (Seq.map Set.ofSeq)
             >> Set.intersectMany
             >> Set.toList
             >> (List.map convertToPrio)
             >> List.sum)

It still looks a bit icky, but it's a definite improvement.

One final push

The key insight to improving the code came to me a bit later. It wasn't obvious to me at first because I wrote both parts in a slightly different way, but both parts do mostly the same thing.

Specifically, they convert a group of strings into sets of characters, finds their intersection, converts to priorities and sums them. The only difference is how the groups of strings are formed.

In part 1 the groups are formed by taking each line and splitting it in half. In part 2 the groups are formed by taking groups of three lines.

Knowing that we can write two helpers:

let formGroups formGroupFn lines =
    lines
    |> List.map (Seq.map convertToPrio)
    |> formGroupFn
    |> List.map (Seq.map Set.ofSeq)

let getSumOfIntersection groups =
    groups
    |> Seq.map (Set.intersectMany >> Seq.sum)
    |> Seq.sum

formGroups takes the lines from the input and forms groups based on the function passed. For good measure it also converts to priorities. There's not really a reason not to do this.

getSumOfIntersections does what its name implies. Note the use of the >> operator to prevent a second Seq.map.

With these two helpers, the solutions become almost identical two-liners:

[<AocSolver(2022, 3, Level = 1)>]
let solve1 (input: string list) =
    input
    |> formGroups (List.map (Seq.splitInto 2))
    |> getSumOfIntersection

[<AocSolver(2022, 3, Level = 2)>]
let solve2 (input: string list) =
    input
    |> formGroups (List.chunkBySize 3)
    |> getSumOfIntersection

Since they are nearly identical we could even abstract that away, but that hardly seems worth it.

Reflection

Today's problem was made relatively easy by the language. Writing out the steps and then converting them to code was almost a 1:1 translation. Trying to improve the look of the code in between solutions made it harder to refactor later because the obvious similarity dissapeared.

Looking through other solutions later, I found few of them that were more to the point than my own. I expected big improvements to be possible, but in the end even extracting all duplicate logic saved but a few lines.