6
\$\begingroup\$

Congratulations, you're now a network administrator! As your first task you will need to configure a firewall to stop any traffic to some blacklisted addresses.

Unfortunately, the only firewall at your disposal only takes in rules in this format:

x.y.z.t/m ALLOW

There's no DENY keyword. If you want to exclude a specific address, you'll have to write a lot of rules to allow everything except that address. If you want to exclude more than one address or a whole range, then you're in luck because these ALLOW rules will overlap to some degree.

The challenge

You are given a list of blacklisted IPs. Write a program that will print out rules for our firewall. Also, be sensible when writing rules: don't just enumerate all 256^4 and don't print out duplicates.

Code golf rules apply: shortest code wins

*this problem is inspired by a real life assignment; a friend actually needed this done

Example

To block address 0.1.2.3 you could write the following ALLOW rules (this is not the only solution possible, and it's certainly not the shortest):

0.1.2.0 ALLOW
0.1.2.1 ALLOW
0.1.2.2 ALLOW
0.1.2.4 ALLOW
...
0.1.2.255 ALLOW

0.1.0.0/24 ALLOW
0.1.1.0/24 ALLOW
0.1.4.0/24 ALLOW
...
0.1.255.0/24 ALLOW

0.0.0.0/16 ALLOW
0.2.0.0/16 ALLOW
...
0.255.0.0/16 ALLOW

1.0.0.0/8 ALLOW
...
255.0.0.0/8 ALLOW
\$\endgroup\$
2
  • \$\begingroup\$ Could you add some test cases? \$\endgroup\$
    – grc
    May 25, 2013 at 7:39
  • 3
    \$\begingroup\$ "shortest code" conflicts with "be sensible". Are there any hard requirements for "being sensible"? Note there is always exactly one optimal solution and it's fairly easy to find and verify optimality. You could require that. \$\endgroup\$ May 25, 2013 at 8:14

3 Answers 3

1
\$\begingroup\$

Python3 - 325 chars

import sys
r=[(0,32)]
for b in (int('%02x'*4%tuple(int(x) for x in y.split('.')),16) for y in sys.stdin):
 i=0
 while i<len(r):l,q=r[i];o=2**q//2;m=l+o;h=m+o;k=l<=b<h;r[i:i+1]=[(l,q-k),(m,q-k)][0:k+1*(not l==h==b)];i+=1-k
for n,m in r:print('%s/%d ALLOW'%('.'.join(str(int(('%08x'%n)[i:i+2],16)) for i in range(0,8,2)),32-m))
\$\endgroup\$
1
\$\begingroup\$

Python 3: 253 characters

Yay, Python!

from ipaddress import *
import sys
def e(x,a):
 b=[]
 for i in a:
  try: b+=i.address_exclude(ip_network(x))
  except ValueError: b+=[i]
 return b
a=[ip_network('0.0.0.0/0')]
for h in sys.stdin:
 for i in h.split(): a=e(i,a)
for i in a: print(i,'ALLOW')

It accepts a list of addresses on stdin, separated by any (ASCII) whitespace you like (no commas, though).

You can save 12 characters by replacing the stdin loop with for i in sys.stdin: a=e(i.strip(),a). The strip() is necessary to get rid of a trailing newline anyway, though, so I figured I'd use split() and another for loop and allow any whitespace.

You can probably save a few more characters by moving the code out of that pesky function. I didn't because I figured I was already confusing myself enough.

You can also make it work for IPv6 instead by changing only one line.

Ungolfed version:

#!/usr/bin/env python3

import ipaddress
import sys

def exclude(address, networks):
    new_networks = []
    for network in networks:
        try:
            new_networks.extend(network.address_exclude(ipaddress.ip_network(address)))
        except ValueError:
            new_networks.append(network)
        except TypeError:
            pass
    return new_networks

networks = [ipaddress.IPv6Network('::/0'), ipaddress.IPv4Network('0.0.0.0/0')]
for line in sys.stdin:
    for address in line.split():
        networks = exclude(line, networks)

for network in networks:
    print(network)

This one has the added benefit of working for IPv4 and IPv6, no tweaking necessary. :)

\$\endgroup\$
1
  • 3
    \$\begingroup\$ You could still remove unnecessary spaces, such as the ones after :s and before the first *. Great first answer on this site! :) +1 \$\endgroup\$
    – Doorknob
    Mar 1, 2014 at 22:53
0
\$\begingroup\$

