El 4 de diciembre de 2017, Google Doodle fue un juego de programación gráfica con un conejito . Los niveles posteriores fueron agradablemente no triviales y parecían un gran candidato para un desafío de golf atómico .

Detalles

Juego

• Hay cuatro movimientos disponibles: saltar hacia adelante, girar a la izquierda, girar a la derecha y girar. Cada uno de estos movimientos es una ficha , que corresponde al hecho de que cada uno es una ficha en el juego.
• El conejito puede enfrentar cuatro direcciones ortogonales (es decir, norte, sur, este, oeste).
• El conejito puede saltar hacia adelante (moverse un cuadrado en la dirección que está mirando) y girar a la izquierda o derecha.
• Los bucles pueden tener cualquier número de otros movimientos dentro de ellos, incluidos otros bucles, y su recuento de iteraciones es cualquier número entero positivo (aunque el juego técnicamente permite un recuento de iteraciones de 0).
• El tablero es un conjunto de cuadrados alineados con cuadrícula y el conejito puede saltar entre cuadrados adyacentes.
• El conejito no puede saltar al vacío. Lo que significa que un intento de saltar del tablero no hace nada. (Esto aparentemente fue una sorpresa para algunas personas y una decepción para otras).
• Los cuadrados están marcados o sin marcar. Cuando el conejito está en un cuadrado, se marca.
• El nivel se completa cuando todos los cuadrados están marcados.
• Puede suponer que existe una solución.

Tu codigo

• Objetivo: dada una tabla, encontrar una o más soluciones más cortas.
• La entrada es una lista de ubicaciones cuadradas que forman el tablero (distinguiendo cuadrados marcados y no marcados) y la salida es una lista de movimientos. El formato de entrada y salida no importa en absoluto, siempre que sean legibles y entendibles por los humanos.
• Criterio ganador: suma del número de movimientos de las soluciones más cortas encontradas dentro de un minuto para cada tablero. Si su programa no encuentra una solución para un tablero en particular, su puntaje para ese tablero es (5 * número de cuadrados).
• No codifique las soluciones de ninguna manera. Su código debe poder tomar cualquier placa como entrada, no solo las que se dan como ejemplos a continuación.

Ejemplos

Las soluciones están ocultas en spoilers para darte la oportunidad de jugar el juego primero e intentar algunas de ellas tú mismo. Además, solo se proporciona una solución a continuación para cada uno.

Ses el cuadrado inicial del conejito (hacia el este), #es un cuadrado sin marcar y Oes un cuadrado marcado. Para los movimientos, mi notación es F= saltar hacia adelante, L= girar a la izquierda, R= girar a la derecha, y LOOP(<num>){<moves>}denota un ciclo que itera <num>veces y lo hace <moves>cada vez. Si el bucle puede ejecutarse varias veces más allá de un número mínimo, <num>puede omitirse (es decir, el infinito funciona).

Nivel 1:

S##

FF

Nivel 2:

S##
  #
  #

BUCLE (2) {FFR}

Nivel 3:

S##
# #
###

LOOP {FFR}

Nivel 4:

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

LOOP {F LOOP (7) {FL}} (encontrado por DJMcMayhem)

Nivel 5:

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

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

Nivel 6:

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

LOOP {LOOP (3) {F} L}

Grandes tableros: (las soluciones más cortas actualmente desconocidas)

12x12:

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

Nivel 5 pero mucho más grande:

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

Más tablas de holey:

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

y

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

Finalmente, la asimetría puede ser un verdadero dolor en el trasero:

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

y

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

Python 3, 67 fichas

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

Este programa probará una sola placa de entrada, pero este controlador de prueba me parece más útil . Pondrá a prueba cada placa al mismo tiempo e imprimirá cuánto tiempo llevó encontrar esa solución. Cuando ejecuto ese código en mi máquina (CPU Intel i7-7700K de cuatro núcleos a 4.20 GHz, 16.0 GB de RAM), obtengo el siguiente resultado:

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

Esta última prueba apenas entra en la restricción de minutos.

Antecedentes

¡Este fue uno de los desafíos más divertidos que he respondido! Tuve un patrón de explosión buscando y buscando heurísticas para reducir las cosas.

