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 string 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.
Related. – Mr. Xcoder – 2017-12-18T18:33:51.510
"find one or more shortest solutions" I thought the halting problem prohibits this – Leaky Nun – 2017-12-18T18:52:56.313
@Leaky Nun This is not related to the halting problem. This is a graph search – WhatToDo – 2017-12-18T18:54:56.993
But looping is allowed... – Leaky Nun – 2017-12-18T18:55:20.700
4I 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. – WhatToDo – 2017-12-18T19:35:37.140
Funnily enough Google will give you the "shortest solution" ribbon without you getting the shortest solution. It wasn't until I read this question that I realized you could adjust the length of the loop, but I got the ribbon for
Loop(4){Loop(4){FFFL}}on the last puzzle. – Post Rock Garf Hunter – 2017-12-18T22:03:11.513I thought I pointed out that "shortest possible" is ambiguous (because you may think that it means "shortest possible globally"), use "shortest possible your program can" is better? – user202729 – 2017-12-19T00:48:34.777
Yes... WhatToDo is correct, like halting problem on finite memory Turing machine is decidable/computable. – user202729 – 2017-12-19T00:49:00.237
@user202729: "possible" appears nowhere in my challenge text. I think the rest of the text clearly implies that programs don't need to find the absolute minimum. – El'endia Starman – 2017-12-19T00:51:52.413
"400. That’s an error. Your client has issued a malformed or illegal request. That’s all we know." I am getting this error when I click on the link, but most of the page appears to be intact. Might want to check that out. – Laurel – 2017-12-20T02:35:16.613
@Laurel: I hard-refreshed and it loads fine for me in Chrome. Not sure what the issue might be. Try a different browser, perhaps? – El'endia Starman – 2017-12-20T02:43:47.413
I'm on Chrome on Mac. This is what I see. What's there exactly? Still not sure where I can play the game.
– Laurel – 2017-12-20T02:49:37.997@Laurel: Cracked open my MacBook to check and I can confirm it works in Chrome on El Capitan. What you should be seeing is a Google Doodle with the game that inspired this challenge. Both this and this suggest clearing your browser cookies.
– El'endia Starman – 2017-12-20T04:10:41.903