Przypomina mi to, gdy kilka lat temu ktoś załadował torrent „Narzędzie hakerskie: pełna lista wszystkich adresów IP”. To była oczywiście tylko wygenerowana lista ~ 4 miliardów adresów IPv4, ale pobrały ją tysiące h4xx0rz. Spójrz mamo, imahacker!

Tak było wtedy, ale obecnie wszyscy przeszli na IPv6 . (Dobrze?)

Twoim zadaniem jest napisanie programu, który wypisze wszystkie adresy IPv6 .

Powinieneś napisać pełny program, który nie pobiera danych wejściowych i wypisuje adresy IPv6, po jednym w wierszu i bez innych danych wyjściowych. Twój program musi wydrukować wszystkie 2 ¹²⁸ możliwych adresów, w tym nieprawidłowe. Każdy adres musi zostać wydrukowany dokładnie raz. Możesz wydrukować adresy w dowolnej kolejności.

Każdy adres może być wydrukowany w całości, z 8 grupami 4 cyfr szesnastkowych oddzielonych dwukropkami, np

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

Możesz, według własnego uznania, użyć dowolnego ze standardowych skrótów z RFC 5952 :

• Zera wiodące w grupie można pominąć, z tym wyjątkiem, że 0nie można ich dalej skracać.
• :: można użyć maksymalnie raz na adres, aby skrócić sekwencję jednej lub więcej grup zerowych.
• Cyfry szesnastkowe mogą używać małych lub wielkich liter.

Jeśli osiągniesz zalecenie dotyczące reprezentacji z RFC 5952 (tylko małe litery, najkrótsza możliwa reprezentacja, z ::jak najwcześniejszym wykorzystaniem, jeśli istnieje wiele miejsc, w których można jej użyć), otrzymasz bonus -20% .

Ze względu na rozmiar danych wyjściowych, twój program nie powinien zakończyć się, gdy tam siedzimy. W pewnym momencie twój program może zostać przerwany za pomocą środków zewnętrznych ( Ctrl+ C, odłączenie zasilania,…). Twój program musi generować dane wyjściowe w postaci strumienia, aby po „rozsądnym” odczekaniu wygenerował kilka wierszy. Zasadniczo nie jest dozwolone budowanie gigantycznego ciągu w pamięci tylko w celu wydrukowania go na końcu. Każdy program, który zabraknie pamięci na „standardowym” komputerze, zostanie zdyskwalifikowany. (Niemniej jednak, jeśli program pozostawiono na działanie przez wystarczająco długi czas, musi wydrukować wszystkie adresy IPv6, a następnie wyjść).

(Jeśli ten warunek stanowi problem dla interpreterów internetowych, którzy uruchamiają program do zakończenia, a następnie pozwalają zobaczyć wynik, a nie masz hostowanego tłumacza, przetestuj program na mniejszej wersji problemu, a następnie ostrożnie go dostosuj do pełnego 2 ¹²⁸ ).

Twój wynik to długość twojego programu w bajtach, pomnożona przez 0,8, jeśli otrzymasz bonus. To jest golf golfowy, więc wygrywa najniższy wynik.

Pyth, 21 bajtów

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

Używa pętli while ze Jzmienną iteratora. Inicjuje maksymalne użycie 8^chr(' '). Blokuje, dodając tę ​​wartość początkową, konwertując na hex, a następnie usuwając pierwszy znak.

Python 3, 65 bajtów · 0,8 = 52,0

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

Pyth, 27 25 24 bajtów

Uwaga: kod zawierał wcześniej błąd, który naprawił zapisany 1 bajt

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

Drukuje adresy jak

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

Poprzednia (bardziej skomplikowana) wersja wykorzystująca operator pada (również 24 bajty):

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

Wyjaśnienie

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

Pyth, 21 bajtów (nieprawidłowy)

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

Nie można tego uruchomić, ponieważ 1) zużyłoby co najmniej 2 ¹³² bajty (2 ⁵² yobibajtów) pamięci i 2) interpreter go nie lubi (2 ¹²⁸ nie mieści się ssize_t, więc nie ma listtakiej wielkości) . Wypisuje adresy w kolejności leksykograficznej. Możesz wypróbować algorytm, zmieniając numery na końcu na coś użytecznego.

C (z rozszerzeniami GCC), 76 bajtów * 0,8 = 60,8

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

Wykorzystuje 128-bitowe rozszerzenie GCC liczb całkowitych, aby po prostu policzyć od ::do ffff:ffff:ffff:ffff:ffff:ffff:ffff:ffff. inet_ntop()poprawnie formatuje każdy adres, aby można było ubiegać się o premię w wysokości -20%.

Wynik

Wykorzystanie seddo generowania co milionowej linii do 10 milionów:

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

