Am 4. Dezember 2017 war Google Doodle ein grafisches Programmierspiel mit einem Hasen . Die späteren Levels waren nicht trivial und sie schienen ein großartiger Kandidat für eine Atomic-Golf- Herausforderung zu sein.

Einzelheiten

Spiel

• Es stehen vier Moves zur Verfügung: Vorwärtsspringen, Links- und Rechtsdrehung und Loop. Jede dieser Bewegungen ist eine Marke , was der Tatsache entspricht, dass es sich bei jeder Bewegung um ein Plättchen im Spiel handelt.
• Der Hase kann vier orthogonale Richtungen haben (dh Norden, Süden, Osten, Westen).
• Der Hase kann vorwärts springen (ein Feld in die Richtung bewegen, in die er schaut) und sich nach links oder rechts drehen.
• Loops können eine beliebige Anzahl anderer Züge enthalten, einschließlich anderer Loops, und ihre Iterationszahl ist eine positive ganze Zahl (obwohl das Spiel technisch eine Iterationszahl von 0 zulässt).
• Das Brett besteht aus einer Reihe von Quadraten, die am Raster ausgerichtet sind, und der Hase kann zwischen benachbarten Quadraten springen.
• Der Hase kann nicht ins Leere springen. Das bedeutet, dass ein Versuch, vom Brett zu springen, nichts bewirkt. (Dies war anscheinend eine Überraschung für einige Leute und eine Enttäuschung für andere.)
• Quadrate sind entweder markiert oder nicht markiert. Wenn sich der Hase auf einem Quadrat befindet, wird er markiert.
• Das Level ist abgeschlossen, wenn alle Quadrate markiert sind.
• Sie können davon ausgehen, dass eine Lösung vorhanden ist.

Dein Code

• Ziel: Finden Sie bei gegebener Tafel eine oder mehrere kürzeste Lösungen.
• Die Eingabe ist eine Liste von Feldpositionen, die das Brett bilden (Unterscheidung zwischen markierten und nicht markierten Feldern), und die Ausgabe ist eine Liste von Zügen. Ein- und Ausgabeformat hat keine Rolle, solange sie für Menschen lesbaren und verständlichen sind.
• Gewinnkriterium: Summe der Züge der kürzesten gefundenen Lösungen innerhalb einer Minute für jedes Brett. Wenn Ihr Programm keine Lösung für eine bestimmte Tafel findet, ist Ihre Punktzahl für diese Tafel (5 * Anzahl der Felder).
• Bitte codieren Sie Lösungen in keiner Weise fest. Ihr Code sollte in der Lage sein, eine beliebige Karte als Eingabe zu verwenden, nicht nur die unten als Beispiele angegebenen.

Beispiele

Lösungen sind in Spoilern versteckt, damit Sie zuerst das Spiel spielen und einige davon selbst ausprobieren können. Im Folgenden wird jeweils nur eine Lösung bereitgestellt.

Sist das Startquadrat des Hasen (nach Osten ausgerichtet), #ist ein nicht markiertes Quadrat und Oist ein markiertes Quadrat. Bei Zügen ist meine Notation F= Vorwärtssprung, L= Links abbiegen, R= Rechts abbiegen und LOOP(<num>){<moves>}bezeichnet eine Schleife, die <num>sich <moves>jedes Mal wiederholt und wiederholt . Wenn die Schleife beliebig oft über eine bestimmte Mindestanzahl hinaus ausgeführt werden <num>kann , kann sie weggelassen werden (dh Unendlich funktioniert).

Level 1:

S##

FF

Level 2:

S##
  #
  #

LOOP (2) {FFR}

Stufe 3:

S##
# #
###

LOOP {FFR}

Level 4:

###
# #
##S##
  # #
  ###

LOOP {F LOOP (7) {FL}} (gefunden von DJMcMayhem)

Level 5:

#####
# # #
##S##
# # #
#####

LOOP (18) {LOOP (10) {FR} L}
Quelle: Reddit

Stufe 6:

 ###
#OOO#
#OSO#
#OOO#
 ###

LOOP {LOOP (3) {F} L}

Riesige Boards: (kürzeste Lösungen derzeit unbekannt)

12x12:

S###########
############
############
############
############
############
############
############
############
############
############
############

Level 5 aber viel größer:

#############
# # # # # # #
#############
# # # # # # #
#############
# # # # # # #
######S######
# # # # # # #
#############
# # # # # # #
#############
# # # # # # #
#############

