Isso me lembra quando, há alguns anos, alguém enviou uma torrent "Hacker tool: lista completa de todos os endereços IP". Obviamente, essa era apenas uma lista gerada dos ~ 4 bilhões de endereços IPv4, mas milhares de "h4xx0rz" fizeram o download. Olha mãe, imahacker!

Isso foi então, mas hoje em dia todo mundo mudou para o IPv6 . (Direito?)

Sua tarefa é escrever um programa que imprima todos os endereços IPv6 .

Você deve escrever um programa completo que não aceite entrada e imprima endereços IPv6, um por linha e nenhuma outra saída. Seu programa deve imprimir todos os 2 ¹²⁸ endereços possíveis, incluindo os inválidos. Cada endereço deve ser impresso exatamente uma vez. Você pode imprimir os endereços em qualquer ordem.

Cada endereço pode ser impresso na íntegra, com 8 grupos de 4 dígitos hexadecimais separados por dois pontos, por exemplo

2001:0db8:85a3:0000:0000:8a2e:0370:7334

Você pode, a seu critério, usar qualquer uma das abreviações padrão da RFC 5952 :

• Os zeros à esquerda em um grupo podem ser omitidos, exceto que 0não podem ser abreviados ainda mais.
• :: pode ser usado no máximo uma vez por endereço para abreviar uma sequência de um ou mais grupos totalmente zero.
• Os dígitos hexadecimais podem usar letras minúsculas ou maiúsculas.

Se você obtiver a recomendação de representação da RFC 5952 (apenas letras minúsculas, menor representação possível, e ::usada o mais cedo possível, se houver vários locais onde ela possa ser usada), você receberá um bônus de -20% .

Devido ao tamanho da saída, não se espera que seu programa termine enquanto estivermos lá. Seu programa pode ser interrompido por meios externos em algum momento ( Ctrl+ C, desligando a energia,…). Seu programa deve produzir saída como um fluxo, para que, após uma espera "razoável", tenha produzido algumas linhas. Basicamente, não é permitido construir uma cadeia gigante na memória apenas para imprimi-la no final. Qualquer programa que fique sem memória em um PC "padrão" é desqualificado. (No entanto, se o seu programa foi deixado em execução por tempo suficiente, ele deve imprimir todos os endereços IPv6 e depois sair.)

(Se essa condição for um problema para intérpretes da web que executam o programa até a conclusão e permitem ver a saída e você não tem um intérprete hospedado, teste seu programa em uma versão menor do problema e ajuste-o com cuidado para o total de 2 ^128. )

Sua pontuação é o comprimento do seu programa em bytes, multiplicado por 0,8 se você receber o bônus. É código de golfe, então a pontuação mais baixa vence.

Pitão, 21 bytes

KJ^8CdWJj\:ct.H+K=tJ4

Usa um loop while com Ja variável iteradora. Inicializa o máximo usando 8^chr(' '). Almofadas adicionando esse valor inicial, convertendo em hexadecimal e removendo o primeiro caractere.

Python 3, 65 bytes · 0,8 = 52,0

from ipaddress import*
n=4**64
while n:n-=1;print(IPv6Address(n))

Pitão, 27 25 24 bytes

Nota: o código apresentava um erro anteriormente, corrigindo 1 byte salvo

J^4 64WJj\:c%"%032x"=tJ4

Imprime os endereços como

ffff:ffff:ffff:ffff:ffff:ffff:ffff:ffff
ffff:ffff:ffff:ffff:ffff:ffff:ffff:fffe
ffff:ffff:ffff:ffff:ffff:ffff:ffff:fffd
ffff:ffff:ffff:ffff:ffff:ffff:ffff:fffc
...
0000:0000:0000:0000:0000:0000:0000:0003
0000:0000:0000:0000:0000:0000:0000:0002
0000:0000:0000:0000:0000:0000:0000:0001
0000:0000:0000:0000:0000:0000:0000:0000

Versão anterior (mais complicada) usando o operador pad (também 24 bytes):

J^4 64WJj\:c.[\032.H=tJ4

Explicação

J^4 64                  set J to 2^128
WJ                     while J is not 0:
            =tJ               decrement J
    %"%032x"                 format to length-32 hex string
   c           4            split every 4 chars
j\:                        join by : and print

Pitão, 21 bytes (inválido)

jmj\:c.[\032.Hd4^4 64

Isso não pode ser executado, pois 1) consumiria pelo menos 2 ¹³² bytes (2 ⁵² yobibytes) de memória e 2) o intérprete não gostou (2 ¹²⁸ não se encaixa ssize_t, portanto, nenhum listdesse tamanho) . Seria imprimir os endereços em ordem lexicográfica. Você pode experimentar o algoritmo alterando os números no final para algo utilizável.

