Niech fbędzie funkcją, która mapuje bitfield ( {0 1}) o rozmiarze n+1na pole bitowe o wielkości npoprzez zastosowanie XORdo ith i i+1th bitu i zapisanie wyniku w nowym polu bitowym.

Przykład: f("0101") = "111"

Nieformalne obliczenia:

0 XOR 1 = 1

1 XOR 0 = 1

0 XOR 1 = 1

Niech f_inversebędzie funkcją odwrotną do f. Ponieważ odwrotność nie jest unikalna, f_inversezwraca jedno prawidłowe rozwiązanie.

Dane wejściowe: pole bitowe jako ciąg znaków (tj. "0101111101011") I podana liczba naturalnak

Dane wyjściowe: pole bitowe jako ciąg, dzięki czemu ciąg zawiera wynik, jeśli f_inversezostanie zastosowany kczas na wejściowym polu bitowym. (tj. f_inverse(f_inverse(f_inverse(input))))

Kryteria wygranej: najmniej znaków

Premia:

-25Znaki, jeśli f_inversenie są stosowane rekurencyjnie / iteracyjnie, zamiast tego łańcuch wyjściowy jest obliczany bezpośrednio

Skrypt testowy:

a = "011001"
k = 3

def f(a):
    k = len(a)
    r = ""
    for i in xrange(k-1):
        r += str(int(a[i]) ^ int(a[i+1]))
    return r

def iterate_f(a, k):
    print "Input ", a
    for i in xrange(k):
        a = f(a)
        print "Step " + str(i+1), a

iterate_f(a, k)

Możesz go wkleić na przykład tutaj, a następnie wypróbować.

Pyth 33 30-25 = 5 bajtów

Jiz8K+lzQ%"%0*o",KuxG/G8rQ^2KJ

Uruchom go przez wejście takie jak stdin (interpreter online: https://pyth.herokuapp.com/ ):

111
3

a wynik zostanie zapisany na standardowe wyjście.

To jest bezpośrednie tłumaczenie:

Python 2, 127 118 79 - 25 = 54 bajty

def i(s,k):
 l=int(s,8);t=len(s)+k
 while k<1<<t:l^=l/8;k+=1
 print'%0*o'%(t,l)

Nazwij to tak i("111", 3), a wynik zostanie zapisany na standardowe wyjście.

Zauważ, że spodziewamy się, że k nie będzie zbyt duży, ponieważ dla celów gry w golfa wewnętrzna pętla będzie działać przez O (2 ^k ) razy.

Myślę, że zwykle nazywamy tę operację „xorshift” lub coś w tym rodzaju. Jeśli wyrażamy dane wejściowe jako liczby całkowite big-endian, to funkcja f jest po prostu:

• f (x) = x ⊕ (x ≫ 1)

Jeśli zastosujemy dwukrotnie f , otrzymamy:

• f ² (x) = x ⊕ (x ≫ 2)

Jednak zastosowanie 3 razy będzie miało inny wzór:

• f ³ (x) = x ⊕ (x ≫ 1) ⊕ (x ≫ 2) ⊕ (x ≫ 3)

4 razy wróć do podstawowej formy:

• f ⁴ (x) = x ⊕ (x ≫ 4)

I tak dalej:

• f ^{2 k} (x) = x ⊕ (x ≫ 2 ^k )

Zauważ, że jeśli wybierzemy wystarczająco duże 2 ^k , to (x ≫ 2 ^k ) = 0, co oznacza f ^{2 k} (x) = x, a odwrotność jest trywialnie funkcją tożsamości!

Więc strategii znalezienia f ^-k (x) bez wywoływania f ^-1 (x) w ogóle jest:

1. Znajdź K taki, że:

   • K ≥ k
   • K> log ₂ x
   • K jest potęgą 2

2. Wyraźne f ^-k (x) = f ^{-K + (KK),} (x) = f ^-K (F ^KK (X)) = f ^Kk (x)

3. Zatem wynik fnazywa się czasami Kk

4. 25 znaków zysku: p

Aktualizacja 1 : Użyto reprezentacji ósemkowej zamiast binarnej, abyśmy mogli użyć %formatowania do zapisania dużej ilości bajtów.

Aktualizacja 2 : Wykorzystaj okresową strukturę f. Wycofano wersję iteracyjną, ponieważ wersja nie iteracyjna jest krótsza nawet bez premii -25 bajtów.

Aktualizacja 3 : Zredukowano 3 bajty z Pyth, dzięki isaacg!

CJam, 15 14 bajtów

l~{0\{1$^}/]}*

Przyjmuje dane wejściowe jak

"111" 3

Sprawdź to tutaj.

Wyjaśnienie

l~{0\{1$^}/]}*
l~             "Read and evaluate input.";
  {         }* "Repeat k times.";
   0\          "Push a 0 and swap it with the string/array.";
     {   }/    "For each element in the string/array.";
      1$       "Copy the previous element.";
        ^      "XOR.";
           ]   "Wrap everything in a string/array again.";

Wynik jest automatycznie drukowany na końcu programu.

