Implementation of the Tower of Hanoi problem using P5.js for animation and Rust compiled to WebAssembly (WASM).

In 2018, a professor at the Uni asked me to build a series of computer science games; he was looking for a very visual way to show students how the solution algorithms ofNP problems (like the Knapsack Problem, Tower of Hanoi, Tic-Tac-Toe, etc.) behave and grow with their inputs.

Tower of Hanoi is a good exercise when students are getting started with recursion and vectors. The pegs are usually fixed at 3, so it is easy to define the base case, and the only variable is the number of disks. It is worth noting that there are other more efficient approaches, such as The Binary solution or the Gray-code solution, but this was a Complexity course and we wanted to show how exponential time can break your computer while keeping it as minimal as possible.

Vanilla JS Implementation

There was only one design requirement: to show the animated solutions of the problems in a web browser. At that time I was familiar with HTML5 but not with any modern UI frameworks. Frankly, I couldn't imagine myself rendering objects from scratch in a plain HTML canvas. There had to be something out there that had already invented that wheel, and there was.

I foundP5.js, it is sort of the JS version ofProcessing and it has everything I was looking for, a complete API for rendering, painting images and text, calling DOM elements and much more.

The main core of the animation system was thedraw function provided by P5. It works as an infinite loop, so if we want to show the disks moving fromx1, y1 tox2, y2, we have to update the current positionx += speed y += speed where0 < speed < 120. There are two types of motion, vertical and horizontal. An example of the former is:

Note that therefreshCanvas function refreshes the canvas and redraws the towers filled by the disks, but not the one being animated.

You may wonder how the disks know where to move, do they move at the same time as the Hanoi calculations? That would be cool, but unfortunately they don't. We are limited by the recursive algorithm, so we have to wait until all calculations are done (until the call stack is empty).

Therefore, thedraw function constantly checks if the array of moves[towerFrom:towerTo, ...] generated byrecursiveHanoi is not empty. If it is, the animation starts.

recursiveHanoi did the job, but it was very inefficient: it couldn't handle more than 14 disks (16K steps). The root cause was not in the algorithm itself, but in its execution in the V8 interpreter. Anyway, the same recursive function in C++ could run perfectly for more than 20 disks (aprox 16M of steps). So, running compiled bytecode in the browser was clearly the next step.

wasm-pack

After four years, I found some time to pay that deb-tech (yes, quite a long time, eh). To make it fun I rewrote everything from scratch in SolidJS, which went smooth thanks to this amazing libraryp5js-wrapper. For WASM, C++ is still a good choice, but what about Rust? I did some research and foundwasm-pack. A few lines in thecargo.toml file and we were ready to generate compiled + ready to import bytecode!

Let's dive into the configuration:

• Thecrate-type is set to indicate that the crate will be compiled as a dynamic library:wasm-bindgen.
• gloo-utils andserde are included separately to avoid circular dependencies (history).

Once the configuration is ready, we runwasm-pack build -d wasm --no-typescript to compile. There is no advantage in generating ts files because we won't use those definitions since theget_moves function is gonna be called using a Web Worker.

Then, to make thewasm folder accessible to the solid app, we need to update thevite.config.js file following the recommended setup fromvite-plugin-wasm:

The compiled output is now accessible as follows:

But wait a second, we haven't talked about this function yet, and why do we need a Web Worker? Let's move on to the final implementation.

Hanoi Algorithm in Rust

The tricky part of writing WASM code is how to interact with the outside world (I/O operations). Fortunately, our function is quite small, its conditions are mapped as follows:

1. The function takes aNumber -> i32 argument: The number of disks.
2. The function returns an array of strings serialised by theserde_json crate (which allows you to convert a Rust data structure that implements theserde::Serialize trait to aserde_json::Value type, in this case aJsValue).

And that's it, inside the public fn, we can use regular Rust types likeVect.

Web Worker

As mentioned above, the number of disks is exponentially related to the number of steps required in the solution. 20 disks are about 1M, but 24 are more than 16M (which is quite a lot 😰). In fact, the execution time of the recursive function exceeds the Doherty threshold (300ms). So, it becomes mandatory to execute it inside a non-blocking thread, for which we can use the Web Workers API.

A new.js file must be created for the worker anywhere in thesrc folder.

Then, since the worker instance has nothing to do with thesolid component lifecycle, we can instance it outside.

Finally, when the user clicks on the play button, the async function is called:

In Summary

NP problems are highly CPU-intensive, andwasm-pack makes it easier to reduce the execution time. In addition, wrapping these operations in a Web Worker improves the user experience.

A picture is worth a thousand words: for 20 disks the Vanilla JS implementation takes more than312000ms, while Rust does it in under200ms (tested on a Macbook Air M2).

Vanilla JS	WASM (Rust)

Source code available on Github:

That's all I have for you today. Check out my websitehttps://sjdonado.de.

Feedback is more than welcome, drop me a line in the comments section 🙂.