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:

1873924193–1879728099
2042754084–2076891856
4112318198–4113899685
1039794493–1057170966
3791841434–3797494664
1518668516–1518748952
1946127596–1953926346
4058215215–4086224696
3429681642–3455096313
2599576643–2604275147
1800210010–1801990849
1761160149–1766904471
2774395403–2774748831
1520470679–1542287000
2343327790–2346083217

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

 

Links