# Alpha Pie ## 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: ![](/files/-MhF1s783QRYqrWkxlGg) 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. ```python 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: ```python 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. ![](/files/-MhF8u6jL6nYU2jXot2P) --- # Agent Instructions: Querying This Documentation If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question. Perform an HTTP GET request on the current page URL with the `ask` query parameter: ``` GET https://ctf.zeyu2001.com/2021/inctf-2021/alpha-pie.md?ask= ``` The question should be specific, self-contained, and written in natural language. The response will contain a direct answer to the question and relevant excerpts and sources from the documentation. Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.