Coelho saltitante do Google

16

Em 4 de dezembro de 2017, o Google Doodle era um jogo de programação gráfica com um coelho . Os níveis posteriores não eram triviais e pareciam um ótimo candidato para um desafio de .

Detalhes

jogos

  • Existem quatro movimentos disponíveis: pule para frente, vire à esquerda, vire à direita e faça um loop. Cada um desses movimentos é um símbolo , correspondendo ao fato de que eles são cada um dos blocos no jogo.
  • O coelho pode enfrentar quatro direções ortogonais (ou seja, norte, sul, leste, oeste).
  • O coelho pode pular para frente (mover um quadrado na direção em que está voltado) e virar à esquerda ou à direita.
  • Os loops podem ter vários outros movimentos dentro deles, incluindo outros loops, e sua contagem de iterações é qualquer número inteiro positivo (embora o jogo permita tecnicamente uma contagem de iterações de 0).
  • O tabuleiro é um conjunto de quadrados alinhados à grade e o coelho pode pular entre quadrados adjacentes.
  • O coelho não pode pular no vazio. Significando que uma tentativa de pular do quadro não faz nada. (Isso aparentemente foi uma surpresa para algumas pessoas e uma decepção para outras.)
  • Os quadrados são marcados ou desmarcados. Quando o coelho está em um quadrado, ele fica marcado.
  • O nível está completo quando todos os quadrados estão marcados.
  • Você pode assumir que existe uma solução.

Seu código

  • Objetivo: dado um quadro, encontre uma ou mais soluções mais curtas.
  • Entrada é uma lista de locais quadrados que formam o quadro (distinguindo quadrados marcados e não marcados) e saída é uma lista de movimentos. O formato de entrada e saída não importa, desde que sejam legíveis por humanos e compreensíveis.
  • Critério de vitória: soma do número de jogadas das soluções mais curtas encontradas dentro de um minuto para cada placa. Se o seu programa não encontrar uma solução para um quadro em particular, sua pontuação nesse quadro é (5 * número de quadrados).
  • Por favor, não codifique soluções de nenhuma maneira. Seu código deve poder receber qualquer placa como entrada, não apenas as fornecidas como exemplos abaixo.

Exemplos

As soluções estão ocultas nos spoilers para lhe dar a chance de jogar o jogo primeiro e experimentar algumas delas você mesmo. Além disso, apenas uma solução é fornecida abaixo para cada um.

Sé o quadrado inicial do coelho (voltado para o leste), #é um quadrado não marcado e Oé um quadrado marcado. Para movimentos, minha notação é F= pular para frente, L= virar à esquerda,R = virar à direita e LOOP(<num>){<moves>}denota um loop que itera <num>vezes e faz a <moves>cada vez. Se o loop puder executar qualquer número de vezes além de um número mínimo, <num>poderá ser omitido (ou seja, o infinito funciona).

Nível 1:

S##

FF

Nível 2:

S##
  #
  #

LOOP (2) {FFR}

Nível 3:

S##
# #
###

LOOP {FFR}

Nível 4:

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

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

Nível 5:

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

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

Nível 6:

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

LOOP {LOOP (3) {F} L}

Placas enormes: (as menores soluções atualmente desconhecidas)

12x12:

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

Nível 5, mas muito maior:

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

Mais placas holey:

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

e

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

Finalmente, a assimetria pode ser uma verdadeira dor de cabeça:

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

e

#########
# ##  ###
###S  ###
# #######
###    ##
#####   #
####  ###
#########
#########
El'endia Starman
fonte
Relacionado .
Xcoder
"encontrar uma ou mais soluções mais curtos" Eu pensei que o problema da parada proíbe isso
Leaky Nun
Freira @Leaky Isso não está relacionado ao problema da parada. Esta é uma pesquisa de gráficos
WhatToDo
Mas looping é permitido ...
Leaky Nun
4
Eu acho que não se aplica porque o conselho é finito. Para cada loop, ele é executado para sempre ou pára. Um loop sem loops dentro dele fará um loop para sempre se o argumento para o número de iterações for descartado. Nesse caso, o número finito de estados da placa garante que o loop começará a repetir estados, os quais podem ser verificados.
WhatToDo

Respostas:

12

Python 3, 67 tokens

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 testará uma única placa de entrada, mas acho esse driver de teste mais útil . Ele testará todas as placas ao mesmo tempo e imprimirá quanto tempo levou para encontrar essa solução. Quando executo esse código na minha máquina (CPU Intel i7-7700K quad core a 4,20 GHz, 16,0 GB de RAM), recebo a seguinte saída:

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

