Solution for Advent of Code 2016 - Day 20: Firewall Rules

Link to the puzzle text

Part 1

In this puzzle, we have a blacklist of IP addresses and want to know which addresses are still allowed. The blacklists consists of possibly overlapping ranges. The answer is the smallest still allowed address.

We iterate over all IP addresses starting from 0 to 2^32 - 1. If we find an addresses blacklisted by a range, we continue our address after the upper bound of the range. We also sort the ranges by the lower bound beforehand, so once we hit an address not blacklisted, we have our solution.

def get_allowed_ip(ranges):
    ranges.sort()
    range_index = 0
    ip = 0
    while ip < 2 ** 32:
        lower, upper = ranges[range_index]
        if ip >= lower:
            if ip <= upper:
                ip = upper + 1
                continue
            range_index += 1
        else:
            return ip

Part 2

In part 2 we should return the number of all allowed addresses instead of just the first.

We modified the solution above to add allowed addresses to a list. Simply counting would also work, but this way we can still use the function as solution for part 1.

def get_allowed_ips(ranges):
    ranges.sort()
    range_index = 0
    
    allowed_ips = []
    
    ip = 0
    while ip < 2 ** 32:
        lower, upper = ranges[range_index]
        if ip >= lower:
            if ip <= upper:
                ip = upper + 1
                continue
            range_index += 1
        else:
            allowed_ips.append(ip)
            ip += 1
    return allowed_ips

Link to my solutions