4 декабря 2017 года Google Doodle был игрой с графическим программированием с участием кролика . Более поздние уровни были довольно нетривиальными, и они казались отличным кандидатом на испытание атомного гольфа .

Детали

Игра

• Есть четыре доступных хода: прыгать вперед, повернуть налево, повернуть направо и петля. Каждый из этих ходов представляет собой один жетон , соответствующий тому факту, что каждый из них представляет собой один тайл в игре.
• Кролик может быть обращен к четырем ортогональным направлениям (то есть север, юг, восток, запад).
• Зайчик может прыгнуть вперед (переместиться на одну клетку в направлении, в котором он стоит) и повернуть налево или направо.
• Циклы могут иметь любое количество других ходов внутри, включая другие циклы, и их счетчик итераций является любым положительным целым числом (хотя игра технически допускает счетчик итераций 0).
• Доска представляет собой набор выровненных по сетке квадратов, и кролик может прыгать между соседними квадратами.
• Кролик не может прыгнуть в пустоту. Это означает, что попытка отскочить с доски ничего не делает. (Для некоторых это было неожиданно, а для других - разочарованием.)
• Квадраты либо помечены, либо не помечены. Когда зайчик на квадрате, он становится отмеченным.
• Уровень завершен, когда все квадраты отмечены.
• Вы можете предположить, что решение существует.

Ваш код

• Цель: с помощью доски найти одно или несколько кратчайших решений.
• Ввод - это список квадратов, образующих доску (различение отмеченных и немаркированных квадратов), а вывод - это список ходов. Формат ввода и вывода вообще не имеет значения, если они понятны и понятны человеку.
• Критерий выигрыша: сумма количества ходов кратчайших решений, найденных в течение одной минуты для каждой доски. Если ваша программа не находит решения для какой-либо конкретной доски, ваш счет для этой доски (5 * количество квадратов).
• Пожалуйста, не кодируйте решения каким-либо образом. Ваш код должен быть в состоянии принять любую доску, а не только те, которые приведены в качестве примеров ниже.

Примеры

Решения спрятаны в спойлерах, чтобы дать вам возможность сначала поиграть в игру и попробовать некоторые из них самостоятельно. Кроме того, ниже представлено только одно решение для каждого.

Sявляется стартовой площадью кролика (обращенной на восток), #является безымянной и Oотмеченной. Для ходов моя запись F= прыжок вперед,L = поворот налево, R= поворот направо, и LOOP(<num>){<moves>}обозначает цикл, который повторяет <num>время и делает <moves>каждый раз. Если цикл может выполняться любое количество раз, превышающее некоторое минимальное число, он <num>может быть опущен (т.е. работает бесконечность).

1-й уровень:

S##

FF

Уровень 2:

S##
  #
  #

LOOP (2) {} ФРК

Уровень 3:

S##
# #
###

ЦИКЛ {ФРК}

Уровень 4:

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

LOOP {F LOOP (7) {FL}} (найден DJMcMayhem)

Уровень 5:

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

LOOP (18) {LOOP (10) {FR} L}
Источник: Reddit

Уровень 6:

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

LOOP {LOOP (3) {F} L}

Огромные доски: (кратчайшие решения на данный момент неизвестны)

12x12:

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

Уровень 5, но намного больше:

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

Больше дырявых досок:

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

и

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

Наконец, асимметрия может быть настоящей болью в заднице:

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

и

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

Python 3, 67 токенов

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

Эта программа будет тестировать одну плату ввода, но я считаю этот тестовый драйвер более полезным . Он проверит каждую доску одновременно и напечатает, сколько времени понадобилось, чтобы найти это решение. Когда я запускаю этот код на своем компьютере (четырехъядерный процессор Intel i7-7700K @ 4,20 ГГц, 16,0 ГБ ОЗУ), я получаю следующий вывод:

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

Этот последний тест едва слышен при минимальном ограничении.

Фон

Это была одна из самых забавных задач, на которые я когда-либо отвечал! У меня был взрывной паттерн охоты и поиска эвристики, чтобы сократить количество вещей.

