Stellar Quest Out of Control: how I shot 100 asteroids with fewer than 300 bytes of WebAssembly

Stellar (the organization behind the Stellar Lumen cryptocurrency) organizes programming competitions, called “Stellar Quests”. From February 15th to March 1st 2023, the competition revolved around a game called “Asteroids”, where you control a spaceship that moves through galaxies containing fuel pods and asteroids. To win, you need to shoot 100 asteroids without running out of fuel. The full instructions of this game are available on the official website.

This stellar quest had three categories: Fast (first submitted solution), Cheap (most efficient solution), and Out of Control (smallest solution). Here is how I found a solution of fewer than 300 bytes of WebAssembly (WASM) code.

From 1,619 to 298 bytes

I’ll describe each of these steps in more detail below.

First solution

I started with a solution that harvests fuel until a certain level (400) and then starts going for the asteroids. If it can’t find fuel or asteroids anymore it will move to the next galaxy:

fn moveby(engine: &GameEngine, diff_x: i32, diff_y: i32) {
    if diff_x < 0 {
        engine.p_turn(&engine::Direction::Left);
        engine.p_move(&Some((-diff_x) as u32));
    } else {
        engine.p_turn(&engine::Direction::Right);
        engine.p_move(&Some(diff_x as u32));
    }
    if diff_y > 0 {
        engine.p_turn(&engine::Direction::Up);
        engine.p_move(&Some((diff_y) as u32));
    } else {
        engine.p_turn(&engine::Direction::Down);
        engine.p_move(&Some((-diff_y) as u32));
    }
}

#[contractimpl]
impl Solution {
    pub fn solve(env: Env, engine_id: BytesN<32>) {
        let engine = GameEngine::new(&env, &engine_id);
        while engine.p_points() < 100 {
            let map = engine.get_map();
            let my_pos = engine.p_pos();

            let mut ok = false;
            let mut is_fuel = false;
            let mut destination = Point(0, 0);
            let fuel = engine.p_fuel();
            for pos in map.keys() {
                let pos = pos.unwrap();
                let thisisfuel = map.get(pos.clone()).unwrap().unwrap() == engine::MapElement::FuelPod;
                if thisisfuel == is_fuel || (!is_fuel && thisisfuel && fuel < 400) {
                    ok = true;
                    destination = pos;
                    is_fuel = thisisfuel;
                }
            }
            if !ok || (fuel < 200 && !is_fuel) {
                moveby(&engine, 17, 0);
                continue;
            }

            moveby(&engine, destination.0 - my_pos.0, destination.1 - my_pos.1);
            if is_fuel {
                engine.p_harvest()
            } else {
                engine.p_shoot()
            }
        }
    }
}

The size of this code is 1,619 bytes when compiled with make build-optimized.

I experimented a bit with the settings in Cargo.toml and noticed that setting opt-level to "s" instead of "z" and setting overflow-checks to false immediately reduced this code to 1,311 bytes.

Reducing code by only moving right

We get smaller code if we never move left (we’re only optimizing WASM size, not how many steps we take to get to 100 asteroids).

Tracking position and asteroids shot in own variables uses fewer bytes than doing contract calls to p_pos() and p_points().

To make the spaceship not run out of fuel, I made it always first harvest a fuel pod, then shoot an asteroid. This strategy never runs out of fuel so doesn’t require us to keep track of how much fuel we have left.

These simplifications reduced the WASM file to 1,016 bytes:

fn moveby(engine: &GameEngine, diff_x: i32, diff_y: i32) {
    engine.p_turn(&engine::Direction::Right);
    engine.p_move(&Some(diff_x as u32));
    if diff_y > 0 {
        engine.p_turn(&engine::Direction::Up);
        engine.p_move(&Some((diff_y) as u32));
    } else {
        engine.p_turn(&engine::Direction::Down);
        engine.p_move(&Some((-diff_y) as u32));
    }
}