C (com extensões GCC), 76 bytes * 0,8 = 60,8

__uint128_t i;main(){char s[50];for(;inet_ntop(10,&i,s,49),puts(s),++i>0;);}

Este usa a extensão inteiros GCC 128 bits para contar simplesmente a partir ::de ffff:ffff:ffff:ffff:ffff:ffff:ffff:ffff. inet_ntop()formata corretamente cada endereço para que o bônus de -20% possa ser reivindicado.

Resultado

Usando sedpara produzir cada milionésimo linha até 10 milhões:

$ ./ipv6all | sed -n '1~1000000p;10000000q'
::
4042:f00::
8084:1e00::
c0c6:2d00::
9:3d00::
404b:4c00::
808d:5b00::
c0cf:6a00::
12:7a00::
4054:8900::
$ 

Observe que estou usando uma máquina x86_64 little-endian e que os endereços de rede geralmente estão sempre em ordem de rede (big-endian); portanto, a endianidade é efetivamente trocada usando inet_ntop(). Isso não importa - todos os endereços ainda (eventualmente) serão exibidos.

CJam, 36 27 bytes

G32#{(_"%032x"e%4/':*oNo}h;

-9 bytes graças a @Dennis (esqueci que o CJam tem formatação de string). Imprime os endereços em minúscula e decrescente.

Por razões óbvias, use o interpretador Java, não o online. Você pode substituir G32#por algo menor para testes on-line, por exemplo, aqui estão os últimos 100 .

Explicação

