6
\$\begingroup\$

The task

The task is to write a program that turns a list of IPv6 addresses into a shortest possible list of CIDR masks, such that everything but those IPs is matched.

CIDR masks

A CIDR mask matches IPs by a prefix. ::/19 matches all IPs whose first 19 bits are zero, i.e. 0:0000-1fff:*:*:*:*:*:*. Similarly, 55aa::/16 matches all IPs that start with 0101010110101010 bit sequence, i.e. 55aa:*:*:*:*:*:*:*.
A /128 always matches only one IP. A /0 matches all IPs.

Input

Input is a list of IP addresses in full form: eight 4-digit hexadecimal groups separated by : in network order (most significant first). For example, 0000:0000:0000:0000:0000:0000:0000:0000.
You're free to choose any separation character for the input list, might it be newline, space, comma, \0, etc. You can also rely on a-f being in a particular case.

Output

Output is the shortest list of CIDR masks that cover all IP addresses except those listed in input.
Again you're free to choose any separation character.
The CIDR should be formatted as any representation of an IP followed by / and amount of bits in the prefix (in decimal). For example, 0243:F6A8:885A:308D:3131:98A2:0000:0000/112.
You are not required to shorten the IP at all, as in above example. However 243:f6a8:885a:308d:3131:98a2::/112 is not invalid.
The order of masks doesn't matter. If there are multiple representations using equal amount of masks - either will suffice.

Examples

I'm not posting complete outputs, since coming up with an algorithm is a part of the task :)
Instead I'm specifying how much masks does it take, according to my own calculations. If you find a mistake, or a shorter masklist, please report.

>>> 0000:0000:0000:0000:0000:0000:0000:0000
 [128 masks]
>>> 0000:0000:0000:0000:0000:0000:0000:0000 0000:0000:0000:0000:0000:0000:0000:0001
 [127 masks]
>>> ffff:ffff:ffff:ffff:ffff:ffff:ffff:ffff 0000:0000:0000:0000:0000:0000:0000:0000
 [254 masks]
>>> 0000:0000:0000:0000:0000:0000:0000:ffff 0000:0000:0000:0000:0000:0000:0000:0000
 [142 masks]
>>> 0123:4567:89ab:cdef:fedc:ba98:7654:3210 0246:8ace:1357:9bdf:0246:8ace:1357:9bdf
 [248 masks]
>>> 0000:0000:0000:0000:0000:0000:0000:0000 0000:0000:0001:0000:0000:0000:0000:0000 0000:0000:0002:0000:0000:0000:0000:0000 0000:0000:0003:0000:0000:0000:0000:0000 0000:0000:0004:0000:0000:0000:0000:0000 < snip > 0000:0000:00ff:0000:0000:0000:0000:0000
 (256 IPs)
 [20520 masks]
>>> 0000:0000:0000:0000:0000:0000:0000:0000 0000:0000:0000:0000:0000:0000:0000:0001 0000:0000:0000:0000:0000:0000:0000:0002 0000:0000:0000:0000:0000:0000:0000:0003 0000:0000:0000:0000:0000:0000:0000:0004 < snip > 0000:0000:0000:0000:0000:0000:0000:0fff
 (4096 IPs)
 [116 masks]

Scoring

Amount of characters in the code, UTF-8 characters are counted as one, if you must.

Bonus points

  • -16 Cover the case of empty input list.
  • -32 Output shortened IPs: strip leading zeros, replace sequential zero groups with ::, etc. See this Wikipedia article.
    • -32 Do not use the v4-in-v6 form (dead::beef:1.2.3.4).
  • -64 Permit shortened IPs in input.
\$\endgroup\$
  • \$\begingroup\$ For the 256 IPs test case I get 20520. \$\endgroup\$ – Howard Feb 9 '14 at 17:58
  • \$\begingroup\$ Oh... That's merely a typo. I get 20520 too. \$\endgroup\$ – mniip Feb 9 '14 at 18:48
3
\$\begingroup\$

GolfScript, 120 (136 characters - 16 bonus)

n%{':'-{48^71%}%16base}%-1+2.7??:W+${\)1$1$-{}{129,-1%{2\?.2$)<3$@%!&}?:~2$W+16base(;{.48+\9>39*+}%4/':'*'/'+128@-+puts\2~?+\2~?-}/;;}*;

Assumes the addresses as separate lines on STDIN. A considerable amount of the code is actually used to input/output in the correct format. The algorithm itself is quite simple and described here.

\$\endgroup\$
1
\$\begingroup\$

Python 3: 128 points

(240 characters - (16 + 32 + 64) bonus points)

Yay, Python!

(I used the standard library instead of actually writing my own algorithm. Is that cheating?)

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')]
for h in sys.stdin:
 for i in h.split(): a=e(i,a)
for i in a: print(i)

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

If stdin is empty (or has only whitespace), it will print ::/0 (-16 points). It also prints (-32) and handles (-64) shortened IPs.

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 IPv4 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\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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