CJam, 25-25 = 0 bajtów
q~1,*_@{[\{1$^}/_](;)\}/;
To tylko prosty port CJam odpowiedzi GolfScript poniżej, ponieważ po przeczytaniu odpowiedzi Martina Büttnera zdałem sobie sprawę, że mogę zaoszczędzić jeden bajt ze względu na obsługę przez CJam liczb całkowitych i typów znaków. (Zasadniczo CJam nie wymaga 1&użycia siły do wymuszenia znaków ASCII na bity w kodzie GolfScript, ale wymaga wcześniejszego qodczytania danych wejściowych.) Zwykle uważam taki trywialny port za tani trick, ale osiągnięcie zerowego wyniku sprawia, że warto IMO.
W każdym razie ten program działa dokładnie tak, jak oryginalny program GolfScript poniżej, więc zapoznaj się z jego opisem i instrukcjami użytkowania. Jak zwykle możesz przetestować wersję CJam za pomocą tego internetowego tłumacza .
GolfScript, 26-25 = 1 bajt
~1,*.@{[1&\{1$^}/.](;)\}/;
To rozwiązanie iteruje ciąg wejściowy tylko raz, więc uważam, że kwalifikuje się do premii -25 bajtów. Działa poprzez wewnętrzne utrzymanie tablicy k- elementów, która przechowuje bieżący bit każdej z k -iteracji.
Dane wejściowe należy podawać za pomocą stdin, w formacie "1111111" 3, tj. Jako cytowany ciąg znaków 0i 1znaki, po których następuje liczba k . Wyjście będzie na standardowe wyjście, jako ciąg bitów bez cudzysłowów.
Przetestuj ten kod online. (Jeśli program przekroczy limit czasu, spróbuj uruchomić go ponownie; serwer Web GolfScript jest znany z przypadkowych przekroczeń limitu czasu).
Oto rozszerzona wersja tego programu z komentarzami:
~ # eval the input, leaving a string and the number k on the stack
1,* # turn the number k into an array of k zeros ("the state array")
. # make a copy of the array; it will be left on the stack, making up the
# first k bits of the output (which are always zeros)
@ # move the input string to the top of the stack, to be iterated over
{
[ # place a start-of-array marker on the stack, for later use
1& # zero out all but the lowest bit of this input byte
\ # move the state array to the top of the stack, to be iterated over
{ 1$^ } / # iterate over each element of the state array, XORing each
# element with the previous value on the stack, and leave
# the results on the stack
. # duplicate the last value on the stack (which is the output bit we want)
] # collect all values put on the stack since the last [ into an array
(; # remove the first element of the array (the input bit)
) # pop the last element (the duplicated output bit) off the array
\ # move the popped bit below the new state array on the stack
}
/ # iterate the preceding code block over the bytes in the input string
; # discard the state array, leaving just the output bits on the stack
Zasadniczo, podobnie jak większość iteracyjnych rozwiązań, kod ten można rozumieć jako zastosowanie powtarzania
b i , j : = b i , ( j −1) ⊕ b ( i −1), ( j −1) ,
gdzie b 0, j jest j -ty bit wejściowy (na j ≥ 1), b k , j jest j -tego bitu wyjściowego, a b I , 0 = 0 założenia. Różnica polega na tym, że podczas gdy rozwiązania iteracyjne w rzeczywistości obliczają rekurencję „wiersz po rzędzie” (tj. Najpierw b 1, j dla wszystkich j , a następnie b 2, j itd.), To rozwiązanie to oblicza kolumnę według kolumna „(lub dokładniej„ przekątna po przekątnej ”), pierwsze obliczenia b i , i dla 1 ≤ i≤ k , następnie b i , i +1 , następnie b i , i +2 itd.
Jedną (teoretyczną) zaletą tego podejścia jest to, że w zasadzie ta metoda może przetwarzać dowolnie długi ciąg wejściowy przy użyciu tylko pamięci O ( k ). Oczywiście interpreter GolfScript automatycznie czyta wszystkie dane wejściowe do pamięci przed uruchomieniem programu, w większości negując tę zaletę.