#[contractimpl]
impl Solution {
    pub fn solve(env: Env, engine_id: BytesN<32>) {
        let engine = GameEngine::new(&env, &engine_id);
        let mut my_pos = Point(8, 8);
        let mut points = 0;

        while points < 100 {
            let map = engine.get_map();
            // Try to first harvest fuel, and after that shoot an asteroid
            let mut n = 1;
            for result in map.iter() {
                let (pos, elemtype) = result.unwrap();
                if pos.0 >= my_pos.0 {
                    if (elemtype == engine::MapElement::FuelPod && n == 1)
                        || (elemtype == engine::MapElement::Asteroid && n == 2)
                    {
                        moveby(&engine, pos.0 - my_pos.0, pos.1 - my_pos.1);
                        my_pos = pos.clone();
                        if elemtype == engine::MapElement::FuelPod {
                            engine.p_harvest();
                        } else {
                            engine.p_shoot();
                            points += 1;
                        }

                        n += 1;
                    }
                }
            }
            // Move to the start of the next galaxy
            moveby(&engine, 17 - (my_pos.0 % 17), 0);
            my_pos.0 += 17 - (my_pos.0 % 17);
        }
    }
}

Getting below 1,000 bytes by removing map.iter()

By this time I had started more closely inspecting the output WASM. I discovered a tool called wasm-objdump and saw this block in the output of the previous solution:

Import[11]:
 - func[0] sig=0 <v._> <- v._
 - func[1] sig=1 <v.6> <- v.6
 - func[2] sig=2 <d._> <- d._
 - func[3] sig=0 <b.8> <- b.8
 - func[4] sig=0 <m.7> <- m.7
 - func[5] sig=1 <m.1> <- m.1
 - func[6] sig=1 <m.2> <- m.2
 - func[7] sig=0 <v.3> <- v.3
 - func[8] sig=1 <v.1> <- v.1
 - func[9] sig=0 <v.8> <- v.8
 - func[10] sig=2 <v.C> <- v.C

These imported functions by the wasm are low-level Soroban functions to mostly deal with maps and vectors (if you’re interested, the encoding is defined in this JSON file).

I thought that if the solution only used vectors, I could save a number of those imports.

After a number of iterations, I reduced the code to the following solution:

#[contractimpl]
impl Solution {
    pub fn solve(env: Env, engine_id: BytesN<32>) {
        let engine = GameEngine::new(&env, &engine_id);
        let mut my_pos = Point(8, 8);
        while my_pos.0 < 900 {
            let map = engine.get_map();
            for y in 0..17 {
                if let Some(elem_type) = map.get(Point(my_pos.0, y)) {
                    let fuel = elem_type.unwrap_optimized() == engine::MapElement::FuelPod;
                    if (my_pos.0 % 3) == 0 || fuel {
                        if y != my_pos.1 {
                            let dy = if y > my_pos.1 {
                                engine.p_turn(&engine::Direction::Up);
                                1
                            } else {
                                engine.p_turn(&engine::Direction::Down);
                                -1
                            };
                            while y != my_pos.1 {
                                engine.p_move(&None);
                                my_pos.1 += dy;
                            }
                        }
                        if fuel { engine.p_harvest() } else { engine.p_shoot() }
                    }
                }
            }
            engine.p_turn(&engine::Direction::Right);
            engine.p_move(&None);
            my_pos.0 += 1;
        }
    }
}

This solution reduced the WASM file to 853 bytes. Note that we’re trading bytes for very inefficient code. This solution moves to the right step by step and for every column of the map, it does Soroban map query calls for every y coordinate from 0 to 17. It then goes to harvest any fuel that it encounters and shoots asteroids with a 1 out of 3 probability (shooting them all would run out of fuel).

To avoid calling p_points(), the solution just loops until we reach an x-value of 900 which gets us enough asteroids.

Switching to preprogrammed paths

At this moment I started looking into encoding one fixed path, as the random seed that determines where asteroids and fuel pods are is given in advance. I wrote all asteroids and fuel pod coordinates between (-2500, -2500) and (2500,2500) to a text file and started writing programs to analyze paths through them in Kotlin, my preferred programming language.

I first tried the following ‘command’ scheme. Every byte has one bit which is whether we should harvest fuel or shoot an asteroid, 3 bits for how far we should move up (so that’s 0 to 7 squares), and 4 bits for how far we should move right (0 to 16). I managed to find a 158-step (so 158 bytes) path that manages to shoot 100 asteroids:

