Löse das 14-Pegs-Rätsel

8

Einführung

Ein häufiges Puzzle besteht aus einem dreieckigen Brett mit 15 Löchern für T-Stücke, wie in der folgenden Abbildung gezeigt:

Beispiel eines Steckbrettbildes

Beginnend mit allen Stiften im Brett, mit Ausnahme eines Lochs oben, besteht der Sinn des Puzzles darin, Stifte wie Steine ​​so übereinander zu springen, dass genau ein Stift übrig bleibt. Die einzig gültige Bewegung besteht darin, einen Stift über einen benachbarten Stift in eine beliebige Richtung in ein leeres Loch zu springen. Der Stift, der gesprungen wurde, wird dann vom Brett entfernt. Das Spiel endet, wenn keine gültigen Züge mehr vorhanden sind.

Spec

Ihre Aufgabe ist es, ein Programm zu schreiben, das eine vollständige Lösung für das Peg-Puzzle findet, dh eines, bei dem genau ein Peg übrig bleibt. Es gibt mehrere mögliche Lösungen, sodass Ihr Programm nur eine drucken muss.

  • Ihr Programm erhält keine Eingabe. Sie dürfen keine Daten von externen Quellen lesen.
  • Drucken Sie die Liste mit 13 Zügen aus, die ergibt, dass in diesem Format noch 1 Stift übrig ist:

    Peg 1 jumps Peg 3 to Hole 6.

  • Die Löcher / Zapfen sind von oben nach unten von links nach rechts nummeriert, so dass der obere Zapfen / Loch 1 ist und nummeriert wird, bis unten rechts 15 ist.
  • Ihr Programm muss zur Laufzeit die Lösung finden . Das direkte Ausdrucken einer Lösung auf andere Weise als durch Lösen im Programm ist eine automatische Disqualifikation.
  • Bonus : Sie erhalten 10 Bonuspunkte, wenn Sie mehrere eindeutige Lösungen ausgeben können (Sie können nur durch Leerzeilen getrennt drucken).
  • Bonus : Erhalten Sie 5 Bonuspunkte, wenn die Nummer 15nirgends in Ihrem Quellcode erscheint.

Wertung

Dies ist Code-Golf, daher ist die kürzeste Lösung (nach Byte-Anzahl), die eine korrekte Antwort ausgibt, der Gewinner. Bonuspunkte werden von Ihrer Gesamtbytezahl abgezogen. Bitte geben Sie eine Beispielausgabe zum Ausführen Ihres Programms sowie einen Link zu ideoneoder eine ähnliche Site an, wenn möglich, um die Ausführung Ihres Programms zu demonstrieren.

mellamokb
quelle
Wie mischen Sie Bonuspunkte mit dem objektiven Gewinnkriterium, von dem wir nur annehmen können, dass es sich um die Anzahl der Charaktere handelt, da dieses ein Code-Golf-Tag hat?
JB
Klarstellung hinzugefügt "Bonuspunkte werden von Ihrer Gesamtbytezahl abgezogen.", Ist das sinnvoll?
Mellamokb
Der zweite Bonus ist zu leicht zu bekommen15=0xff=(1<4)-1=~(-1<<4)=...
Ratschenfreak
3
Einige Ihrer Darstellungen sind> = 5 Zeichen länger als sich 15selbst;)
mellamokb

Antworten:

8

Ruby, Punktzahl 240 238 234 = 249 - 10 - 5

s=->t,r,c{c>0?(t+t.reverse).gsub(/[A-O]{2}[a-o]/){|j|s[t.tr(j,j.swapcase),r+"Peg #{j[0].ord-64} jumps Peg #{j[1].ord-64} to Hole #{j[2].ord-96}.\n",c-1]}:$><<r+"\n"}
s["aBD,BDG,DGK,CEH,EHL,FIM,aCF,CFJ,FJO,BEI,EIN,DHM,DEF,GHI,HIJ,KLM,LMN,MNO,","",13]

