Beefy Boxes and Bandwidth Generously Provided by pair Networks
Pathologically Eclectic Rubbish Lister

Comment on

( #3333=superdoc: print w/replies, xml ) Need Help??

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:
then they should be replaced with this line:
because the output is exactly equal to the union of the three inputs.

If those three lines had been these instead:
then the output would be the same as the input, because there are no complete larger networks that are unions of these. is ruled out because the original input did not include the address

If the input contained these lines instead:
then the output would be
These two networks cannot be merged into because the original input does not include the address

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, will never appear; if this network is in the input, it will be represented as 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:
represents the IP address only.
represents the two addresses and
represents the four addresses,,, and
represents the four addresses,,, and

Sometimes two netblocks can be combined into a single one. For example, the two netblocks
happen to represent the same set of addresses as
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

In reply to Challenge Problem: Merging Network Addresses by Dominus

Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post; it's "PerlMonks-approved HTML":

  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.
  • Log In?

    What's my password?
    Create A New User
    and all is quiet...

    How do I use this? | Other CB clients
    Other Users?
    Others imbibing at the Monastery: (11)
    As of 2017-05-23 13:22 GMT
    Find Nodes?
      Voting Booth?