P2815 IPv6 Address Compression

(Friendly note: IPv6 basics have appeared many times in the NOIP preliminary contest.) Internet Protocol, the protocol of the Internet, is what we usually call IP. What we most often refer to is its fourth version, IPv4, which was released by IETF in 1981. Its address length is $32$ binary bits, so there are $2^{32}$ IP addresses available, about $4.3$ billion. At that time, no one expected that even such a large IPv4 address space would one day run out. In the 21st century, the rapid development of the Internet has brought us a convenient life. Today, the world’s population has exceeded $7$ billion. Computers and various networked devices have entered thousands of households, no longer just the tools of scientists in the 1980s. This has created a conflict between the growing number of networked devices and the limited IPv4 address space. Although Network Address Translation (NAT) can be used to share IP addresses and temporarily alleviate the exhaustion problem, it is obviously not a long-term solution. IETF was forward-looking and released the IPv6 protocol as early as 1998. Starting with Microsoft’s Windows Vista in 2006, it became a default-installed network protocol. As the successor to IPv4, its address length is $128$ binary bits, that is, $2^{128}$ IP addresses are available. However, faced with such lengthy addresses, a network engineer named Xiaoming, who has a poor memory, encountered many difficulties when configuring routing tables. He has come to you, hoping you can write a program to compress IPv6 addresses according to the standard IPv6 formatting rules.

[IPv6 Format] In binary, an IPv6 address is $128$ bits long. It is divided into groups of $16$ bits, separated by colons “:”, making $8$ groups in total. Each group is written as a 4-digit hexadecimal number. For example, `2001:0db8:0000:0000:0123:4567:89ab:cdef` is a valid IPv6 address. IPv6 addresses can be compressed under certain conditions: 1. Leading zeros in each group can be omitted. For example, the address above can be compressed to `2001:db8:0:0:123:4567:89ab:cdef`. 2. A double colon `::` can represent one or more consecutive groups of `0`, but it can only appear once. For example, the address above can be compressed to `2001:db8::123:4567:89ab:cdef`. Please help the forgetful network engineer Xiaoming solve his problem. [Supplementary Rules] 1. The input is a fully expanded IPv6 address. It is guaranteed that the input IPv6 address contains no double colon, and that any omitted zeros in each group have been filled. 2. Since `::` can be used only once, compress the longest run of all-zero groups. For example, `2001:0db8:0000:0000:1:0000:0000:0000` is compressed to `2001:db8:0:0:1::`, not `2001:db8::1:0:0:0`. 3. Since `::` can be used only once, if there are multiple runs of all-zero groups with the same maximum length, compress the earliest one. For example, `2001:0db8:0000:0000:ffff:0000:0000:1` is compressed to `2001:db8::ffff:0:0:1`, not `2001:db8:0:0:ffff::1`. 4. The input IPv6 address may not be compressible. In that case, output it as-is. Tip: The compression rules shown in this problem match the default IPv6 display style on macOS (Darwin), whereas Windows and Linux do not use `::` when there is only a single all-zero group. However, IPv6 addresses compressed in this way can still be correctly recognized by Windows and Linux. For example, `2001:0db8:ffff:0000:0123:4567:89ab:cdef` is compressed by Darwin as `2001:db8:ffff::123:4567:89ab:cdef`, while Linux and Windows compress it as `2001:db8:ffff:0:123:4567:89ab:cdef`.

A string of $39$ characters representing a fully expanded IPv6 address.

A string representing the compressed IPv6 address.

Translated by ChatGPT 5