Weitere löchrige Bretter:

S##########
###########
## ## ## ##
###########
###########
## ## ## ##
###########
###########
## ## ## ##
###########
###########

und

S#########
##########
##  ##  ##
##  ##  ##
##########
##########
##  ##  ##
##  ##  ##
##########
##########

Schließlich kann Asymmetrie ein echtes Ärgernis sein:

#######
# ##  #
#######
###S###
# ##  #
# ##  #
#######

und

#########
# ##  ###
###S  ###
# #######
###    ##
#####   #
####  ###
#########
#########

Python 3, 67 Token

import sys
import time

class Bunny():
    def __init__(self):
        self.direction = [0, 1]
        self.coords = [-1, -1]

    def setCoords(self, x, y):
        self.coords = [x, y]

    def rotate(self, dir):
        directions = [[1, 0], [0, 1], [-1, 0], [0, -1]]
        if dir == 'L':
            self.direction = directions[(directions.index(self.direction) + 1) % 4]
        if dir == 'R':
            self.direction = directions[(directions.index(self.direction) - 1) % 4]

    def hop(self):
        self.coords = self.nextTile()

    # Returns where the bunny is about to jump to
    def nextTile(self):
        return [self.coords[0] + self.direction[0], self.coords[1] + self.direction[1]]

class BoardState():
    def __init__(self, map):
        self.unvisited = 0
        self.map = []

        self.bunny = Bunny()
        self.hopsLeft = 0

        for x, row in enumerate(map):
            newRow = []
            for y, char in enumerate(row):
                if char == '#':
                    newRow.append(1)
                    self.unvisited += 1

                elif char == 'S':
                    newRow.append(2)

                    if -1 in self.bunny.coords:
                        self.bunny.setCoords(x, y)
                    else:
                        print("Multiple starting points found", file=sys.stderr)
                        sys.exit(1)

                elif char == ' ':
                    newRow.append(0)

                elif char == 'O':
                    newRow.append(2)

                else:
                    print("Invalid char in input", file=sys.stderr)
                    sys.exit(1)

            self.map.append(newRow)

        if -1 in self.bunny.coords:
            print("No starting point defined", file=sys.stderr)
            sys.exit(1)

    def finished(self):
        return self.unvisited == 0

    def validCoords(self, x, y):
        return -1 < x < len(self.map) and -1 < y < len(self.map[0])

    def runCom(self, com):
        if self.finished():
            return

        if self.hopsLeft < self.unvisited:
            return

        if com == 'F':
            x, y = self.bunny.nextTile()
            if self.validCoords(x, y) and self.map[x][y] != 0:
                self.bunny.hop()
                self.hopsLeft -= 1

                if (self.map[x][y] == 1):
                    self.unvisited -= 1
                self.map[x][y] = 2

        else:
            self.bunny.rotate(com)

class loop():
    def __init__(self, loops, commands):
        self.loops = loops
        self.commands = [*commands]

    def __str__(self):
        return "loop({}, {})".format(self.loops, list(self.commands))

    def __repr__(self):
        return str(self)


def rejectRedundantCode(code):
    if isSnippetRedundant(code):
        return False

    if type(code[-1]) is str:
        if code[-1] in "LR":
            return False
    else:
        if len(code[-1].commands) == 1:
            print(code)
            if code[-1].commands[-1] in "LR":
                return False

    return True


def isSnippetRedundant(code):
    joined = "".join(str(com) for com in code)

    if any(redCode in joined for redCode in ["FFF", "RL", "LR", "RRR", "LLL"]):
        return True

    for com in code:
        if type(com) is not str:
            if len(com.commands) == 1:
                if com.loops == 2:
                    return True

                if type(com.commands[0]) is not str:
                    return True

                if com.commands[0] in "LR":
                    return True

            if len(com.commands) > 1 and len(set(com.commands)) == 1:
                return True

            if isSnippetRedundant(com.commands):
                return True

    for i in range(len(code)):
        if type(code[i]) is not str and len(code[i].commands) == 1:
            if i > 0 and code[i].commands[0] == code[i-1]:
                return True
            if i < len(code) - 1 and code[i].commands[0] == code[i+1]:
                return True

        if type(code[i]) is not str:
            if i > 0 and type(code[i-1]) is not str and code[i].commands == code[i-1].commands:
                return True
            if i < len(code) - 1 and type(code[i+1]) is not str and code[i].commands == code[i+1].commands:
                return True

            if len(code[i].commands) > 3 and all(type(com) is str for com in code[i].commands):
                return True

    return False