Generalmente, aquí en PPCG tiendo a responder preguntas relativamente fáciles. Me gusta especialmente la etiqueta de cadena porque generalmente es muy adecuada para mis idiomas. Un día, hace aproximadamente dos semanas, estaba mirando mis insignias y me di cuenta de que nunca había recibido la insignia de avivamiento . Así que miré a través del sin respuestapestaña para ver si algo me llamó la atención, y encontré esta pregunta. Decidí que respondería sin importar el costo. Terminó siendo un poco más difícil de lo que pensé, pero finalmente obtuve una respuesta de fuerza bruta de la que puedo decir que estoy orgulloso. Pero este desafío está totalmente fuera de lo normal para mí, ya que generalmente no paso más de una hora más o menos en una sola respuesta. Esta respuesta me llevó un poco más de 2 semanas y al menos 10+ de trabajo para finalmente llegar a esta etapa, aunque no estaba haciendo un seguimiento cuidadoso.

La primera iteración fue una solución pura de fuerza bruta. Usé el siguiente código para generar todos los fragmentos hasta la longitud 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

En este punto, estaba seguro de que probar cada respuesta posible sería demasiado lento, por lo que solía isSnippetRedundantfiltrar fragmentos que podrían escribirse con un fragmento más corto. Por ejemplo, me negaría a producir el fragmento de código ["F", "F", "F"]porque se podrían lograr exactamente los mismos efectos [Loop(3, ["F"]), por lo que si llegamos al punto en el que probamos fragmentos de longitud 3, sabemos que ningún fragmento de longitud 3 podría resolver el tablero actual. Esto usó muchas buenas mnemotecnias, pero finalmente fue muuuuchodemasiado lento. El caso de prueba 12 tardó poco más de 3.000 segundos con este enfoque. Esto es claramente significativamente demasiado lento. Pero utilizando esta información y un montón de ciclos informáticos para forzar soluciones brutas a cada placa, pude encontrar un nuevo patrón. Noté que casi todas las soluciones encontradas generalmente se verían como las siguientes:

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

anidadas varias capas de profundidad, con los coms individuales en cada lado opcional Esto significa que soluciones como:

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

nunca aparecería De hecho, nunca hubo una secuencia de más de 3 tokens sin bucle. Una forma de utilizar esto sería filtrar todo esto y no molestarse en probarlos. Pero generarlos todavía tomaba una cantidad de tiempo no despreciable, y filtrar a través de millones de fragmentos como este apenas reduciría el tiempo libre. En cambio, reescribí drásticamente el generador de código para generar solo fragmentos siguiendo este patrón. En pseudocódigo, el nuevo generador sigue este patrón general:

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

Esto redujo el caso de prueba más largo a 140 segundos, lo cual es una mejora ridícula. Pero a partir de aquí, todavía había algunas cosas que necesitaba mejorar. Comencé a filtrar de manera más agresiva el código redundante / inútil y a verificar si el código se había probado antes. Esto lo redujo aún más, pero no fue suficiente. Al final, la pieza final que faltaba era el contador de bucle. A través de mi algoritmo altamente avanzado (léase: ensayo y error aleatorio ), determiné que el rango óptimo para permitir que los bucles se ejecuten es [3-8]. Pero hay una gran mejora allí: si sabemos que [loop(8, [loop(8, ['F', loop(5, ['F', 'L'])]), 'L'])]no puede resolver nuestro tablero, entonces no hay absolutamente ninguna manera de que[loop(3, [loop(8, ['F', loop(5, ['F', 'L'])]), 'L'])]o cualquier cuenta de bucle de 3-7 podría resolverlo. Entonces, en lugar de iterar a través de todos los tamaños de bucles de 3-8, establecemos el recuento de bucles en el bucle externo al máximo. Esto termina reduciendo el espacio de búsqueda en un factor de maxLoop - minLoop, o 6 en este caso.

Esto ayudó mucho, pero terminó inflando el puntaje. Ciertas soluciones que había encontrado anteriormente por la fuerza bruta requieren que se ejecuten números de bucle más grandes (por ejemplo, las tablas 4 y 6). Entonces, en lugar de establecer el recuento del bucle externo en 8, establecemos el recuento del bucle externo en 17, un número mágico también calculado por mi algoritmo altamente avanzado. Sabemos que podemos hacer esto porque aumentar el recuento de bucles del bucle más externo no tiene ningún efecto en la validez de la solución. Este paso en realidad redujo nuestra puntuación final en 13. Por lo tanto, no es un paso trivial.