Eine einfache Ruby-Implementierung, die alle möglichen Lösungen für dieses Rätsel druckt (dauert auf meinem Computer weniger als eine Minute). Die ersten Ausgabezeilen sind hier zu sehen:

Peg 6 jumps Peg 3 to Hole 1.
Peg 4 jumps Peg 5 to Hole 6.
Peg 1 jumps Peg 2 to Hole 4.
Peg 14 jumps Peg 9 to Hole 5.
Peg 7 jumps Peg 8 to Hole 9.
Peg 12 jumps Peg 13 to Hole 14.
Peg 10 jumps Peg 6 to Hole 3.
Peg 4 jumps Peg 5 to Hole 6.
Peg 3 jumps Peg 6 to Hole 10.
Peg 15 jumps Peg 10 to Hole 6.
Peg 6 jumps Peg 9 to Hole 13.
Peg 14 jumps Peg 13 to Hole 12.
Peg 11 jumps Peg 12 to Hole 13.

Peg 6 jumps Peg 3 to Hole 1.
Peg 4 jumps Peg 5 to Hole 6.
Peg 1 jumps Peg 2 to Hole 4.
Peg 14 jumps Peg 9 to Hole 5.
Peg 7 jumps Peg 8 to Hole 9.
...

Das Online-Beispiel finden Sie hier .

Howard
quelle
Ich bin gespannt, wie viele Gesamtlösungen es gibt.
Mellamokb
@mellamokb Es heißt, es gibt 29760 Lösungen.
Howard
4
29760 Lösungen? Als ich zum ersten Mal von diesem Spiel erfuhr, brauchte ich ewig, um eines zu finden .
PhiNotPi
2
Das ist merkwürdig. Es gibt 2 ^ 14 (16384) Board-Zustände und wahrscheinlich sind nicht alle erreichbar. Ich hätte gewettet, dass es weniger Lösungen als Staaten gibt.
KaoD
2
@kaoD: Eine Lösung ist eigentlich eine Folge von 13 Zügen (13 aufeinanderfolgende Zustände aus dem ursprünglichen Board-Zustand), von denen es technisch (2 ^ 15) ^ 13 einzigartige Möglichkeiten gibt und von denen eine sehr große Mehrheit nach den Regeln falsch ist . Es gibt auch tatsächlich 2 ^ 15 (32768) mögliche Board-Zustände, da es 15 Löcher gibt, die entweder gefüllt oder leer sein können (von denen eine Handvoll irrelevant sind, da das Board mit einem Loch beginnt)
mellamokb
3

Python, 324 Zeichen, Punktzahl = 319

f=0xf
x=0x12413624725935836a45647b48d58c59e69d6af78989abcdcdedef
Z=[(x>>12*i&f,x>>12*i+4&f,x>>12*i+8&f)for i in range(18)]
M=[[65532,'']]
for i in' '*13:
 Q=[]
 for p,m in M:
  for a,b,c in[x[::-1]for x in Z]+Z:
   if p>>a&p>>b&~p>>c&1:Q+=[[p^2**a^2**b^2**c,m+"Peg %d jumps Peg %d to Hole %d.\n"%(a,b,c)]]
 M=Q
print M[0][1]

Der Peg-Status wird als Bitmaske beibehalten. Menthält eine Liste der Peg-Zustände und die Anweisungen, um zu diesem Zustand zu gelangen.

Ich könnte es auch dazu bringen, alle Lösungen auszudrucken (es gibt 29760 davon), aber es würde mehr als 10 Zeichen kosten, dies zu tun.

Ich kann es nicht auf ideone posten, da es ungefähr 90 Sekunden dauert, bis es ausgeführt wird.

Ausgabe:

