Firewall Rules

Advent of Code 2016 Day 20

Part 1

1. I have an idea. It may not work.
2. Does my idea work? We may never know.
3. Does my better idea work? Heck ya!

I have an idea. It may not work.

My idea, in parts:

Starting from the input as a list:

5-8
0-2
4-7

Sort the list of ranges of integers in ascending order by the lower boundary:

0-2
4-7
5-8

Initialize a set of unique values:

{ }

Add all integers in the first range:

{0,1,2}

Perform a check about the lower bound of the next range:

Is it two greater than the highest integer in the set?
  If so, the integer one higher than the highest integer is the answer
Else, it's either less than, equal to, or one higher than the highest in the set
  Add all integers to the set

Do this until a match is found...assuming the lowest integer less less than the highest possible integer in the set.

I wonder if this will work.

I'm excited to write it!

Does my idea work? We may never know.

That's because I thought of an even better one!

During the time I stepped away, I gained some clarity about the task.

And I've come up with a much faster algorithm that doesn't involve sets of numbers at all!

My better idea, in parts:

Starting from the input as a list:

5-8
0-2
4-7

Sort the list of ranges of integers in ascending order by the lower boundary:

0-2
4-7
5-8

Set a max as 0:

max = 0

Update max based on the first range:

max = Math.max(max, 2)

Continue as long as the lower bound of the next range is less than max + 1.

By the time that loop ends:

return max + 1

Why it's faster:

• No collections of millions/billions/trillions of numbers
• It only reads three numbers each iteration: 1) current max; 2) upper bound; 3) lower bound

The question is, will it work in practice?

Does my better idea work? Heck ya!

• It worked on the example list
• And it worked using my puzzle input!

Better yet, it only had to check 18 out of over 1005 ranges before terminating!

Part 2

1. From one...to all. Saw that coming.
2. Updating my Part 1 algorithm

From one...to all. Saw that coming.

I'm pretty confident this will only require a small adjustment to my algorithm:

• Right now, I use a do...while loop, stopping as soon as I find a non-blocked IP
• To find them all, I instead need to iterate through each range and collect all non-blocked IPs

Updating my Part 1 algorithm

Round 1

Set max as 0
Set ips as an empty set

For each range of ips
  If the lower bound of the range is greater than the integer one higher than max
    For each integer from max + 1 up to but not including the lower bound
      Add the integer to ips
  Update max to the higher integer between max and the upper bound in the range

Return the count of integers in ips

It generates the correct answer!

But - since the correct answer is just a count of the non-blocked IPs - I shouldn't have to store each IP.

I should just be able to increment a tally!

Round 2

Set max as 0
Set ips as 0

For each range of ips
  If the lower bound of the range is greater than the integer one higher than max
    Increment ips by the difference of the lower bound and max + 1
  Update max to the higher integer between max and the upper bound in the range

Return the count of integers in ips

It generates the correct answer, too!

Hey, wait a second.

I could combine algorithms for Parts 1 and 2, with only a minor performance sacrifice!

reduce() to the rescue again!

Round 3

For each range of ips, accumulate a 2-element array
  Element 1 is ips, an array
  Element 2 is max, starting as 0
  If the lower bound of the range is greater than the integer one higher than max
    For each integer from max + 1 up to but not including the lower bound
      Add the integer to ips
  Update max to the higher integer between max and the upper bound in the range

Return the first integer in the array, and the length of the array

In JavaScript:

let [ips,] = ranges.reduce((acc, range) => {
    if (range[0] > acc[1] + 1) {
      for (let i = acc[1] + 1; i < range[0]; i++) {
        acc[0].push(i)
      }
    }
    acc[1] = Math.max(acc[1], range[1])
    return acc
}, [[], 0])
return [ips[0], ips.length]

As a GIF:

I did it!!

• I solved both parts!
• I recognized this puzzle could be solved by sorting the ranges, then checking the range boundaries
• I wrote four algorithms!
• The last one solved both parts in two statements!
• All of my algorithms run faster than I anticipated at the onset!

This puzzle made me feel like I went from Beginner to Expert Computer Programmer:

• At first, I thought I'd have to evaluate and store a collection containing trillions of integers!
• By the end, I wrote a combined algorithm that only evaluates a fraction of the 2000 integers in my puzzle input!