Dynamically solves the bullet hell challenge by relying on the binary to do simulation.

bullet_hell.solve.py

import struct
import collections

import pwn

MAX_X = 30
MAX_Y = 40
WANTED_SCORE = 1337


def qol_patch():
    elf = pwn.ELF('bullet_hell')
    # Don't tick without input
    elf.asm(elf.symbols['wtimeout'], 'ret')
    # Become immortal
    elf.asm(elf.symbols['die'], 'ret')
    elf.save('./patched')


def get_state_addr(proc):
    # Pretty sure you can get this more intelligently, but cbs
    GAME_STATE_OFFSET = 0x2e040
    maps = open(f'/proc/{proc.pid}/maps')
    heap_line = next(m for m in maps if m.strip().endswith('[heap]'))
    return int(heap_line.split('-')[0], 16) + GAME_STATE_OFFSET


def read_struct(proc, addr, struct_def, struct_name):
    rep = collections.namedtuple(struct_name, struct_def.keys())
    typ = ''.join(struct_def.values())
    raw = proc.readmem(addr, count=struct.calcsize(typ))
    return rep(*struct.unpack(typ, raw))

def read_arr(proc, addr, item_type, n_items):
    return struct.unpack(item_type*n_items, proc.readmem(addr, count=n_items*struct.calcsize(item_type)))

def read_gamestate(proc, base_addr):
    return read_struct(proc, base_addr, {
        'player_x':    'i',
        'player_y':    'i',
        'score':       'i',
        'bullets':     'P',
        'bullets_len': 'N'
    }, 'GameState')

def read_bullets(proc, game_state):
    return [] if game_state.bullets == 0 else [
        read_struct(proc, bullet_ptr, {
            'x':  'i',
            'y':  'i',
            'dx': 'i',
            'dy': 'i'
        }, 'Bullet')
        for bullet_ptr in read_arr(proc, game_state.bullets, 'P', game_state.bullets_len)
        if bullet_ptr != 0
    ]


def provide_game_states(bin_path):
    # Start the process
    proc = pwn.process(bin_path, aslr=False)
    proc.send(b'_')
    game_state_addr = get_state_addr(proc)
    game_state = read_gamestate(proc, game_state_addr)

    pwn.log.info(f'Game State struct @ {game_state_addr:x}')

    while game_state.score < WANTED_SCORE - 1:
        if game_state.score % 100 == 0:
            pwn.log.info(f'Up to frame {game_state.score}')
        game_state = read_gamestate(proc, game_state_addr)
        bullets = read_bullets(proc, game_state)
        yield game_state, bullets

        proc.send(b'_')
        proc.clean()


def search_for_path(state_provider):
    """
    We technically already have all the bullet positions from the state_provider
    this automates generating inputs to solve the challenge, but you could just play
    it by hand
    """
    PADDING = 5
    INV_MOVE_OFFSETS = {'_': (0, 0), 'l': (-1, 0), 'k': (0, 1), 'j': (0,-1), 'h': (1, 0)}
    arr_get = lambda arr, i, j: arr[i][j] if PADDING <= i < len(arr) - PADDING and PADDING <= j < len(arr[0]) - PADDING else False
    grid = lambda: [[False] * MAX_X for _ in range(MAX_Y)]

    # Construct reachabilities for each frame going forward
    init_state, _init_bullets = next(state_provider)
    t = grid()
    t[init_state.player_y][init_state.player_x] = True
    layer_reachable = [t]

    for _state, bullets in state_provider:
        layer_bullets = set((b.x, b.y) for b in bullets)

        last_layer = layer_reachable[-1]
        cur_reachable = grid()

        for y, row in enumerate(last_layer):
            for x, _col in enumerate(row):
                for dx, dy in INV_MOVE_OFFSETS.values():
                    if arr_get(last_layer, y+dy, x+dx) and (x, y) not in layer_bullets:
                        cur_reachable[y][x] = True
        layer_reachable.append(cur_reachable)

    # Back track over the frames to find a path
    pos = next(
        (x, y)
        for x in range(PADDING, MAX_X - PADDING)
        for y in range(PADDING, MAX_Y - PADDING)
        if layer_reachable[-1][y][x]
    )
    steps = ''
    for layer in reversed(layer_reachable):
        x, y = pos
        for move_key, (dx, dy) in INV_MOVE_OFFSETS.items():
            new_pos = (x+dx, y+dy)
            if arr_get(layer, new_pos[1], new_pos[0]):
                steps += move_key
                pos = new_pos
                break
        else:
            raise "WTF?"
    
    assert pos == (init_state.player_x, init_state.player_y)
    # Algo is off by one, since there are no bullets initially we just ignore it hehe
    return '_' + ''.join(reversed(list(steps)))


if __name__ == '__main__':
    qol_patch()
    provider = provide_game_states('./patched')
    
    print(search_for_path(provider))