👨‍💻
CTFs
HomePlaygroundOSCPBuy Me a Flag 🚩
  • 🚩Zeyu's CTF Writeups
  • Home
  • Playground
  • OSCP
  • My Challenges
    • SEETF 2023
    • The InfoSecurity Challenge 2022
    • SEETF 2022
    • Cyber League Major 1
    • STANDCON CTF 2021
      • Space Station
      • Star Cereal
      • Star Cereal 2
      • Mission Control
      • Rocket Science
      • Space University of Interior Design
      • Rocket Ship Academy
      • Space Noise
  • 2023
    • DEF CON CTF 2023 Qualifiers
    • hxp CTF
      • true_web_assembly
    • HackTM CTF Qualifiers
      • Crocodilu
      • secrets
      • Hades
  • 2022
    • niteCTF 2022
      • Undocumented js-api
      • js-api
    • STACK the Flags 2022
      • Secret of Meow Olympurr
      • The Blacksmith
      • GutHib Actions
      • Electrogrid
      • BeautyCare
    • LakeCTF Qualifiers
      • People
      • Clob-Mate
      • So What? Revenge
    • The InfoSecurity Challenge 2022
      • Level 1 - Slay The Dragon
      • Level 2 - Leaky Matrices
      • Level 3 - PATIENT0
      • Level 4B - CloudyNekos
      • Level 5B - PALINDROME's Secret (Author Writeup)
    • BalsnCTF 2022
      • 2linenodejs
      • Health Check
    • BSidesTLV 2022 CTF
      • Smuggler
      • Wild DevTools
      • Tropical API
    • Grey Cat The Flag 2022
    • DEF CON CTF 2022 Qualifiers
    • Securinets CTF Finals 2022
      • StrUggLe
      • XwaSS ftw?
      • Strong
      • Artist
    • NahamCon CTF 2022
      • Flaskmetal Alchemist
      • Hacker TS
      • Two For One
      • Deafcon
      • OTP Vault
      • Click Me
      • Geezip
      • Ostrich
      • No Space Between Us
    • Securinets CTF Quals 2022
      • Document-Converter
      • PlanetSheet
      • NarutoKeeper
    • CTF.SG CTF
      • Asuna Waffles
      • Senpai
      • We know this all too well
      • Don't Touch My Flag
      • Wildest Dreams Part 2
      • Chopsticks
    • YaCTF 2022
      • Shiba
      • Flag Market
      • Pasteless
      • Secretive
      • MetaPDF
      • Crackme
    • DiceCTF 2022
      • knock-knock
      • blazingfast
    • TetCTF 2022
      • 2X-Service
      • Animals
      • Ezflag Level 1
  • 2021
    • hxp CTF 2021
    • HTX Investigator's Challenge 2021
    • Metasploit Community CTF
    • MetaCTF CyberGames
      • Look, if you had one shot
      • Custom Blog
      • Yummy Vegetables
      • Ransomware Patch
      • I Hate Python
      • Interception
    • CyberSecurityRumble CTF
      • Lukas App
      • Finance Calculat0r 2021
      • Personal Encryptor with Nonbreakable Inforation-theoretic Security
      • Enterprice File Sharing
      • Payback
      • Stonks Street Journal
    • The InfoSecurity Challenge (TISC) 2021
      • Level 4 - The Magician's Den
      • Level 3 - Needle in a Greystack
      • Level 2 - Dee Na Saw as a need
      • Level 1 - Scratching the Surface
    • SPbCTF's Student CTF Quals
      • 31 Line PHP
      • BLT
      • CatStep
    • Asian Cyber Security Challenge (ACSC) 2021
      • Cowsay As A Service
      • Favorite Emojis
      • Baby Developer
      • API
      • RSA Stream
      • Filtered
      • NYONG Coin
    • CSAW CTF Qualification Round 2021
      • Save the Tristate
      • securinotes
      • no pass needed
      • Gatekeeping
      • Ninja
    • YauzaCTF 2021
      • Yauzacraft Pt. 2
      • Yauzabomber
      • RISC 8bit CPU
      • ARC6969 Pt. 1
      • ARC6969 Pt. 2
      • Back in 1986 - User
      • Lorem-Ipsum
    • InCTF 2021
      • Notepad 1 - Snakehole's Secret
      • RaaS
      • MD Notes
      • Shell Boi
      • Listen
      • Ermittlung
      • Alpha Pie
    • UIUCTF 2021
      • pwnies_please
      • yana
      • ponydb
      • SUPER
      • Q-Rious Transmissions
      • capture the :flag:
      • back_to_basics
      • buy_buy_buy
    • Google CTF 2021
      • CPP
      • Filestore
    • TyphoonCon CTF 2021
      • Clubmouse
      • Impasse
    • DSTA BrainHack CDDC21
      • File It Away (Pwn)
      • Linux Rules the World! (Linux)
      • Going Active (Reconnaissance)
      • Behind the Mask (Windows)
      • Web Takedown Episode 2 (Web)
      • Break it Down (Crypto)
    • BCACTF 2.0
      • L10N Poll
      • Challenge Checker
      • Discrete Mathematics
      • Advanced Math Analysis
      • Math Analysis
      • American Literature
      • More Than Meets the Eye
      • 􃗁􌲔􇺟􊸉􁫞􄺷􄧻􃄏􊸉
    • Zh3ro CTF V2
      • Chaos
      • Twist and Shout
      • 1n_jection
      • alice_bob_dave
      • Baby SSRF
      • bxxs
      • Sparta
    • Pwn2Win CTF 2021
      • C'mon See My Vulns
      • Illusion
    • NorzhCTF 2021
      • Leet Computer
      • Secure Auth v0
      • Triskel 3: Dead End
      • Triskel 2: Going In
      • Triskel 1: First Contact
      • Discovery
    • DawgCTF 2021
      • Bofit
      • Jellyspotters
      • No Step On Snek
      • Back to the Lab 2
      • MDL Considered Harmful
      • Really Secure Algorithm
      • The Obligatory RSA Challenge
      • Trash Chain
      • What the Flip?!
      • Back to the Lab 1
      • Back to the Lab 3
      • Dr. Hrabowski's Great Adventure
      • Just a Comment
      • Baby's First Modulation
      • Two Truths and a Fib
    • UMDCTF 2021
      • Advantageous Adventures
      • Roy's Randomness
      • Whose Base Is It Anyway
      • Cards Galore
      • Pretty Dumb File
      • Minetest
      • Donnie Docker
      • Subway
      • Jump Not Easy
      • To Be XOR Not To Be
      • Office Secrets
      • L33t M4th
      • Bomb 2 - Mix Up
      • Jay
    • Midnight Sun CTF 2021
      • Corporate MFA
      • Gurkburk
      • Backups
    • picoCTF 2021
      • It Is My Birthday (100)
      • Super Serial (130)
      • Most Cookies (150)
      • Startup Company (180)
      • X marks the spot (250)
      • Web Gauntlet (170 + 300)
      • Easy Peasy (40)
      • Mini RSA (70)
      • Dachshund Attacks (80)
      • No Padding, No Problem (90)
      • Trivial Flag Transfer Protocol (90)
      • Wireshark twoo twooo two twoo... (100)
      • Disk, Disk, Sleuth! (110 + 130)
      • Stonks (20)
    • DSO-NUS CTF 2021
      • Insecure (100)
      • Easy SQL (200)
Powered by GitBook
On this page
  • Challenge
  • Solution

Was this helpful?

  1. 2021
  2. InCTF 2021

Alpha Pie

Breadth-first Search algorithm for a fun programming task

PreviousErmittlungNextUIUCTF 2021

Last updated 3 years ago

Was this helpful?

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.