CGI/Perl Guide | Learning Center | Forums | Advertise | Login
Site Search: in

  Main Index MAIN
INDEX
Search Posts SEARCH
POSTS
Who's Online WHO'S
ONLINE
Log in 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 (32909 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 (32899 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 (32897 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 (32893 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 (32891 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 (32888 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 (32887 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 (32876 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 (32838 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) Powered by Gossamer Forum v.1.2.0

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