Le 4 décembre 2017, le Google Doodle était un jeu de programmation graphique mettant en scène un lapin . Les niveaux ultérieurs étaient bien non triviaux et ils semblaient être un excellent candidat pour un défi de golf atomique .

Détails

Jeu

• Il y a quatre mouvements disponibles: sauter en avant, tourner à gauche, tourner à droite et boucler. Chacun de ces mouvements est un jeton , correspondant au fait qu'ils sont chacun une tuile dans le jeu.
• Le lapin peut faire face à quatre directions orthogonales (ie nord, sud, est, ouest).
• Le lapin peut sauter en avant (se déplacer d'un carré dans la direction vers laquelle il fait face) et tourner à gauche ou à droite.
• Les boucles peuvent avoir n'importe quel nombre d'autres mouvements à l'intérieur, y compris d'autres boucles, et leur nombre d'itérations est un entier positif (bien que le jeu autorise techniquement un nombre d'itérations de 0).
• Le plateau est un ensemble de carrés alignés sur la grille et le lapin peut sauter entre les carrés adjacents.
• Le lapin ne peut pas sauter dans le vide. Ce qui signifie qu'une tentative de descendre du plateau ne fait rien. (C'était apparemment une surprise pour certaines personnes et une déception pour d'autres.)
• Les carrés sont marqués ou non. Lorsque le lapin est sur un carré, il devient marqué.
• Le niveau est terminé lorsque tous les carrés sont marqués.
• Vous pouvez supposer qu'une solution existe.

Votre code

• Objectif: compte tenu d'un tableau, trouver une ou plusieurs solutions les plus courtes.
• L'entrée est une liste d'emplacements carrés formant le tableau (en distinguant les carrés marqués et non marqués) et la sortie est une liste de mouvements. Le format d' entrée et de sortie n'a pas d'importance du tout, tant qu'ils sont lisibles et compréhensibles par l'homme.
• Critère gagnant: somme du nombre de coups des solutions les plus courtes trouvées en une minute pour chaque planche. Si votre programme ne trouve pas de solution pour un tableau particulier, votre score pour ce tableau est (5 * nombre de carrés).
• Veuillez ne pas coder en dur les solutions en aucune façon. Votre code devrait pouvoir prendre n'importe quelle carte en entrée, pas seulement celles données comme exemples ci-dessous.

Exemples

Les solutions sont cachées dans des spoilers pour vous donner une chance de jouer au jeu en premier et d'essayer certaines d'entre elles vous-même. De plus, une seule solution est fournie ci-dessous pour chacun.