Mówię „ciąg / tablica”, ponieważ zaczynam od łańcucha (który jest tylko tablicą znaków), ale wciąż biorę XOR między nimi i między liczbami. Character Character ^podaje liczbę całkowitą (na podstawie XOR punktów kodowych) Character Integer ^i Integer Character ^daje znak (na podstawie XOR liczby z punktem kodowym - interpretowane jako punkt kodowy). I Integer Integer ^oczywiście podaje tylko liczbę całkowitą.

Więc rodzaje lecą wszędzie, ale na szczęście, kiedy mam całkowitą to albo 0czy 1i kiedy mam postać to albo '0a '1, a wynik jest zawsze pożądana jeden (w obu typów). Ponieważ ciągi znaków to tylko tablice znaków, mieszanie znaków z cyframi nie stanowi żadnego problemu. Na koniec, gdy wszystko jest drukowane, znaki nie mają specjalnych separatorów, więc na wynik nie ma wpływu, który bit jest reprezentowany jako liczba lub znak.

J, 17 znaków

Zawsze używaj 0 jako cyfry wiodącej.

   (~:/\@]^:[,~[$0:)

   3 (~:/\@]^:[,~[$0:) 1 1 1 
0 0 0 1 0 0

Zaczynając od stanu 128 1 w górnym rzędzie (po lewej) i losowego (po prawej), pokazując ostatnie 128 cyfr przez pierwszą iterację 129.

   viewmat (~:/\)^:(<129) 128$1               viewmat (~:/\)^:(<129) ?128$2

APL 11

((0,≠\)⍣⎕)⎕

Wyjaśnienie:

≠\  compare increasing number of elements (1 1 1 ->1 0 1)
0,    add a starting zero
()⍣⎕  repeat the function in parenthesis ⎕ times, ⎕ is the second argument
()⎕   apply all to ⎕, that is first argument

Spróbuj na tryapl.org

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ę.

Python, 94 78

Zostanie wykonany przynajmniej raz, a tym samym daje ten sam wynik dla n=0in=1

def f(x,n):
 c='0'
 for i in x:c+='10'[i==c[-1]]
 return f(c,n-1)if n>1 else c

Stara wersja, która konwertuje ciąg na tablicę numeryczną i „integruje” moduł 2

from numpy import*
g=lambda x,n:g(''.join(map(str,cumsum(map(int,'0'+x))%2)),n-1)if n>0 else x

Python 2, 68

g=lambda l,n,s=0:n and g(`s`+(l and g(l[1:],1,s^(l>='1'))),n-1)or l

Całkowicie zwrotne rozwiązanie. Łatwiej to zrozumieć, jeśli jest podzielony na dwie funkcje

f=lambda l,s=0:`s`+(l and f(l[1:],s^(l>='1')))
g=lambda l,n:n and g(f(l),n-1)or l

gdzie foblicza kolejne różnice i gkomponuje się fze sobą n razy.

Funkcja foblicza skumulowane sumy XOR l, które są operacją odwrotną do kolejnych różnic XOR. Ponieważ dane wejściowe są podawane jako ciąg, musimy wyodrębnić int(l[0]), ale zrób to krócej w porównaniu z ciągiem l>='1'.

Python 2, 69

Iteracyjne rozwiązanie wykorzystujące execpętlę okazało się 1 znak dłużej.

l,n=input()
exec"r=l;l='0'\nfor x in r:l+='10'[l[-1]==x]\n"*n
print l

Może istnieje krótszy sposób radzenia sobie ze sznurkiem. Gdybyśmy mogli mieć wejścia / wyjścia jako listy liczb, zaoszczędziłoby to 5 znaków

l,n=input()
exec"r=l;l=[0]\nfor x in r:l+=[l[-1]^x]\n"*n
print l

Perl 5, 34

#!perl -p
s/ .*//;eval's/^|./$%^=$&/eg;'x$&

Parametry podane na standardowym wejściu oddzielone spacją.

$ perl a.pl  <<<"1101 20"
101111011011011011010110

JavaScript ES6, 47 znaków

f=(s,k)=>k?f(0+s.replace(s=/./g,x=>s^=x),--k):s

Nawiasem mówiąc, nie ma efektów ubocznych :)

C # - 178 161 115 znaków

static string I(string a, int k){var s = "0";foreach(var c in a)s+=c==s[s.Length-1]?'0':'1';return k<2?s:I(s,--k);}

Nie golfowany z uprzężą

using System;
using System.Text;

namespace InverseXOR
{
    class Program
    {
        static string I(string a, int k)
        {
            var s = "0";
            foreach (var c in a)
                s += c == s[s.Length - 1] ? '0' : '1';
            return k < 2 ? s : I(s, --k);
        }

        static void Main(string[] args)
        {
            Console.WriteLine(I(args[0], Convert.ToInt32(args[1])));
        }
    }
}

CJam, 20 bajtów

q~{:~0\{1$!_!?}/]s}*

Dane wejściowe są jak "111" 3

Wypróbuj online tutaj