Wasm Builders 🧱

Bernard Kolobara
Bernard Kolobara

Posted on • Updated on

Advent of Code '21 in hand written WebAssembly: Day 2

#learning #wat

You can find the 2nd Day challenges on the Advent of Code website.

Part 1

The first problem requires us to keep track of x & y coordinates while looping through commands.

Similar to Day 1, we first need to adjust a bit the input to place it into the WebAssembly memory. This time the transformations are a bit simpler because all of the numbers are single digit and fit into one byte, so we don't need to worry about little/big endians when encoding them. The command can be transformed to one letter:

forward 5\n            f\05
down 5\n               d\05
forward 8\n     ->     f\08
up 3\n                 u\03
down 8\n               d\08
forward 2\n            f\02
Enter fullscreen mode Exit fullscreen mode

Inside of our module the input will look like this:

(module
  (memory 1)
  (data (i32.const 0) "f\05d\05f\08u\03d\08f\02"))
Enter fullscreen mode Exit fullscreen mode

Let's implement first a loop through all the values:

;; ...
  (func (export "part_1")
    (local $i i32)
    (local $command i32)
    (local $value i32)

    (block $loop_break
      (loop $loop
        ;; Load value at the memory location $i into $command
        local.get $i
        ;; Load 8 bytes (unsigned) into an i32 stack slot
        i32.load8_u
        local.set $command
        ;; Load value at the memory location $i+1 into $value
        local.get $i
        i32.const 1
        i32.add
        i32.load8_u
        local.set $value

        ;; Compare $command to zero & break loop if true
        local.get $command
        i32.const 0
        i32.eq
        br_if $loop_break

        ;; Increment $i by 2
        local.get $i
        i32.const 2
        i32.add
        local.set $i
        br $loop))
;; ...
Enter fullscreen mode Exit fullscreen mode

$i is used to store a pointer to the memory location of the input we are currently processing. We are iterating in 2 byte steps, the first byte of the command is the direction, the second the value. Once we hit a memory location with the value 0 for $command we stop.

The only thing we still need to do is to introduce two local variables $x & $y that we update on each iteration depending on the command letter.

;; ..
  (func (export "part_1") (result i32)
    ;; ..
    (local $x i32)
    (local $y i32)

    (block $loop_break
      (loop $loop
        ;; ..

        ;; Load the command onto the stack
        local.get $command
        ;; If it's the letter f (utf8 value 102) update $y
        i32.const 102
        i32.eq
        (if (then
          ;; Add value to $y
          local.get $y
          local.get $value
          i32.add
          local.set $y))

        ;; Load the command onto the stack
        local.get $command
        ;; If it's the letter d (utf8 value 100) update $x
        i32.const 100
        i32.eq
        (if (then
          ;; Add value to $x
          local.get $x
          local.get $value
          i32.add
          local.set $x))

        ;; Load the command onto the stack
        local.get $command
        ;; If it's the letter u (utf8 value 117) update $x
        i32.const 117
        i32.eq
        (if (then
          ;; Subtract value from $x
          local.get $x
          local.get $value
          i32.sub
          local.set $x))

        ;; ...
        br $loop))

      ;; Multiply $x by $y
      local.get $x
      local.get $y
      i32.mul)
;; ...
Enter fullscreen mode Exit fullscreen mode

That's it! 🎉

Part 2

For the second part we just need to introduce a new local $aim and slightly adjust our calculation in each if branch:

;; ...
  (func (export "part_2") (result i32)
    ; ...
    (local $aim i32)
    (local $x i32)
    (local $y i32)

    (block $loop_break
      (loop $loop
        ;; ...
        ;; Load the command onto the stack
        local.get $command
        ;; If it's the letter f (utf8 value 102) update $y
        i32.const 102
        i32.eq
        (if (then
          ;; Add value to $x
          local.get $x
          local.get $value
          i32.add
          local.set $x
          ;; Add value * $aim to $y
          local.get $y
          local.get $aim
          local.get $value
          i32.mul
          i32.add
          local.set $y
          ))

        ;; Load the command onto the stack
        local.get $command
        ;; If it's the letter d (utf8 value 100) update $x
        i32.const 100
        i32.eq
        (if (then
          ;; Add value to $aim
          local.get $aim
          local.get $value
          i32.add
          local.set $aim))

        ;; Load the command onto the stack
        local.get $command
        ;; If it's the letter u (utf8 value 117) update $x
        i32.const 117
        i32.eq
        (if (then
          ;; Subtract value from $aim
          local.get $aim
          local.get $value
          i32.sub
          local.set $aim))
;; ...
Enter fullscreen mode Exit fullscreen mode

For me the solution was 2044620088, what's awfully close to the maximum value you can store inside of an i32 and I got worried for a second that we have overflown our variable by multiplying too big numbers, but in the end the answer was accepted. And I didn't need to switch to i64.

WebAssembly lets you only execute an i64.mul operation if both operands on the stack are i64. This means that we would need to first convert our 2 last values to i64 ones with i64.extend_i32_u:

;; ...
  (func (export "part_2") (result i64)
    ;; ...
      ;; Multiply $x by $y
      local.get $x
      i64.extend_i32_u
      local.get $y
      i64.extend_i32_u
      i64.mul)
;; ...
Enter fullscreen mode Exit fullscreen mode

This wasn't that bad. Let's try Day 3.

You can check out the complete solutions on GitHub.

Latest comments (0)