Uwaga: Używam komputera z małą końcówką x86_64, a adresy sieciowe zwykle są zawsze uporządkowane w sieci (big-endian), więc endianowość jest skutecznie zamieniana za pomocą inet_ntop(). To nie ma znaczenia - wszystkie adresy będą nadal (ostatecznie) wyświetlane.

CJam, 36 27 bajtów

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

-9 bajtów dzięki @Dennis (zapomniałem, że CJam ma formatowanie ciągów). Drukuje adresy małymi i malejącymi.

Z oczywistych powodów użyj interpretera Java, a nie internetowego. Możesz go jednak zastąpić G32#czymś mniejszym do testowania online, np. Oto ostatnie 100 .

Wyjaśnienie

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 bajtów

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

Jako efekt uboczny metody zastosowanej do wstawienia dwukropków adresy są drukowane z kolumną znajdującą się najbardziej po prawej stronie, widoczną po lewej stronie:

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

Moje pierwsze zgłoszenie Verilog, prawdopodobnie przydałoby się więcej golfa, ale nie mam teraz na to siły. cjest zegarem, ojest wyjściem ASCII. Nie kwalifikuje się do premii za formatowanie ze względu na zerowanie zamiast skrótu.

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

Jest to prosta iteracja, po której następuje pewne kręcenie bitów w celu uzyskania wyjściowego ASCII. Odcinam okrężnicę po ostatniej grupie małym hakiem. Syntezuje i wydaje się działać dla xc3s500e-4ft256-4 na ISE 13.7 lin64.

C, 91-126 bajtów

Moja oryginalna wersja, 119 bajtów.

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]);}

Najlepsza przenośna wersja gry w golfa, 103 bajty (dzięki @Dennis za niektóre z tych koncepcji)

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);}}

Objaśnienie: Sam algorytm jest dość prosty. Użyłem dłuższego niż bez znaku int, ponieważ jest krótszy. Zadeklarowanie ich na poziomie pliku oznacza, że ​​wszystko jest wstępnie zainicjowane zerami. Ta ffunkcja jest prostym przyrostem z przeniesieniem, który działa na niskich 16 bitach każdego słowa. Pętla kończy się, gdy przenosi się na 129-ty bit.

Iteracja wsteczna dla printf oznacza, że ​​drukujemy adresy w „właściwej” kolejności, a także kontrola drukowania nowego wiersza jest krótsza o kilka znaków.

Wykorzystuje to niektóre nieprzenośne konstrukcje. Najlepiej jest traktować go jako dialekt K&R, ponieważ używa niejawnych typów zwrotów int i nie obejmuje stdio.h. I moje użycie longa zostało o tym poinformowane - w większości nowoczesnych systemów int jest wystarczający, ponieważ ma 32 bity. Prawdopodobnie mogłoby to działać niezmodyfikowane na PDP-11 Unix.

Może być jednak krótszy. Jeśli założymy, że możemy użyć int (jako typu szerszego niż 16 bitów lub typu dokładnie 16 bitów o różnych właściwościach, które są prawdziwe w wielu systemach, takich jak dopełnianie dwójki i przewijanie arytmetyczne), możemy pozbyć się rzeczy związane z używaniem długiego.

Wersja dla int szerszych niż 16 bitów, 97 bajtów.

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);}}

Wersja dla systemów 16-bitowych, 91 bajtów.

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

Co dziwne, oryginalny kompilator K&R tak naprawdę nie obsługiwał deklaracji bez int (kompiluje się dobrze, ale traktuje zmienne jako zewnętrzne i dlatego nieokreślone w czasie łączenia), więc potrzebne są dodatkowe trzy bajty, aby zmienić deklarację int*p,a[9];na w sumie 94.

Ponadto, jeśli założenie, że zostało przerwane przed zakończeniem produkcji, było twardym ograniczeniem, moglibyśmy usunąć kontrolę końcową, oszczędzając pięć bajtów.

Bonus: w pełni przenośna wersja ANSI, 126 bajtów:

#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);}}

Nowe wiersze we wszystkich wersjach są wstawiane w celu zapewnienia czytelności oraz w miejscach, w których białe znaki nie są wymagane, i są wykluczane z liczby bajtów, z wyjątkiem nowej linii po #includewierszu w wersji ANSI.

Wszystkie wersje oprócz wersji ANSI wypadają na końcu main i dlatego mogą zwrócić fałszywy kod wyjścia do systemu operacyjnego.

AutoIt3, 142 231 bajtów

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

Wyjaśnienie

• For $a=0 To 2^32-1: Iteruj 4 razy ponad 0-2 ^ 32 ((2 ^ 32) ^ 4 = 2 ^ 128) możliwych kombinacji.
• $s=StringFormat("%08x%08x%08x%08x",$a,$b,$c,$d): Konwertuj liczby na ciąg szesnastkowy o długości 32 (4 * 32).
• For $j=0 To 8: Iteruj po wszystkich 8 sekcjach łańcucha.
• ConsoleWrite(StringMid($s,$j*4+1,4)&($j<7?":":"")): Wyodrębnij 4 kolejne znaki z ciągu i dodaj dwukropek ( :) na końcu, jeśli nie dotarliśmy do ostatniej sekcji, a następnie wyślij wszystko do konsoli
• Next: Zakończ wewnętrzną pętlę for
• ConsoleWrite(@LF): Dodaj znak końca wiersza na końcu wiersza
• Next: Zakończ zewnętrzne pętle for

