Day 20: Firewall Rules

author: Harshvardhan Pandit

license: MIT

You'd like to set up a small hidden computer here so you can use it to get back into the network later. However, the corporate firewall only allows communication with certain external IP addresses.

You've retrieved the list of blocked IPs from the firewall, but the list seems to be messy and poorly maintained, and it's not clear which IPs are allowed. Also, rather than being written in dot-decimal notation, they are written as plain 32-bit integers, which can have any value from 0 through 4294967295, inclusive.

For example, suppose only the values 0 through 9 were valid, and that you retrieved the following blacklist:

5-8
0-2
4-7

The blacklist specifies ranges of IPs (inclusive of both the start and end value) that are not allowed. Then, the only IPs that this firewall allows are 3 and 9, since those are the only numbers not in any range.

Given the list of blocked IPs you retrieved from the firewall (your puzzle input), what is the lowest-valued IP that is not blocked?

Solution logic

We start from 0 and continue upwards. The input contains integer ranges that are considered to be blacklisted, so we can skip them. Once we get to a blacklist, we can skip directly to the end of the input. We check at each iteration whether our value lies in any of the blacklisted ranges. To make it simpler to find and work on things, we sort the input rules according to their starting value. This allows us to not check further values if our current value is greater than the rule's ending value.

Parsing rules from input



In [1]:

    
import re
numbers = re.compile('(\d+)')

UPPER_LIMIT = 4294967295

with open('../inputs/day20.txt', 'r') as f:
    data = [
        tuple(map(
                int, numbers.findall(line))) 
        for line in f.readlines()]
    data.sort()



In [2]:

    
rule_index = 0
n = 0

while n <= UPPER_LIMIT:
    for i in range(rule_index, len(data)):
        low, high = data[i]
        if low <= n <= high:
            n += 1
            break
    else:
        print('answer', n)
        break









    



answer 4793564

Part Two

How many IPs are allowed by the blacklist?

Solution logic

Instead of breaking if none of the rules match, we keep a counter that we increment to count the number of IPs.



In [3]:

    
rule_index = 0
n = 0
ips = 0

while n <= UPPER_LIMIT:
    for i in range(rule_index, len(data)):
        low, high = data[i]
        if low <= n <= high:
            n = high + 1
            break
    else:
        ips += 1
        n += 1

print(ips)

== END ==