Skip to content

Instantly share code, notes, and snippets.

@aaugustin
Last active November 4, 2015 05:02
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save aaugustin/cb98edb9df9f28de3125 to your computer and use it in GitHub Desktop.
Save aaugustin/cb98edb9df9f28de3125 to your computer and use it in GitHub Desktop.
Quick'n'dirty solver for http://gameaboutsquares.com/.
#!/usr/bin/env python
# Copyright (c) 2014 Aymeric Augustin
# Released under the WTFPLv2 - http://www.wtfpl.net/txt/copying/
"""
Quick'n'dirty solver for http://gameaboutsquares.com/.
Install requests or save http://gameaboutsquares.com/game.c.js next to this
file. Then run: python gameaboutsquares.py. Tested with Python 2.7 and 3.4.
"""
from collections import deque, namedtuple, OrderedDict
import re
# The following list is hardcoded because it's difficult to extract a human-
# friendly, plain-text representation of colors from their hexadecimal codes.
COLORS = [
"red", # c0392b
"blue", # 2980b9
"dark blue", # 2c3e50
"orange", # e67e22
"turquoise", # 16a085
"green", # 27ae60
"purple", # 9b59b6
"grey", # 7f8c8d
"yellow", # f1c40f
"light red", # c24646
"dark green", # 0b7140
"olive", # 555744
"light orange", # f19c2e
]
# Data structures for items on the board. row and col are integers storing the
# row (top to bottom) and column (left to right) where the item is located.
# way is a string during the loading phase and an integer during the solving
# phase; in both cases in stores the direction of the item. val is an integer
# encoding the color of the item; it can be used as an index in COLORS.
Arrow = namedtuple('Arrow', ['row', 'col', 'way'])
Square = namedtuple('Square', ['row', 'col', 'val', 'way'])
Target = namedtuple('Target', ['row', 'col', 'val'])
# LOADING PHASE
# load_javascript(), load_levels() and preprocess_level(level) build a
# convenient representation of the items in a level with the above data
# structures. Their implementation is both horrific and uninteresting.
def load_javascript():
try:
with open('game.c.js', 'r') as f:
return f.read()
except IOError:
import requests
data = requests.get('http://gameaboutsquares.com/game.c.js').text
with open('game.c.js', 'w') as f:
f.write(data)
return data
def load_levels():
js = load_javascript()
js = js.replace('\n', '')
order = re.search(r'levelOrder="([\w ]+)"\.split\(" "\);', js).group(1)
order = order.split()
levels = re.search(r'var h=({.*});', js).group(1)
levels = re.sub(r'\b(\w+):function\(\){(.*?)},?',
r'"\1": [\n\2\n],\n', levels)
# targets: new a(<col>, <row>, new d, <val>)
levels = re.sub(r'new a\((-?\d+),(-?\d+),new d,(-?\d+)\);?',
r' Target(\2, \1, \3),\n', levels)
# arrows: new a(<col>, <row>, new b(<direction>))
levels = re.sub(r'new a\((-?\d+),(-?\d+),new b\("(\w+)"\)\);?',
r' Arrow(\2, \1, "\3"),\n', levels)
# squares: new c(<col>, <row>, <val>, new b(<direction>))
levels = re.sub(r'new c\((-?\d+),(-?\d+),(-?\d+),new b\("(\w+)"\)\);?',
r' Square(\2, \1, \3, "\4"),\n', levels)
# squares on arrows: new c(<col>, <row>, <val>)
levels = re.sub(r'new c\((-?\d+),(-?\d+),(-?\d+)\);?',
r' Square(\2, \1, \3, "inherit"),\n', levels)
levels = eval(levels)
return OrderedDict((name, levels[name]) for name in order)
def preprocess_level(level):
raw_arrows = [item for item in level if isinstance(item, Arrow)]
# Transform orientation information into a numerical value.
arrows = []
for arrow in raw_arrows:
way = ['up', 'down', 'left', 'right'].index(arrow.way)
arrows.append(Arrow(arrow.row, arrow.col, way))
raw_squares = [item for item in level if isinstance(item, Square)]
# As above, also obtain missing orientation information from arrows.
squares = []
for square in raw_squares:
if square.way == 'inherit':
for arrow in arrows:
if arrow.row == square.row and arrow.col == square.col:
way = arrow.way
break
else:
way = ['up', 'down', 'left', 'right'].index(square.way)
squares.append(Square(square.row, square.col, square.val, way))
raw_targets = [item for item in level if isinstance(item, Target)]
# Store targets in the same order as squares for convenience.
targets = [{t.val: t for t in raw_targets}.get(s.val) for s in raw_squares]
return arrows, squares, targets
# SOLVING PHASE
def solve(arrows, squares, targets):
# Determine the smallest rectangle enclosing all items.
items = [item for item in arrows + squares + targets if item is not None]
row_min = min(item.row for item in items)
row_max = max(item.row for item in items) + 1
col_min = min(item.col for item in items)
col_max = max(item.col for item in items) + 1
def find_path(padding=0):
# find_path() performs a simple Breadth First Search in a graph where
# each board position (i.e. what you see on screen) defines a vertex
# and each movement (i.e. when you click a square) defines an edge.
# The graph is computed on demand. It isn't stored.
# find_path() explores positions within a rectangle defined by
# extending the smallest rectangle enclosing all items with some
# padding. To simplify the implementation, rows and columns are
# shifted so the upper left corner of that rectangle is at (0, 0)
# and its lower left corner is at (n_rows - 1, n_cols - 1).
row_off = padding - row_min
col_off = padding - col_min
n_rows = row_off + row_max + padding
n_cols = col_off + col_max + padding
# position_id(squares) turns a position into a unique
# integer that is used as a graph vertex identifier. This should be
# cheaper that using the entire position, both in memory and CPU, all
# the more since it's a perfect hash. It could be reversed, perhaps to
# improve the display of solutions, but this property isn't used yet.
n_positions = n_rows * n_cols * 4
def position_id(squares):
res = 0
for row, col, _, way in squares:
res *= n_positions
res += ((row + row_off) * n_cols + (col + col_off)) * 4 + way
return res
# The following function takes a position, moves one square and
# returns the resulting position, or None if a square is pushed
# outside of the rectangle. There are two kind of moves:
# - If the square is initiating a move, the way parameter isn't
# provided and the direction is the square's orientation.
# - If the square is pushed by another square, the direction is
# provided by the way parameter.
def move_square(squares, square_index, way=None):
square = squares[square_index]
if way is None:
way = square.way
# Handle movement.
if way == 0: # up
if square.row + row_off == 0:
return
new_row, new_col = square.row - 1, square.col
elif way == 1: # down
if square.row + row_off == n_rows - 1:
return
new_row, new_col = square.row + 1, square.col
elif way == 2: # left
if square.col + col_off == 0:
return
new_row, new_col = square.row, square.col - 1
elif way == 3: # right
if square.col + col_off == n_cols - 1:
return
new_row, new_col = square.row, square.col + 1
# Handle direction.
for arrow in arrows:
if arrow.row == new_row and arrow.col == new_col:
new_way = arrow.way
break
else:
new_way = square.way
# Create a new position with these changes.
new_square = Square(new_row, new_col, square.val, new_way)
new_squares = list(squares)
new_squares[square_index] = new_square
# If the movement pushed another square, move it. Recursion is
# guaranteed to terminate because all moves are in the same
# direction, so each square may move most once.
for other_square_index, other_square in enumerate(new_squares):
if other_square_index == square_index:
continue
if other_square.row == new_row and other_square.col == new_col:
return move_square(new_squares, other_square_index, way)
else:
return new_squares
# The following function computes whether a given position is winning.
def target_reached(squares):
for square, target in zip(squares, targets):
if target is None:
continue
if square.row == target.row and square.col == target.col:
continue
return False
else:
return True
# To implement a Breadth First Search, we don't have to compute the
# entire graph. We just need to keep track of which positions we've
# already visited, and for each of them, which path led there. In
# addition to the previous position, we also store the color of the
# square that moved. We also need a queue of positions to visit.
source = position_id(squares)
done = {source: (None, None)}
todo = deque([(squares, source)])
while True:
# Fetch the next position to visit from the queue. If the queue is
# empty, no solution exists in the current rectangle.
try:
cur_squares, cur_position_id = todo.popleft()
except IndexError:
return
# Try each possible move in this position.
for square_index in range(len(squares)):
new_squares = move_square(cur_squares, square_index)
# If it pushes a square outside of the rectangle, ignore it.
if new_squares is None:
continue
new_position_id = position_id(new_squares)
# If it results in a position we've already seen, ignore it.
if new_position_id in done:
continue
done[new_position_id] = (cur_position_id, square_index)
# If we've found a solution, return it.
if target_reached(new_squares):
path = []
while new_position_id != source:
new_position_id, square_index = done[new_position_id]
path.append(squares[square_index].val)
return list(reversed(path))
# If this is a new valid position, add it to the queue.
todo.append((new_squares, new_position_id))
# Since the size of the graph is in O(board size ^ number of squares),
# which is also O(padding ^ (2 * number of squares)), we start with no
# padding and increase it up to number of squares - 1 only if needed.
for padding in range(len(squares)):
path = find_path(padding)
if path is not None:
return path
if __name__ == '__main__':
levels = load_levels()
for index, (name, level) in enumerate(levels.items()):
print("")
print("Level {} ({})".format(index, name))
print("")
solution = solve(*preprocess_level(level))
if solution is None:
print("No solution found :(")
else:
print("Solution in {} moves:".format(len(solution)))
print("")
grouped = []
for val in solution:
if grouped and grouped[-1][0] == val:
grouped[-1][1] += 1
else:
grouped.append([val, 1])
for val, count in grouped:
print(' - {} x {}'.format(count, COLORS[val]))
Level 0 (hi)
Solution in 2 moves:
- 2 x red
Level 1 (hi3)
Solution in 2 moves:
- 1 x blue
- 1 x red
Level 2 (order2)
Solution in 6 moves:
- 2 x red
- 2 x blue
- 2 x dark blue
Level 3 (push)
Solution in 9 moves:
- 1 x blue
- 2 x red
- 1 x blue
- 1 x red
- 3 x blue
- 1 x red
Level 4 (stairs)
Solution in 5 moves:
- 1 x blue
- 1 x red
- 1 x blue
- 1 x dark blue
- 1 x blue
Level 5 (stairs2)
Solution in 5 moves:
- 1 x blue
- 1 x red
- 1 x dark blue
- 1 x blue
- 1 x dark blue
Level 6 (lift)
Solution in 8 moves:
- 1 x dark blue
- 1 x red
- 1 x blue
- 1 x red
- 2 x blue
- 1 x dark blue
- 1 x red
Level 7 (presq)
Solution in 6 moves:
- 6 x blue
Level 8 (sq)
Solution in 9 moves:
- 1 x orange
- 1 x dark blue
- 5 x orange
- 2 x dark blue
Level 9 (nobrainer)
Solution in 5 moves:
- 2 x orange
- 1 x blue
- 1 x orange
- 1 x blue
Level 10 (crosst)
Solution in 8 moves:
- 3 x red
- 2 x dark blue
- 3 x blue
Level 11 (t)
Solution in 14 moves:
- 1 x red
- 4 x dark blue
- 1 x red
- 1 x dark blue
- 2 x blue
- 2 x red
- 2 x blue
- 1 x dark blue
Level 12 (rotation)
Solution in 9 moves:
- 2 x orange
- 1 x dark blue
- 1 x orange
- 1 x dark blue
- 1 x orange
- 1 x dark blue
- 1 x orange
- 1 x dark blue
Level 13 (asymm)
Solution in 10 moves:
- 2 x blue
- 1 x orange
- 1 x blue
- 1 x orange
- 1 x dark blue
- 1 x orange
- 3 x blue
Level 14 (clover)
Solution in 8 moves:
- 1 x red
- 1 x dark blue
- 1 x orange
- 1 x dark blue
- 1 x blue
- 1 x orange
- 1 x blue
- 1 x red
Level 15 (preduced)
Solution in 13 moves:
- 3 x red
- 1 x blue
- 1 x red
- 1 x blue
- 2 x red
- 1 x blue
- 3 x red
- 1 x blue
Level 16 (herewego)
Solution in 14 moves:
- 4 x red
- 2 x blue
- 1 x red
- 1 x blue
- 5 x red
- 1 x blue
Level 17 (reduced)
Solution in 19 moves:
- 3 x red
- 2 x blue
- 3 x dark blue
- 1 x red
- 1 x dark blue
- 1 x red
- 1 x blue
- 1 x red
- 1 x blue
- 1 x dark blue
- 1 x red
- 1 x dark blue
- 2 x red
Level 18 (reduced2)
Solution in 18 moves:
- 1 x dark blue
- 3 x blue
- 1 x red
- 1 x blue
- 2 x dark blue
- 1 x blue
- 7 x red
- 1 x blue
- 1 x dark blue
Level 19 (spiral2)
Solution in 27 moves:
- 9 x red
- 1 x blue
- 1 x red
- 1 x blue
- 1 x red
- 1 x dark blue
- 1 x blue
- 1 x red
- 1 x dark blue
- 1 x blue
- 1 x dark blue
- 1 x red
- 1 x blue
- 1 x dark blue
- 1 x blue
- 2 x dark blue
- 1 x blue
- 1 x red
Level 20 (recycle2)
Solution in 23 moves:
- 1 x dark blue
- 1 x grey
- 1 x purple
- 2 x grey
- 1 x purple
- 1 x dark blue
- 3 x grey
- 1 x turquoise
- 1 x grey
- 2 x turquoise
- 1 x dark blue
- 2 x turquoise
- 1 x dark blue
- 2 x turquoise
- 1 x dark blue
- 1 x grey
- 1 x purple
Level 21 (recycle3)
Solution in 43 moves:
- 1 x light red
- 1 x dark green
- 3 x light red
- 1 x olive
- 1 x light orange
- 1 x light red
- 1 x dark green
- 1 x light red
- 1 x light orange
- 1 x light red
- 1 x olive
- 1 x light orange
- 1 x light red
- 2 x dark green
- 1 x olive
- 2 x light orange
- 1 x olive
- 4 x light orange
- 1 x olive
- 2 x light orange
- 1 x light red
- 1 x dark green
- 1 x light orange
- 2 x olive
- 1 x light red
- 1 x olive
- 1 x dark green
- 1 x light red
- 1 x olive
- 2 x light orange
- 1 x dark green
- 2 x light orange
Level 22 (shirt)
Solution in 15 moves:
- 1 x red
- 3 x blue
- 5 x dark blue
- 1 x red
- 1 x dark blue
- 1 x red
- 1 x dark blue
- 2 x red
Level 23 (shuttle)
Solution in 17 moves:
- 2 x blue
- 1 x dark blue
- 6 x blue
- 1 x dark blue
- 2 x red
- 1 x blue
- 1 x dark blue
- 1 x blue
- 1 x red
- 1 x blue
Level 24 (spiral)
Solution in 17 moves:
- 6 x red
- 2 x blue
- 3 x red
- 2 x blue
- 1 x red
- 1 x dark blue
- 1 x blue
- 1 x red
Level 25 (splinter)
Solution in 23 moves:
- 1 x blue
- 1 x dark blue
- 1 x blue
- 1 x red
- 2 x blue
- 9 x dark blue
- 2 x blue
- 1 x dark blue
- 1 x blue
- 1 x dark blue
- 1 x red
- 1 x blue
- 1 x dark blue
Level 26 (elegant)
Solution in 20 moves:
- 2 x blue
- 1 x dark blue
- 1 x red
- 1 x blue
- 1 x red
- 1 x blue
- 1 x orange
- 2 x dark blue
- 1 x blue
- 1 x dark blue
- 1 x blue
- 1 x dark blue
- 1 x orange
- 2 x dark blue
- 3 x orange
Level 27 (shuttle2)
Solution in 22 moves:
- 1 x red
- 3 x blue
- 1 x dark blue
- 1 x blue
- 1 x dark blue
- 2 x blue
- 3 x dark blue
- 1 x blue
- 1 x dark blue
- 1 x blue
- 2 x dark blue
- 1 x blue
- 2 x dark blue
- 1 x blue
- 1 x dark blue
Level 28 (shirt2)
Solution in 17 moves:
- 2 x blue
- 2 x red
- 2 x dark blue
- 1 x red
- 4 x blue
- 5 x dark blue
- 1 x blue
Level 29 (windmill)
Solution in 15 moves:
- 1 x blue
- 3 x dark blue
- 1 x blue
- 1 x orange
- 1 x red
- 2 x orange
- 2 x dark blue
- 1 x red
- 1 x orange
- 1 x blue
- 1 x dark blue
Level 30 (paper)
Solution in 28 moves:
- 2 x red
- 5 x blue
- 1 x dark blue
- 3 x blue
- 1 x dark blue
- 2 x blue
- 1 x red
- 3 x blue
- 2 x dark blue
- 2 x red
- 1 x blue
- 2 x dark blue
- 1 x red
- 1 x dark blue
- 1 x blue
Level 31 (shuttle5)
Solution in 21 moves:
- 1 x dark blue
- 1 x blue
- 1 x red
- 2 x blue
- 1 x red
- 1 x dark blue
- 1 x blue
- 1 x red
- 1 x blue
- 1 x red
- 2 x dark blue
- 1 x red
- 1 x blue
- 1 x red
- 4 x blue
- 1 x red
Level 32 (shirtDouble)
Solution in 31 moves:
- 2 x blue
- 3 x red
- 1 x blue
- 1 x red
- 1 x blue
- 2 x dark blue
- 3 x red
- 2 x dark blue
- 2 x red
- 1 x blue
- 6 x red
- 1 x dark blue
- 1 x red
- 1 x dark blue
- 1 x red
- 1 x dark blue
- 2 x red
Level 33 (splinter2)
Solution in 23 moves:
- 1 x blue
- 1 x dark blue
- 2 x blue
- 1 x red
- 1 x blue
- 1 x dark blue
- 7 x red
- 3 x blue
- 2 x red
- 1 x blue
- 1 x red
- 2 x dark blue
Level 34 (reduced3)
Solution in 33 moves:
- 1 x dark blue
- 3 x blue
- 1 x red
- 1 x blue
- 4 x dark blue
- 4 x red
- 1 x dark blue
- 1 x blue
- 2 x red
- 2 x dark blue
- 2 x red
- 1 x dark blue
- 1 x red
- 1 x dark blue
- 2 x red
- 1 x dark blue
- 2 x red
- 1 x dark blue
- 2 x red
Level 35 (elegant2)
Solution in 39 moves:
- 2 x orange
- 1 x dark blue
- 3 x orange
- 4 x red
- 1 x orange
- 1 x red
- 1 x orange
- 2 x dark blue
- 1 x red
- 3 x dark blue
- 4 x orange
- 1 x dark blue
- 1 x orange
- 1 x dark blue
- 2 x red
- 1 x orange
- 1 x red
- 4 x dark blue
- 3 x red
- 1 x dark blue
- 1 x red
@ammaratef45
Copy link

good work man

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