G32#             16^32 = 2^128. Call this n
{ ... }h;        While loop. The final ; is to pop n at the end
 (               Decrement n
 _               Copy n
 "%032x"e%       String format to hex, padded to 32 digits
 4/              Split into groups of 4
 ':*             Join with colons
 oNo             Output with newline

Python 2.7, 67 bytes

n=4**64
while n:n-=1;s='%032x'%n;exec"s=s[4:]+':'+s[:4];"*7;print s

Como efeito colateral do método usado para inserir os dois pontos, os endereços são impressos com a coluna mais à direita aparecendo à esquerda:

ffff:ffff:ffff:ffff:ffff:ffff:ffff:ffff
fffe:ffff:ffff:ffff:ffff:ffff:ffff:ffff
fffc:ffff:ffff:ffff:ffff:ffff:ffff:ffff
...
0003:0000:0000:0000:0000:0000:0000:0000
0002:0000:0000:0000:0000:0000:0000:0000
0001:0000:0000:0000:0000:0000:0000:0000

Verilog, 335

Minha primeira inscrição no Verilog, provavelmente poderia usar mais golfe, mas não tenho energia para fazê-lo agora. cé relógio, oé saída ASCII. Não se qualifica para o bônus de formatação devido ao preenchimento de zero em vez de abreviação.

module b(output[0:38]o,input c);reg[127:0]a;wire[0:39]d;assign o=d[0:38];always @(posedge c) a<=a+(~(&a));genvar i,j;generate for(i=0;i<8;i=i+1) begin:q for(j=0;j<4;j=j+1) begin:r assign d[5*i+j]=a[16*i+4*j:16*i+4*j+7]>9?{4'h6,a[16*i+4*j:16*i+4*j+7]-9}:{4'h3,a[16*i+4*j:16*i+4*j+7]};end assign d[5*i+4]=8'h3A; end endgenerate endmodule

Essa é uma iteração simples, seguida de alguns ajustes de bits para tornar a saída ASCII. Eu corto o cólon após o último grupo com um pequeno corte. Sintetiza e parece funcionar para xc3s500e-4ft256-4 no ISE 13.7 lin64.

C, 91-126 bytes

Minha versão original, 119 bytes.

long a[9],i;
f(long*x){if(65536&++*x)*x=0,f(x+1);}
main(){for(;!a[8];f(a))for(i=7;i+1;i--)printf(i?"%lx:":"%lx\n",a[i]);}

Melhor versão portátil de golfe, 103 bytes (obrigado @Dennis por alguns desses conceitos)

long*p,a[9];
main(i){while(!a[8]){
for(i=8;i--;printf(i?"%lx:":"%lx\n",a[i]));
for(p=a;++*p>>16;*p++=0);}}

Explicação: O próprio algoritmo é razoavelmente direto. Usei int longo, e não sem sinal, porque é mais curto. Declará-los no nível do arquivo significa que tudo é pré-inicializado com zeros. A ffunção é um incremento simples com carry que opera nos baixos 16 bits de cada palavra. O loop termina quando é carregado no 129º bit.

Iterar para trás para o printf significa que imprimimos os endereços na ordem "adequada" e também a verificação para imprimir uma nova linha é alguns caracteres mais curta.

Isso usa algumas construções não portáteis. É melhor considerado como um dialeto K&R de C, pois usa tipos de retorno int implícitos e não inclui stdio.h. E meu uso de long foi informado por isso - na maioria dos sistemas modernos, int é suficiente porque é de 32 bits. Provavelmente isso pode ser executado sem modificação no PDP-11 Unix.

No entanto, pode ser mais curto. Se assumirmos que podemos usar int (seja como um tipo maior que 16 bits ou exatamente com 16 bits com várias propriedades que são verdadeiras em muitos sistemas, como complemento de dois e rolagem aritmética), podemos nos livrar de as coisas relacionadas ao uso longo.

Versão para int maior que 16 bits, 97 bytes.

a[9],*p;main(i){while(!a[8]){
for(i=8;i--;printf(i?"%x:":"%x\n",a[i]));
for(p=a;++*p>>16;*p++=0);}}

Versão para sistemas de 16 bits, 91 bytes.

a[9],*p;main(i){while(!a[8]){
for(i=8;i--;printf(i?"%x:":"%x\n",a[i]));
for(p=a;!++*p;p++);}}

Curiosamente, no entanto, o compilador K&R original na verdade não suporta a declaração sem int (ele compila bem, mas trata as variáveis ​​como externas e, portanto, indefinidas no tempo do link), portanto, são necessários três bytes adicionais para alterar a declaração int*p,a[9];para um total de 94.

Além disso, se a suposição de que ela foi interrompida antes de concluir a saída fosse uma restrição rígida, poderíamos remover a verificação final, economizando cinco bytes.

Bônus: versão totalmente portátil ANSI, 126 bytes:

#include<stdio.h>
long*p,i,a[9];
int main(){while(!a[8]){
for(i=8;i--;printf(i?"%lx:":"%lx\n",a[i]));
for(p=a;++*p>>16;*p++=0);}}

As novas linhas em todas as versões são inseridas para facilitar a leitura e em locais onde o espaço em branco não é necessário e são excluídas da contagem de bytes, exceto a nova linha após a #includelinha na versão ANSI.

Todas as versões, exceto a versão ANSI, caem no final do main e, portanto, podem retornar um código de saída falso ao sistema operacional.

AutoIt3, 142 231 bytes

For $a=0 To 2^32-1
For $b=0 To 2^32-1
For $c=0 To 2^32-1
For $d=0 To 2^32-1
$s=StringFormat("%08x%08x%08x%08x",$a,$b,$c,$d)
For $j=0 To 8
ConsoleWrite(StringMid($s,$j*4+1,4)&($j<7?":":""))
Next
ConsoleWrite(@LF)
Next
Next
Next
Next

Explicação

• For $a=0 To 2^32-1: Itere 4 vezes em 0-2 ^ 32 ((2 ^ 32) ^ 4 = 2 ^ 128) combinações possíveis.
• $s=StringFormat("%08x%08x%08x%08x",$a,$b,$c,$d): Converta os números em uma sequência hexadecimal com um comprimento de 32 (4 * 32).
• For $j=0 To 8: Itere sobre todas as 8 seções da sequência.
• ConsoleWrite(StringMid($s,$j*4+1,4)&($j<7?":":"")): Extraia os próximos 4 caracteres da string e adicione dois pontos ( :) no final, se ainda não atingimos a última seção, emita tudo no console
• Next: Finalize o loop for interno
• ConsoleWrite(@LF): Adicione um avanço de linha no final da linha
• Next: Finalize os for-loops externos

Tamanho de saída esperado: (Uma linha (39 bytes) + avanço de linha) (= 40 bytes) * 2 ^ 128 = 1,361 * 10 ^ 16 YB (yottabytes)

Goma de canela, 16 bytes

0000000: 678b 36d0 b54c d44d 8bc5 455b 8d0c 0500  g.6..L.M..E[....                               .

Experimente online. (TIO limita a saída)

Explicação

O gmodo coloca o Cinnamon Gum no modo de geração . O restante da cadeia de caracteres descompacta para este regex:

[0-9a-f][0-9a-f][0-9a-f][0-9a-f]:[0-9a-f][0-9a-f][0-9a-f][0-9a-f]:[0-9a-f][0-9a-f][0-9a-f][0-9a-f]:[0-9a-f][0-9a-f][0-9a-f][0-9a-f]:[0-9a-f][0-9a-f][0-9a-f][0-9a-f]:[0-9a-f][0-9a-f][0-9a-f][0-9a-f]:[0-9a-f][0-9a-f][0-9a-f][0-9a-f]:[0-9a-f][0-9a-f][0-9a-f][0-9a-f]

Em seguida, ele cria um gerador de todas as seqüências possíveis que correspondem ao regex e iteram através dele, imprimindo cada uma.

Um pouco divertido, o regex golfier ([0-9a-f]{4,4}:){7,7}[0-9a-f]{4,4}realmente comprime para uma seqüência mais longa do que o regex acima.

Commodore BASIC 2.0, 339 bytes

Para obter dígitos hexadecimais em minúsculas, este programa é gravado no "modo deslocado" (pressione <SHIFT>+<C=>)

1k=65535:a=0
2fOb=0tok:fOc=0tok:fOd=0tok:fOe=0tok:fOf=0tok:fOg=0tok:fOh=0tok
3x=a:goS6:?":";:x=b:goS6:?":";:x=c:goS6:?":";:x=d:goS6:?":";:x=e:goS6:?":";:x=f
4goS6:?":";:x=g:goS6:?":";:x=h:goS6:?
5nE:nE:nE:nE:nE:nE:nE:nE:a=a+1:ifa<65536tH2
6y=x/4096:goS7:y=x/256aN15:goS7:y=x/16aN15:goS7:y=xaN15:goS7:reT
7?mI("0123456789abcdef",y+1,1);:reT

Simplesmente fazer esse trabalho no Commodore 64 foi um desafio, devido à memória, tamanho da tela, tamanho dos dados e outras limitações. Eu considerei implementar a representação abreviada, mas outras limitações (como a incapacidade não documentada de usar elementos da matriz como índices de loop) significavam que aumentaria o comprimento do programa em cerca de 1000 bytes.

A linha 7 é uma implementação da HEX$()qual o Commodore BASIC 2.0 está ausente. Não posso usar um DEF FNpara isso, porque esses podem apenas retornar números, não seqüências de caracteres. A linha 6 é uma sub-rotina que a aplica a um grupo de quatro dígitos, que seria consideravelmente menor se as funções pudessem retornar cadeias.

As linhas 2 e 5 são oito loops aninhados, implementados como sete loops "for" e um goto condicional porque oito loops "for", quando combinados com os dois "gosubs" para imprimir o endereço, irão sobrecarregar a pequena pilha do C64.

Um C64 pode imprimir cerca de 1,2 endereços por segundo, para um tempo de execução estimado de 1,3 * 10 ^ 31 anos.

PowerShell (v4), 193 166 162 145 103 bytes

Versão sem bônus do TimmyD em 103 bytes:

$i=[bigint]::Pow(4,64);while($i-gt0){('{0:X32}'-f($i-=1)-replace'0(?=.{32})'-re‌​place'.{4}(?!$)','$0:')}

Versão anterior com bônus em 145 * 0.8 = 116 bytes

Com a ajuda de TimmyD e tomkandy , quem ressalta isso 0 -eq $falsemas ([bigint]0) -eq $true. Portanto, todas as minhas versões anteriores não serão encerradas.

$i=[bigint]::Pow(4,64);while($i-gt0){$i-=1;[IPAddress]::Parse((('{0:X32}'-f$i
)-replace'0(?=.{32})'-replace'.{4}(?!$)','$0:')).IPAddressToString}

Anteriormente, aos 162, antes de algumas regex serem alteradas:

$i=[bigint]::Pow(4,64)
while($i){$i-=1;if(($x='{0:X32}'-f$i).Length-eq33){$x=$x.Substring(1)}
[IPAddress]::Parse(($x-replace'.{4}(?!$)','$0:')).IPAddressToString}

"Um desafio em que o PowerShell deve ser razoavelmente competitivo!" - eu, antes de tentar.

Explicação

# PowerShell (PS) has no IP address arithmetic, e.g. IP + 1
#- PS has no 128 bit integers
#- PS has no automatic bignums

# Start from the top, with the BigInteger specialised Power()
$i = [BigInt]::pow(4,64)

# Loop 4**64 through 1, work with $i-1 for ff... -> ::0
while ($i) {
    # PS has no decrement operator for bignums
    # (no using $i-- in the while loop test)
    $i-=1

    # The Net.IPAddress class can't turn a BigInteger
    # into an IPv6 address directly. And because it mashes
    # IPv4 and IPv6 into one class, there's no obvious way 
    # to make a small number always cast to an IPv6 address.
    # Format the bignum as a string of 32 hex digits.
    $x = '{0:X32}' -f $i

    # The BigInteger often formats as /33/ hex digits, 
    # with a leading zero (to avoid unintentional +/- sign bits)
    # ( https://msdn.microsoft.com/library/dd268287 )
    # So remove the leading 0, if there is one
    if (($x).Length-eq33){$x=$x.Substring(1)}

    # I can't always remove the leading zero, because it 
    # can't parse FFFFF... into an address without colons
    # and this regex replace into groups of 4 with colons
    # would go wrong at length 31. No : after the last group
    # This is still better than split/join ... because there
    # isn't a split-into-groups-of-N that I know of.
    $x = ($x -replace '.{4}(?!$)', '$1:'

    # Woo! * 0.8 bonus! 45 characters to save 38! :D
    [IPAddress]::Parse($x).IPAddressToString

}

AutoIt3, 137 bytes

For $i=0 To 4^64
$s=StringFormat("%032x",$i)
For $j=0 To 7
ConsoleWrite(StringMid($s,$j*4+1,4)&($j<7?':':''))
Next
ConsoleWrite(@LF)
Next

Python 2, 95 bytes

def i(p=0):
 while p<4**64:print':'.join(hex(p)[2:].zfill(32)[4*s:4*s+4]for s in range(8));p+=1

Simplesmente passa por todos os números de 0 a 2 ^ 128. Primeiro, converte o número atual em sequência hexadecimal e retira o '0x'que essa função fornece. Em seguida, ajusta a string para ter 32 zeros na frente e depois a divide em grupos de quatro. Finalmente, junta os grupos de quatro com dois pontos, imprime isso e adiciona 1 ao número atual. Tem o bônus adicional de que você pode iniciá-lo com qualquer valor, se você der um, mas nenhuma entrada é necessária.

Haskell 111

s[]=[[]]
s(a:b)=[y:z|z<-s b,y<-a]
r=replicate
main=mapM putStrLn$s$tail$concat$r 8$":":r 4"0123456789abcdef"

Com a minha própria função de sequência, sela não perde mais a memória, mas não parece mais jogar golfe.

CBM BASIC v7.0 (166 caracteres)

a=65535
fOi=0toa:fOj=0toa:fOk=0toa:fOl=0toa:fOm=0toa:fOn=0toa:fOo=0toa:fOp=0toa:?hE(i)":"hE(j)":"hE(k)":"hE(l)":"hE(m)":"hE(n)":"hE(o)":"hE(p):nE:nE:nE:nE:nE:nE:nE:nE

A resposta de Mark é para o BASIC 2.0 do Commodore 64, que não possui um comando interno para imprimir números em hexadecimal. No entanto, graças à HEX$()função no BASIC 7.0, a versão do Commodore 128 é muito mais curta. Ele não cabe em uma única linha lógica (que no C128 é limitada a 160 caracteres), mas ainda pode ser inserida como duas linhas separadas no modo direto.

Ruby 75

x=->s,n{n>0?65536.times{|m|x.(s+?:*(8<=>n)+m.to_s(16),n-1)}: p(s)};x.('',8)

Essa é uma solução recursiva que usa um prefixo para cada e encontra todos os sufixos possíveis. Recursivamente.

Tcl 341 318 301

proc ip6 {p c} {
    set s %x:%x:%x:%x:%x:%x:%x:%x
    set p [scan $p $s]
    while {[set d 7]} {
        $c [format [string map {x 04x} $s] {*}$p]
        while {[set i [lindex $p $d]]==0xFFFF} {
            lset p $d 0
            if {!$d} return
            incr d -1
        }
        lset p $d [incr i]
    }
}
ip6 fFFF:FFFF:FFFF:FFFF:FFFF:FFFF:FFFF:0000 puts