IPV4 subnet list cleaner (in CIDR notation) We have a lot of IPV4 address, to group into subnets, so we need a tool for doing this:

Our list is very ugly, not ordered and sometime in subnet notation, sometime in simple address.

Sample:

192.168.5.16/30
192.168.5.18
192.168.2.231/27
192.173.17.0/24
192.168.1.5/32
192.168.5.18/32
192.168.3.0/24
192.168.2.231/27
192.168.2.245/29
192.168.4.0/29
192.173.16.0/24
192.173.18.0/24
192.173.19.0/24
10.100.12.24


some explanation about the input (our old list):


each line hold only 1 IPV4 subnet
if a line don't contain any subnet info like on line 2, it's a single ip, so the 32 bit mask is to be considered.
subnet info is in the CIDR form: IPV4/integer where integer is mask length
IPV4 is not necessarely the base (first in range) of subnet
list is not sorted
list is not short... could make more the 60k entries...
there is repetition, overlap of subnets... lot of useless lines


( The last is the main reason we need to build this tool! ;-)

From this sample list we want to obtain shortened, sorted and cleaned list like:

10.100.12.24/32
192.168.1.5/32
192.168.2.224/27
192.168.3.0/24
192.168.4.0/29
192.168.5.16/30
192.173.16.0/22


Where all lines is subnet and all IPV4 part is base IP (begin of range), sorted, and without overlap or repetitions.

And where all IP present somewhere in input is present and no one more!

CIDR

For informations about:


Subnetting http://en.wikipedia.org/wiki/IPv4_subnetting_reference
CIDR notation http://en.wikipedia.org/wiki/Classless_Inter-Domain_Routing#CIDR_notation


Code golf


Input values could be given as you will, (arguments, read from file or STDIN)
Output to STDOUT, one subnet per line.
Output has to be sorted by the unsigned integer value of IPV4 (big-endian)
Output has to contain as few lines as possible
Of course, sum of output subnet must match sum of input subnet! no more, nor less!  So 0.0.0.0/0 which override everything is not accepted! (unless it's the only valid answer, see last test)
Use of libraries forbiden! Standard loophole applies
Shortest code wins!


Test cases

For testing this, (under bash) I use something like:

for i in {167772416..167774464};do
     echo $[i&gt;&gt;24].$[i&gt;&gt;16&amp;255].$[i&gt;&gt;8&amp;255].$[i&amp;255]
  done


as input, this must render:

10.0.1.0/24
10.0.2.0/23
10.0.4.0/22
10.0.8.0/24
10.0.9.0/32


or

for i in {167772416..167774464};do
     [ $i -gt 167773316 ] &amp;&amp; [ $i -lt 167773556 ] ||
         echo $[i&gt;&gt;24].$[i&gt;&gt;16&amp;255].$[i&gt;&gt;8&amp;255].$[i&amp;255]/30
  done


Note, I've added /30 after each ip. this will do a lot of overlap!

10.0.1.0/24
10.0.2.0/23
10.0.4.0/25
10.0.4.128/29
10.0.5.116/30
10.0.5.120/29
10.0.5.128/25
10.0.6.0/23
10.0.8.0/24
10.0.9.0/30


Extreme test rule

63.168.3.85/2
64.168.3.85/2
192.168.3.85/2
191.168.3.85/2


This special case must render:

0.0.0.0/0


Accepted answers

As this question seem not so easy, I will add time from question to the list


  
  CJam, 101 - user23013 - 38 hours
  Perl, 223 - nutki - 1 week
  Pure bash, 1040 - F.Hauri - 4 days
CJam, 101 95 94
qN/{'//('./1\+256b2b\{i)&lt;}/}%_|{{):T;_aM+:M(a&amp;}gT+}%${_2$#!{;}*}*]{_(!a32*+32&lt;8/2fb'.*'/@,(N}%

The {~}2j construct didn't make it shorter...
Try it here. (And link for Firefox.)
Explanation
qN/               &quot; Read each line. &quot;;
{                 &quot; For each line: &quot;;
    '//           &quot; Split by / &quot;;
    ('./          &quot; Split first item by . &quot;;
    1\+256b2b     &quot; The address + 2^32 in base 2, which always has length 33 &quot;;
    \{i)&lt;}/       &quot; For each other items N (if any), get the first N+1 bits. &quot;;
}%
_|                &quot; Remove duplicates. &quot;;
{                 &quot; For each item (each array of bits): &quot;;
    {             &quot; Do: &quot;;
        ):T;      &quot; Remove last bit and save it in T. &quot;;
        _aM+:M    &quot; Add the array to M. &quot;;
        (a#)      &quot; Find the array in the original M. &quot;;
    }g            &quot; while it is found. &quot;;
    T+            &quot; Append the last T back. &quot;;
}%
$                 &quot; Sort. &quot;;
{                 &quot; Reduce and wrap in array: &quot;;
    _2$#!         &quot; Test if the previous string is a prefix of the current. &quot;;
     {;}*         &quot; If so, discard it. &quot;;
}*]
{                 &quot; For each item (each array of bits): &quot;;
    _(!a32*+32&lt;   &quot; Remove first bit and pad to 32 bits to the right. &quot;;
    8/2fb'.*      &quot; Convert to IP address. &quot;;
    '/@,(         &quot; Append / and original length - 1. &quot;;
    N             &quot; Append a newline. &quot;;
}%