Gra BattleBlock Theatre czasami zawiera układankę, która jest uogólnioną wersją Lights Out . Masz trzy sąsiadujące bloki, z których każdy wskazuje poziom od 1 do 4 włącznie z paskami, np .:

|
||||
||

Jeśli dotkniesz bloku, to ten blok, podobnie jak każdy sąsiedni blok, zwiększy jego poziom (zawijając z 4 do 1). Układanka jest rozwiązana, gdy wszystkie trzy bloki pokazują ten sam poziom (nie ma znaczenia, który poziom). Ponieważ kolejność dotykania bloków nie ma znaczenia, oznaczamy rozwiązanie według częstotliwości dotykania każdego bloku. Optymalnym rozwiązaniem dla powyższych danych wejściowych byłoby 201:

|    --> || --> |||     |||
||||     |      ||      |||
||       ||     ||  --> |||

Gra bardzo łatwo generalizuje dowolną liczbę bloków, chociaż w przypadku niektórych liczb nie wszystkie konfiguracje są rozwiązywalne.

Wyzwanie

Biorąc pod uwagę sekwencję poziomów bloków, zwróć, jak często każdy blok musi być dotykany, aby rozwiązać zagadkę. Np. Powyższy przykład zostałby podany jako 142i mógłby dać 201wynik. Jeśli nie ma rozwiązania, zwróć wybrane, spójne wyjście, które można odróżnić od wszystkich potencjalnych rozwiązań, np. -1Pusty ciąg.

Możesz napisać funkcję lub program, wziąć dane wejściowe przez STDIN, argument wiersza poleceń lub argument funkcji, w dowolnym dogodnym formacie listy lub ciągu znaków, i podobnie wyprowadzić dane poprzez wartość zwracaną lub drukując do STDOUT.

Twój kod powinien zwrócić poprawne wyniki dla wszystkich przypadków testowych w ciągu minuty na rozsądnej maszynie. (Nie jest to całkowicie ścisły limit, więc jeśli twoje rozwiązanie zajmie minutę i dziesięć sekund, to dobrze, ale jeśli zajmie to 3 minuty, nie będzie. Dobry algorytm łatwo je rozwiąże w kilka sekund.)

To jest kod golfowy, więc wygrywa najkrótsza odpowiedź (w bajtach).

Przykłady

Rozwiązania nie są unikalne, więc możesz uzyskać różne wyniki.

Input                          Output

1                              0
11                             00
12                             No solution
142                            201
434                            101
222                            000
4113                           0230
32444                          No solution
23432                          10301
421232                         212301
3442223221221422412334         0330130000130202221111
22231244334432131322442        No solution
111111111111111111111222       000000000000000000000030
111111111111111111111234       100100100100100100100133
412224131444114441432434       113013201011001101012133

O ile mi wiadomo, istnieją dokładnie 4 rozwiązania dla każdego wejścia, w których liczba bloków wynosi 0 mod 3 lub 1 mod 3, a istnieją 0 lub 16 rozwiązań, w których jest to 2 mod 3.

Python 2, 115 bajtów

n=input()
for F in range(4):
 t=[F];b=0;exec"x=(-n[b]-sum(t[-2:]))%4;t+=x,;b+=1;"*len(n)
 if x<1:print t[:-1];break

To jest wersja programu w golfa, którą napisałem podczas omawiania problemu z Martinem.

Dane wejściowe to lista za pośrednictwem STDIN. Dane wyjściowe to lista reprezentująca ostatnie znalezione rozwiązanie, jeśli istnieje rozwiązanie, lub zero, jeśli go nie ma. Na przykład:

>>>
[1, 4, 2]
[2, 1, 1]
>>>
[1, 2]
0
>>>
map(int,"3442223221221422412334")
[2, 3, 3, 2, 1, 3, 2, 0, 0, 2, 1, 3, 2, 2, 0, 0, 2, 2, 3, 1, 1, 3]

Pyth, 32 29 bajtów

V4J]NVQaJ%_+s>J_2@QN4)I!eJPJB

Port obowiązkowy. Dzięki @Jakube za oszczędność 3 bajtów.

Metoda wprowadzania jest taka sama jak powyżej, spróbuj online .

Wyjaśnienie (długie i pełne logiki!)

Po pierwsze, dwie podstawowe obserwacje:

• Uwaga 1: Nie ma znaczenia, w jakiej kolejności dotkniesz bloków

