Das Spiel BattleBlock Theatre enthält gelegentlich ein Puzzle, das eine verallgemeinerte Version von Lights Out ist . Sie haben drei benachbarte Blöcke, von denen jeder eine Stufe zwischen 1 und 4 einschließlich mit Balken anzeigt, z.

|
||||
||

Wenn Sie einen Block berühren, erhöht dieser Block sowie ein beliebiger benachbarter Block seinen Pegel (von 4 auf 1). Das Rätsel ist gelöst, wenn alle drei Blöcke dasselbe Level aufweisen (egal welches Level). Da die Reihenfolge, in der Sie die Blöcke berühren, keine Rolle spielt, geben wir an, wie oft jeder Block berührt wird. Die optimale Lösung für die obigen Eingaben wäre 201:

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

Das Spiel verallgemeinert sehr leicht eine beliebige Anzahl von Blöcken, obwohl für einige Zahlen nicht alle Konfigurationen lösbar sind.

Die Herausforderung

Geben Sie bei einer vorgegebenen Folge von Blockebenen an, wie oft jeder Block berührt werden muss, um das Rätsel zu lösen. ZB würde das obige Beispiel als gegeben 142und könnte 201als Ergebnis ergeben. Wenn es keine Lösung gibt, geben Sie eine konsistente Ausgabe Ihrer Wahl zurück, die von allen möglichen Lösungen unterscheidbar ist, z. B. -1oder eine leere Zeichenfolge.

Sie können eine Funktion oder ein Programm schreiben, Eingaben über STDIN, Befehlszeilenargument oder Funktionsargument in einem beliebigen geeigneten Listen- oder Zeichenfolgenformat vornehmen und auf ähnliche Weise über einen Rückgabewert oder durch Drucken an STDOUT ausgeben.

Ihr Code sollte innerhalb einer Minute auf einem vernünftigen Computer für alle Testfälle korrekte Ergebnisse liefern. (Dies ist kein striktes Limit. Wenn Ihre Lösung also eine Minute und zehn Sekunden dauert, ist das in Ordnung. Wenn es jedoch drei Minuten dauert, ist dies nicht der Fall. Ein guter Algorithmus kann sie problemlos in Sekunden lösen.)

Dies ist Codegolf, daher gewinnt die kürzeste Antwort (in Bytes).

Beispiele

Die Lösungen sind nicht eindeutig, daher erhalten Sie möglicherweise unterschiedliche Ergebnisse.

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

Soweit ich weiß, gibt es genau 4 Lösungen für jeden Eingang, bei denen die Anzahl der Blöcke 0 bis 3 oder 1 bis 3 beträgt, und es gibt 0 oder 16 Lösungen, bei denen es 2 bis 3 beträgt.

Python 2, 115 Bytes

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

Dies ist die Golfversion des Programms, das ich geschrieben habe, als ich das Problem mit Martin besprochen habe.

Eingabe ist eine Liste über STDIN. Die Ausgabe ist eine Liste, die die zuletzt gefundene Lösung darstellt, wenn es eine Lösung gibt, oder Null, wenn es keine gibt. Beispielsweise:

>>>
[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 Bytes

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

Der obligatorische Hafen. Vielen Dank an @Jakube für die 3-Byte-Speicherung.

Die Eingabemethode ist dieselbe wie oben. Versuchen Sie es online .

Erklärung (lang und voller Logik!)

Erstens zwei grundlegende Beobachtungen:

• Beobachtung 1: Es spielt keine Rolle, in welcher Reihenfolge Sie die Blöcke berühren

• Beobachtung 2: Wenn Sie einen Block viermal berühren, entspricht dies einer einmaligen Berührung

Mit anderen Worten, wenn es eine Lösung gibt, dann gibt es eine Lösung, bei der die Anzahl der Berührungen zwischen 0 und einschließlich 3 liegt.

Da Modulo 4 so schön ist, machen wir das auch mit den Blöcken. Für den Rest dieser Erklärung entspricht die Blockstufe 0 der Blockstufe 4.

Bezeichnen a[k]wir nun die aktuelle Blockstufe kund x[k]die Häufigkeit, mit der wir einen Block kin einer Lösung berühren . Geben Sie nauch die Gesamtzahl der Blöcke an. Wie @Jakube festgestellt hat, muss eine Lösung Folgendes erfüllen:

  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

wo C ist das letzte Level, auf dem alle Blöcke enden, zwischen 0 und einschließlich 3 (denken Sie daran, wir behandeln Level 4 als Level 0) und alle obigen Gleichungen sind wirklich Kongruenzen Modulo 4.

Hier ist der lustige Teil:

• Bemerkung 3 : Wenn eine Lösung existiert, existiert eine Lösung für jede letzte Blockstufe 0 <= C <= 3.

Es gibt drei Fälle, basierend auf der Anzahl der Blöcke modulo 3. Die Erklärung für jeden von ihnen ist die gleiche - für jede Anzahl von Blöcken gibt es eine Teilmenge von Blöcken, die, wenn Sie jeden von ihnen einmal berühren, alle Blockebenen um erhöht genau 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

Dies erklärt, warum es 4 Lösungen für 0 mod 3und 1 mod 3und normalerweise 16 Lösungen für gibt 2 mod 3. Wenn Sie bereits eine Lösung haben und die Blöcke wie oben berühren, erhalten Sie eine andere Lösung, die auf einer höheren Blockebene endet (umwickelt).

Also, was bedeutet das? Wir können jede Cgewünschte letzte Blockstufe auswählen ! Lassen Sie uns wählen C = 0, weil dies Bytes spart.

Nun werden unsere Gleichungen:

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]

