Skip to content

Instantly share code, notes, and snippets.

@phenomist

phenomist/jailbreak-solver.py

Last active July 1, 2019 14:29
Show Gist options
  • Save phenomist/bcbf98be2dd73d990c2c0aff4862d4f7 to your computer and use it in GitHub Desktop.
Save phenomist/bcbf98be2dd73d990c2c0aff4862d4f7 to your computer and use it in GitHub Desktop.
Download ZIP
Solver for the puzzle game Jailbreak
Raw
jailbreak-solver.py
import collections
moves = {"N":(-1,0),"E":(0,1),"W":(0,-1),"S":(1,0)}
def level_collection(lvnum): # Level collection including some variations found.
if lvnum == 11:
return [
"#######",
"#@....G",
"#....X#",
"#.....#",
"##...##",
"#######"]
if lvnum == 12:
return [
"#######",
"#.....#",
"#...#.#",
"#....@#",
"###.###",
"###X###",
"###G###"]
if lvnum == 13:
return [
"#########",
"#...#..@#",
"#.#...#.#",
"#...#...#",
"#X#...#.#",
"GX..#X..#",
"#########"]
if lvnum == 14:
return [
" #G#",
" #.#",
" ##.##",
" #...#",
" ###.###",
" #....X#",
" ###.#.###",
" #X......#",
" ###.#.#.###",
" #........X#",
" ###.#.#.#.###",
" #X..........#",
"###.#.#.#.#.###",
"#............X#",
"#######@#######",
" ###"]
if lvnum == 21:
return [
"######",
"#@...G",
"#...X#",
"#..X.#",
"#....#",
"######"]
if lvnum == 22:
return [
"########",
"#.....XG",
"#.#....#",
"#@....X#",
"#..X...#",
"########"]
if lvnum == 23:
return [
"########",
"#.....X#",
"#.....X#",
"#.....X#",
"#@....XG",
"########"]
if lvnum == 24:
return [
"#########",
"#@......G",
"#.#.#.#X#",
"#.X...#X#",
"#.#.#.#X#",
"#.X.....#",
"#.#.#.#.#",
"#.X.....#",
"#########"]
if lvnum == 25: #74 moves
return [
"############",
"#......XXXXG",
"#.....######",
"#.....######",
"#.....######",
"#@....######",
"############"]
if lvnum == 25.1: #106 moves
return [
"############",
"#.....XXXXXG",
"#.....######",
"#..........#",
"#..........#",
"#@.........#",
"############"]
if lvnum == 25.2: #163 moves
return [
"#############",
"#.....XXXXXXG",
"#.....#######",
"#...........#",
"#...........#",
"#@..........#",
"#############"]
if lvnum == 26:
return [
"##########",
"#.....XXXG",
"#....#XXX#",
"#....#...#",
"#....#...#",
"#........#",
"#@.......#",
"##########"]
if lvnum == 27:
return [
"#########",
"#......X#",
"#.#...#.#",
"#...@..XG",
"#.#...#.#",
"#......X#",
"#########"]
if lvnum == 28:
return [
"############",
"#@.........#",
"#...X...X..G",
"#.X...X...X#",
"#..........#",
"############"]
if lvnum == 29:
return [
"##########",
"#@.......#",
"#.#...X..#",
"#.#.X..X.##",
"#.#X.X..X.G",
"#.........#",
"###########"]
if lvnum == 31:
return [
"#G#######",
"#XX.....#",
"#@......#",
"#XX.....#",
"#########"]
if lvnum == 32: #9 moves
return [
"#########",
"#...@..X#",
"#..X.X.X#",
"#X......#",
"#.....X.#",
"#.X.....#",
"#.......#",
"#...X...#",
"####G####"]
if lvnum == 33: #38 moves
return [
"#########",
"#...@..XG",
"#..X.X.X#",
"#X......#",
"#.....X.#",
"#.X.....#",
"#.......#",
"#...X...#",
"#########"]
if lvnum == 33.5: #46 moves
return [
"#########",
"#...@..XG",
"#X.X.X.X#",
"#X......#",
"#.....X.#",
"#XX.....#",
"#.......#",
"#...X...#",
"#########"]
if lvnum == 33.6: #74 moves
return [
"#########",
"#...@..X#",
"#X.X.X.X#",
"#X......#",
"#.....X.#",
"GXX.....#",
"#.......#",
"#...X...#",
"#########"]
if lvnum == 34:
return [
"#########",
"#@......#",
"#.......#",
"#......X#",
"#.XXX..X#",
"####G####"]
if lvnum == 35:
return [
"#########",
"###X##X##",
"###.##.##",
"#@......#",
"#.......#",
"#......X#",
"#.XXX..X#",
"####G####"]
if lvnum == 41:
return [
"####G####",
"#X.X.X.X#",
"#.#.#.#.#",
"#.......#",
"#.#.#.#.#",
"#.......#",
"#O#O#O#O#",
"#...@...#",
"########"]
if lvnum == 42:
return [
"########",
"#X....XG",
"###..###",
"#...@OX#",
"#.#..#.#",
"#......#",
"####...#",
"########"]
if lvnum == 43:
return [
"#######",
"#X...X#",
"#X...XG",
"#X...X#",
"#..O..#",
"#..O..#",
"##.@.##",
"#######"]
if lvnum == 44:
return [
"#######",
"#X....#",
"#.....#",
"#..XO@#####",
"#.....#...#",
"#X........G",
"########X##"]
if lvnum == 45:
return [
"#############",
"#.X.X.X.X.X.#",
"#...........###",
"#@.........O..#",
"#...........#G#",
"#..X.X.X.X.X#",
"#############"]
if lvnum == 51:
return [
"###########",
"#.....XXXXG",
"#.....#####",
"#.....#####",
"#.....#####",
"#@....#####",
"###########"]
if lvnum == 52:
return [
"#########",
"#......X#",
"#.#...###",
"#...@..XG",
"#.#...###",
"#......X#",
"#########"]
if lvnum == 53:
return [
"###########"
"####....X.G",
"####.####.#",
"#X.X.X.X#.#",
"#.#.#.#.#.#",
"#.......#.#",
"#.#.#.#.#.#",
"#.......#.#",
"#O#O#O#O#.#",
"#...@.....#",
"###########"]
if lvnum == 53.1:
return [
"#########",
"####k####",
"#X.X.X.X#",
"#.#.#.#.#",
"#.......#",
"#.#.#.#.#",
"#.......#",
"#O#O#O#O#",
"#...@...g",
"#########"]
if lvnum == 54:
return [
"#######",
"#X....####",
"#.....##X##",
"#..XO@....G",
"#.....#...#",
"#X....#####",
"#######"]
if lvnum == 55:
return [
"#######",
"#....X#",
"#.....#",
"#@OX..#####",
"#.....#...#",
"#....X....G",
"########X##"]
if lvnum == 56:
return [
"##########",
"#@.......#",
"#.#...X..#",
"#...X..X.##",
"#.#X.X..X.G",
"#.........#",
"###########"]
if lvnum == 57:
return [
"#########",
"#....XXXG",
"#.#.###X#",
"#.....#X#",
"#.#.#.#X#",
"#.......#",
"#.#.#.#.#",
"#@......#",
"#########"]
if lvnum == 71:
return [
"###########",
"#@........#",
"#....####.#",
"#....XXXX.G",
"#....####.#",
"#.........#",
"###########"]
if lvnum == 80:
return [
"#############",
"#.X.X.X.X.X.####",
"#..............#",
"#@..........##.#",
"#..............#",
"#..X.X.X.X.X#G##",
"#############"]
if lvnum == 81:
return [
"####################",
"#...XXX...#.....#..G",
"#.....#...#..X..#..#",
"#.....#......#..X..#",
"#..@..#......#.....#",
"####################"]
if lvnum == 82: #78 WWNWSSSENWSSNSNEEENSSNEEWWNNNNSSSSEEWWNNNNSNSNSNSSSSEEENNNNEEEWEWWESSSNSSEENEE
return [
"##############",
"#............#",
"#...X.X.X.X.X#",
"#...@........#",
"#...X.X.X.X.XG",
"#............#",
"#...X.X.X.X.X#",
"#............#",
"##############"]
if lvnum == 83: #40 NESESEEWWWNNWEENWWSSESSEENENNNSEEENEEESE
return [
"#############",
"#.....XX....#",
"#......XX...G",
"#@......XX..#",
"#........XX.#",
"#.........XX#",
"#############"]
if lvnum == 84:
return [
"#############",
"#......X....#",
"#.....X.XXX.#",
"#@..........G",
"#......X....#",
"#.....X.XXX.#",
"#############"]
if lvnum == 99:
return [
"####",
"#@.g",
"#k##",
"###,"]
def init_state(board): # returns a state "object" which is an array [position, grid, movehistory]
start = [[j for j in i] for i in board]
spos = (0,0)
for i in range(len(start)):
for j in range(len(start[i])):
if start[i][j] == "@":
spos = (i,j)
return [spos,start,""]
def prettyprint(grid): # prints the grid in a nice format
for i in grid:
print("".join(i))
def compact(grid): # helper function to convert grids into a hashable format
return "".join(["".join(i) for i in grid]).replace("#","")
def compact1d(grid): # convert 1d board to string
return "".join(grid).replace("#","")
def replay(start_board, movelist): # prints out the entire movesequence
state = init_state(start_board)
for i in movelist:
prettyprint(state[1])
print()
state = move(state, i, set())[1]
prettyprint(state[1])
def move(prev_state, move, alreadyseen): # Simulates playing a certain move during a certain state.
push, key = False, False
assert move in moves
#if compact(prev_state[1]) in alreadyseen:
# return "NO", -1 #repeated state
moveto = prev_state[1][prev_state[0][0]+moves[move][0]][prev_state[0][1]+moves[move][1]]
if moveto in ["X", "#", "g"]:
return "NO", -1 #can't move
if moveto in ["k"]:
key = True
if moveto in ["G"]:
#print(len(prev_state[2])+1,prev_state[2]+move)
return "WIN", prev_state[2]+move
if moveto in ["O", "K"]:
push = moveto
if prev_state[1][prev_state[0][0]+2*moves[move][0]][prev_state[0][1]+2*moves[move][1]] not in ["."]:
return "NO", -1 #can't move
enemies = 0
goals = 0
for delta in moves:
if prev_state[1][prev_state[0][0]+moves[move][0]+moves[delta][0]][prev_state[0][1]+moves[move][1]+moves[delta][1]] == "X":
enemies += 1
if enemies == 1:
return "NO", -1 #you will die
# move is valid, let us now copy
next_board = [[a for a in b] for b in prev_state[1]]
if key:
for i in next_board:
for j in range(len(i)):
if i[j] == "g":
i[j] = "G"
next_state = [(prev_state[0][0]+moves[move][0],prev_state[0][1]+moves[move][1]),next_board,prev_state[2]+move]
next_board[prev_state[0][0]][prev_state[0][1]] = "."
next_board[prev_state[0][0]+moves[move][0]][prev_state[0][1]+moves[move][1]] = "@"
if push:
next_board[prev_state[0][0]+2*moves[move][0]][prev_state[0][1]+2*moves[move][1]] = push
for delta in moves:
dist = 1
curpos = (next_state[0][0]+moves[delta][0],next_state[0][1]+moves[delta][1])
while next_board[curpos[0]][curpos[1]] == ".":
curpos = (curpos[0]+moves[delta][0],curpos[1]+moves[delta][1])
dist += 1
if dist != 1 and next_board[curpos[0]][curpos[1]] == "X":
next_board[curpos[0]][curpos[1]] = "."
next_board[curpos[0]-moves[delta][0]][curpos[1]-moves[delta][1]] = "X"
return "CONT", next_state
def board_solver(board): # BFS solver for Jailbreak instances.
start_state = init_state(board)
alreadyseen = {compact(start_state[1])}
q = collections.deque()
q.append(start_state)
i, r, w = 0, 0, 0
while len(q) > 0:
i += 1
st = q.popleft()
if i%10000 == 0 or len(st[2]) > r:
print(i, len(q), len(st[2]), w)
r = len(st[2])
for m in moves:
tr = move(st, m, alreadyseen)
if tr[0] == "WIN":
w += 1
#return tr[1]
if tr[0] == "CONT":
if compact(tr[1][1]) not in alreadyseen:
q.append(tr[1])
alreadyseen.update({compact(tr[1][1])})
#alreadyseen.update({compact(st[1])})
def mutate(board):
pass
while True:
board = level_collection(int(input()))
solve = board_solver(board)
#replay(board, solve)
@phenomist
Copy link
Author

phenomist commented Apr 6, 2018 •
edited

Updated 2018/4/6 2:25 PM - Added block pushing functionality, level selection, fixed no-repeat (should be a substantial speedup)
Updated 2018/4/7 1:29 AM - Some code reorganization. Added replay writing functionality (doesn't check whether replay is bad though)
Updated 2018/4/18 12:21 AM - Added latest levels. Did some memory optimizations, should use ~60% less memory, and should be faster too. 5.3 is likely too slow (i.e. memory overflow) so also implemented locks and keys - use 53.1 instead. Also added some statistics tracking.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment