Advent of Code F# – Day 16

(this post is part of the F# Advent Calendar project, check out all the other great posts there! And special thanks to Sergey Tihon for organizing this!)

The source code for this post (both Part 1 and Part 2) is available here and you can click here to see my solutions for the other Advent of Code challenges.

Description for today’s challenge is here.

 

Day 16

The input for today’s challenge looks like this:

Sue 1: goldfish: 6, trees: 9, akitas: 0

Sue 2: goldfish: 7, trees: 1, akitas: 0

Sue 3: cars: 10, akitas: 6, perfumes: 7

Sue 4: perfumes: 2, vizslas: 0, cars: 6

so to make parsing a little easier, I decided to use Regex with a bit of help from an active pattern:

day16_01

and we also need a type to represent what we remember about each Aunt Sue. (ok, we don’t strictly need one, a tuple can also do the trick, but as we’ll be passing the payload around I think it’s a lightweight record would be easier to work with in this case )

day16_02

For each line in the input:

Sue 1: goldfish: 6, trees: 9, akitas: 0

we need to fetch the number, and a key-value pair for each of the things we remember about that particular Aunt Sue. Something along the lines of:

day16_03

Now, we have all the information we can remember about all 500 Aunt Sue’s, as well as the facts our My First Crime Scene Analysis Machine has told us about the Aunt Sue that we need to send a thank you card for:

day16_04

Finally, we just need to go through all the Aunt Sue’s, and find the one that matches up with the facts.

As the requirement specified,

Things missing from your list aren’t zero – you simply don’t remember the value.

so if we can’t find a given key (from the list of facts) in the things we remember about an Aunt Sue we should just presume it to be true:

day16_05

 

Day 16 (Part 2)

Oh, what shock horror, that we managed to misread the machine’s output! Luckily, our code is written in F# and pattern matching makes the required change a piece of cake 

Since the new requirements are:

the cats and trees readings indicates that there are greater than that many, while the pomeranians and goldfish readings indicate that there are fewer than that many…

so we just need to tweak our logic slightly with additional match cases to cater for those two special cases:

day16_06

and job done! F# saves the day and Aunt Sue gets her thank you card! ho ho ho 

7 Comments

  1. Pingback: F# Advent Calendar in English 2015 | Sergey Tihon's Blog

  2. nowprovision   •  

    Would it a compile regex make sense if input 500 lines?

  3. Yan Cui   •  

    Good question, so I tried comparing the two versions and turns out using a compiled regex is actually slower in this case – might need a bigger input size to amortize the initial cost of compiling the regex.

    The current version runs between 7-9ms, whereas with compiled regex it takes between 10-13ms.
    At a 1000 lines of input, no-compiled-regex starts to see more volatile and swings between 10-30ms, but avgs around 15ms. The compiled-regex version is less volatile but also slower – avg around 22ms after a few runs.

    So there doesn’t seem to be any benefit from compiling the regex in this case, and according to this article from Jeff Attwood way back (http://blog.codinghorror.com/to-compile-or-not-to-compile/) there are also other trade-offs around memory footprint and startup time as well. I reckon this is worth a more comprehensive investigation/benchmark.

  4. Pingback: F# Weekly #51, 2015 | Sergey Tihon's Blog

  5. Pingback: F# Weekly #51, 2015-IT??

  6. Pingback: The week in .NET - 12/22/2015 - .NET Blog - Site Home - MSDN Blogs

  7. Pingback: ???? 2015? 12? 22? - Korea Evangelist - Site Home - MSDN Blogs

Leave a Reply

Your email address will not be published.