Deadfish jest jednym z najbardziej znanych niekompletnych języków programowania Turinga. Ma tylko jeden akumulator (który zaczyna się od 0) do przechowywania danych i tylko cztery polecenia:
i - Increment the accumulator
s - Square the accumulator
d - Decrement the accumulator
o - Output the accumulator
Program Deadfish może wyglądać następująco:
iiisdo
I to by wydrukowało:
8
Wyzwanie
Utwórz program, który wprowadzi liczbę i wyświetli kod Deadfish, aby wyświetlić liczbę (lub utwórz funkcję, która przyjmuje liczbę jako parametr i zwraca kod). Musi działać dla dowolnej liczby całkowitej od 0
do255
Cel
Postaraj się, aby Twój kod umożliwił wygenerowanie podanego numeru możliwie najkrótszego kodu. Na przykład:
iiiiiiiiio
i
iiiso
każdy wydruk 9
, ale drugi jest krótszy.
Punktacja
Twój wynik to:
The number of characters in your source code +
The sum of the lengths of your output for all numbers from 1-255
-100 if the language you chose is Deadfish :)
Najniższy wynik wygrywa!
W pierwotnym wyzwaniu miałem tylko sumę 6 liczb (91, 199,100 i 123). To było ode mnie, że nie chciałem, aby każdy testował dla każdej liczby, i chciałem, aby najkrótszy kod był odpowiedni. Potem zdałem sobie sprawę, że programiści są dobrzy w tworzeniu skryptów do testowania takich rzeczy i wolałbym, aby to był konkurs na najlepszy algorytm z golfem jako rozstrzygającym.
Dlatego zmieniłem to, jak zasugerował Martin Büttner.
źródło
16^2 = 0
czy16^2 = 256
czy16^2 = error
?-1
OR256
, zostanie zresetowany do0
. Ale jeśli trafisz liczbę większą niż256
przez podniesienie do kwadratu, to pozostanie niezmieniona, np17^2 = 289
. (patrz strona esolang)Odpowiedzi:
Perl,
132131 bajtów + 2036 bajtów = 2167Obejmuje +2 za
-lp
Uruchom z numerem docelowym na STDIN, np
deadfish.pl:
Grep jest filtrem, który nieco ogranicza eksplozywną eksplozję (choć ten program nadal potrzebuje 2 GB na twarde przypadki). Działa również bez, ale nie mogę go uruchomić na takim sprzęcie, z wyjątkiem łatwych przypadków. Ale w zasadzie ten
110=108+2
bajtowy program również działa:Lista wyników:
źródło
ES6 JavaScript 2126 + 311 = 2437 punktów
Częściowo skomentowane:
Wykorzystuje to fakt, że w Deadfish możesz wydrukować więcej niż jedną postać.
Przykład:
10
kompilacja, doiodo
której należy „wypisz jeden, zmniejsz, wypisz zero”.Stosowanie:
Oto dane wyjściowe JSON:
Wygenerowane przez ten kod:
które drukuje
result = (the result)
ic =
rzecz powyżej.To jest niezwykle wysoki wynik, mimo że jest dość prosty. Wyszukuje najbliższy idealny kwadrat, oblicza pierwiastek kwadratowy z tego idealnego kwadratu, dodaje „s” i odpowiednio zwiększa / zmniejsza.
Stara wersja, która nie korzystała z faktu, że „10” = „wydrukuj jeden, wydrukuj zero”
źródło
d
źle zrozumiałeś efekt operacji - jeśli zmniejszy się-1
, zostanie zresetowany0
, a nie255
.o
; wyprowadza akumulator i nową linię.iodo
wyjścia1\n0\n
, a nie10
.o
. Również wiele kompilatorów (w różnych językach) nie drukuje nowego wiersza zo
Mathematica,
254165 znaków + 3455 = 3620Mniej golfa:
Uważam, że uzyskane liczby są optymalne. Przeszukuje najpierw wszystkie 256 liczb, śledząc najkrótszy znaleziony sposób reprezentacji każdej liczby. Wyszukiwanie buduje rodzaj funkcji odnośnika w funkcji,
g
która jest następnie stosowana do danych wejściowych.Dla porównania, oto wszystkie 255 wyników:
źródło
n > 256
nien ≥ 256
. Jest to również zgodne ze stroną esolang: „Chociaż komentarz w implementacji C stwierdza/* Make sure x is not greater then [sic] 256 */
, implementacja ustawia wartość na zero wtedy i tylko wtedyvalue == -1 || value == 256
”.d
, więc powinno zostać wydrukowane 0.C, kod 433 + wyjście 3455 = 3888
C ++, kod 430 + wynik 3455 = 3885
A teraz coś z zupełnie innej beczki.
Użyłem danych wyjściowych z odpowiedzi Mathematica Martina (zaktualizowanej 23 października, ponieważ wcześniej była niepoprawna dla ponad 240). Mój wynik to te same 3455 znaków. Analizowałem wzorce na wyjściu i odkryłem, że [0,255] może być reprezentowane przez tę sekwencję:
i
ss
si
s lubd
ss
si
lub 0-16d
so
Następnym krokiem było staranne skonstruowanie tych pięciu kolumn (
c
poprzezg
poniższy kod). Użyłem liczb ujemnych, aby wskazaćd
zamiasti
w kolumnache
ig
. Następnie okazuje się, że wyniki działają głównie jak licznik wg
kolumnie, ponieważ każdy wierszu
zwykle usuwa jedend
lub dodaje jedeni
względem poprzedniego wiersza (v
). Istnieje 15 wyjątków, które są przechowywane wx
(indeksach) ib
(pięć kolumn, zapakowanych w liczbę całkowitą, która wymaga tylko 14 bitów do przechowywania maksimum10832
).Na przykład pierwszy „wyjątek” to pierwszy wiersz, w którym oprócz zera chcemy zerowych znaków
o
. Takx[0]
jest0
ib[0]
jest544
, co po rozpakowaniu (styl „little endian”, ponieważg
kolumna zliczająca){ 32, 0, 4, 0, 0 }
. Zawsze odejmujemy 32 odg
i 4 od,e
aby pola bitów niepodpisane działały (tj. Te dwie kolumny reprezentują liczby ujemne koncepcyjnie, gdyd
jest to wymaganei
, ale w implementacji wartości są przesunięte, aby uniknąć rzeczywistych liczb ujemnych).Oto tabela przedstawiająca działanie pierwszych dziesięciu liczb (puste są zerami):
Widać, że
g
najczęściej tylko przyrosty o jeden dla każdego nowego wiersza, ale niektóre wiersze (0, 4, 8, ..., które miałem nadzieję znaleźć w OEIS) „resetują” sekwencję, co oznacza, żeg
przyjmuje nową wartość i co najmniej jedna inna kolumna jest również modyfikowana.Liczba znaków w kodzie wyklucza spacje oprócz obowiązkowej nowej linii przed każdą
#
i spacji pounsigned
iint
. Można zapisać 3 znaki kompilując jak C ++ zamiast C, zastępując<stdio.h>
z<cstdio>
, i*(int*)&u
z(int&)u
.Zabawny fakt na temat tego kodu: wcześniejsza wersja używała tablicy 256 związków zamiast tylko
u
iv
. Ta wersja spowodowała, że GCC 4.7.2 wygenerowało wewnętrzny błąd kompilatora! Jednak GCC 4.9 to naprawiło i powyższy kod działa z każdą wersją.źródło
for(...)
zscanf
- to zmniejszy liczbę znaków).#include
, a może uczyniszstruct
wnętrzeunion
nienazwanym.for
Pętla jest nadal konieczne ze względu na sposób mogę obliczyć wynik. To plus usunięcie nazwy struktury zapisało 5 znaków; kolejne 2 zostały zapisane przez zmieniających==
się>
i usuwania nowej linii spływu. :) Program jest w pełni poprawny tylko w C99, ponieważmain
nie zwraca jawnie wartości; usunięcie#include
wyników powoduje błąd z powoduscanf()
teraz.256
.Haskell,
220021772171 = 2036 + 135działa to poprzez nieskończoną listę wszystkich martwych programów posortowanych według ich długości, wraz ze stanem wewnętrznym i wyjściem. funkcja
f
przeszukuje listę i zwraca pierwszą pasującą pozycję.takie podejście pozwala na wielokrotność
o
w każdym wynikowym kodzie, ale nie ogranicza go ani do drukowania wszystkich cyfr osobno, ani do drukowania całej liczby jednocześnie. na przykład tutaj 216 ma kodiiosso
.Edycja:
zgodnie ze specyfikacją, gdy stan wynosi 256 (ale nie 257), jest on zamieniany na 0. teraz mój kod bierze to pod uwagę. na przykład 160 to
iissoso
.ma to kilka problemów z wydajnością; ponieważ
l
jest to lista najwyższego poziomu, której wszystkie elementy,l
które zostały ocenione, pozostają w pamięci, dlatego w pewnym momencie prawdopodobnie w środowisku wykonawczym zabraknie pamięci.Aby obliczyć wynik, stworzyłem wersję równoważną, ale mniej obciążającą pamięć.
mój bardziej wydajny kod działa poprzez ponowne obliczenie listy przy każdej aplikacji
f
, aby śmieciarz mógł wyrzucić wcześniej przeszukaną część listy. w pewnym sensie jest to pierwsze wyszukiwanie z wykorzystaniem lenistwa.bardziej efektywny kod dodaje również pewne ograniczenia na kolejne elementy listy - to odfiltrowuje wszystkie kody, które zawierają
id
lubdi
, lub zawieras
, gdy stan jest mniejszy niż 2.Edycja:
przeniosłem
g
funkcję z najwyższego poziomu na funkcję pomocnikaf'
, więc terazg
filtruję kody, które wydrukowały coś, co nie jest przedrostkiem naszej poszukiwanej liczby. teraz kod jest znacznie szybszy.bardziej wydajny kod:
zwróć uwagę, że bardziej wydajny kod nie będzie miał takich samych wyników, ponieważ programy przechodzą przez wszystkie możliwe kody w różnej kolejności. będą jednak wyświetlać kody o tej samej długości. przełączanie
c:x
zx++[c]
powoduje, że programy są równoważne.z tym kodem byłem w stanie obliczyć wszystkie programy w
520,81 sekundy.Edycja:
podobno jest to najlepsza odpowiedź! zauważyłem to dopiero teraz, jak dotąd, kiedy zapytano o to ...
wyniki:
źródło
Picat 516 + 2060 = 2576
Jest to nieco zmodyfikowana wersja programu Siergieja Dymczenki . Ta wersja wyświetla bardziej kompaktowe programy Deadfish.
O ile rozumiem zdanie „długości wyjść”, oznacza to, że sumuję dane wyjściowe bez znaków nowej linii.
Posługiwać się:
1-255 Kody:
Wydajność:
Wersja programu do pomiaru czasu:
Wynik:
Pełna wydajność:
źródło
ioio
drukuje"12"
i nie"11"
JavaScript (E6) 141 + 3455 = 3596
Funkcja rekurencyjna szuka najbliższego pierwiastka kwadratowego, ale unikając 16, ponieważ 16 * 16 = 256 zostanie zmieniona na 0. Wiele innych odpowiedzi nie otrzymuje tego punktu.
Testuj w konsoli FireFox / FireBug
Wydajność
źródło
Picat, kod 242 + wyjście 3455 = 3697
Informacje na temat programu Picat można znaleźć na stronie http://picat-lang.org/ .
Mniej golfa:
źródło
Python 3 - 4286 + 168 = 4454
Niezbyt poważny, ale niezwykle prosty. Tylko znajdzie najlepszą dodawania do 0, kwadrat, 4 th zasilania
i 8 th moc.EDIT: golfed 75 bajtów, 8 th moc nic nie zrobił
EDYCJA 2: Usunięto niektóre bajty, aby poprawnie zaimplementować
d
. Wynik jednak wzrósł.Python 3 - 2594 + 201 = 2795
Ten wykorzystuje rodzaj wyszukiwania w głąb, aby znaleźć najkrótszy program. Dodałem do niego kilka (niepotrzebnych?) Optymalizacji, aby uzyskać wynik; w ten sposób nie musi biegać tak wiele ścieżek. Może spróbuj usunąć niektóre z nich. Nie pokonuje JS, ponieważ wykorzystuje inteligentne sztuczki, takie jak wielokrotne
o
.EDYCJA: Grał w golfa z 93 bajtami, najwyraźniej miałem wiele bzdur kodu pozostawionych tam przez rozwój. Usunąłem również wszystko, co do tej pory uważałem za niepotrzebne. Nadchodzę, JS.
EDYCJA 2: Grał w golfa o kolejne 8 bajtów. To
return
było niepotrzebne.EDYCJA 3: Grał w golfa o dodatkowe 5 bajtów. Teraz, kiedy się tego pozbyliśmy, możemy po prostu umieścić
elif
zamiast tegoreturn
.EDYCJA 4: Poprawiono funkcjonalność
d
. Rozmiar powiększony o 1 bajt, wynik o niektóre bajty.źródło
APL: 80 + 3456 = 3536
Objaśnienie: (poprawione po notatce edc65, dzięki)
⍵ <4: ⍵⍴'i 'Jeśli argument jest mniejszy niż 3, powtórz „i” tyle razy
(⌈, ⌊) ⍵ * .5 ⍵ jest argumentem, weź pierwiastek kwadratowy i weź sufit i podłogę
| ⍵-2 * ⍨ podnieś sufit i podłogę do potęgi 2, usuń argument i zrób pozytyw
b ← ⊃ (>, <, =) / pobierz wektor boolowski za pomocą a> b, a
(⍵> 240) ⌽ Aby uniknąć przejścia do 256, wykonaj „i” dla liczb powyżej 240 zamiast ^ 2
b / „identyfikatory” używają tej wartości logicznej, aby pobrać i, d lub s i dołączyć ją do rozwiązania za pomocą,
, ∇ (-⊃b) + b [2] + ⍵ * ÷ 1 + 3⊃b Rekurencyjnie wywołuje funkcję z argumentem -b 1 + b [2] podniesionym do potęgi (odwrotność b [3] +1)
Może zliczyć moc wyjściową za pomocą:
¨ stosuje funkcję do każdej liczby 0-255
+ / ⊃, / ⍴¨ liczy całkowitą liczbę elementów
Ponownie możesz wypróbować wszystkie powyższe na TryApl.org
BTW: To jest 3456, a nie 3455, ponieważ rozważam również 0, ponieważ myślę, że problem był pytaniem. Jeśli jest to 1-255, wynik wynosi 80 + 3455 = 3535
źródło
Python 2712 = 2608 + 104
Kod:
Posługiwać się:
0-255 Kod:
źródło
CJam,
2436 2392 22962173 ( 74 znaków + 2099)Co przekłada się na:
Próbuje zoptymalizować długość kodu Deadfish, wybierając najkrótszą ścieżkę do osiągnięcia każdej cyfry liczby.
Dzięki Martin za tłumaczenie Unicode
Oto pełna lista kodów
Wypróbuj online tutaj:
źródło
o
drukuje się nowa linia. Wszystkie kompilatory również drukowały po prostu bez nowej linii.C printf("%d\n",x);
C# Console.WriteLine(x)
GO fmt.Println(x)
pascal WRITELN(val);
python print accumulator (no comma)
bash echo $no;; (no -n)