progress

~/problems / Bit manipulation

Ordered CIDR firewall

On a phone? Coding is easier on a laptop: email this problem to yourself . Meanwhile: quiz this topic or fight a boss.

medium assessment 2 levels ~45 min Databricks

Level 1 First matching rule for one address

Build Firewall(rules). rules is an ordered list of (action, block) pairs:

  • action is "ALLOW" or "DENY".
  • block is an IPv4 block in CIDR form such as "172.16.4.0/22", or a bare address such as "8.8.4.4", which means /32. The prefix length can be anything from /0 to /32. If the base address has bits set past the prefix ("10.9.9.9/8"), ignore them: that block is the same as "10.0.0.0/8".

check(ip) -> str takes a dotted-quad address and returns the action of the earliest rule in the list whose block contains it. If no rule matches, return "DENY".

Up to 10,000 rules and 100,000 check calls may be made on one firewall. ⭐ Bonus: scanning every rule for every call passes; a speed test with 8,000 rules and 40,000 checks earns a star if a check doesn't look at every rule.

fw = Firewall([
    ("DENY",  "172.16.4.8/29"),   # 172.16.4.8 .. 172.16.4.15
    ("ALLOW", "172.16.0.0/16"),
    ("DENY",  "0.0.0.0/0"),
])
fw.check("172.16.4.12")   # "DENY"   the first rule wins
fw.check("172.16.4.16")   # "ALLOW"
fw.check("9.9.9.9")       # "DENY"   caught by /0
Firewall([]).check("1.2.3.4")   # "DENY"   nothing matched
Show hint

an address is a 32-bit integer, and a /p block is every address that shares its top p bits.

Level 2 unlocks when level 1 passes.

Topic: Bit manipulation (IP / CIDR). IPv4 as a 32-bit int; lowest set bit for block sizes.

Read the visual guide
0:00
Ctrl ' run · Ctrl ↵ submit
esc