Вызов Кода — Белый Список Inverse Cidr

Задача

Задача состоит в том, чтобы написать программу, которая превращает список адресов IPv6 в кратчайший список масок CIDR, чтобы сопоставлялось все, кроме этих IP-адресов.

CIDR-маски

Маска CIDR соответствует IP-адресам по префиксу.

 dead::beef:1.2.3.4 

matches all IPs whose first 19 bits are zero, i.e. :: . Сходным образом, >>> 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] matches all IPs that start with 243:f6a8:885a:308d:3131:98a2::/112 битовая последовательность, т.е. 0243:F6A8:885A:308D:3131:98A2:0000:0000/112 .
А / always matches only one IP. A a-f соответствует всем IP.

Вход

Ввод представляет собой список IP-адресов в полной форме: восемь 4-значных шестнадцатеричных групп, разделенных \0 in network order (most significant first). For example, 0000:0000:0000:0000:0000:0000:0000:0000 .
Вы можете выбрать любой символ-разделитель для списка ввода, будь то новая строка, пробел, запятая, : , etc. You can also rely on /0 находясь в конкретном случае.

Выход

Выходные данные — это кратчайший список масок CIDR, охватывающий все IP-адреса, кроме тех, которые указаны во входных данных.
Опять же, вы можете выбрать любой символ-разделитель.
CIDR следует форматировать как любое представление IP-адреса, за которым следует /128 and amount of bits in the prefix (in decimal). For example, 55aa:*:*:*:*:*:*:* .
Вам вообще не требуется сокращать IP-адрес, как в приведенном выше примере. Однако 0101010110101010 is not invalid.
Порядок масок не имеет значения. Если существует несколько представлений, использующих одинаковое количество масок, подойдет любое из них.

Примеры

Я не публикую полные выводы, так как придумать алгоритм — часть задачи :)
Вместо этого я указываю, сколько масок потребуется, по моим собственным расчетам. Если вы обнаружите ошибку или более короткий список масок, сообщите об этом.

55aa::/16

Подсчет очков

Количество символов в коде, символы UTF-8 при необходимости считаются за один.

Бонусные баллы

• -16 Рассмотрим случай пустого списка ввода.
• -32 Вывод сокращенных IP-адресов: удалить ведущие нули, заменить последовательные группы нулей на 0:0000-1fff:*:*:*:*:*:* , etc. See эта статья в Википедии.
  • -32 Не используйте форму v4-in-v6 ( ::/19 ).
• -64 Разрешить ввод сокращенных IP-адресов.

#код-вызов

GolfScript, 120 (136 символов – 16 бонусных)

 
 
 #!/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)
 
 
 

Предполагается, что адреса представляют собой отдельные строки в STDIN. Значительная часть кода фактически используется для ввода/вывода в правильном формате. Сам алгоритм достаточно прост и описан здесь.

Питон 3: 128 баллов

(240 символов - (16+32+64) бонусных очков)

Ура, Питон!

(Я использовал стандартную библиотеку вместо того, чтобы писать собственный алгоритм. Это жульничество?)

for

Он принимает список адресов на стандартном вводе, разделенных любыми пробелами (ASCII), которые вам нравятся (однако без запятых).

Если стандартный ввод пуст (или содержит только пробелы), он будет напечатан split() (-16 points). It also prints (-32) and handles (-64) shortened IPs.

Вы можете сэкономить 12 символов, заменив цикл stdin на strip() . The for i in sys.stdin: a=e(i.strip(),a) в любом случае необходимо избавиться от завершающего символа новой строки, поэтому я решил использовать ::/0 and another 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) цикл и разрешите любые пробелы.

Вероятно, вы сможете сэкономить еще несколько символов, убрав код из этой надоедливой функции. Я этого не сделал, потому что решил, что уже достаточно запутываю себя.

Вы также можете заставить его работать для IPv4, изменив только одну строку.

Негольфированная версия:

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

У этого есть дополнительное преимущество работы с IPv4. и IPv6, настройка не требуется. :)