#[contractimpl]
impl Solution {
    pub fn solve(env: Env, engine_id: BytesN<32>) {
        let engine = GameEngine::new(&env, &engine_id);
        const DATA: &[u8] = &[
            0x9b, 0x8f, 0x8f, 0xbc, 0xdd, 0xed, 0x31, 0x77, 0x97, 0x8f, 0x82, 0x8f, 0xea, 0xfd,
            0x02, 0x42, 0x47, 0xbe, 0x21, 0x3d, 0xa5, 0x02, 0x4c, 0x26, 0x8f, 0xa6, 0x33, 0x2a,
            0xf0, 0x51, 0x14, 0x53, 0x24, 0x06, 0xe1, 0x13, 0x70, 0x79, 0x83, 0x8f, 0x82, 0x8f,
            0x82, 0x8f, 0x8d, 0xbb, 0x25, 0x11, 0x97, 0x08, 0x73, 0x27, 0xec, 0x7e, 0x32, 0xca,
            0x2c, 0x1c, 0x84, 0x8f, 0x82, 0x13, 0x35, 0x4c, 0xab, 0x41, 0x53, 0x21, 0xbe, 0x61,
            0x12, 0x33, 0xac, 0x37, 0x30, 0x47, 0x28, 0xe4, 0x13, 0x30, 0x0c, 0xc7, 0x16, 0x0f,
            0x4c, 0xe9, 0x27, 0x31, 0xa4, 0xe5, 0x0d, 0x30, 0x22, 0x7e, 0x9c, 0x13, 0x52, 0x8f,
            0xb4, 0x53, 0x72, 0x8a, 0x8f, 0x8b, 0x17, 0xdf, 0x2b, 0x31, 0x60, 0x9c, 0xd3, 0x34,
            0x74, 0x45, 0x11, 0x17, 0x47, 0xbb, 0x35, 0x12, 0x76, 0xd9, 0x9e, 0x02, 0x65, 0xab,
            0x56, 0xbd, 0x64, 0xa9, 0xa2, 0x66, 0x50, 0x4a, 0x74, 0x40, 0x35, 0x8b, 0x8f, 0x82,
            0x8f, 0x84, 0x93, 0x33, 0x6e, 0x67, 0xc0, 0x24, 0x63, 0x14, 0x23, 0x83, 0x65, 0x20,
            0x31, 0xc8, 0x71, 0x19,
        ];
        for value in DATA.iter() {
            engine.p_turn(&engine::Direction::Up);
            engine.p_move(&Some(((value >> 4) & 0x07) as u32));
            engine.p_turn(&engine::Direction::Right);
            engine.p_move(&Some((value & 0x0F) as u32));
            if value & 0x80 == 0x80 {
                engine.p_harvest()
            } else {
                engine.p_shoot()
            }
        }
    }
}

This step reduced the WASM file to 726 bytes.

Getting rid of the shoot/harvest bit

The two ‘actions’, shoot and harvest, differ quite a bit. Shooting takes 5 units of fuel, but harvesting doesn’t cost any fuel. Also, moving costs 2 fuel units per square moved, regardless of whether we make a big step of N units at once, or call move(1) N times. This means we can just keep doing 1-square steps and calling p_harvest() at every square we visit.

Harvesting every square we visit makes it unnecessary to ‘plan’ a visit to a fuel pod; the plan can focus on shooting asteroids while making sure there are fuel pods on the squares visited on the way.

This allowed us to more efficiently encode our path:

• 4 bits Y: move up by Y squares, while harvesting fuel on every step and shoot at the end.
• 4 bits X: move right by X squares, while harvesting and shoot at the end.

When lucky, we can shoot 2 asteroids for every byte (occasionally we probably shoot into the void, but that’s OK), and we just need to make sure that the path leads over enough fuel pods. There’s a path of 53 bytes that works and this led to the following solution:

fn turn_move_shoot(engine: &engine::Client, direction: &engine::Direction, count: u8) {
    engine.p_turn(direction);
    for _ in 0..count {
        engine.p_move(&None);
        engine.p_harvest();
    }
    engine.p_shoot();
}

#[contractimpl]
impl Solution {
    pub fn solve(env: Env, engine_id: BytesN<32>) {
        let engine = GameEngine::new(&env, &engine_id);
        const DATA: &[u8] = &[
            29, 141, 179, 17, 181, 159, 100, 111, 44, 144, 139, 180, 201, 201, 247, 167, 219, 88,
            56, 104, 221, 187, 189, 47, 138, 195, 227, 148, 56, 239, 154, 114, 221, 36, 75, 229,
            152, 20, 97, 228, 93, 97, 165, 47, 86, 102, 203, 17, 110, 90, 169, 158, 120,
        ]; 
        for value in DATA.iter() {
            turn_move_shoot(&engine, &engine::Direction::Up, (value >> 4) & 0x0F);
            turn_move_shoot(&engine, &engine::Direction::Right, value & 0x0F);
        }
    }
}