Este último teste mal chega abaixo da restrição de minutos.

fundo

Este foi um dos desafios mais divertidos que já respondi! Eu tinha um padrão de explosão caçando e procurando heurísticas para reduzir as coisas.

Geralmente, aqui no PPCG eu tendem a responder perguntas relativamente fáceis. Gosto especialmente da tag porque geralmente é muito adequada para meus idiomas. Um dia, cerca de duas semanas atrás, eu estava examinando meus distintivos e percebi que nunca havia conseguido o distintivo de avivamento . Então eu olhei através da respostaguia para ver se alguma coisa chamou minha atenção, e eu encontrei esta pergunta. Eu decidi que iria responder, não importa o custo. Acabou sendo um pouco mais difícil do que eu pensava, mas finalmente recebi uma resposta de força bruta da qual posso dizer que me orgulho. Mas esse desafio está totalmente fora do normal para mim, pois geralmente não passo mais de uma hora em uma única resposta. Essa resposta levou um pouco mais de duas semanas e pelo menos 10 ou mais de trabalho para finalmente chegar a esse estágio, embora eu não estivesse acompanhando atentamente.

A primeira iteração foi uma solução pura de força bruta. Usei o código a seguir para gerar todos os trechos com comprimento 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

Nesse ponto, eu tinha certeza de que testar todas as respostas possíveis seria muito lento, então eu costumava isSnippetRedundantfiltrar trechos que poderiam ser escritos com um trecho mais curto. Por exemplo, eu me recusaria a produzir o trecho ["F", "F", "F"]porque os mesmos efeitos poderiam ser alcançados [Loop(3, ["F"]); portanto, se chegarmos ao ponto em que testamos trechos de comprimento 3, sabemos que nenhum trecho de comprimento 3 poderia resolver o quadro atual. Isso usou muitas boas mnemônicas, mas acabou sendo ótimomuito devagar. O Testcase 12 levou pouco mais de 3.000 segundos usando essa abordagem. Isso é claramente significativamente muito lento. Mas, usando essas informações e vários ciclos de computador para soluções breves de força bruta para todas as placas, pude encontrar um novo padrão. Percebi que quase todas as soluções encontradas geralmente se parecem com as seguintes:

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

aninhou várias camadas de profundidade, com as coms individuais de cada lado sendo opcionais. Isso significa que soluções como:

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

nunca apareceria. De fato, nunca houve uma sequência de mais de três tokens sem loop. Uma maneira de utilizar isso seria filtrar todos eles e não se preocupar em testá-los. Mas gerá-los ainda levava um tempo não desprezível e filtrar milhões de trechos como esse dificilmente reduziria o tempo. Em vez disso, reescrevi drasticamente o gerador de código para gerar apenas trechos seguindo esse padrão. No pseudo-código, o novo gerador segue esse padrão geral:

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

Isso reduziu o caso de teste mais longo para 140 segundos, o que é uma melhoria ridícula. Mas a partir daqui, ainda havia algumas coisas que eu precisava melhorar. Comecei a filtrar de forma mais agressiva o código redundante / sem valor e a verificar se o código já havia sido testado antes. Isso reduziu ainda mais, mas não foi suficiente. No final, a peça final que faltava era o contador de voltas. Através do meu algoritmo altamente avançado (leia-se: tentativa e erro aleatórios ), determinei que o intervalo ideal para permitir a execução de loops é [3-8]. Mas há uma grande melhoria: se sabemos que isso [loop(8, [loop(8, ['F', loop(5, ['F', 'L'])]), 'L'])]não pode resolver nossa diretoria, então não há absolutamente nenhuma maneira de[loop(3, [loop(8, ['F', loop(5, ['F', 'L'])]), 'L'])]ou qualquer contagem de loop de 3 a 7 pode resolvê-lo. Portanto, em vez de percorrer todos os tamanhos de loop de 3 a 8, definimos a contagem de loop no loop externo para o máximo. Isso acaba reduzindo o espaço de pesquisa por um fator de maxLoop - minLoop, ou 6 nesse caso.

Isso ajudou muito, mas acabou inflando o placar. Certas soluções que eu encontrei anteriormente por força bruta exigem um número maior de loop (por exemplo, placas 4 e 6). Então, em vez de definir a contagem de loop externo como 8, definimos a contagem de loop externo como 17, um número mágico também calculado pelo meu algoritmo altamente avançado. Sabemos que podemos fazer isso porque aumentar a contagem do loop mais externo não afeta a validade da solução. Este passo reduziu nossa pontuação final em 13. Portanto, não é um passo trivial.

DJMcMayhem
fonte