Advent of Code Day 18–Window, Scan and Collect
Today’s Advent of Code challenge was relatively kind, although time did not permit me to do much refactoring of my solution. I’ve been using all the test cases in the problem descriptions this year which has done wonders for the accuracy of my final answers (both right first time again today), but it does tend to shape the way you tackle to problem so that you can write tests for intermediate pieces.
In this challenge, we had to generate the next string in a sequence based on the previous string. This afforded another opportunity for the ever handy
Seq.windowed function which was ideal for giving us the relevant three characters from the line above to calculate the character on the next line:
let next = function | [| '^';'^';'.'|] | [| '.';'^';'^'|] | [| '^';'.';'.'|] | [| '.';'.';'^'|] -> '^' | _ -> '.' let generateNextRow previousRow = ("." + previousRow + ".") |> Seq.windowed 3 |> Seq.map next |> Seq.toArray |> System.String
Since we can generate the next line from the previous one, I wanted a function to emit a sequence of lines given a starting line. I tried a bunch of different ideas including recursive sequences,
Seq.unfold, but it turned out that
Seq.scan gave me the simplest route to what I wanted:
let generateRows startRow rows = Seq.init (rows-1) id |> Seq.scan (fun s _ -> generateNextRow s) startRow
We needed to be able to count all the ‘.’ characters in the sequence of strings, and
Seq.collect is ideal for flattening a sequence of sequences to allow us to count more easily:
let countSafe (data:seq<string>) = data |> Seq.collect id |> Seq.filter ((=) '.') |> Seq.length
Now we have all the bits in place to solve parts a and b of the puzzle. Thankfully there was no need to aggressively optimise for part b since it solved it in about 20 seconds, but there is of course plenty of room for improvement.
let solve startRow rows = generateRows startRow rows |> countSafe let input = "^.....^.^^^^^.^..^^.^.......^^..^^^..^^^^..^.^^.^.^....^^...^^.^^.^...^^.^^^^..^^.....^.^...^.^.^^.^" solve input 40 |> printfn "part a: %d" solve input 400000 |> printfn "part b: %d"
As usual code is up on GitHub and I welcome any suggestions for improvements.