Advent of Code F# — Day 20

ps. look out for all my oth­er solu­tions for Advent of Code chal­lenges here.


Day 20

See details of the chal­lenge here.

Today’s input looks like this:


First, let’s read the input into a list of tuples rep­re­sent­ing the low­er-upper bound ranges.

Notice that I’ve also gone through the trou­ble of sort­ing the input by the low­er bounds. This way, as we iter­ate through the ranges we can build up an over­al range where:

  • the low­er bound is 0
  • the upper bound is the high­est upper bound val­ue we have processed so far

and where there are gaps between the cur­rent upper bound and the low­er bound in the next range, those are the allowed IPs val­ues.

eg. for my input the first 3 ranges are:

(0, 1888888)

(1888889, 1904062)

(1900859, 2087697)

  1. after pro­cess­ing (0, 1888888) the over­all range is 0–1888888
  2. (1888889, 1904062) forms a con­tin­u­ous range after 1888888, so the over­all range is now 0–1904062
  3. (1900859, 2087697) over­laps with the over­all range on the low­er bound, that’s ok, the over­all range is now 0–2087697

no gaps were found in the 3 ranges so far.

Sup­pose the next range is (2087700, 2100000), then a gap would appear and we will have 2 allowed IPs: 2087698 and 2087699.

To put that into code, here’s a find­Al­lowedIPs func­tion that will process all the sort­ed list of ranges and yield all the allowed IPs as a lazy sequence. ps. for part 2 where we need to find the no. of allowed IPs this is a O(n) solu­tion where n is the no. of black­list ranges.

To solve part 1, we need the first allowed IP.

let part1 = find­Al­lowedIPs input |> Seq.head


Part 2

How many IPs are allowed by the black­list?

let part2 = find­Al­lowedIPs input |> Seq.length



Liked this post? Why not support me on Patreon and help me get rid of the ads!