Oczekiwany rozmiar wyjściowy: (jedna linia (39 bajtów) + przesunięcie linii) (= 40 bajtów) * 2 ^ 128 = 1,361 * 10 ^ 16 YB (yottabajtów)

Guma cynamonowa, 16 bajtów

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

Wypróbuj online. (TIO ogranicza moc wyjściową)

Wyjaśnienie

gStawia tryb Cinnamon Gum w tryb generowania . Reszta ciągu dekompresuje się do tego wyrażenia regularnego:

[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]

Następnie tworzy generator wszystkich możliwych ciągów pasujących do wyrażenia regularnego i przechodzi przez niego, drukując każdy z nich.

Nieco zabawnie, regex golfisty ([0-9a-f]{4,4}:){7,7}[0-9a-f]{4,4}faktycznie kompresuje się do dłuższego łańcucha niż regex powyżej.

Commodore BASIC 2.0, 339 bajtów

Aby uzyskać małe cyfry szesnastkowe, program jest napisany w „trybie przesuniętym” (naciśnij <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

Samo wykonanie tej pracy na Commodore 64 było wyzwaniem ze względu na pamięć, rozmiar ekranu, rozmiar danych i inne ograniczenia. Zastanawiałem się nad implementacją skróconej reprezentacji, ale inne ograniczenia (takie jak nieudokumentowana niemożność użycia elementów tablicy jako indeksów pętli) oznaczały, że zwiększyłoby to długość programu o około 1000 bajtów.

Linia 7 jest implementacją HEX$(), której brakuje Commodore BASIC 2.0. Nie mogę użyć DEF FNdo tego, ponieważ mogą one zwracać tylko liczby, a nie ciągi znaków. Wiersz 6 to podprogram, który stosuje go do grupy czterech cyfr, która byłaby znacznie krótsza, gdyby funkcje mogły zwracać ciągi.

Linie 2 i 5 to osiem zagnieżdżonych pętli, zaimplementowanych jako siedem pętli „for” i warunkowe goto, ponieważ osiem pętli „for”, w połączeniu z dwoma „gosubami” do drukowania adresu, przepełni maleńki stos C64.

C64 może drukować około 1,2 adresów na sekundę, przy szacowanym czasie działania 1,3 * 10 ^ 31 lat.

PowerShell (v4), 193 166 162 145 103 bajtów

Wersja bez premii TimmyD o wielkości 103 bajtów:

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

Poprzednia wersja z premią przy 145 * 0,8 = 116 bajtów

Z pomocą TimmyD i tomkandy , którzy to podkreślają, 0 -eq $falseale ([bigint]0) -eq $true. Więc wszystkie moje poprzednie wersje się nie kończą.

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

Poprzednio w wersji 162, przed kilkoma zmianami wyrażeń regularnych:

$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}

„Wyzwanie, w którym PowerShell powinien być dość konkurencyjny!” - ja, zanim spróbowałem.

Wyjaśnienie

# 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 bajtów

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 bajtów

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

Po prostu przechodzi przez każdą liczbę od 0 do 2 ^ 128. Najpierw konwertuje bieżącą liczbę na ciąg szesnastkowy, a następnie usuwa dane podane przez '0x'tę funkcję. Następnie dopasowuje ciąg znaków, tak aby miał 32 zera z przodu, a następnie dzieli go na cztery grupy. W końcu łączy cztery grupy z dwukropkami, drukuje je i dodaje 1 do bieżącej liczby. Ma dodatkową premię, że możesz ją uruchomić od dowolnej wartości, jeśli ją dasz, ale nie potrzebujesz żadnych danych wejściowych.

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"

Dzięki własnej funkcji sekwencji snie przecieka już pamięć, ale nie czuję się już golfem.

CBM BASIC v7.0 (166 znaków)

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

Odpowiedź Marka dotyczy BASIC 2.0 Commodore 64, który nie ma wbudowanego polecenia drukowania liczb w systemie szesnastkowym. Jednak dzięki HEX$()funkcji w BASIC 7.0 wersja Commodore 128 jest znacznie krótsza. Nie mieści się w jednej linii logicznej (która w C128 jest ograniczona do 160 znaków), ale nadal może być wprowadzana jako dwie osobne linie w trybie bezpośrednim.

Ruby 75

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

Jest to rozwiązanie rekurencyjne, które pobiera każdy prefiks i znajduje każdy możliwy sufiks. Rekurencyjnie.

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