def flatten(code):
    flat = ""
    for com in code:
        if type(com) is str:
            flat += com
        else:
            flat += flatten(com.commands) * com.loops

    return flat

def newGen(n, topLevel = True):
    maxLoops = 9
    minLoops = 2
    if n < 1:
        yield []

    if n == 1:
        yield from [["F"], ["L"], ["R"]]

    elif n == 2:
        yield from [["F", "F"], ["F", "L"], ["F", "R"], ["L", "F"], ["R", "F"]]

    elif n == 3:
        for innerCode in newGen(n - 1, False):
            for loops in range(minLoops, maxLoops):
                if len(innerCode) != 1 and 0 < innerCode.count('F') < 2:
                    yield [loop(loops, innerCode)]

        for com in "FLR":
            for suffix in newGen(n - 2, False):
                for loops in range(minLoops, maxLoops):
                    if com not in suffix:
                        yield [loop(loops, [com])] + suffix

    else:
        for innerCode in newGen(n - 1, False):
            if topLevel:
                yield [loop(17, innerCode)]
            else:
                for loops in range(minLoops, maxLoops):
                    if len(innerCode) > 1:
                        yield [loop(loops, innerCode)]

        for com in "FLR":
            for innerCode in newGen(n - 2, False):
                for loops in range(minLoops, maxLoops):
                    yield [loop(loops, innerCode)] + [com]
                    yield [com] + [loop(loops, innerCode)]

def codeLen(code):
    l = 0
    for com in code:
        l += 1
        if type(com) is not str:
            l += codeLen(com.commands)

    return l


def test(code, board):
    state = BoardState(board)
    state.hopsLeft = flatten(code).count('F')

    for com in code:
        state.runCom(com)


    return state.finished()

def testAll():
    score = 0
    for i, board in enumerate(boards):
        print("\n\nTesting board {}:".format(i + 1))
        #print('\n'.join(board),'\n')
        start = time.time()

        found = False
        tested = set()

        for maxLen in range(1, 12):
            lenCount = 0
            for code in filter(rejectRedundantCode, newGen(maxLen)):
                testCode = flatten(code)
                if testCode in tested:
                    continue

                tested.add(testCode)

                lenCount += 1
                if test(testCode, board):
                    found = True

                    stop = time.time()
                    print("{} token solution found in {} seconds".format(maxLen, stop - start))
                    print(code)
                    score += maxLen
                    break

            if found:
                break

    print("Final Score: {}".format(score))

def testOne(board):
    start = time.time()
    found = False
    tested = set()
    dupes = 0

    for maxLen in range(1, 12):
        lenCount = 0
        for code in filter(rejectRedundantCode, newGen(maxLen)):
            testCode = flatten(code)
            if testCode in tested:
                dupes += 1
                continue

            tested.add(testCode)

            lenCount += 1
            if test(testCode, board):
                found = True
                print(code)
                print("{} dupes found".format(dupes))
                break

        if found:
            break

        print("Length:\t{}\t\tCombinations:\t{}".format(maxLen, lenCount))

    stop = time.time()
    print(stop - start)

#testAll()
testOne(input().split('\n'))

Dieses Programm testet eine einzelne Eingangskarte, aber ich finde diesen Testtreiber nützlicher . Es wird jedes einzelne Board zur gleichen Zeit getestet und gedruckt, wie lange es gedauert hat, um diese Lösung zu finden. Wenn ich diesen Code auf meinem Computer ausführe (Intel i7-7700K Quad-Core-CPU bei 4,20 GHz, 16,0 GB RAM), erhalte ich die folgende Ausgabe:

Testing board 1:
2 token solution found in 0.0 seconds
['F', 'F']


Testing board 2:
4 token solution found in 0.0025103092193603516 seconds
[loop(17, [loop(3, ['F']), 'R'])]


Testing board 3:
4 token solution found in 0.0010025501251220703 seconds
[loop(17, [loop(3, ['F']), 'L'])]


Testing board 4:
5 token solution found in 0.012532949447631836 seconds
[loop(17, ['F', loop(7, ['F', 'L'])])]


Testing board 5:
5 token solution found in 0.011022329330444336 seconds
[loop(17, ['F', loop(5, ['F', 'L'])])]


Testing board 6:
4 token solution found in 0.0015044212341308594 seconds
[loop(17, [loop(3, ['F']), 'L'])]


