tło
W niektórych możliwych przyszłościach świat przekształci swój system liczbowy z dziesiętnego (podstawa 10 lub b10
) na jakąś inną bazę (dwójkową b2
, ósemkową b8
, szesnastkową b16
, a nawet jednoargumentową b1
, w którym to przypadku jesteśmy zepsute!). Tak więc, przygotowując się do tego możliwego wydarzenia zmieniającego świat, zdecydujesz się zabezpieczyć wszystkie swoje programy. Można to zrobić, używając tylko liczby pojedynczej 0
si 1
w połączeniu z operatorami w celu zastąpienia istniejących stałych liczbowych.
Jest jednak tylko jeden problem: masz mnóstwo programów do zmiany, a ręczne przekształcenie każdej liczby w wyrażenie zajęłoby tygodnie! Dlatego decydujesz się napisać program (lub funkcję), aby zdecydować, które wyrażenie powinno zastąpić każdą liczbę.
Wkład
Wejście będzie dodatnią liczbą całkowitą. Twój kod musi być w stanie obsłużyć dowolną liczbę całkowitą do 1000.
(Jeśli Twój kod obsługuje wartości dziesiętne i / lub ujemne, patrz punktacja poniżej.)
Wydajność
Twój kod musi wypisywać wyrażenie, które ocenia dane wejściowe w co najmniej jednym języku. Może to być dowolny język; to nie musi być ten sam, w którym zapisany jest Twój program lub funkcja. Ponadto, to wyrażenie nie musi być pełnym programem lub funkcją.
Dla jasności dane wyjściowe mogą zawierać dowolne z następujących operacji:
- przyrost / spadek
- dodaj / suma
- odejmuj / neguj
- pomnożyć / podwójnie (tylko jeśli nie dotyczy bezpośrednio liczby
2
!) - divide / modulo
- wykładniki / logarytmy
- kwadrat / sqrt (ponownie, tylko jeśli nie dotyczą one bezpośrednio liczby
2
!) - operacje bitowe (bOR, bAND, bNOT, bXOR, zmiany bitów)
- ustawianie / uzyskiwanie zmiennych
- manipulacja stosami
Być może nie używać eval()
lub inne podobne funkcje w wyjściu. Nie możesz również używać w danych wyjściowych żadnych funkcji wykonujących działania inne niż wymienione powyżej.
Aha, i jeszcze jedno: ponieważ chcemy, aby dane wyjściowe były poprawne w jak największej liczbie zasad, jedynymi stałymi liczbowymi, które może zawierać, są: 0
i 1
. Liczby takie jak 10
(dziesięć) są niedozwolone, chyba że język interpretuje je jako a 1
i a 0
. Używanie ciągów zawierających liczby również nie jest dozwolone, podobnie jak używanie znaków takich jak CJam A
- K
(które reprezentują 10
- 20
).
Przypadki testowe
(Wszystkie dane wyjściowe są w języku JavaScript, ale mogą działać w innych językach).
Wejście 1:
2
Możliwe wyjście 1:
1+1
Wejście 2:
13
Możliwe wyjście 2:
(a=1+1+1)*a+a+1
Wejście 3:
60
Możliwe wyjście 3:
(b=(a=1+1+1+1)*a)*a-a
Wejście 4:
777
Możliwe wyjście 4:
(c=(b=((a=1+1+1+1)*a-a+1)*a)*a+b)+c+c-a+1
Wejście 5:
1000
Możliwe wyjście 5:
Math.pow((a=1+1+1)*a+1,a)
Punktacja
Celem tego wyzwania jest maksymalne skrócenie danych wyjściowych kodu. Twój wynik zostanie obliczony w następujący sposób:
Wynik podstawowy: średnia liczba bajtów wszystkich wyjść dla liczb całkowitych od 1 do 1000.
Wynik dziesiętny: jeśli kod obsługuje co najmniej 3 miejsca dziesiętne, jest to średnia liczba bajtów wszystkich wyników sekwencji liczb rozpoczynających się
0.001
i kończących o1000
, zwiększana o1.001
każdym razem.0.001, 1.002, 2.003...998.999, 1000.000
Następnie weź 50% zniżki na ten wynik.Wynik ujemny: jeśli kod obsługuje liczby ujemne i zero, jest to średnia liczba bajtów wyjść wszystkich liczb całkowitych z
-1000
do0
. Następnie weź 10% zniżki na ten wynik.
(Najłatwiejszym sposobem ich obliczenia jest prawdopodobnie pętla z programem / funkcją w środku).
Twój końcowy wynik jest średnią z którejkolwiek z powyższych formuł.
Jeśli dane wyjściowe nie są deterministyczne (tj. Nieco losowe; wiele przebiegów z tym samym wejściem daje wiele unikalnych wyników), to wynik dla każdego wejścia jest określany przez największe wyjście z dziesięciu przebiegów na moim CPU.
Ponadto, ponieważ nie wiesz, jak cenne będą dane komputerowe w przyszłości, liczba bajtów kodu generatora musi być mniejsza niż 512 bajtów.
Najniższy wynik od dwóch tygodni (30 września) zostanie ogłoszony zwycięzcą. Gratulacje dla zwycięzcy, @ThomasKwa !
Tabela liderów
Aby upewnić się, że twoja odpowiedź wyświetla się poprawnie, zacznij od tego nagłówka:
# Language name/Other language name, X points
Gdzie X
jest wynik twojej odpowiedzi. Przykład:
# CJam/Pyth, 25.38 points
Jeśli masz jakieś pytania lub sugestie, daj mi znać. Powodzenia!
źródło
0
lub1
domyślnie?Integer.parseInt("1000", 1+1+1+1+1+1+1+1+1+1)
? Jestem pewien, żeparseInt
używa tylko dozwolonych operacji ;-)Odpowiedzi:
Kod maszynowy Python / Zilog Z80,
11.65311.488Bonusy: liczby ujemne.
Zakłada, że
hl
para rejestrów początkowo ma wartość 0 i zwraca wynikhl
.Używane są tylko te trzy instrukcje:
Używamy niewielkiej modyfikacji zrównoważonej reprezentacji binarnej BBR2 o minimalnej wadze . Ponieważ BBR2 minimalizuje wagę (liczbę niezerowych cyfr), ale chcemy zminimalizować wagę plus liczbę przesunięć bitów, zmieniamy stałą w algorytmie z
3/2
na5/3
.Aby obliczyć wynik i zweryfikować, użyj tego kodu:
Przykładowe dane wyjściowe:
Lub w montażu:
Więcej przykładowych programów:
Możliwe optymalizacje: OP określa, że instrukcje
inc h
idec h
, które bezpośrednio zmieniają górny bajthl
, są niedozwolone, alesla h
nieudokumentowanesl1 h
(przesunięcie lewego bitu o 1 odpowiednio dlah
tego przesunięcia w0
ai1
) jest dozwolone.sla h
isl1 h
mają po dwa bajty, ale czasem mogą skrócić wynik.źródło
+
tłumaczydec
. Ciągle czytam negatywne przykłady.CJam / CJam,
143,26342,71328,89923,90121,90320,468Nie obowiązują żadne bonusy.
Wypróbuj online: uruchomienie próbne | kalkulator wyników |weryfikacja
Przykład działa
źródło
%
z nich zastąpiłem dłuższym wyrażeniem. Linki powinny teraz działać.ß / BrainFuck, 34.201 punktów
ß źródło (194B):
Jeśli ktoś jest zainteresowany, dodam wyjaśnienie. Wyjście BF jest już dość zoptymalizowane, ale wydaje mi się, że mógłbym wykorzystać pozostałe 318B kodu ß do implementacji
usuwanie kolizji operatora.Próbki:
Uruchamianie w systemie Windows:
Uruchamianie w systemie Linux:
Zatwierdź w internetowym tłumaczu BF .
Wyniki:
= 37.495
.= 60.959 * 0.5 = ~30.48
.= 38.4765234765235 * 0.9 = ~34.629
= (37.495 + 30.48 + 34.629)/3 = 34.201
.źródło
Ruby / Ruby, 29,77885
31,873 * 0,9 (ujemny) 30,872 (dodatni).
Podstawową strategią jest symetryczna reprezentacja podstawy 3 („zbalansowana trójskładnikowa”), tzn. Kiedy cyfry są
-1,0,1
zamiast0,1,2
Oto wynik od 0 do 40 przed czyszczeniem
I po sprzątaniu
źródło
Ceylon / Ceylon,
49,8640,95 punktówTrzecia wersja wykorzystuje Ceylon 1.2 do generatora i 509 bajtów kodu:
import ceylon.language{S=String,I=Integer,e=expand}S q(I n)=>n==0then"0"else(n<0then"-"+p(-n,"-")else p(n,"+"));variable Map<[I,S],S>c=map{};S p(I n,S s){S v=c[[n,s]]else(n<8then s.join([1].repeat(n)))else(let(a="+-".replace(s,""))e(e{for(x in 2..8)let(l=(n^(1.0/x)).integer){for(r in l:2)if(r>1)let(w=r^x){if(w-n<n)"("+p(r,"+")+")^("+p(x,"+")+")"+(w<n then s+p(n-w,s)else(n<w then a+p(w-n,a)else""))}}}).reduce<S>((x,y)=>x.size<y.size then x else y))else"";c=[n,s]in c then c else map{[n,s]->v,*c};return v;}
Spada do 35,22 punktów, ale nie umieszczę tego w tytule, ponieważ Celyon 1.2 został opublikowany tylko 29 października. Nie sądzę, że byłbym w stanie zaimplementować ten algorytm na Cejlonie 1.1 w tym rozmiarze.) Więcej szczegółów na dole, tutaj opiszę drugą wersję. (Pierwsza wersja jest widoczna w historii - obsługuje tylko liczby dodatnie, ale mieści się w 256 bajtach).
Druga wersja
Teraz druga wersja, która obsługuje ujemne liczby całkowite (i 0) i generalnie generuje nieco krótszy wynik, używając dodatkowo
-
. (Ta wersja faktycznie używa dozwolonej długości, pierwsza próbowała pozostać poniżej 256 bajtów zamiast 512.)Kod ma długość 487, więc jest jeszcze miejsce na późniejsze optymalizacje. (Istnieje również wiele rezerw w postaci białych znaków i długich nazw zmiennych).
Punktacja:
Niektóre przykładowe wyniki:
Jak widać, wartości ujemne są zawsze o jeden bajt (wiodące
-
) dłuższe niż odpowiadające im wartości dodatnie.Podstawowa idea jest taka sama jak w poprzednim programie: znajdź kwadrat w pobliżu naszej liczby docelowej i rekurencyjnie reprezentuj jego pierwiastek, a resztę. Ale teraz pozwalamy, aby nasz kwadrat był również trochę większy niż liczba docelowa, co powoduje, że reszta jest ujemna. (
+0.5
Można zmienić na inną stałą, aby ulepszyć algorytm, ale wygląda na to, że już osiągnąłem tu optymalny - zarówno 0,4, jak i 0,6 dają gorsze wyniki.)Aby wartości ujemne ujemny (a poza tym mają taką samą strukturę jak pozytywnymi mijamy operatora
sign
do naszej funkcji rekurencyjnejp
- to jest albo"+"
albo"-"
. Możemy użyć jej dla stolarza w błahych przypadkach (tj n <9), jak również jak dla reszty, jeśli jest dodatnia, i użyj znaku przeciwnego dla reszty, jeśli jest ujemna.Te
proof
uchwyty funkcyjne początkowy znak (ze szczególnym przypadku do 0), top
funkcja ma rzeczywistej pracy, z rekursji.Trzecia wersja, dla Ceylon 1.2
Wersja w golfa (tj. Usunięte komentarze i białe znaki) jest umieszczona na górze, dokładnie w 509 bajtach kodu.
Wykorzystuje tę samą zasadę podstawową, co druga wersja, ale zamiast zwykłych kwadratów próbuje również użyć wyższych mocy liczb (wypróbowanie wykładników od 2 do 8) i używa najkrótszego wyniku. Zapisuje również wyniki w pamięci podręcznej, ponieważ w przeciwnym razie byłoby to nie do zaakceptowania zbyt wolno dla większych numerów z wieloma rekurencyjnymi połączeniami.
Punktacja:
Duży wcięty konstrukt w środku to trzy zagnieżdżone iteracyjne pojęcia, dwa wewnętrzne w wyrażeniu let. Są one następnie usuwane przy użyciu funkcji rozwinięcia dwukrotnie, a
reduce
funkcja znajduje najkrótszy z tych ciągów.Złożyłem prośbę o funkcję, aby móc to zrobić w jednym zrozumieniu.
Wewnątrz tego pojęcia budujemy ciąg znaków od nasady
r
, wykładnikax
i reszty (n-w
lubw-n
).let
Ekspresja imap
funkcja są nowe na Cejlonie 1.2.map
mógł zostać zastąpiony przezHashMap
(co wymagałoby więcej znaków do importu, chociaż prawdopodobnie byłoby to jeszcze szybsze, ponieważ nie budowałbym mapy nowej dla każdego nowego wpisu). Dolet
wyrażenia jaklet (w = r ^ x)
mogła być zastąpiona przez zastosowanieif
klauzuli podobnegoif(exists w = true then r ^ x)
(i wtedy nie potrzebowałby dwóchexpand
połączeń albo), ale to nadal będzie nieco dłużej, nie mieszczące się wewnątrz dozwolonych 511 bajtów.Tutaj przykładowe dane wyjściowe odpowiadające tym wybranym powyżej, wszystkie z wyjątkiem naprawdę małych liczb są krótsze:
Na przykład teraz mamy 1000 = (3 ^ 2 + 1) ^ 3, zamiast 1000 = (6 ^ 2-4) ^ 2-5 ^ 2 + 1.
źródło
less than 512
. Możesz użyć maks. z 511 bajtów;)Ruby / dc,
20,29618,41416,968Programowanie dynamiczne! Definiuje listę funkcji, które po otrzymaniu instrukcji dc zwracają nowe wyrażenie i wartość liczbową tego wyrażenia. Następnie, zaczynając od
1
preferencji, tworzy listę wszystkich osiągalnych wartości aż do pożądanej wartości.edytować:
Dodano funkcję dla n-1 i zmusiła go do uruchomienia algorytmu przez wiele przejść. Wydaje się, że potrzebuje 7 przejść, aby się ustabilizować. Musiałem skrócić niektóre nazwy zmiennych, aby pozostały w obrębie 512 bajtów.
edycja 2:
Dodano funkcje dla n (n-1) , n (n + 1) i n ^ 3, gdy byłem przy tym. Skróciłem nieco kod, lądując dokładnie na 512 bajtach.
Wygenerowane liczby:
Wynik składa się całkowicie z pięciu różnych znaków:
1
przesuwa wartość 1 na stos;d
duplikuje górę stosu;+
,-
i*
wyświetla dwie najwyższe wartości i przesuwa odpowiednio ich sumę, różnicę i iloczyn. Każde wygenerowane wyrażenie dodaje po wykonaniu tylko jedną wartość do stosu....
źródło
-
operatora, pozostając w liczbie bajtów?Python 2.6,
78.069- 66.265 punktówPrzesłanie mojej odpowiedzi za to, co jest warte (w tym przypadku nie za wiele ... ale jednoznaczne wykazanie, że w przypadku tego wyzwania nie wystarczy po prostu pomyśleć o skomponowaniu wyniku jako sumy przesuniętych bitowo wartości; biorąc pod uwagę, że nie ma cyfr poza 0 lub 1 może pojawić się na wyjściu). Mogę wrócić później z innym sposobem generowania produkcji.
Sam kod nie jest zbyt długi (176 znaków):
Generuje poprawne, ale pełne dane wyjściowe:
Fragment, który oblicza wynik:
źródło