Und neu anordnen:

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]

Was wir also sehen können, ist, wenn wir haben x[0], dann können wir alle Gleichungen außer der letzten verwenden, um jede andere herauszufindenx[k] . Die letzte Gleichung ist eine zusätzliche Bedingung, die wir überprüfen müssen.

Dies gibt uns einen Algorithmus:

• Probieren Sie alle Werte für x[0]
• Verwenden Sie die obigen Gleichungen, um alle anderen zu berechnen x[k]
• Überprüfen Sie, ob die letzte Bedingung erfüllt ist. Wenn ja, speichern Sie die Lösung.

Das ergibt die obige Lösung.

Warum bekommen wir manchmal keine Lösung dafür 2 mod 3? Werfen wir noch einmal einen Blick auf diese beiden Muster:

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

Betrachten Sie nun die Gleichungen an diesen Positionen, dh für die erste:

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]

Addiere sie:

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

Für den zweiten:

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]

Addiere sie noch einmal:

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

Wenn also (a[1] + a[4] + a[7] + a[10])und (a[0] + a[3] + a[6] + a[9])nicht gleich sind, dann haben wir keine Lösung. Wenn sie jedoch gleich sind, erhalten wir 16 Lösungen. Dies war für den n = 11Fall, aber dies verallgemeinert sich natürlich auf eine beliebige Zahl2 mod 3 - nimm die Summe jedes dritten Elements ab dem zweiten und vergleiche mit der Summe jedes dritten Elements ab dem ersten.

Ist es nun endlich möglich, herauszufinden, was sein x[0]muss, anstatt alle Möglichkeiten auszuprobieren? Da wir unser Ziellevel Cauf 0 begrenzt haben, gibt es nur ein einziges, x[0]das eine Lösung in dem Fall 0 mod 3oder 1 mod 3(as 4 solutions / 4 final levels = 1 solution for a specific final level) gibt.

Die Antwort ist ja! Wir können dies tun für 0 mod 3:

 .X..X
.X..X.

Was bedeutet:

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]   /

Subtrahieren ergibt:

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

Ähnlich 1 mod 3können wir für dieses Muster tun:

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

Welches gibt:

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

Diese verallgemeinern sich natürlich, indem die Indizes in Schritten von 3 erweitert werden.

Für 2 mod 3, da wir zwei Untergruppen haben , die jeden Block abdecken, können wir holen eigentlich jeder x[0]. Tatsächlich gilt dies für x[0], x[1], x[3], x[4], x[6], x[7], ...(im Grunde genommen für jeden Index, der nicht kongruent ist 2 mod 3, da sie von keiner Teilmenge abgedeckt werden).

Wir haben also eine Möglichkeit x[0], alle Möglichkeiten zu wählen, anstatt sie zu versuchen ...

... aber die schlechte Nachricht ist, dass dies nicht an Bytes (124 Bytes) spart:

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 Zeichen

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

edit 4: Es wurde erkannt, dass die Berechnungen Q[N]-Q[N+1]+solution[-3]und Q[-2]-Q[-1]+solution[-3]ident sind. Deshalb überberechne ich die Lösung um 1 und filtere die Lösungen, wobei der letzte Eintrag 0 ist. Dann füge ich den letzten Eintrag ein. Glücklicherweise benötigen die Sonderfälle bei diesem Ansatz keine zusätzliche Behandlung. -27 Zeichen

edit 3: Einige Golftricks von FryAmTheEggman anwenden: -7 Charakter

