Advent of Code 2016 - Day 20

Day 20: Firewall Rules

Useful Links

‹›

• 2016 Main Page
• My solution code

Concepts and Packages Demonstrated

bisect

Problem Intro

We’re dealing with a firewall that has a blacklist of IP addresses. The IPs are represented as 32-bit integers, ranging from 0 to 4294967295. The blacklist is a series of ranges, inclusive of the start and end values.

Here’s an example of the input data:

5-8
0-2
4-7

Our goal is to find the allowed IP addresses.

Part 1

What is the lowest-valued IP that is not blocked?

My initial approach was to create a class that manages the denied IP ranges. The idea is to merge any overlapping or adjacent ranges to simplify the blacklist. Once all the blacklist ranges are processed and merged, I can determine the allowed ranges by looking at the gaps between the denied ranges.

Here’s the Allowed_IPs class from my first solution (ip_addresses.py):

class Allowed_IPs():
    def __init__(self, min_ip, max_ip) -> None:
        self._min_ip = min_ip
        self._max_ip = max_ip
        self._deny_ranges = []
        self._allowed_ranges = []
    
    # ... (properties omitted for brevity)
    
    def add_deny(self, new_min, new_max):
        # ... (code omitted for brevity)

The add_deny method is where the magic happens. It takes a new blacklist range and merges it with the existing _deny_ranges. Let’s break down the logic:

1. Iterate and Merge: The code iterates through the existing deny_ranges. For each deny_range, it checks for overlaps with the new_range.
   • If the new_range can extend an existing deny_range to the left or right, it updates the boundaries of the existing range.
   • If the new_range is completely contained within an existing deny_range, no action is needed.
   • If no merge occurs, the new_range is added as a new entry in _deny_ranges.

2. Sort: After a potential addition, the _deny_ranges list is sorted by the lower bound of each range. This is crucial for the next step.

3. Consolidate: The code then performs another pass to merge any adjacent or overlapping ranges that might have been created. It identifies ranges to be removed and pops them from the list.

After adding all the ranges, _compute_allow_ranges calculates the gaps between the sorted and consolidated _deny_ranges.

This approach worked for Part 1, but I ran into issues with Part 2, and it’s not the most efficient way to handle this problem.

A Better Approach

I found a more elegant solution online that uses Python’s bisect module for more efficient range management. This solution maintains a list of allowed ranges and uses deny to chip away at them.

What is bisect?

The bisect module in Python provides support for maintaining a list in sorted order without having to sort the list after each insertion. It uses a binary search algorithm, which is much more efficient (O(log n)) for searching and finding insertion points than the linear scan (O(n)) I was doing in my original solution.

Here’s the IntRange class from the second solution:

import bisect

class IntRange(object):
    def __init__(self, min_ip, max_ip):
        self._ranges = [(min_ip, max_ip)]

    def __len__(self):
        return sum(hi - lo + 1 for (lo, hi) in self._ranges)

    def deny(self, deny_min, deny_max):
        i = 0
        while i < len(self._ranges):
            lo, hi = self._ranges[i]

            # Range is completely denied
            if deny_min <= lo and hi <= deny_max:
                del self._ranges[i]
                continue

            # Denial is completely within the range, split it
            elif lo < deny_min and deny_max < hi:
                del self._ranges[i]
                self._ranges.insert(i, (lo, deny_min - 1))
                self._ranges.insert(i + 1, (deny_max + 1, hi))

            # Partial overlap, adjust the range
            elif lo <= deny_min <= hi:
                self._ranges[i] = (lo, deny_min - 1)

            elif lo <= deny_max <= hi:
                self._ranges[i] = (deny_max + 1, hi)

            i += 1

The deny method in this class is much cleaner. It handles all the cases of overlap and splitting of ranges in a more straightforward way:

1. Complete Overlap: If an allowed range is completely within the new deny range, it’s simply deleted.
2. Splitting: If the deny range falls in the middle of an allowed range, the allowed range is split into two new, smaller allowed ranges.
3. Partial Overlap: If the deny range overlaps with one end of an allowed range, the allowed range is simply truncated.

This approach is more robust and less prone to the edge case errors I encountered with my initial solution. The full implementation of this class also uses bisect.insort to add new allowed ranges, which keeps the _ranges list sorted and makes the deny logic simpler.

Part 2

How many IPs are allowed by the blacklist?

With the IntRange class, this becomes a simple matter of getting the length of the IntRange object, which is the sum of the lengths of all the allowed ranges.

Using my original Allowed_IPs class, I could get the answer by summing the sizes of the allowed ranges.

Results

Here’s the output from the more efficient ip_addresses2.py solution:

First IP: 17348584
Number of allowed IPs: 104
Execution time: 0.0150 seconds

My original solution was a bit slower, but produced the same results. This was a good lesson in choosing the right data structures and algorithms for the job. The bisect module is a powerful tool for working with sorted lists.

‹›