• Uwaga 2: Jeśli dotkniesz bloku 4 razy, jest to równoznaczne z dotknięciem go raz

Innymi słowy, jeśli istnieje rozwiązanie, wówczas istnieje rozwiązanie, w którym liczba dotknięć wynosi od 0 do 3 włącznie.

Ponieważ modulo 4 jest tak fajny, zróbmy to również z blokami. W pozostałej części tego objaśnienia poziom bloku 0 jest równoważny poziomowi bloku 4.

Teraz oznaczmy, a[k]że jest to bieżący poziom bloku ki x[k]to, ile razy dotykamy bloku kw rozwiązaniu. Niech także nbędzie całkowitą liczbą bloków. Jak zauważył @Jakube, rozwiązanie musi spełniać:

  a[0]   + x[0] + x[1]
= a[1]   + x[0] + x[1] + x[2]
= a[2]          + x[1] + x[2] + x[3]
= a[3]                 + x[2] + x[3] + x[4]
...
= a[n-1]                                     ...  + x[n-2] + x[n-1] + x[n]
= a[n]                                       ...           + x[n-1] + x[n]
= C

gdzie Cjest ostateczny poziom, na którym kończą się wszystkie bloki, od 0 do 3 włącznie (pamiętaj, że traktujemy poziom 4 jako poziom 0), a wszystkie powyższe równania są naprawdę przystające modulo 4.

Oto zabawna część:

• Uwaga 3 : Jeśli istnieje rozwiązanie, istnieje rozwiązanie dla dowolnego końcowego poziomu bloku 0 <= C <= 3.

Istnieją trzy przypadki oparte na liczbie bloków modulo 3. Wyjaśnienie każdego z nich jest takie samo - dla dowolnej liczby bloków istnieje podzbiór bloków, który, jeśli dotkniesz każdego z nich raz, zwiększa wszystkie poziomy bloków o dokładnie 1.

0 mod 3 (touch every third block starting from the second):
    .X. / .X. / .X.

1 mod 3 (touch every third block starting from the first):
    X. / .X. / .X. / .X

2 mod 3 (touch every third block starting from either the first or second):
    X. / .X. / .X. / .X.
    .X. / .X. / .X. / .X

To wyjaśnia, dlaczego istnieją 4 rozwiązania dla 0 mod 3i 1 mod 3, a zazwyczaj 16 do rozwiązania 2 mod 3. Jeśli masz już rozwiązanie, dotknięcie bloków jak wyżej daje kolejne rozwiązanie, które kończy się na wyższym poziomie bloku (owijanie się).

Co to znaczy? Możemy wybrać dowolny końcowy poziom bloku, Cjaki chcemy! Wybierzmy C = 0, ponieważ oszczędza to bajty.

Teraz nasze równania stają się:

0 = a[0] + x[0] + x[1]
0 = a[1] + x[0] + x[1] + x[2]
0 = a[2] + x[1] + x[2] + x[3]
0 = a[3] + x[2] + x[3] + x[4]
...
0 = a[n-1] + x[n-2] + x[n-1] + x[n]
0 = a[n] + x[n-1] + x[n]

I przestawiaj:

x[1] = -a[0] - x[0]
x[2] = -a[1] - x[0] - x[1]
x[3] = -a[2] - x[1] - x[2]
x[4] = -a[3] - x[2] - x[3]
...
x[n] = a[n-1] - x[n-2] - x[n-1]
x[n] = a[n] - x[n-1]

Widzimy więc, że jeśli mamy x[0], możemy użyć wszystkich równań oprócz ostatniego, aby się dowiedzieć x[k]. Ostatnie równanie jest dodatkowym warunkiem, który musimy sprawdzić.

To daje nam algorytm:

• Wypróbuj wszystkie wartości dla x[0]
• Użyj powyższych równań, aby opracować wszystkie pozostałe x[k]
• Sprawdź, czy ostatni warunek jest spełniony. Jeśli tak, zapisz rozwiązanie.

To daje powyższe rozwiązanie.

Dlaczego więc czasami nie dostajemy rozwiązania 2 mod 3? Spójrzmy jeszcze raz na te dwa wzory:

X. / .X. / .X. / .X.
.X. / .X. / .X. / .X

Rozważmy teraz równania dla tych pozycji, tj. Dla pierwszego:

0 = a[0] + x[0] + x[1]
0 = a[3] + x[2] + x[3] + x[4]
0 = a[6] + x[5] + x[6] + x[7]
0 = a[9] + x[8] + x[9] + x[10]

Dodaj je:

0 = (a[0] + a[3] + a[6] + a[9]) + (x[0] + x[1] + ... + x[9] + x[10])

Po drugie:

0 = a[1] + x[0] + x[1] + x[2]
0 = a[4] + x[3] + x[4] + x[5]
0 = a[7] + x[6] + x[7] + x[8]
0 = a[10] + x[9] + x[10]

Dodaj je ponownie:

0 = (a[1] + a[4] + a[7] + a[10]) + (x[0] + x[1] + ... + x[9] + x[10])

Więc jeśli (a[1] + a[4] + a[7] + a[10])i (a[0] + a[3] + a[6] + a[9])nie są równi, to nie mamy rozwiązania. Ale jeśli są równe, otrzymujemy 16 rozwiązań. Tak było w n = 11przypadku, ale oczywiście uogólnia się na dowolną liczbę, którą jest 2 mod 3- weź sumę co trzeciego elementu, zaczynając od drugiego, i porównaj z sumą co trzeciego elementu, zaczynając od pierwszego.

Czy w końcu można dowiedzieć się, co x[0]musi być, zamiast wypróbować wszystkie możliwości? W końcu, ponieważ ograniczyliśmy nasz poziom docelowy Cdo 0, istnieje tylko jeden, x[0]który daje rozwiązanie w przypadku 0 mod 3lub 1 mod 3(as 4 solutions / 4 final levels = 1 solution for a specific final level).

Odpowiedź brzmi tak! Możemy to zrobić dla 0 mod 3:

 .X..X
.X..X.

Co przekłada się na:

0 = a[2] + x[1] + x[2] + x[3]   -> 0 = (a[2] + a[5]) + (x[1] + ... + x[5])
0 = a[5] + x[4] + x[5]          /


0 = a[1] + x[0] + x[1] + x[2]   -> 0 = (a[1] + a[4]) + (x[0] + x[1] + ... + x[5])
0 = a[4] + x[3] + x[4] + x[5]   /

Odejmowanie daje:

x[1] = (a[2] + a[5]) - (a[1] + a[4])

Podobnie 1 mod 3możemy zrobić ten wzór:

 .X..X.
X..X..X

Co daje:

x[0] = (a[2] + a[5]) - (a[0] + a[3] + a[6])

Te oczywiście uogólniają się, rozszerzając indeksy o 3.

Ponieważ 2 mod 3, ponieważ mamy dwa podzbiory, które obejmują każdy blok, możemy wybrać dowolny x[0]. W rzeczywistości dotyczy to x[0], x[1], x[3], x[4], x[6], x[7], ...(w zasadzie każdego indeksu niezgodnego z 2 mod 3, ponieważ nie są one objęte żadnym podzbiorem).

Mamy więc sposób na wybranie x[0]zamiast wypróbowania wszystkich możliwości ...

... ale zła wiadomość jest taka, że ​​nie oszczędza to na bajtach (124 bajty):

def f(n):s=[];L=len(n);B=sum(n[~-L%3::3])-sum(n[-~L%3::3]);x=A=0;exec"s+=B%4,;A,B=B,-n[x]-A-B;x+=1;"*L*(L%3<2or B<1);print s

Pyth, 72 76 73 66 39 38 znaków

Ph+f!eTmu+G%+&H@G_3-@QH@QhH4UtQd^UT2]Y

edycja 4: Uświadomiłem sobie, że obliczenia Q[N]-Q[N+1]+solution[-3]i Q[-2]-Q[-1]+solution[-3]ident. Dlatego przeliczam rozwiązanie o 1 i filtruję rozwiązania, gdzie ostatni wpis to 0. Następnie wstawiam ostatni wpis. Na szczęście specjalne przypadki nie wymagają dodatkowego leczenia przy takim podejściu. -27 znaków

edycja 3: Stosowanie sztuczek golfowych od postaci FryAmTheEggman: -7

edycja 2: Używając filtru, zmniejszania i mapowania: -3 znak

edycja 1: W mojej pierwszej wersji nic nie wydrukowałem, jeśli nie było rozwiązania. Nie sądzę, że jest to dozwolone, dlatego postać +4.

Oczekuje listy liczb całkowitych jako danych wejściowych [1,4,2]i zwraca prawidłowe rozwiązanie, [2,0,1]jeśli istnieje, w przeciwnym razie pusta lista [].

Wyjaśnienie:

Niech Qbędzie lista 5 poziomów i Ylista rozwiązań. Należy uwzględnić następujące równania:

  Q0 + Y0 + Y1 
= Q1 + Y0 + Y1 + Y2
= Q2      + Y1 + Y2 + Y3
= Q3           + Y2 + Y3 + Y4
= Q4                + Y3 + Y4

Dlatego jeśli używamy dowolny Y0i Y1możemy obliczyć Y2, Y3a Y4w następujący sposób.

Y2 = (Q0 - Q1     ) mod 4
Y3 = (Q1 - Q2 + Y0) mod 4
Y4 = (Q2 - Q3 + Y1) mod 4

Niż wszystkie poziomy oprócz ostatniego są równe (ponieważ nie użyliśmy równania = Q4 + Y3 + Y4. Aby sprawdzić, czy ten ostatni jest równy innym poziomom, możemy po prostu sprawdzić, czy (Q3 - Q4 + Y2) mod 4 == 0. Zwróć uwagę, że lewa część będzie wartością Y5Jeśli obliczę szóstą część rozwiązania, mogę po prostu sprawdzić, czy jest to zero.

W moim podejściu po prostu iteruję wszystkie możliwe początki ( [0,0], do [3,3]) i obliczam długość (dane wejściowe) -1 więcej wpisów i filtruję wszystkie rozwiązania, które kończą się na zero.

mu+G%+&H@G_3-@QH@QhH4UtQd^UT2   generates all possible solutions

jest to w zasadzie następujące:

G = start value           //one of "^UT2", [0,0], [0,1], ..., [9,9]
                          //up to [3,3] would be enough but cost 1 char more
for H in range(len(Q)-1): //"UtQ"
   G+=[(H and G[-3])+(Q(H)-Q(H+1))%4] //"+G%+&H@G_3-@QH@QhH4"
   //H and G[-3] is 0, when H is empty, else G[-3]

następnie filtruję te możliwe rozwiązania pod kątem prawidłowych:

f!eT //only use solutions, which end in 0

Do tej listy rozwiązań dołączam pustą listę, aby zawierała co najmniej jeden element

 +....]Y

i weź pierwsze rozwiązanie h, pop ostatni element pi wydrukuj go

 Ph

Zauważ, że to również działa, jeśli jest tylko jeden blok. W moim podejściu uzyskuję pozycję początkową [0,0] i jej nie przedłużam. Ponieważ ostatni wpis to 0, wypisuje rozwiązanie [0].

Drugi przypadek specjalny (2 bloki) wcale nie jest taki wyjątkowy. Nie jestem pewien, dlaczego wcześniej skomplikowałem sprawę.

Ruby, 320 313 znaków

m=gets.chop.chars.map{|x|x.to_i-1}
a=m.map{0}
t=->n{m[n]+=1
m[n-1]+=1if n>0
m[n+1]+=1if n<m.size-1
m.map!{|x|x%4}
a[n]=(a[n]+1)%4}
t[0]until m[0]==1
(2...m.size).map{|n|t[n]until m[n-1]==1}
r=0
while m.uniq.size>1&&m[-1]!=1
(0...m.size).each_with_index{|n,i|([1,3,0][i%3]).times{t[n]}}
(r+=1)>5&&exit
end
$><<a*''

Zdecydowanie można golfa więcej. Nie daje nic dla nierozwiązywalnych łamigłówek.

Wersja bez golfa:

#!/usr/bin/ruby

nums = gets.chomp.chars.map {|x| x.to_i-1 }
touches = nums.map {0}

# our goal: make all the numbers 1
# utility function
touch = ->n {
    nums[n] += 1
    nums[n-1] += 1 if n > 0
    nums[n+1] += 1 if n < (nums.length-1)
    nums.map! {|x| x % 4 }
    touches[n] = (touches[n] + 1) % 4
}

# first, start with the very first number
touch[0] until nums[0] == 1

# then, go from index 2 to the end to make the previous index right
(2...nums.length).each {|n|
    touch[n] until nums[n-1] == 1
}

iters = 0
if nums.uniq.length != 1
    # I have no idea why this works
    while nums[-1] != 1
        (0...nums.length).each_with_index {|n, i|
            ([1, 3, 0][i % 3]).times { touch[n] }
        }
        if (iters += 1) > 5
            puts -1
            exit
        end
    end