edit 2: Mit Filter verkleinern und mappen: -3 Zeichen

edit 1: In meiner ersten Version habe ich nichts gedruckt, wenn es keine Lösung gab. Ich denke das ist nicht erlaubt, daher +4 Zeichen.

Erwartet eine Liste von Ganzzahlen als Eingabe [1,4,2]und gibt eine gültige Lösung aus, [2,0,1]falls vorhanden, andernfalls eine leere Liste [].

Erläuterung:

Sei Qdie Liste der 5 Ebenen und Ydie Liste der Lösung. Die folgenden Gleichungen müssen gelten:

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

Deshalb , wenn wir jede verwenden Y0und Y1können wir berechnen Y2, Y3und Y4in der folgenden Weise.

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

Dann sind alle Ebenen außer der letzten gleich (weil wir die Gleichung nicht verwendet haben) = Q4 + Y3 + Y4. Um zu überprüfen, ob diese auch den anderen Ebenen entspricht, können wir einfach prüfen, ob (Q3 - Q4 + Y2) mod 4 == 0. Beachten Sie, dass der linke Teil der Wert ist Y5Wenn ich den 6. Teil der Lösung berechne, kann ich einfach prüfen, ob es Null ist.

In meinem Ansatz iteriere ich einfach über alle möglichen Starts ( [0,0], bis [3,3]) und berechne die Länge (Eingabe) -1 weiterer Einträge und filtere alle Lösungen, die mit einer Null enden.

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

Im Grunde ist es das Folgende:

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]

dann filtere ich diese möglichen Lösungen nach gültigen:

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

Zu dieser Liste von Lösungen füge ich eine leere Liste hinzu, so dass mindestens ein Element darin enthalten ist

 +....]Y

Nehmen Sie die erste Lösung h, platzieren Sie das letzte Element pund drucken Sie es aus

 Ph

Beachten Sie, dass dies auch funktioniert, wenn nur ein Block vorhanden ist. Bei meiner Annäherung erhalte ich die Startposition [0,0] und verlängere sie nicht. Da der letzte Eintrag 0 ist, wird die Lösung [0] gedruckt.

Der zweite Sonderfall (2 Blöcke) ist doch nicht so besonders. Ich bin mir nicht sicher, warum ich die Dinge früher überkompliziert habe.

Ruby, 320 313 Zeichen

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*''

Kann definitiv mehr golfen werden. Gibt nichts für unlösbare Rätsel aus.

Ungolfed-Version:

#!/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 * ''

Okay, das hat Spaß gemacht. Hier ist der grundlegende Algorithmus mit der {n}Darstellung von n "Berührungen" auf der Zahl über n, wie an einem der Beispiele gezeigt:

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

Ich war hier ein bisschen ratlos. Wie kann ich aus 111...1110einer Reihe gleicher Zahlen eine Serie machen? Also habe ich meine Lösung und die richtige Lösung verglichen (Anmerkung: Die "Touch" -Zahlen sind alle um eins höher als sie sein sollten, da die Eingabe 1-indiziert ist, während die Ausgabe 0-indiziert ist):

3033233103233301320210
0330130000130202221111

Mir ist aufgefallen, dass jede Nummer eine andere als die richtige mod 4ist. Deshalb habe ich sie mit +s, -s und =s markiert :

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)

Das hat eine Weile geklappt, bis ich merkte, dass manchmal das Endergebnis 111...11112oder war11...1113 auch! Glücklicherweise hat das wiederholte Anwenden der magischen Formel, die keinen Sinn macht, aber auch funktioniert, diese aussortiert.

Also, da hast du es. Ein Programm, das zunächst Sinn ergibt, sich aber mit der Zeit immer hässlicher macht. Typisch für eine Code-Golf-Lösung, denke ich. :)

Python 2, 294 , 289 , 285 , 281, 273 Bytes

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

DEMO

Ich bin sicher, dass dies weiter golfen werden kann ..

Hier sind die Ergebnisse aus den Testfällen:

[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]

Der Algorithmus stellt zunächst sicher, dass die Werte aller Blöcke mit Ausnahme des letzten Blocks gleich sind (indem er alle Blöcke mit Ausnahme der ersten 2 durchläuft und zu den "Berührungszahlen" addiert). Wenn die Anzahl der Blöcke dies zulässt ( (num_of_blocks - 1) % 3 != 1), wird zurückgegangen und sichergestellt, dass die Werte der übrigen Blöcke mit dem letzten Block übereinstimmen. Druckt, xwenn es keine Lösung gibt.