Welcome to day 3! Let's get started.
You can read the full problem statement here.
Let's start out once again by transforming the input into hexadecimal values so we can embed them inside of the module's memory:
00100 04 11110 1e 10110 -> 16 10111 17 10101 15 ...
Looking the the input file, the numbers have up to 12 bits. This means that we need to reserver at least 2 bytes (16 bits) to fit the input. Because we deal with more than 1 byte, we need to encode the values as little endian inside the WebAssembly memory. This is how they are represented inside of WAT:
(module (memory 1) (data (i32.const 0) "\04\00\1e\00\16\00..."))
We need to count all of the bits in each column. To keep track of the count we could introduce local variables, but to avoid limiting our solution to an exact number of bits (local variables) we can store the count inside of the memory.
Let's move our input 16 * 4 bytes inside the memory and leave the memory locations from 0 to 64 free so we can store up to 16
i32 values inside of them.
(module (memory 1) (data (i32.const 64) "\04\00\1e\00\16\00..."))
To make our life a bit easier, let's create also a few helper functions that can increment the location of a particular bit or give us back the count:
;; ... ;; Load i32 value at position 4 * $bit in memory, add 1 ;; to it and store the value back at the same position. (func $inc (param $bit i32) (local $location i32) local.get $bit i32.const 4 i32.mul local.tee $location local.get $location i32.load i32.const 1 i32.add i32.store) ;; Return i32 value at position 4 * $bit in memory. (func $count (param $bit i32) (result i32) local.get $bit i32.const 4 i32.mul i32.load) ;; ...
local.teeinstruction is similar to
local.set. It sets the value of a local, but it doesn't remove it from the stack. If it's followed by
local.getit simulates a "duplicate top of the stack" operation. WebAssembly doesn't have a dedicated instruction to duplicate the top value on the stack, but there is one for dropping the top value:
The next step is to loop through all values. This code is similar to the previous two days. The only difference is that we start looping from memory position 64 instead of 0. Because we reserve the first 64 bytes for counters:
;; ... (func (export "part_1") (local $i i32) (local $value i32) ;; Start looping from position 64 in memory i32.const 64 local.set $i (block $loop_break (loop $loop ;; increase $i by 2 (bytes) local.get $i i32.const 2 i32.add local.tee $i ;; Load the memory location at $i i32.load16_u local.tee $value ;; Check if it's equal 0 (reached end of the input) i32.const 0 i32.eq br_if $loop_break br $loop))) ;; ...
We stop the loop as soon as we run into a memory location with the value 0. This could be an issue if our input actually contained values that are 0, but luckily it doesn't and we don't need to deal for now with this edge case.
The recently explained instruction
local.tee is used again to temporarily store the value inside of the
The next step is to loop again through all bits (16 times) for each
;; ... (func (export "part_1") (local $i i32) (local $j i32) ;; ... (block $loop_break (loop $loop ;; ... br_if $loop_break ;; Reset $j to 0 i32.const 0 local.set $j (block $loop_bits_break (loop $loop_bits ;; increase $j by 1 and stop when 16 is reached local.get $j i32.const 1 i32.add local.tee $j i32.const 16 i32.eq br_if $loop_bits_break br $loop_bits)) br $loop))) ;; ...
I spent a lot of time on this loop because I kept running into an infinite loop scenario. The issue was that I forgot resetting
$j to 0 before each loop. With the introduction of multiple locals it gets really hard to keep a mental model of the whole application in your head and at this low level it's super easy to run into such issues. I generally try to write the code in small increments and test my assumptions by introducing helper local variables to print out some information deeply nested into the program structure. It may help to use a "real" debugger once the problems get more complicated.
Now let's count each bit:
;; ... ;; Reset $j to 0 i32.const 0 local.set $j (block $loop_bits_break (loop $loop_bits ;; If bit $j is set inside of $value ;; increment the counter i32.const 1 local.get $j i32.shl local.get $value i32.and i32.const 0 i32.ne (if (then local.get $j call $inc)) ;; increase $j by 1 and stop when 16 is reached ;; ...
To check if a bit
$j is set inside of
$value we first create a number with just this bit set using the
i32.shl (shift left) instruction.
Let's look at an example how
i32.const 1 ;; 0...00001 i32.const 4 i32.shl ;; moves all bits inside of 1 (2nd value ;; on the stack) to the left for 4 places ;; (the top most value on the stack). ;; This leaves only 0...10000 (16) on the stack.
If we now perform a binary
and operation between
$value and the left shifted number, the result is going to be either:
- 0 if the bit is not set inside of
- not 0 if it is set
If it's not 0, we increment the counter for the bit
$j. For this we can use the
call instruction and the earlier defined
Now that we know how many times each bit is repeated, we just need to divide each counter with the number of iterations (
($i - 64 offset) / 4 bytes) to determine if the bit 1 shows up more times than 0 (> 0.5). If yes, we add this bit to the local
Epsilon can be calculated as
$gamma xor 0b1111.... The binary value needs to be adjusted, depending how many bits are present in the input values. In the example we had 5 bits (decimal value of 31 => 11111). For the input file it was 12 bits for me (decimal value of 4095).
Here is the whole final loop:
;; ... ;; Reset $j to 0 i32.const 0 local.set $j (block $loop_bits_break (loop $loop_bits ;; If bit $j is set more times than the number ;; of iterations add it to $gamma. local.get $j call $count ;; Convert the value to a f32 f32.convert_i32_u ;; ($i - 64 offset) / 4 bytes local.get $i i32.const 64 i32.sub i32.const 2 i32.div_u f32.convert_i32_u f32.div ;; If the division is greater than 0.5 set the bit f32.const 0.5 f32.gt (if (then ;; Get a number with just the bit $j set i32.const 1 local.get $j i32.shl local.get $gamma i32.add local.set $gamma)) ;; Increase $j by 1 and stop when 16 is reached local.get $j i32.const 1 i32.add local.tee $j i32.const 16 i32.eq br_if $loop_bits_break br $loop_bits)) ;; Calculate epsilon local.get $gamma i32.const 31 ;; 32 -> 11111 i32.xor local.get $gamma i32.mul) ;; ...
We reuse the local
$j for the final loop. There are a few new instructions here, like
f32.convert_i32_u that converts an i32 value to a f32, so we can do floating point math. Most other operations, like
f32.gt behave similar to their
i32 counterpart, but work with the 32 bit floating point type.
That's it, we are done with the first part of day 3! 🎉
You can see the full code for the solution on GitHub.
As you probably noticed, it's getting fairly complicated to hand craft solutions in WebAssembly for the problems. It's starting to take away too much of my time and I will be declaring defeat for now 😊. I would gladly accept PRs if someone manages to solve any of the other days.
I hope you had as much fun following along as I had solving the problems in hand written WebAssembly. Until next time!