end

puts touches * ''

Okej, to było fajne. Oto podstawowy algorytm {n}reprezentujący n „dotyku” na liczbie powyżej n, jak pokazano na jednym z przykładów:

we want each number to be a 1
first make the first number a 1
3442223221221422412334
2}
1242223221221422412334
 {3} now keep "touch"ing until the number to the left is a 1
1131223221221422412334
  {2}
1113423221221422412334
   {2}
1111243221221422412334
... (repeat this procedure)
1111111111111111111110

Trochę mnie tu utknęło. Jak mogę zamienić 111...1110ciąg na te same liczby? Porównałem więc moje rozwiązanie i prawidłowe rozwiązanie (uwaga: liczby „dotykowe” wszystkie są o jeden większe niż powinny, ponieważ dane wejściowe są indeksowane 1, podczas gdy dane wyjściowe są indeksowane 0):

3033233103233301320210
0330130000130202221111

Zauważyłem, że każda liczba jest o jeden od właściwej mod 4, więc oznaczyłem je +s, -s i =s:

3033233103233301320210 original program output
+-=+-=+-=+-=+-=+-=+-=+ amount to modify by (+1, -1, or 0 (=))
4334534404534602621511 result (the correct answer)

0330130000130202221111 (the original solution, digits equal to result mod 4)

To działało przez jakiś czas, dopóki nie zauważyłem, że czasem końcowy wynik był 111...11112lub 11...1113też! Na szczęście wielokrotne stosowanie magicznej formuły, która nie ma sensu, ale prace również je rozwiązały.

Więc masz to. Program, który na początku ma sens, ale z czasem staje się coraz bardziej brzydki. Myślę, że to dość typowe rozwiązanie dla golfa kodowego. :)

Python 2, 294,289,285,281 273 bajtów

n=input();l=len(n);s=[0]*l
for i in range(2,l):
 a=(n[i-2]-n[i-1])%4;s[i]+=a;n[i-1]+=a;n[i]+=a
 if i+1<l:n[i+1]+=a
 n=[a%4for a in n]
if l%3>1 and n!=[n[0]]*l:print"x"
else:
 for i in range(l%3,l-1,3):s[i]+=(n[l-1]-n[l-2])%4
 m=min(s);s=[(a-m)%4 for a in s];print s

PRÓBNY

Jestem pewien, że można dalej grać w golfa ..

Oto wyniki z przypadków testowych:

[1]
-> [0]

[1,1]
-> [0, 0]

[1,2]
-> x

[1,4,2]
-> [2, 0, 1]

[4,3,4]
-> [1, 0, 1]

[2,2,2]
-> [0, 0, 0]

[4,1,1,3]
-> [0, 2, 3, 0]

[3,2,4,4,4]
-> x

[2,3,4,3,2]
-> [0, 0, 3, 3, 1]

[4,2,1,2,3,2]
-> [2, 0, 2, 3, 3, 1]

[3,4,4,2,2,2,3,2,2,1,2,2,1,4,2,2,4,1,2,3,3,4]
-> [0, 3, 3, 0, 1, 3, 0, 0, 0, 0, 1, 3, 0, 2, 0, 2, 2, 2, 1, 1, 1, 1]

[2,2,2,3,1,2,4,4,3,3,4,4,3,2,1,3,1,3,2,2,4,4,2]
-> x

[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,2,2,2]
-> [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3, 0]

[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,2,3,4]
-> [1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 3, 3]

[4,1,2,2,2,4,1,3,1,4,4,4,1,1,4,4,4,1,4,3,2,4,3,4]
-> [1, 0, 3, 0, 0, 3, 2, 3, 1, 0, 0, 1, 0, 3, 1, 1, 3, 1, 0, 0, 2, 1, 2, 3]

Algorytm najpierw upewnia się, że wartości wszystkich bloków oprócz ostatniego bloku są takie same (poprzez iterowanie i dodawanie do „liczeń dotykowych” wszystkich bloków oprócz pierwszych 2). Następnie, jeśli pozwala na to liczba bloków ( (num_of_blocks - 1) % 3 != 1), wraca i sprawdza, czy wartości pozostałych bloków są zgodne z ostatnim blokiem. Drukuje, xjeśli nie ma rozwiązania.