Breadth-first Search algorithm for a fun programming task
Challenge
We have created a mini game to test your skills. Go grab the flag!!
authors : careless_finch, malf0y
nc misc.challenge.bi0s.in 1337
Solution
Here are the rules of the challenge:
This could be solved by performing a breadth-first search (BFS) on all the possible moves. The problem with a depth-first search (DFS) - which I tried at first - was that we could get a solution, but it wouldn't be the best solution (it will exceed the maximum number of moves) , and finding the best solution would take too long on later levels.
But even on a BFS, the lower layers would eventually get too big since each game state would have many possible moves. To solve this, I filtered out those moves that heuristically "don't make sense".
In particular, I implemented this function that computes the "difference" between the current grid and the target grid. This is essentially the sum of the absolute differences of the x and y coordinates between the grids.
def compute_difference(self, other_grid):
result = 0
values = []
for row in self.grid:
values += [x for x in row if x != '0']
for value in values:
x1, y1 = self.get_coords(value)
x2, y2 = other_grid.get_coords(value)
result += abs(x1 - x2) + abs(y1 - y2)
return result
Heuristically, if making a move increases this difference, then that move is worse than one that decreases it. After generating all the possible moves, a threshold is applied at each layer to filter these bad moves.
Here's the final solve script:
from pwn import *
from copy import deepcopy as copy
from pprint import pprint
class Grid:
def __init__(self, grid, path=[]):
self.grid = grid
self.path = path
def make_move(self, move):
"""
move: [current-x-cord, current-y-cord, to-x-cord, to-y-cord]
"""
curr_x, curr_y, to_x, to_y = move
tmp = self.grid[curr_y][curr_x]
self.grid[curr_y][curr_x] = '0'
if self.grid[to_y][to_x] == '0':
self.grid[to_y][to_x] = tmp
self.path.append(move)
else:
raise ValueError("Destination is not empty")
def get_possible_moves(self):
result = []
for y in range(len(self.grid)):
for x in range(len(self.grid)):
if self.grid[y][x] != '0':
if y != len(self.grid) - 1 and self.grid[y+1][x] == '0':
result.append((x, y, x, y + 1))
if y != 0 and self.grid[y-1][x] == '0':
result.append((x, y, x, y - 1))
if x != len(self.grid) - 1 and self.grid[y][x+1] == '0':
result.append((x, y, x + 1, y))
if x != 0 and self.grid[y][x-1] == '0':
result.append((x, y, x - 1, y))
return result
def get_coords(self, value):
for y in range(len(self.grid)):
for x in range(len(self.grid)):
if self.grid[y][x] == value:
return (x, y)
def compute_difference(self, other_grid):
result = 0
values = []
for row in self.grid:
values += [x for x in row if x != '0']
for value in values:
x1, y1 = self.get_coords(value)
x2, y2 = other_grid.get_coords(value)
result += abs(x1 - x2) + abs(y1 - y2)
return result
def copy(self):
return Grid(copy(self.grid), copy(self.path))
def __eq__(self, other_grid):
return self.grid == other_grid.grid
def __str__(self):
to_ret = '+' + '-' * (len(self.grid) * 4 - 1) + '+\n'
for row in self.grid:
to_ret += '| ' + ' | '.join(row) + ' |' + '\n'
to_ret += '+' + '-' * (len(self.grid) * 4 - 1) + '+\n'
return to_ret
def solve(grid, target_grid):
print("Solving...")
layer = [grid]
done = False
visited = []
while not done:
next_layer = []
curr_min_diff = 10000000000
curr_best_grid = None
for grid in layer:
if grid in visited:
continue
elif grid == target_grid:
print("Solved!")
return grid.path
possible_moves = grid.get_possible_moves()
visited.append(grid)
for move in possible_moves:
new_grid = grid.copy()
new_grid.make_move(move)
diff = new_grid.compute_difference(target_grid)
if diff < curr_min_diff:
curr_best_grid = new_grid
curr_min_diff = diff
next_layer.append(new_grid)
treshold = curr_min_diff
print("Threshold:", treshold)
if treshold <= 10:
next_layer = [x for x in next_layer if x.compute_difference(target_grid) <= treshold]
else:
next_layer = [curr_best_grid]
layer = next_layer
conn = remote("misc.challenge.bi0s.in", 1337)
print(conn.recv().decode())
print(conn.recv().decode())
conn.send(b'y\n')
print(conn.recv().decode())
received = conn.recv().decode()
print(received)
level = 0
while True:
grid = []
target_grid = []
for line in received.splitlines():
if line.startswith('|'):
row = []
data = [x.strip() for x in line.split('|') if x and not x.isspace()]
grid.append(data[:len(data) // 2])
target_grid.append(data[len(data) // 2:])
grid = Grid(grid)
target_grid = Grid(target_grid)
print("Level:", level)
print(grid)
print(target_grid)
solved = solve(grid, target_grid)
# print(solved, len(solved))
for move in solved:
print("Sending move...")
curr_x, curr_y, to_x, to_y = move
conn.send(f"{curr_y},{curr_x},{to_y},{to_x}\n")
received = conn.recv().decode()
print(received)
received = conn.recv().decode()
print(received)
level += 1
if level == 9:
break
print(conn.recv().decode())
After successfully solving nine levels, we get the flag.
