Advent of Code 2016 Day 20 (F#)

Advent of Code 2016 – Day 19 (Swift)
Advent of Code 2016 Day 18 (Bash)

Advent of Code 2016 Day 17 (Ruby)

Advent of Code 2016 Day 16 (Scala)

Advent of Code 2016 Day 15 (Typescript)

Advent of Code 2016 Day 14 (Go)

Advent of Code 2016 Day 13 (Lua)
Advent of Code 2016 Day 12 (C#)
Advent of Code 2016 Day 11 (Groovy)

Advent of Code 2016 Day 10 (OcaML)

Advent of Code 2016 Day 9 (Factor)

Advent of Code 2016 Day 8 (c++)
Advent of Code 2016 Day 7 (Javascript)
Advent of Code 2016 – Day 6 (Julia)
Advent of Code 2016 – Day 5( Java 8)

Advent of Code 2016 – Day 4 (Perl 6)

Advent of Code 2016 – Day 3 (Clojure)
Advent of Code – Day 2 (Python 3)
Advent Of Code 2016 – Day 1(Haskell)

Day 20

Start: 12/26/2016

Finish 1/6/2017

Language: F#

SPOILER ALERT: If you have any inkling, any whatsoever, to work on the Advent of Code…. DO NOT READ THIS BLOG POST.  DO NOT LOOK AT MY GITHUB PROJECT.  It is no fun if you’re not solving it yourself, and you’ll feel so much better about yourself if you can figure it out without looking up an answer.  This blog post is not to give away the answer, but instead, is there for people to learn from.

As always, the following code is in my GitHub:

The Challenge

This challenge wasn’t too bad at first glance.  Given a list of blacklisted ranges of IP addresses, find the first IP address not in a blacklist.  I decided to give F# a go with this.  After OcaML didn’t go so well, I was determined to use my lessons learned and write some better code.

There was a long delay on this one due to Christmas, and a vacation in between, so I definitely missed my goal of 25 languages in 25 days.  But let’s see how far I can go.

Part 1

As usual, code first.

open System

let readlines  = System.IO.File.ReadAllLines("../day20.txt")
let toInts arr = uint32 arr
let getFilterFunction range =  (fun x -> x  (Seq.last range))
let uintRange = seq { System.UInt32.MinValue..System.UInt32.MaxValue} 
let allFiltersPass (filters:seqbool)>) (num:UInt32) = Seq.forall (fun f -> (f num)) filters
let skipIfOutOfRange filterFuncs = uintRange |> Seq.skipWhile (fun x -> (not (allFiltersPass filterFuncs x)) )

let main argv = 
        Seq.toArray readlines 
        |> (fun x -> x.Split[|'-'|])
        |> toInts
        |> getFilterFunction
        |> skipIfOutOfRange
        |> Seq.head
        |> printfn "%d"

This wasn’t too bad, as I read and sanitize the input to be integers.  Then I just start iterating through numbers from 0 to MAX_INT until I find one that doesn’t fit within all the functions

Part 2

Part 2 is much tougher.  Instead of finding the first non-blacklisted IPs, we needed a count of all non-blacklisted IPs.

The basic idea was to start at zero, and then find the first number that is not in a blacklisted range.  Then find the next number that is a range and subtract the difference.  Add that difference to the sum, and start again with the ranges that are left.

First, I had to implement a solve method to do the basic checking

let rec solve num accum  ranges = 
        let matching = (getFiltersMatching num ranges)
        let remainingRanges = (getRemainingRanges ranges num)
        match Seq.isEmpty matching with
        | true ->
            match (Seq.isEmpty remainingRanges) with
            | true -> accum + (System.UInt32.MaxValue - num) + 1u
            | false -> 
                let invalidNumber = (getFirstInvalidNumber remainingRanges)
                let diff = invalidNumber - num
                solve (getNextStartingNumber (invalidNumber+1u) remainingRanges) (accum + diff) remainingRanges
        | false ->     
            let lastValid = (getLastValidNumber matching)
            match lastValid with
            | System.UInt32.MaxValue -> accum
            | otherwise -> solve (lastValid+1u) accum remainingRanges

let main argv = 
        Seq.toArray readlines 
        |> (fun x -> x.Split[|'-'|])
        |> toInts
        |> solve 0u 0u
        |> printfn "%d"

This was ugly code, to be sure.  First I check if I’m already in a range, and if I am, either I’m at the end of my int range, or I need to recursively check the number out of my current range.  If I’m currently in a number not in a range, I need to check what the next invalid number is.  I subtract my current number from the invalid number and then add it to an accumulator.

I had to write a few utility functions to find information about the ranges

let getFirstInvalidNumber ranges =
         |> (fun r -> (Seq.head r))
         |> Seq.min

let getNextStartingNumber num ranges = 
        getFiltersMatching num ranges
        |> (fun r -> (Seq.last r))
        |> Seq.filter (fun x -> x >= num)
        |> Seq.min

let isNumBeforeRange num range =
        num  Seq.filter (fun r -> (isNumBeforeRange num r) )

let getLastValidNumber ranges =
         match (Seq.isEmpty ranges) with
         | false ->
                |> (fun r -> (Seq.last r))
                |> Seq.max
         | true -> System.UInt32.MaxValue

These were just straight forward sequence operations.



F# did not go as smoothly as I wanted.  I got part two wrong at first, and it took me a while to write ugly code.  The documentation was great though, and Visual Studio Code was a blast to write F# in (inline type annotations? Yes, please.)  I would definitely consider F# for a .NET project over OcaML.

I give myself a C+ on this one.  I had a vacation in the middle, but I still had some time on either end that I was working on this one.

Next up, PHP.



Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s