Как правило, здесь, на PPCG, я склонен отвечать на относительно простые вопросы. Мне особенно нравится строковый тег, потому что он обычно очень хорошо подходит для моих языков. Однажды, около двух недель назад, я просматривал свои значки и понял, что никогда не получал значок пробуждения . Так я просмотрел без ответавкладка, чтобы увидеть, если что-нибудь попалось на глаза, и я нашел этот вопрос. Я решил, что я отвечу на это независимо от стоимости. В итоге все оказалось немного сложнее, чем я думал, но я наконец-то получил ответ грубой силы, которым могу гордиться. Но этот вызов для меня совершенно вне нормы, так как я обычно не трачу больше часа или около того на один ответ. Этот ответ занял у меня чуть более 2 недель и, по крайней мере, 10+ работ, чтобы, наконец, дойти до этой стадии, хотя я не следил внимательно.

Первая итерация была чисто грубым решением. Я использовал следующий код для генерации всех фрагментов до длины 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

В этот момент я был уверен, что тестирование каждого возможного ответа будет слишком медленным, поэтому я использовал isSnippetRedundantдля фильтрации фрагменты, которые можно записать с помощью более короткого фрагмента. Например, я бы отказался ["F", "F", "F"]выдавать фрагмент, потому что с его помощью можно достичь тех же самых эффектов [Loop(3, ["F"]), поэтому, если мы дойдем до точки, где мы тестируем фрагменты длины 3, мы знаем, что ни один фрагмент длины 3 не может решить текущую доску. Это использовало много хороших мнемоник, но в конечном итоге было Waaaay слишком медленно. Тестовый случай 12 занял чуть более 3000 секунд, используя этот подход. Это явно значительно слишком медленно. Но используя эту информацию и кучу компьютерных циклов, чтобы перебрать краткие решения для каждой платы, я смог найти новый шаблон. Я заметил, что почти каждое найденное решение будет выглядеть примерно так:

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

вложенный в несколько слоев, с одиночными комами на каждой стороне. Это означает, что такие решения, как:

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

никогда не появится На самом деле, никогда не было последовательности из более чем трех непетлевых токенов. Один из способов использовать это - отфильтровать все это и не пытаться их проверять. Но генерация их по-прежнему занимала немалое количество времени, а фильтрация по миллионам фрагментов, подобным этой, едва ли сократила бы время. Вместо этого я радикально переписал генератор кода, чтобы генерировать только фрагменты, следуя этому шаблону. В псевдокоде новый генератор следует такой общей схеме:

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

Это сократило самый длинный контрольный пример до 140 секунд, что является нелепым улучшением. Но отсюда были некоторые вещи, которые мне нужно было улучшить. Я начал более агрессивно отфильтровывать избыточный / бесполезный код и проверять, проверялся ли код раньше. Это сократило это далее, но этого было недостаточно. В конце концов, последней недостающей частью был счетчик циклов. С помощью моего очень продвинутого алгоритма (читай: случайная проба и ошибка ) я определил, что оптимальный диапазон, в котором можно запускать циклы - [3-8]. Но в этом есть огромное улучшение: если мы знаем, что это или любой цикл из 3-7 может решить эту проблему. Поэтому вместо того, чтобы повторять циклы всех размеров от 3 до 8, мы устанавливаем максимальное число циклов во внешнем цикле. Это приводит к сокращению пространства поиска в[loop(8, [loop(8, ['F', loop(5, ['F', 'L'])]), 'L'])] не можем решить нашу доску, то нет абсолютно никакого способа, которым[loop(3, [loop(8, ['F', loop(5, ['F', 'L'])]), 'L'])]maxLoop - minLoop 6 раз, в этом случае.

Это очень помогло, но в итоге завышало счет. Для некоторых решений, которые я нашел ранее с помощью грубой силы, требуются большие номера петель (например, платы 4 и 6). Таким образом, вместо того, чтобы устанавливать счетчик внешних циклов на 8, мы устанавливаем счетчик внешних циклов на 17, магическое число, также вычисляемое моим очень продвинутым алгоритмом. Мы знаем, что можем сделать это, потому что увеличение числа циклов самого внешнего цикла не влияет на правильность решения. Этот шаг фактически уменьшил наш окончательный счет на 13. Так что это не тривиальный шаг.