Testing board 7:
8 token solution found in 29.32585096359253 seconds
[loop(17, [loop(4, [loop(5, [loop(6, ['F']), 'L']), 'L']), 'F'])]


Testing board 8:
8 token solution found in 17.202533721923828 seconds
[loop(17, ['F', loop(7, [loop(5, [loop(4, ['F']), 'L']), 'F'])])]


Testing board 9:
6 token solution found in 0.10585856437683105 seconds
[loop(17, [loop(7, [loop(4, ['F']), 'L']), 'F'])]


Testing board 10:
6 token solution found in 0.12129759788513184 seconds
[loop(17, [loop(7, [loop(5, ['F']), 'L']), 'F'])]


Testing board 11:
7 token solution found in 4.331984758377075 seconds
[loop(17, [loop(8, ['F', loop(5, ['F', 'L'])]), 'L'])]


Testing board 12:
8 token solution found in 58.620323181152344 seconds
[loop(17, [loop(3, ['F', loop(4, [loop(3, ['F']), 'R'])]), 'L'])]

Final Score: 67

Dieser letzte Test quietscht nur knapp unter der Minute Einschränkung.

Hintergrund

Dies war eine der unterhaltsamsten Herausforderungen, die ich je beantwortet habe! Ich hatte eine Explosionsmusterjagd und suchte nach Heuristiken, um die Dinge zu reduzieren.

Generell neige ich hier bei PPCG dazu, relativ einfache Fragen zu beantworten. Ich mag den String- Tag besonders gern, da er im Allgemeinen für meine Sprachen ziemlich gut geeignet ist. Vor ungefähr zwei Wochen habe ich eines Tages meine Abzeichen durchgesehen und festgestellt, dass ich das Wiederbelebungsabzeichen noch nie bekommen hatte . Also habe ich die unbeantworteten Fragen durchgesehenKlicken Sie auf, um zu sehen, ob mir etwas aufgefallen ist, und ich habe diese Frage gefunden. Ich entschied, dass ich es unabhängig von den Kosten beantworten würde. Es endete ein bisschen schwieriger als ich dachte, aber ich bekam endlich eine brachiale Antwort, auf die ich stolz sein kann. Aber diese Herausforderung ist für mich völlig ungewöhnlich, da ich normalerweise nicht mehr als eine Stunde für eine einzelne Antwort aufbringe. Diese Antwort hat mich etwas mehr als 2 Wochen gekostet und mindestens 10+ Arbeit gekostet, um endlich zu diesem Stadium zu gelangen, obwohl ich nicht sorgfältig nachverfolgt habe.

Die erste Iteration war eine reine Brute-Force-Lösung. Ich habe den folgenden Code verwendet, um alle Snippets bis zur Länge N zu generieren :

def generateCodeLenN(n, maxLoopComs, maxLoops, allowRedundant = False):
    if n < 1:
        return []

    if n == 1:
        return [["F"], ["L"], ["R"]]

    results = []

    if 1:
        for com in "FLR":
            for suffix in generateCodeLenN(n - 1, maxLoopComs, maxLoops, allowRedundant):
                if allowRedundant or not isSnippetRedundant([com] + suffix):
                    results.append([com] + suffix)

    for loopCount in range(2, maxLoopComs):
        for loopComs in range(1, n):
            for innerCode in generateCodeLenN(loopComs, maxLoopComs, maxLoops - 1, allowRedundant):
                if not allowRedundant and isSnippetRedundant([loop(loopCount, innerCode)]):
                    continue

                for suffix in generateCodeLenN(n - loopComs - 1, maxLoopComs, maxLoops - 1, allowRedundant):
                    if not allowRedundant and isSnippetRedundant([loop(loopCount, innerCode)] + suffix):
                        continue

                    results.append([loop(loopCount, innerCode)] + suffix)

                if loopComs == n - 1:
                    results.append([loop(loopCount, innerCode)])

    return results

