16
\$\begingroup\$

On December 4, 2017, the Google Doodle was a graphical programming game featuring a bunny. The later levels were nicely non-trivial and they seemed like a great candidate for an challenge.

Details

Game

  • There are four available moves: hop forward, turn left, turn right, and loop. Each of these moves is one token, corresponding to the fact that they are each one tile in the game.
  • The bunny can face four orthogonal directions (i.e. north, south, east, west).
  • The bunny can hop forward (move one square in the direction it's facing) and turn left or right.
  • Loops may have any number of other moves inside them, including other loops, and their iteration count is any positive integer (though the game technically allows an iteration count of 0).
  • The board is a set of grid-aligned squares and the bunny can hop between adjacent squares.
  • The bunny cannot hop into the void. Meaning that an attempt to hop off the board does nothing. (This was apparently a surprise for some people and a disappointment for others.)
  • Squares are either marked or unmarked. When the bunny is on a square, it becomes marked.
  • The level is complete when all squares are marked.
  • You may assume a solution exists.

Your code

  • Objective: given a board, find one or more shortest solutions.
  • Input is a list of square locations forming the board (distinguishing marked and unmarked squares) and output is a list of moves. Input and output format does not matter at all, so long as they are human-readable and understandable.
  • Winning criterion: sum of number of moves of shortest solutions found within one minute for each board. If your program does not find a solution for any particular board, your score for that board is (5 * number of squares).
  • Please do not hardcode solutions in any manner. Your code should be able to take any board as input, not just the ones given as examples below.

Examples

Solutions are hidden in spoilers to give you a chance to play the game first and attempt some of these yourself. Also, only one solution is provided below for each.

S is the bunny's starting square (facing east), # is an unmarked square, and O is a marked square. For moves, my notation is F = hop forward, L = turn left, R = turn right, and LOOP(<num>){<moves>} denotes a loop that iterates <num> times and does <moves> each time. If the loop can run any number of times beyond some minimum number, <num> may be omitted (i.e. infinity works).

Level 1:

S##

F F

Level 2:

S##
  #
  #

LOOP(2){F F R}

Level 3:

S##
# #
###

LOOP{F F R}

Level 4:

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

LOOP{ F LOOP(7){F L} } (found by DJMcMayhem)

Level 5:

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

LOOP(18){ LOOP(10){F R} L}
Source: Reddit

Level 6:

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

LOOP{ LOOP(3){F} L }

Huge boards: (shortest solutions currently unknown)

12x12:

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

Level 5 but way bigger:

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

More holey boards:

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

and

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

Finally, asymmetry can be a real pain in the butt:

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

and

#########
# ##  ###
###S  ###
# #######
###    ##
#####   #
####  ###
#########
#########
\$\endgroup\$
  • \$\begingroup\$ Related. \$\endgroup\$ – Mr. Xcoder Dec 18 '17 at 18:33
  • \$\begingroup\$ "find one or more shortest solutions" I thought the halting problem prohibits this \$\endgroup\$ – Leaky Nun Dec 18 '17 at 18:52
  • \$\begingroup\$ @Leaky Nun This is not related to the halting problem. This is a graph search \$\endgroup\$ – WhatToDo Dec 18 '17 at 18:54
  • \$\begingroup\$ But looping is allowed... \$\endgroup\$ – Leaky Nun Dec 18 '17 at 18:55
  • 4
    \$\begingroup\$ I think it doesn't apply because the board is finite. For each loop, it either runs forever, or halts. A loop with no loops inside of it will only loop forever if the argument for the number of iterations is dropped. In that case, the finite number of board states guarantees the loop will start repeating states, which can be checked for. \$\endgroup\$ – WhatToDo Dec 18 '17 at 19:35
12
\$\begingroup\$

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

This program will test a single input board, but I find this test driver more useful. It will test every single board at the same time and print how long it took to find that solution. When I run that code on my machine (Intel i7-7700K quad core CPU @ 4.20 GHz, 16.0 GB RAM), I get the following output:

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

This last test just barely squeaks in under the minute restriction.

Background

This was one of the most fun challenges I've ever answered! I had a blast pattern hunting and looking for heuristics to cut down on things.

Generally, here on PPCG I tend to answer relatively easy questions. I'm especially fond of the tag because it's generally pretty well suited for my languages. One day, about two weeks ago, I was looking through my badges and I realized that I had never gotten the revival badge. So I looked through the unanswered tab to see if anything caught my eye, and I found this question. I decided that I would answer it no matter the cost. It ended up being a bit harder than I thought it would, but I finally got a brute-force answer that I can say I'm proud of. But this challenge is totally out of the norm for me since I don't usually spend more than an hour or so on a single answer. This answer took me a little over 2 weeks and at least 10+ of work to finally get to this stage, though I wasn't keeping careful track.

The first iteration was a pure brute force solution. I used the following code to generate all snippets up to length 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

At this point, I was sure that testing every single possible answer would be way too slow, so I used isSnippetRedundant to filter out snippets that could be written with a shorter snippet. For example, I would refuse to yield the snippet ["F", "F", "F"] because the exact same effects could be achieved with [Loop(3, ["F"]), so if it we get to the point where we test length-3 snippets, we know that no length-3 snippet could solve the current board. This used a lot of good mnemonics, but ultimately was waaaay too slow. Testcase 12 took just over 3,000 seconds using this approach. This is clearly significantly too slow. But using this information and a bunch of computer cycles to brute force short solutions to every board, I could find a new pattern. I noticed that almost every solution found would generally look like something like the following:

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

nested several layers deep, with the single coms on each side being optional. This means that solutions like:

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

would never appear. In fact, there was never a sequence of more than 3 non-loop tokens. One way to utilize this would be to filter out all of these and not bother to test them. But generating them was still taking a non-negligible amount of time, and filtering through the millions of snippets like this would barely cut time off. Instead I drastically rewrote the code-generator to only generate snippets following this pattern. In pseudo code, the new generator follows this general pattern:

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

This cut the longest test case down to 140 seconds, which is a ridiculous improvement. But from here, there were still some things I needed to improve. I started more aggressively filtering out redundant/worthless code and checking to see if code has been tested before. This cut it down further, but it wasn't enough. In the end, the final piece that was missing was the loop counter. Through my highly advanced algorithm (read: random trial and error) I determined that the optimal range to allow loops to run in is [3-8]. But there's a huge improvement in there: If we know that [loop(8, [loop(8, ['F', loop(5, ['F', 'L'])]), 'L'])] can't solve our board, then there's absolutely no way that [loop(3, [loop(8, ['F', loop(5, ['F', 'L'])]), 'L'])] or any loop count from 3-7 could solve it. So rather than iterating through all the loop sizes from 3-8, we set the loop count on the outer loop to the max. This ends up cutting the search space down by a factor of maxLoop - minLoop, or 6 in this case.

This helped a lot, but ended up inflating the score. Certain solutions I had found earlier by brute force require larger loop numbers to run (for example, boards 4 and 6). So rather than setting the outer loop count to 8, we set the outer loop count to 17, a magical number also calculated by my highly advanced algorithm. We know we can do this because increasing the loop count of the outermost loop has no effect on the solution's validity. This step actually reduced our final score by 13. So not a trivial step.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.