Perl Guru Forums: Fun With Perl: Perl Golf: [GOLF] IPv6 Address Compression

CGI/Perl Guide | Learning Center | Forums | Advertise | Login

Site Search: in


	MAIN INDEX	SEARCH POSTS	WHO'S ONLINE	LOG IN

Home: Fun With Perl: Perl Golf:
[GOLF] IPv6 Address Compression

mhx
Enthusiast / Moderator

Feb 16, 2002, 6:58 AM

Post #1 of 9 (58712 views)

[GOLF] IPv6 Address Compression	Can't Post

Let's play another little one-hole course here...

The Problem: Zero-Compression of IPv6 Addresses

Anyone who's aware of IPv6 addresses knows they can be quite long. They are normally represented as 8 hexadecimal 16-bit words, separated by colons:

Code

FEDC:BA98:7654:3210:FEDC:BA98:7654:3210 
1080:0000:0000:0000:0008:0800:200C:417A 
FF01:0:0:0:0:0:0:43 
0:0:0:0:0:0:0:0

Alternatively, you may write the two low-order 16-bit words in a "traditional" way to represent IPv4 addresses:

Code

0:0:0:0:0:0:13.1.68.3 
0:0:0:0:0:FFFF:129.144.52.38

As all of these are obviously very long, [url=http://rfc.net/rfc1884.html]RFC 1884 suggests a zero-compressed representation, where one series of consecutive zero groups can be replaced by a double colon. And, of course, leading zeros are always redundant.

So, these IPv6 addresses...

Code

1080:0000:0000:0000:0008:0800:200C:417A 
FF01:0:0:0:0:0:0:43 
0:0:0:0:0:0:0:1 
0:0:0:0:0:0:0:0 
0:0:0:0:0:0:013.001.068.003 
0:0:0:0:0:FFFF:129.144.52.38

...can be turned into these compressed IPv6 addresses...

Code

1080::8:800:200C:417A 
FF01::43 
::1 
:: 
::13.1.68.3 
::FFFF:129.144.52.38

...with a Perl script, of course Wink

The Task

With the fewest number of characters possible, write a Perl program that reads a series of valid, newline separated, arbitrary IPv6 addresses from standard input and writes a series of newline separated compressed representations of these addresses to standard output.
The output must hold the shortest possible compression of the IPv6 address in case more than one solution is possible.

The Rules

Your script must run under the latest stable Perl distribution (currently 5.6.1). You may exploit all bugs in that distribution if that helps to improve your score. You may use all standard modules that came with the distribution. Your script may not be platform-dependent and it may not use other programs or scripts.

The Score

The score is the sum of all characters. However, you may use a line similar to the following one right at the start of your script:

Code

#!/usr/bin/perl

Everything between "#!" and "perl" (including both) does not count, as well as the newline character you put at the end of that line. Each character you put in between "perl" and the end of the line will count.
For example, the following script has a score of 8 (3 for the " -n" and 5 for the "print").

Code

#!/usr/local/bin/perl -n 
print

The End

A score of less than 100 is possible. You should consider to put your solution in a spoiler tag (see [url=http://perlguru.com/gforum.cgi?do=markup_help;]Get Markup Help), so others who want to play don't see your solution right away.

Have a lot of fun!

-- mhx

At last with an effort he spoke, and wondered to hear his own words, as if some other will was using his small voice. "I will take the Ring," he said, "though I do not know the way."

-- Frodo

freddo
User

Feb 16, 2002, 7:14 AM

Post #2 of 9 (58702 views)

Re: [mhx] [GOLF] IPv6 Address Compression [In reply to]	Can't Post

Hello MHX,

just two questions (because your post is, of course, so incomplete* Wink

) are the addresses all written in hex, and what will 1::2::3 expand to? (true, i didnt looked at that rfc yet)...

freddo
* just joking
;---

freddo
User

Feb 16, 2002, 7:20 AM

Post #3 of 9 (58700 views)

Re: [freddo] [GOLF] IPv6 Address Compression [In reply to]	Can't Post

my guess is 1::2::3 is going to be 1:0:2:0:0:0:0:3? is it part of the golf?

and for the hex stuff is ask coz perlguru.com is, for example:
66.70.219.115
0102.70.219.115
0102.0106.0333.0163
0x42.70.219.115
0x42.70.219.0163
0x4246DB73
1111939955
010221555563

and one could imagine more variations, anyway oct is fine for that stuff anyway Wink

freddo

this was upated, sadly, after mhx posts of Feb 16, 2002, 4:33 PM
;---

(This post was edited by freddo on Feb 16, 2002, 7:37 AM)

mhx
Enthusiast / Moderator

Feb 16, 2002, 7:33 AM

Post #4 of 9 (58696 views)

Re: [freddo] [GOLF] IPv6 Address Compression [In reply to]	Can't Post

In Reply To

are the addresses all written in hex,

Yes, when written in "true" IPv6 style. When written in "IPv4 compatibility" style, the last part of the address is written like an IPv4 address (like in the examples I gave). But in general, IPv6 addresses are always written in hex.

In Reply To

and what will 1::2::3 expand to?

Nothing will expand. This golf course is about compressing.
The address you gave is not a valid IPv6 address, since only one series of zero groups may be replaced by a double colon. If there are more than one, like in

Code

1:0:0:0:1:0:0:1

you could compress that to one of

Code

1::1:0:0:1 
1:0:0:0:1::1

For the game, I always want the shortest possible compression, i.e. the one the removes most of the zeroes.

-- mhx

At last with an effort he spoke, and wondered to hear his own words, as if some other will was using his small voice. "I will take the Ring," he said, "though I do not know the way."

-- Frodo

mhx
Enthusiast / Moderator

Feb 16, 2002, 7:36 AM

Post #5 of 9 (58694 views)

Re: [freddo] [GOLF] IPv6 Address Compression [In reply to]	Can't Post

In Reply To

my guess is 1::2::3 is going to be 1:0:2:0:0:0:0:3? is it part of the golf?

Nope, it's still not valid Wink

, thus it's not part of the golf.
But you should consider every other valid IPv6 address to be part of it.
Much fun!

-- mhx

At last with an effort he spoke, and wondered to hear his own words, as if some other will was using his small voice. "I will take the Ring," he said, "though I do not know the way."

-- Frodo

freddo
User

Feb 16, 2002, 7:42 AM

Post #6 of 9 (58691 views)

Re: [mhx] [GOLF] IPv6 Address Compression [In reply to]	Can't Post

Thanks for clarification MHX,

for everybody:
sadly, i updated my second posts while MHX was replying to it, so just ignore it. (i just tried to clarify my point of view)

freddo
;---

mhx
Enthusiast / Moderator

Feb 16, 2002, 7:45 AM

Post #7 of 9 (58690 views)

Re: [freddo] [GOLF] IPv6 Address Compression [In reply to]	Can't Post

In Reply To

66.70.219.115
0102.70.219.115
0102.0106.0333.0163
0x42.70.219.115
0x42.70.219.0163
0x4246DB73
1111939955
010221555563

and one could imagine more variations, anyway oct is fine for that stuff anyway

I'll give you a regular expression that will test if an IPv6 address is valid or not in a few minutes.

In Reply To

this was upated, sadly, after mhx posts of Feb 16, 2002, 4:33 PM

Fortunately, mhx has noticed that Cool

-- mhx

At last with an effort he spoke, and wondered to hear his own words, as if some other will was using his small voice. "I will take the Ring," he said, "though I do not know the way."

-- Frodo

mhx
Enthusiast / Moderator

Feb 16, 2002, 2:53 PM

Post #8 of 9 (58679 views)

Re: [freddo] [GOLF] IPv6 Address Compression [In reply to]	Can't Post

Or in a few hours, since I had no internet access... Crazy

Here's my IPv6 validator. It didn't fit into a single regex, but at least into a single expression. Wink

[perl]
#!/usr/bin/perl -w
use re 'eval';

$byte = '(?:[01]?\d?\d|2[0-4]\d|25[0-5])';
$word = '[[:xdigit:]]{1,4}';
$ipv4 = "$byte\\.$byte\\.$byte\\.$byte";

while( <> ) {
chomp;
printf "'$_' is %s\n",
/^(?:
$word(?::$word){7} # 8 hex words
| (?:$word:){6} $ipv4 # 6 hex words follow by IPv4 address
| (.*:)(:.*) # other compressed address
)$/x
&& (
not defined $1 # not a compressed address
or (
$pre = $1, $post = $2, $c = 0,
$pre =~ /^(?:(?:$word:(?{++$c}))*|:)$/g &&
$post =~ /^(?:(?::$word(?=:|$)(?{++$c}))*|:)(:$ipv4)?$/ &&
$c < (defined $1 ? 6 : 8)
)
) ? 'valid' : 'INVALID'
}
[/perl]

It's just a quick hack, so don't rely on it being always right. I tried to implement a check for what I think are correct IPv6 addresses, and I'm pretty sure I made a few mistakes...

-- mhx

At last with an effort he spoke, and wondered to hear his own words, as if some other will was using his small voice. "I will take the Ring," he said, "though I do not know the way."

-- Frodo

mhx
Enthusiast / Moderator

Mar 1, 2002, 7:08 AM

Post #9 of 9 (58641 views)

Re: [mhx] [GOLF] IPv6 Address Compression [In reply to]	Can't Post

So, since unfortunately nobody has submitted a solution yet :( I'll post my first try on this hole:

#!/usr/bin/perl -p
/::/||[s]\b0+(?=\B)]]g,$,='}0>>||s>\b(0:){',eval"s>\\b(0:){3,$,2$,1$,0}0>>",s;^$|^:|:$;::;]

The score is 94. Sorry I didn't post it in markup because the [s] in the code confuses the markup processor ;-)

-- mhx

At last with an effort he spoke, and wondered to hear his own words, as if some other will was using his small voice. "I will take the Ring," he said, "though I do not know the way."

-- Frodo

Search for (options)

Web Applications & Managed Hosting Powered by Gossamer Threads
Visit our Mailing List Archives