The more efficient encoding reduced the WASM file to 640 bytes.

Encoding 16 moves and shoots in every byte

Now that I had 2 moves & shoots per byte, I tried getting more out of every byte. First I went with 4 moves & shoots per byte by right-shifting the value by 2 for every step. With various schemes it got harder and harder to find a path that actually crosses enough fuel pods, but I managed to make every byte encode 16 moves & shoots, and then 25 bytes are enough to encode a path that ends up shooting (more than) 100 asteroids. (It’s quite inefficient, it shoots 25 * 16 = 400 times, so it frequently misses).

I also switched to moving left & up instead of right & up because the RawVal encoding “Left” is one byte shorter than the one encoding “Right”.

This solution reduced the WASM file to 511 bytes:

#[contractimpl]
impl Solution {
    pub fn solve(env: Env, engine_id: BytesN<32>) {
        let engine = GameEngine::new(&env, &engine_id);
        const DATA: &[u8] = &[
            14, 65, 100, 169, 79, 55, 50, 216, 131, 16, 252, 148, 54, 143, 22, 95, 200, 33, 69, 5,
            45, 106, 4, 209, 192,
        ];

        for i in 0..16 * DATA.len() {
            engine.p_turn(if (i & 1) == 1 {
                &engine::Direction::Left
            } else {
                &engine::Direction::Up
            });
            let value = (DATA[i / 16] >> (i % 8)) & 0xf;
            for _ in 0..(value + 2) {
                engine.p_move(&Some(1));
                engine.p_harvest();
            }
            engine.p_shoot();
        }
    }
}

Removing Soroban SDK error checking

I then looked into the decompiled WASM of the above solution. I noticed a lot of code dedicated to error-checking the result of every contract call. I experimented with removing this in a custom build of the Soroban SDK, but found it easier to just convert my solution to C that I could compile with the wasi-sdk.

That solution was as follows:

#define u64 unsigned long long

__attribute__((import_module("d"), import_name("_"))) u64 call_contract(u64 a, u64 b, u64 c);
__attribute__((import_module("v"), import_name("_"))) u64 create_vector(u64 size_hint);
__attribute__((import_module("v"), import_name("6"))) u64 vec_push(u64 vector_id, u64 value);

u64 v(u64 dat) {
  return vec_push(create_vector(5), dat);
}
u64 turn(u64 engine_id, u64 num) {
  return call_contract(engine_id, 911044435769L, v(v(num)));
}
void move(u64 engine_id, int cnt, u64 symbol) {
  turn(engine_id, symbol);
  u64 vec;
  while (cnt)
  {
    call_contract(engine_id, 911014686377L, v((1 << 4) + 1));
    call_contract(engine_id, 238811294867317657L, vec = create_vector(5));
    cnt--;
  }
  call_contract(engine_id, 58306520732569L, vec);
}

__attribute__((export_name("solve")))
u64 solve(u64 engine_id) {
  unsigned char raw_data[] = {
      14, 65, 100, 169, 79, 55, 50, 216, 131, 16, 252, 148, 54, 143, 22, 95, 200, 33, 69, 5, 45, 106, 4, 209, 192
  };
  const u64 left_symbol = 99266457L;
  const u64 up_symbol = 33625;
  for (int i = 0; i < 16 * sizeof(raw_data) / sizeof(raw_data[0]); i++) {
    int value = raw_data[i / 16] >> ((i % 8));
    move(engine_id, (value & 0xf) + 2, (((i)&1) ? left_symbol : up_symbol));
  }
  return 5;
}

This solution generates a WASM file that I could further post-process with wasm-dis and wasm-as to throw out a number of unneeded fields and exports, such as __wasm_call_ctors and export "memory". For the output to actually work, the WASM file also needed to be extended with custom contractenvmetav0 and contractspecv0 blocks (that the Rust Soroban SDK adds automatically). That final post-processed WASM was 363 bytes for me and that was my submission for the “Out of Control” leaderboard.

Dropping the contractspecv0 block

After the “Out of Control” event was over, I learned that the contractspecv0 block wasn’t needed for solutions to be run by the online contest environment (the provided local test methods however don’t accept WASM files that don’t have it). Dropping that block saves another 65 bytes, which brings the final file size to 298 bytes.