Peg 6 jumps Peg 3 to Hole 1.
Peg 4 jumps Peg 5 to Hole 6.
Peg 1 jumps Peg 2 to Hole 4.
Peg 14 jumps Peg 9 to Hole 5.
Peg 12 jumps Peg 13 to Hole 14.
Peg 7 jumps Peg 8 to Hole 9.
Peg 10 jumps Peg 6 to Hole 3.
Peg 4 jumps Peg 5 to Hole 6.
Peg 3 jumps Peg 6 to Hole 10.
Peg 15 jumps Peg 10 to Hole 6.
Peg 6 jumps Peg 9 to Hole 13.
Peg 14 jumps Peg 13 to Hole 12.
Peg 11 jumps Peg 12 to Hole 13.
Keith Randall
quelle
Sie müssen nur mindestens 2 Lösungen ausdrucken, um den 10-Punkte-Bonus zu erhalten.
Mellamokb
3

C, 386 Zeichen, Punktzahl = 371

int f[37],o[36],t[36],r[14],i[14],m=1,s=~3,j=18;main(){while(j--)o[j]=o[18+j]=(f[j]=t[18+j]="AABBCCDDDEEFFGHKLM"[j]-64)+(t[j]=f[18+j]="DFGIHJKMFLNMOIJMNO"[j]-64)>>1;while(m)if(!f[++j])s=r[--m],j=i[m];else if(s>>f[j]&s>>o[j]&~s>>t[j]&1)if(r[m]=s,s^=1<<f[j]|1<<o[j]|1<<t[i[m]=j],j=-1,++m>13)for(m=printf("\n");m<14;++m)printf("Peg %d jumps Peg %d to Hole %d.\n",f[i[m]],o[i[m]],t[i[m]]);}

Druckt alle 29760-Lösungen in weniger als einer Sekunde aus.

Diese Version geht (unter anderem) davon aus, dass der Compiler die implizite Deklaration von printf () zulässt. Mit implicit-int konnten etwa sechs weitere Zeichen gespeichert werden, diese Funktion wurde jedoch technisch aus C99 entfernt.

Außerdem können vier weitere Bytes gespeichert werden, indem die Großbuchstaben in den beiden Zeichenfolgen durch die entsprechenden Steuerzeichen ersetzt werden. Ich habe das hier nicht gemacht, weil Compiler solche Zeichenfolgen nicht zulassen müssen und es bereits dichten Quellcode vollständig unleserlich macht.

Der Klarheit halber ist hier derselbe Algorithmus ohne die verschleierteren Größenoptimierungen:

#include <stdio.h>
int f[37], o[36], t[36], r[14], i[14], m, j, s = ~3;
int main(void)
{
    for (j = 0 ; j < 18 ; ++j) {
        f[j] = t[18+j] = "AABBCCDDDEEFFGHKLM"[j] - 64;
        t[j] = f[18+j] = "DFGIHJKMFLNMOIJMNO"[j] - 64;
        o[j] = o[18+j] = (f[j] + t[j]) >> 1;
    }
    j = 0;
    for (m = 1 ; m ; ++j) {
        if (!f[j]) {
            --m;
            s = r[m];
            j = i[m];
        } else if ((s >> f[j]) & (s >> o[j]) & (~s >> t[j]) & 1) {
            r[m] = s;
            i[m] = j;
            s ^= (1 << f[j]) | (1 << o[j]) | (1 << t[j]);
            j = -1;
            ++m;
            if (m > 13) {
                printf("\n");
                for (m = 1 ; m < 14 ; ++m)
                    printf("Peg %d jumps Peg %d to Hole %d.\n",
                           f[i[m]], o[i[m]], t[i[m]]);
            }
        }
    }
    return 0;
}

f, o und t sind die Liste der in der ersten Schleife initialisierten zulässigen Sprünge. r und ich bilden die Geschichte, die das Programm verwendet, um alle möglichen Spiele zurückzuverfolgen und zu erkunden.

Ich bin sicher, das kann verbessert werden!

Brot-Box
quelle
Es gibt eine Ein-Zeichen-Einsparung bei der Initialisierung, die >>1durch ersetzt wird /2.
Peter Taylor
Die Verwendung von / anstelle von >> würde Parens um den Zusatz benötigen.
Brotkasten
Ah, verstehe die Parens falsch, weil sie sich in der ungolfed unterscheiden.
Peter Taylor