Zu diesem Zeitpunkt war ich mir sicher, dass das Testen jeder einzelnen Antwort viel zu langsam sein würde. Deshalb habe ich isSnippetRedundantSnippets herausgefiltert, die mit einem kürzeren Snippet geschrieben werden konnten. Zum Beispiel würde ich mich weigern, das Snippet zu liefern, ["F", "F", "F"]weil genau die gleichen Effekte erzielt werden könnten. [Loop(3, ["F"])Wenn wir also den Punkt erreichen, an dem wir Länge-3-Snippets testen, wissen wir, dass kein Länge-3-Snippet das aktuelle Board lösen kann. Dies verwendete eine Menge guter Mnemonics, war aber letztendlich waaaayzu langsam. Testfall 12 dauerte mit diesem Ansatz etwas mehr als 3.000 Sekunden. Dies ist eindeutig deutlich zu langsam. Aber wenn ich diese Informationen und eine Reihe von Computerzyklen verwende, um kurze Lösungen für jedes Board zu erzwingen, kann ich ein neues Muster finden. Mir ist aufgefallen, dass fast jede gefundene Lösung im Allgemeinen ungefähr so ​​aussieht:

[<com> loop(n, []) <com>]

Mehrere Ebenen tief verschachtelt, wobei die einzelnen Koms auf jeder Seite optional sind. Dies bedeutet, dass Lösungen wie:

["F", "F", "R", "F", "F", "L", "R", "F", "L"]

würde nie erscheinen. Tatsächlich gab es nie eine Folge von mehr als 3 Nicht-Schleifen-Token. Eine Möglichkeit, dies zu nutzen, besteht darin, alle herauszufiltern und sich nicht die Mühe zu machen, sie zu testen. Das Generieren dieser Dateien dauerte jedoch nicht unerheblich lange, und das Durchsuchen der Millionen solcher Ausschnitte würde kaum zu einer Zeitersparnis führen. Stattdessen habe ich den Code-Generator drastisch umgeschrieben, um nur Snippets nach diesem Muster zu generieren. Im Pseudocode folgt der neue Generator diesem allgemeinen Muster:

def codeGen(n):
    if n == 1:
        yield each [<com>]

    if n == 2:
        yield each [<com>, <com>]

    if n == 3:
        yield each [loop(n, <com length 2>]
        yield each [loop(n, <com>), <com>]

    else:
        yield each [loop(n, <com length n-1>)]
        yield each [loop(n, <com length n-2>), <com>]
        yield each [<com>, loop(n, <com length n-2>)]

        # Removed later
        # yield each [<com>, loop(n, <com length n-3>), <com>]
        # yield each [<com>, <com>, loop(n, <com length n-3>)]
        # yield each [loop(n, <com length n-3>), <com>, <com>]

Dies reduzierte den längsten Testfall auf 140 Sekunden, was eine lächerliche Verbesserung darstellt. Aber von hier aus gab es noch einige Dinge, die ich verbessern musste. Ich fing aggressiver an, redundanten / wertlosen Code herauszufiltern und zu prüfen, ob der Code zuvor getestet wurde. Dies reduzierte es weiter, aber es war nicht genug. Am Ende fehlte als letztes Stück der Schleifenzähler. Durch meinen hochentwickelten Algorithmus (gelesen: zufälliger Versuch und Irrtum ) habe ich festgestellt, dass der optimale Bereich, in dem Schleifen ablaufen dürfen, [3-8] ist. Aber da gibt es eine enorme Verbesserung: Wenn wir wissen, dass [loop(8, [loop(8, ['F', loop(5, ['F', 'L'])]), 'L'])]das unser Board nicht lösen kann, dann gibt es absolut keinen Weg[loop(3, [loop(8, ['F', loop(5, ['F', 'L'])]), 'L'])]oder jede Schleifenanzahl von 3-7 könnte es lösen. Anstatt also alle Schleifengrößen von 3 bis 8 durchzugehen, setzen wir die Schleifenzahl für die äußere Schleife auf den Maximalwert. Dies führt dazu, dass der Suchraum maxLoop - minLoopin diesem Fall um den Faktor oder 6 verringert wird.

Das hat sehr geholfen, aber am Ende hat es die Punktzahl erhöht. Bestimmte Lösungen, die ich zuvor mit brachialer Gewalt gefunden hatte, erfordern größere Schleifenzahlen (z. B. Platinen 4 und 6). Anstatt die Anzahl der äußeren Schleifen auf 8 zu setzen, setzen wir die Anzahl der äußeren Schleifen auf 17, eine magische Zahl, die ebenfalls von meinem hochentwickelten Algorithmus berechnet wurde. Wir wissen, dass wir dies tun können, da das Erhöhen der Schleifenzahl der äußersten Schleife keinen Einfluss auf die Gültigkeit der Lösung hat. Dieser Schritt reduzierte unser Endergebnis tatsächlich um 13. Also kein trivialer Schritt.