I'm posing this problem because it's reasonably (someone I knew really needs to do it) and because I couldn't think of a good way to do it in Perl. I wrote a solution in C in about a hundred lines, but the algorithm depended on using a pair of linked lists, and there didn't seem to be any efficient translation to Perl or to Perl's data structures.

---

An ISP has a file that lists all their networks, in CIDR format. (If you don't know what this is, see the explanation below.) However, some of these blocks are parts of larger networks. Where all the subnetworks of a larger network appear in the input, they should be removed and replaced with a line representing the large network.

For example, if these lines appear in the input:

209.152.214.112/30
209.152.214.116/31
209.152.214.118/31

then they should be replaced with this line:

209.152.214.112/29

because the output 209.152.214.112/29 is exactly equal to the union of the three inputs.

If those three lines had been these instead:

209.152.214.112/30
209.152.214.116/32
209.152.214.118/31

then the output would be the same as the input, because there are no complete larger networks that are unions of these. 209.152.214.112/29 is ruled out because the original input did not include the address 209.152.214.117.

If the input contained these lines instead:

209.152.214.112/31
209.152.214.116/31
209.152.214.118/31

then the output would be

209.152.214.112/31
209.152.214.116/30

These two networks cannot be merged into 209.152.214.112/29 because the original input does not include the address 209.152.214.114.

See below for more information about CIDR format network addresses.

You may assume that the input is in order, sorted by ascending IP address. You may assume that if a.b.c.d/n appears in the input, then the low-order (32-n) bits of a.b.c.d will all be 0. For example, 1.2.3.252/29 will never appear; if this network is in the input, it will be represented as 1.2.3.248/29. The input has one network per line, and the output should be in the same format as the input. The output should be minimal, so that if the output is fed back into your program, it is edmitted unchanged because there is nothing more to do.

The ISP has a file with thousands of networks, so the program should be reasonably efficient.

Sample inputs and outputs are available from my web site.

---

Explanation of CIDR format network addresses

A network number represents a contiguous sequence of IP addresses. It has the form a.b.c.d/m where a, b, c, and d are between 0 and 255, and m is between 2 and 32. a.b.c.d indicates a 32-bit number, as is usual with IP addresses. The netblock a.b.c.d/n represents the network comprising all the IP addresses whose first m bits match the first m bits of the number a.b.c.d, and whose remaining bits have any values at all. For example:

130.91.6.0/32

represents the IP address 130.91.6.0 only.

130.91.6.0/31

represents the two addresses 130.91.6.0 and 130.91.6.1.

130.91.6.0/30

represents the four addresses 130.91.6.0, 130.91.6.1, 130.91.6.2, and 130.91.6.3.

130.91.6.12/30

represents the four addresses 130.91.6.12, 130.91.6.13, 130.91.6.14, and 130.91.6.15.

Sometimes two netblocks can be combined into a single one. For example, the two netblocks

192.241.36.8/30
192.241.36.12/30

happen to represent the same set of addresses as

192.241.36.8/29

If the program input contains the first two netblocks, the program should recognize that and combine them into a single netblock for output.

See Subnetting and CIDR for a more detailed explanation.

--
Mark Dominus
Perl Paraphernalia