Wyobraź sobie, że masz dwa pola B(x)
i B(y)
każdy z nich zawiera nieznany bit - 0 lub 1 oraz maszynę, F
która może je prześwietlić i wytworzyć trzecie pole dla B(x^y)
( xor ). F
może również obliczyć B(x*y)
( i ). W rzeczywistości są to tylko szczególne przypadki pojedynczej operacji, którą może wykonać maszyna - każda z nich to produkt wewnętrzny oznaczony F()
poniżej.
Dla dwóch tablic o tej samej długości
[B(x[0]), B(x[1]), ..., B(x[n-1])]
[B(y[0]), B(y[1]), ..., B(y[n-1])]
produkt wewnętrzny jest zdefiniowany jako
B(x[0]*y[0] ^ x[1]*y[1] ^ ... ^ x[n-1]*y[n-1])
„ Każdy ” oznacza F()
może przetwarzać wiele par x[]
, y[]
za jednym zamachem. Od x[]
i y[]
od jednej pary muszą być tej samej długości; x[]
-s i y[]
-s z różnych par niekoniecznie muszą.
Pola są reprezentowane przez unikalne identyfikatory liczb całkowitych.
Może wyglądać implementacja produktu wewnętrznego w JavaScript
var H=[0,1]; // hidden values, indexed by boxId
function B(x) { // seal x in a new box and return the box id
return H.push(x)-1;
}
function F(pairs) { // "inner product each"
return pairs.map(function (pair) {
var r = 0, x = pair[0], y = pair[1];
for (var i = 0; i < x.length; i++) r ^= H[x[i]] * H[y[i]];
return B(r);
})
}
(Proszę przetłumaczyć powyższe na wybrany język).
Biorąc pod uwagę dostęp do F()
implementacji odpowiedniej dla twojego języka (ale nie ma dostępu do H
lub B()
) i podane dwie tablice identyfikatorów pól stanowiących 16-bitowe reprezentacje binarne dwóch liczb całkowitych, a
a b
Twoim zadaniem jest wytworzenie identyfikatorów pól dla 16-bitowej reprezentacji binarnej od a+b
(przepełnienie odrzucając) z minimalną liczbą F()
połączeń.
Rozwiązanie, które wywołuje F()
najmniej czasu, wygrywa. Więzy zostaną zerwane przez policzenie łącznej liczby x[],y[]
par, F()
z którymi wywołano - mniej znaczy lepiej. Jeśli nadal jest związany, rozmiar twojego kodu (wyłączając implementację F()
i jego pomocników) określa zwycięzcę w tradycyjny sposób golfa. Jako odpowiedzi użyj tytułu „MyLang, 123 połączenia, 456 par, 789 bajtów”.
Napisz funkcję lub pełny program. Dane wejściowe / wyjściowe / argumenty / wynik są tablicami int w dowolnym rozsądnym formacie. Reprezentacja binarna może być mała lub duża - wybierz jedną.
Dodatek 1: Aby nieco ułatwić wyzwanie, możesz założyć, że pola o identyfikatorach 0 i 1 zawierają wartości 0 i 1. Daje to stałe, przydatne np. Do negacji ( x^1
to „nie”). Oczywiście istniały sposoby obejścia braku stałych, ale reszta wyzwania i tak jest wystarczająco trudna, więc wyeliminujmy to rozproszenie.
Dodatek 2: Aby wygrać nagrodę, musisz wykonać jedną z następujących czynności:
opublikuj swój wynik (połączenia, pary, bajty) i kod przed upływem terminu
opublikuj swój wynik i skrót sha256 kodu przed upływem terminu; następnie opublikuj rzeczywisty kod w ciągu 23 godzin po terminie
F
tylko raz. To z pewnością byłoby oszustwo, ale nie jestem pewien, czy byłoby to dobre oszustwo, czy złe.y=f(x)
i pozwolęx
polegaćy
.data Box = B Int deriving (Show); f :: [[[Box]]] -> [Box]
Potrzebuję więcej czasu, aby dowiedzieć się, jak wdrożyćf
(Haskell zmusza tu małe litery) - jutro spróbuję.Odpowiedzi:
Python 3 , 5 połączeń, 92 pary, 922 bajty
Python 3 , 5 połączeń, 134 pary, 3120 bajtówPython 3 , 6 wywołań, 106 par, 2405 bajtów[JavaScript (Node.js)], 9 wywołań, 91 par, 1405 bajtówJavaScript (Node.js), 16 wywołań, 31 par, 378 bajtówWypróbuj online!
PIERWSZA WERSJA Dobra, to nie gra w golfa. To tylko adaptacja kodu @ ngn.
Jedynym pomysłem jest to, że nie musisz obliczać ostatniego przeniesienia, ponieważ odrzucasz przepełnienie. Połączenia
F
są również pogrupowane według dwóch. Być może można je pogrupować w inny sposób, ale wątpię, czy można znacznie zmniejszyć liczbę par ze względu na charakter podstawowego algorytmu dodawania.EDYCJA : Wciąż nie grałem w golfa. Z pewnością można by zmniejszyć liczbę par, a prawdopodobnie także liczbę połączeń. Zobacz https://gist.github.com/jferard/864f4be6e4b63979da176bff380e6c62 celu uzyskania „dowodu” z sympią.
EDYCJA 2 Przełączono na Python, ponieważ jest dla mnie bardziej czytelny. Teraz mam ogólną formułę, myślę, że mogę osiągnąć limit 5 (może 4) połączeń.
EDYCJA 3 Oto podstawowe cegły:
Ogólna formuła to:
Rozszerzona wersja to:
5 połączeń wydaje mi się limitem. Teraz mam trochę pracy, aby usunąć pary i zagrać w golfa!
EDYCJA 4 grałem w golfa.
Wersja bez golfa:
Wypróbuj online!
źródło
F()
. Gwarantuję, że istnieje sposób na znaczne ich zmniejszenie (jest to najtrudniejsza część tego wyzwania), a następnie będzie miejsce na optymalizację liczby par, a na końcu oczywiście grę w golfa (ale jest to najmniej ważne kryterium).... + x * y * z + ...
. Nie możemy go użyćF
do oceny, ale jeśli dokonaliśmy obliczeńx * y
z poprzedniegoF
wywołania, musimy tylko:... + (x * y) * z + ...
(pasuje do formatuF
). Grając w sympy, udało mi się oszczędzić połączenia (krok 1: oblicz r0, c0, r1; krok 2: oblicz c1 i niektóre wartości Aux; krok 3: oblicz r2, c2, r3, c3), a teraz szukam ogólnego rozwiązanie.Haskell, 1 połączenie (oszustwo?), 32 pary (można poprawić), 283 bajtów (to samo)
Proszę, nie gniewajcie się na mnie, nie chcę z tym wygrywać, ale w uwagach do wyzwania zachęciłem mnie do wyjaśnienia, o czym mówiłem.
Próbowałem użyć monady stanowej do obsługi dodawania pól oraz zliczania połączeń i par i to działało, ale nie udało mi się sprawić, aby moje rozwiązanie działało w tym ustawieniu. Zrobiłem więc to, co zasugerowałem w komentarzach: po prostu ukryj dane za konstruktorem danych i nie zaglądaj. (Czystym sposobem byłoby użycie oddzielnego modułu i nie eksportowanie konstruktora.) Ta wersja ma tę zaletę, że jest znacznie prostsza.
Ponieważ mówimy o pudełkach bitów, umieszczam
Bool
w nich wartości. Definiujęzero
jako dane pole z bitem zerowym - aone
nie jest potrzebne.Używamy funkcji debugowania,
trace
aby zobaczyć, jak częstof
była wywoływana i z iloma parami.&&&
przegląda pola według dopasowania wzorca, nierówność/=
zastosowana wBool
wartościach wynosixor
.test
Funkcja przyjmuje ślepego binarnego sumatora jako pierwszego argumentu, a następnie dwa numery w którym dodatek jest badane. ZwracaBool
wskazanie, czy test się powiódł. Najpierw tworzone są pola wprowadzania, następnie wywoływany jest sumator, wynik jest rozpakowywany (zunB
) i porównywany z oczekiwanym wynikiem.Zaimplementowałem dwa sumatory, przykładowe rozwiązanie
simple
, dzięki czemu możemy zobaczyć, że dane wyjściowe debugowania działają poprawnie, a moje rozwiązanie używa rekurencji wartościvalrec
.Widzisz, jak się definiuję
res
pod względem samego siebie? Jest to również znane jako wiązanie węzła .Teraz możemy zobaczyć, jak
f
nazywa się to tylko raz:Lub zamień
valrec
na,simple
aby zobaczyć, jakf
jest wywoływany 32 razy.Wypróbuj online! (wyniki śledzenia są wyświetlane w obszarze „Debugowanie”)
źródło
f
jest leniwa, potencjalnie nieskończona lista, która materializuje się podczas iteracji? Obawiam się, że jest to sprzeczne z duchem wyzwania - pozwala ci odłożyć decyzję o tym, co przekazać jako-pierwszyi+1
argument do momentu, gdy uzyskasz wynik odpowiadającyi
-temu. O wiele bardziej interesujące jest ustalenie, ile połączeńf
potrzebujesz, dzięki w pełni zmaterializowanym, niezmiennym argumentom :)f
może pobierać nieskończone dane wejściowe (dodawać nieskończone strumienie bitów, tak!), Nie o to chodzi. Och, a tak naprawdętrace
wiadomość zapewnia, że długość jest skończona i znana na początku. Nie powiedziałbym też, że decyzja jest odroczona: wszystko zostało zaplanowane z wyprzedzeniem, zgodnie z żądaniem, ja po prostu ślepo tasuję pudełka. I zauważ, że nie chodzi o kolejność argumentów: mógłbym to zmienić, abyres
zawierał najpierw wynik, a następnie bity przenoszenia.f
; czy przekazujesz to pole jako kolejny argument w tym samym wywołaniu dof
?JavaScript, 32 połączenia, 32 pary, 388 bajtów
Dyalog APL, 32 połączenia, 32 pary, 270 bajtów
To naiwne przykładowe rozwiązanie, które może służyć jako szablon.
Zauważ, że liczba bajtów musi obejmować tylko sekcję otoczoną „POCZĄTEK / ROZWIĄZANIE KOŃCOWE”.
Wyjaśnienie:
Wybrałem kolejność bitów little-endian (bit
x[0]
jest najmniej znaczący).Zauważ, że mod dodawania 1-bitowego można zrealizować jako
F([[[x,y],[x,y]]])
(to znaczy:x*x ^ y*y
- mnożenie mod 2 jest idempotentne), a mnożenie binarne jakoF([[[x],[y]]])
.Przechodzimy przez bity od najmniej znaczącego do najbardziej znaczącego i na każdym kroku obliczamy bit wyniku i przeniesienie.
To samo w APL Dyalog (ale przy użyciu losowych identyfikatorów skrzynek):
źródło