Sest le carré de départ du lapin (face à l'est), #est un carré non marqué et Oest un carré marqué. Pour les mouvements, ma notation est F= hop en avant, L= tourner à gauche, R= tourner à droite, et LOOP(<num>){<moves>}dénote une boucle qui répète <num>et fait à <moves>chaque fois. Si la boucle peut s'exécuter un certain nombre de fois au-delà d'un certain nombre minimum, <num>peut être omise (c'est-à-dire que l'infini fonctionne).

Niveau 1:

S##

FF

Niveau 2:

S##
  #
  #

BOUCLE (2) {FFR}

Niveau 3:

S##
# #
###

BOUCLE {FFR}

Niveau 4:

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

LOOP {F LOOP (7) {FL}} (trouvé par DJMcMayhem)

Niveau 5:

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

BOUCLE (18) {BOUCLE (10) {FR} L}
Source: Reddit

Niveau 6:

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

BOUCLE {BOUCLE (3) {F} L}

Planches énormes: (solutions les plus courtes actuellement inconnues)

12x12:

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

Niveau 5 mais bien plus grand:

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

Planches plus trouées:

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

et

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

Enfin, l'asymétrie peut être une vraie douleur dans le cul:

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

et

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

Python 3, 67 jetons

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

Ce programme testera une seule carte d'entrée, mais je trouve ce pilote de test plus utile . Il testera chaque carte en même temps et imprimera le temps qu'il a fallu pour trouver cette solution. Lorsque j'exécute ce code sur ma machine (processeur quadricœur Intel i7-7700K à 4,20 GHz, 16,0 Go de RAM), j'obtiens la sortie suivante:

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

Ce dernier test grince à peine sous la restriction des minutes.

Contexte

Ce fut l'un des défis les plus amusants auxquels j'ai jamais répondu! J'ai eu une chasse aux motifs explosifs et je cherchais des heuristiques pour réduire les choses.

Généralement, ici sur PPCG, j'ai tendance à répondre à des questions relativement faciles. J'aime particulièrement le tag chaîne car il est généralement assez bien adapté à mes langues. Un jour, il y a environ deux semaines, je regardais mes badges et je me suis rendu compte que je n'avais jamais obtenu le badge de renaissance . J'ai donc regardé sans réponseonglet pour voir si quelque chose a attiré mon attention, et j'ai trouvé cette question. J'ai décidé de répondre, peu importe le prix. Cela a fini par être un peu plus difficile que je ne le pensais, mais j'ai finalement obtenu une réponse brutale dont je peux dire que je suis fier. Mais ce défi est totalement hors norme pour moi car je ne passe généralement pas plus d'une heure sur une seule réponse. Cette réponse m'a pris un peu plus de 2 semaines et au moins 10+ de travail pour enfin arriver à ce stade, même si je ne suivais pas attentivement.

La première itération était une solution pure force brute. J'ai utilisé le code suivant pour générer tous les extraits jusqu'à la longueur N :

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

À ce stade, j'étais sûr que tester chaque réponse possible serait beaucoup trop lent, j'ai donc utilisé isSnippetRedundantpour filtrer les extraits qui pourraient être écrits avec un extrait plus court. Par exemple, je refuserais de fournir l'extrait de code ["F", "F", "F"]car les mêmes effets pourraient être obtenus avec [Loop(3, ["F"]), donc si nous arrivons au point où nous testons des extraits de longueur 3, nous savons qu'aucun extrait de longueur 3 ne pourrait résoudre la carte actuelle. Cela a utilisé beaucoup de bons mnémoniques, mais finalement était waaaaytrop lent. Le testcase 12 a pris un peu plus de 3 000 secondes avec cette approche. C'est clairement beaucoup trop lent. Mais en utilisant ces informations et un tas de cycles informatiques pour proposer des solutions courtes de force brute à chaque carte, j'ai pu trouver un nouveau modèle. J'ai remarqué que presque toutes les solutions trouvées ressemblaient généralement à quelque chose comme ceci:

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

imbriqué plusieurs couches en profondeur, avec les coms simples de chaque côté étant facultatifs. Cela signifie que des solutions comme:

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

n'apparaîtrait jamais. En fait, il n'y a jamais eu de séquence de plus de 3 jetons non-boucle. Une façon de l'utiliser serait de filtrer tous ces éléments et de ne pas prendre la peine de les tester. Mais leur génération prenait toujours un temps non négligeable, et le filtrage à travers des millions d'extraits comme celui-ci permettrait à peine de couper le temps. Au lieu de cela, j'ai complètement réécrit le générateur de code pour générer uniquement des extraits de code en suivant ce modèle. En pseudo code, le nouveau générateur suit ce schéma général:

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

Cela a réduit le plus long cas de test à 140 secondes, ce qui est une amélioration ridicule. Mais à partir d'ici, il y avait encore des choses à améliorer. J'ai commencé à filtrer de manière plus agressive le code redondant / sans valeur et à vérifier si le code avait été testé auparavant. Cela a réduit davantage les choses, mais ce n'était pas suffisant. Au final, la dernière pièce manquante était le compteur de boucles. Grâce à mon algorithme très avancé (lire: essais et erreurs aléatoires ), j'ai déterminé que la plage optimale pour permettre aux boucles de s'exécuter est [3-8]. Mais il y a une énorme amélioration: si nous savons que [loop(8, [loop(8, ['F', loop(5, ['F', 'L'])]), 'L'])]cela ne peut pas résoudre notre conseil, il n'y a absolument aucun moyen[loop(3, [loop(8, ['F', loop(5, ['F', 'L'])]), 'L'])]ou n'importe quel nombre de boucles de 3-7 pourrait le résoudre. Donc, plutôt que d'itérer à travers toutes les tailles de boucle de 3 à 8, nous réglons le nombre de boucles sur la boucle externe au maximum. Cela finit par réduire l'espace de recherche par un facteur de maxLoop - minLoop, ou 6 dans ce cas.

Cela a beaucoup aidé, mais a fini par gonfler le score. Certaines solutions que j'avais trouvées plus tôt par force brute nécessitent des nombres de boucles plus grands pour fonctionner (par exemple, les cartes 4 et 6). Ainsi, plutôt que de définir le nombre de boucles externes sur 8, nous avons défini le nombre de boucles externes sur 17, un nombre magique également calculé par mon algorithme très avancé. Nous savons que nous pouvons le faire car l'augmentation du nombre de boucles de la boucle la plus externe n'a aucun effet sur la validité de la solution. Cette étape a en fait réduit notre score final de 13. Ce n'est donc pas une étape triviale.