7
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>>24].$[i>>16&255].$[i>>8&255].$[i&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 ] && [ $i -lt 167773556 ] ||
echo $[i>>24].$[i>>16&255].$[i>>8&255].$[i&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
1What is the sort order? – Peter Taylor – 2015-03-25T15:47:09.990
@PeterTaylor It seems to be ordered byte-by-byte, in big-endian format. The subnets number can be ignored since if two subnets have the same IPv4 part, the larger contains the smaller, which can be ignored. – PurkkaKoodari – 2015-03-25T16:01:58.797
1I'm confused about what the number after the
/
is doing, because at first sight it seems it can be safely ignored in the example. Is it possible for the first four numbers to be the same and the one after the/
? Also only one out of192.168.<16 through 19>.0/24
is shown. I assume that's because it's been masked off to 22 bits and simplified to192.168.16.0/22
(there's no real explanation in the question about this.) But by that logic I can mask everything and0.0.0.0/0
should be a complete and valid output for all cases. – Level River St – 2015-03-25T18:41:31.1601@steveverrill it's mask length:
32bits => 255.255.255.255
, or24bits => 255.255.255.0
,30bits => 255.255.255.252
. And you're right:192.168.1[6-9].0/24 => 192.168.16.0/22
– F. Hauri – 2015-03-25T20:19:29.227@steveverrill You're right I missed this rule: no more!:
0.0.0.0/0
could not be accepted! – F. Hauri – 2015-03-25T20:25:47.860No answer? Not so easy? – F. Hauri – 2015-03-25T22:01:57.857
I don't really understand your explanation
of course, sum of output subnet must match sum of input subnet! no more, nor less!
Maybe it's my lack of knowledge of IPV4, but is it valid (for example) to condense all the addresses starting192.168
down to192.168.0.0/16
? And if not, why not? It's not clear to me from the rules why this hasn't been done in your example, yet it has been done for the addresses that you condensed into192.173.16.0/22
. Is there a minimum value for the mask length or something? – Level River St – 2015-03-26T00:26:03.227@steveverrill for sample: if
192.168.1.4
is not covered by the input list, theys must not match the output list! No more! For all IP betweeen0.0.0.0
to255.255.255.255
( -> 4294967296 possibilities) no more must be found in ouptut than in input – F. Hauri – 2015-03-26T06:30:57.4131Ok i get it now.
192.173.16.0/22
expands exactly to192.173.[16-19].0/24
and as the output must be as brief as possible this is not only acceptable but also required. – Level River St – 2015-03-26T14:09:11.990When you say "Use of libraries forbidden", does that forbid core functions included in platform that may operate on IP addresses or external libraries? – 640KB – 2019-05-01T19:24:48.820
Hem yes, I think, but if you post, comments from community will give better answer... – F. Hauri – 2019-05-01T20:35:10.683