December is a month of woodfires, celebration and of course... geeky puzzles! In this blog post I want to have a look at this year's first Advent of Code puzzle.

In tradition with earlier iterations of AoC, we start off with an easy task. We are provided a calibration document:

1abc2
pqr3stu8vwx
a1b2c3d4e5f
treb7uchet

(See The puzzle page for the full puzzle input)

Let's start by saving the document in input.txt, and loading it:

let input = System.IO.File.ReadLines "input.txt"

Part 1

We need to provide the sum of a calibration values in the calibration document; a calibration value is the first and last digit contained in the calibration string combined into a double-digit number. Important to note here: if we only have one number, we repeat it (e.g. treb7uchet = 77).

Let's start by creating a function that extracts the digits from a word:

let digits word =
    word |> Seq.filter (System.Char.IsDigit)

While it's tempting to convert our digits into integers here, we do not. Leaving it as it is makes converting it to a double-digit number easier.

We can then use our digits function in a function to extract our calibration values, by taking the first and last digits in the string, combining them into a single string, and converting it to an integer:

let calibrationValue input =
    let digits = digits input

    seq {
        (Seq.head digits)
        (Seq.last digits)
    }
    |> System.String.Concat
    |> int

Now all there is left is turning our input into calibration values using Seq.map, taking the sum of the values, and printing the results:

input
|> Seq.map calibrationValue
|> Seq.sum
|> printfn "%A"

That was easy!

Part 2

For me, the second part of the puzzle was a bit trickier. Due to a mistake in the software, some digits are written out in words. for example, twoapple5bee has calibration value 25.

An important thing to note here is that these written-out characters can overlap. For example oneight has calibration value 18. Before I realized this, I wrote a solution based on string replacement, which fails to cover these cases.

Instead, let's write a recursive function replaceWordsForDigits that checks whether a string starts with a written-out digit; if so, we replace the first letter with that digit. Otherwise we'll keep that digit as is. We then append the result of doing the same for the same string without the first character.

In the end, we'll be able to use it like this:

input
|> Seq.map replaceWordsForDigits
|> Seq.map calibrationValue
|> Seq.sum
|> printfn "%A"

Let's first create a list of tuples that we can use to map written-out words to digits:

let wordsToDigits =
    [ ("one", "1")
      ("two", "2")
      ("three", "3")
      ("four", "4")
      ("five", "5")
      ("six", "6")
      ("seven", "7")
      ("eight", "8")
      ("nine", "9") ]

We then create the recursive function; our base case is an empty string, which should just return an empty string

let rec replaceWordsForDigits input =
    match input with
    | String.empty -> String.empty
    | input ->
    //TODO: try to find the written-out digit that our string starts with
    //TODO: return the string, potentially with the first character replaced for a digit

We then try to find the digit the string starts with, by iterating over all of the options using List.tryFind; if we find one, we only need to return the second element of the tuple; we use Option.map to extract this.

let rec replaceWordsForDigits input =
    match input with
    | "" -> ""
    | input ->
        let firstDigit =
            wordsToDigits
            |> List.tryFind (fun (word, _) -> input.StartsWith word)
            |> Option.map snd
    //TODO: return the string, potentially with the first character replaced for a digit

We then define how to recurse the function: we call function again on the same string, without the first character. We return that result, prepending the digit we found, or simply putting the original first character back.

let rec replaceWordsForDigits input =
    match input with
    | "" -> ""
    | input ->
        let firstDigit =
            wordsToDigits
            |> List.tryFind (fun (word, _) -> input.StartsWith word)
            |> Option.map snd

        let recur = (input.Substring(1) |> replaceWordsForDigits)

        match firstDigit with
        | Some digit -> digit + recur
        | None -> input.Substring(0, 1) + recur

And there you have it! See the full solution on the bottom of the page.

Shortcomings

There are a few things about this solution that are not optimized for speed, but generally make the code more readable:

Instead of returning an altered string, it's easy to convert replaceWordsForDigits to return a filtered list of digit characters, which saves iterating over your values one extra time.

We also parse the full string into digits, even though we really just care about the first and the last; the strings used in the puzzle input are not very big, but for longer strings only parsing out the first and last digits can probably save you some time.

Full solution:

let input = System.IO.File.ReadLines "input.txt"

let digits word =
    word |> Seq.filter (System.Char.IsDigit)

let calibrationValue input =
    let digits = digits input

    seq {
        (Seq.head digits)
        (Seq.last digits)
    }
    |> System.String.Concat
    |> int

let wordsToDigits =
    [ ("one", "1")
      ("two", "2")
      ("three", "3")
      ("four", "4")
      ("five", "5")
      ("six", "6")
      ("seven", "7")
      ("eight", "8")
      ("nine", "9") ]

let rec replaceWordsForDigits input =
    match input with
    | "" -> ""
    | input ->
        let firstDigit =
            wordsToDigits
            |> List.tryFind (fun (word, _) -> input.StartsWith word)
            |> Option.map snd

        let recur = (input.Substring(1) |> replaceWordsForDigits)

        match firstDigit with
        | Some digit -> digit + recur
        | None -> input.Substring(0, 1) + recur

input
|> Seq.map replaceWordsForDigits
|> Seq.map calibrationValue
|> Seq.sum
|> printfn "%A"