PHP 5.3, 465 characters

$r=array_map(function($v){return explode('.',$v);},$w);$l=256;$n=" ALLOW\r\n";$o='';$a=$b=$c=$d=range(0,$l-1);foreach($r as$i){unset($a[$i[0]],$b[$i[1]],$c[$i[2]],$d[$i[3]]);}for($x=0;$x<$l;$x++){for($y=0;$y<$l;$y++){for($z=0;$z<$l;$z++){for($t=0;$t<$l;$t++){$k="$x.$y.$z.$t";if(isset($a[$x])){$o.="$k/8$n";break 3;}elseif(isset($b[$y])){$o.="$k/16$n";break 2;}elseif(isset($c[$z])){$o.="$k/24$n";break;}else$o.=isset($d[$t])?"$k$n":'';}}}}file_put_contents($p,$o);

Usage:

$w = array('2.5.5.4', '1.2.3.4');
$p = 'data.txt';
$r=array_map(function($v){return explode('.',$v);},$w);$l=256;$n=" ALLOW\r\n";$o='';$a=$b=$c=$d=range(0,$l-1);foreach($r as$i){unset($a[$i[0]],$b[$i[1]],$c[$i[2]],$d[$i[3]]);}for($x=0;$x<$l;$x++){for($y=0;$y<$l;$y++){for($z=0;$z<$l;$z++){for($t=0;$t<$l;$t++){$k="$x.$y.$z.$t";if(isset($a[$x])){$o.="$k/8$n";break 3;}elseif(isset($b[$y])){$o.="$k/16$n";break 2;}elseif(isset($c[$z])){$o.="$k/24$n";break;}else$o.=isset($d[$t])?"$k$n":'';}}}}file_put_contents($p,$o);

This will write to data.txt

Uncompressed:

$deny = array('2.5.5.4', '1.2.3.4');
$file = 'data.txt';

$list = array_map(function($v){return explode('.', $v);}, $deny);
$l = 256;
$n = " ALLOW\r\n";$o = '';

$first = $second = $third = $fourth = range(0,$l-1);
foreach($list as $ip){unset($first[$ip[0]], $second[$ip[1]], $third[$ip[2]], $fourth[$ip[3]]);}
    
for($x=0;$x<$l;$x++){
    for($y=0;$y<$l;$y++){
        for($z=0;$z<$l;$z++){
            for($t=0;$t<$l;$t++){
                if(isset($first[$x])){
                    $o .= "$x.0.0.0/8$n";break 3;
                }else{
                    if(isset($second[$y])){
                        $o.="$x.$y.0.0/16$n";break 2;
                    }else{
                        if(isset($third[$z])){
                            $o.="$x.$y.$z.0/24$n";break 1;
                        }else{
                            if(isset($fourth[$t])){
                                $o.="$x.$y.$z.$t$n";
                            }
                        }
                    }
                }
            }
        }
    }
}

file_put_contents($file, $o);
\$\endgroup\$
5
  • \$\begingroup\$ Won't this solution only consider the subnets /8, /16 and /24? \$\endgroup\$
    – jarnbjo
    May 27, 2013 at 14:56
  • \$\begingroup\$ @jarnbjo correct, but it will write the rest without /x. For examlpe in this case it will write 1.2.3.0 ALLOW\r\n1.2.3.1 ALLOW\r\n 1.2.3.2 ALLOW\r\n1.2.3.3 ALLOW\r\n1.2.3.5 ALLOW .... \$\endgroup\$
    – HamZa
    May 27, 2013 at 14:59
  • 1
    \$\begingroup\$ The shortest rule list to block only 0.1.2.3 would require the rule "0.1.2.0/31 ALLOW" instead of allowing the IP addresses 0.1.2.0 and 0.1.2.1 separately. \$\endgroup\$
    – jarnbjo
    May 27, 2013 at 15:59
  • \$\begingroup\$ @jarnbjo I know, but if I would take that into consideration the code will be too huge, I'm already using PHP so I'm suffering enough from the code length. Besides it isn't specified by the OP :) \$\endgroup\$
    – HamZa
    May 27, 2013 at 16:30
  • 1
    \$\begingroup\$ I assumed that returning the shortest rule list is part of the "being sensible" requirement. Otherwise you could shorten your code a lot and simply output each allowed IP address, but that's obviously not what's asked for either. \$\endgroup\$
    – jarnbjo
    May 27, 2013 at 23:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.