Nothing is more doomed than a follow up to a blog post with “Part 1” in the title. It took over a year, but I was able to avoid this embarrassment and finally got around to part two.
This article compares and contrasts three implementations of the Sudoku board generator I wrote about previously. I outline a few differences between TypeScript, Rust, and C++ implementations. C++ and Rust were chosen because it’s relatively easy to build those for Web Assembly (will cover in a later post). And Typescript is serving as a performance baseline.
You can find the repositories here:
As outlined in my previous post, two major subtasks of generating the boards are: creating related nodes that represent board location, and filling the cells recursively.
Somewhat surprisingly, the Rust and C++ implementations were a little simpler than the TypeScript versions. The key difference between is the use of the support for user-defined types by standard library data structures and algorithms.
Set data structure ensures that no two equivalent values are contained within the set. So if we add a duplicate cell, it is ignored. TypeScript has a
C++ and Rust sets, by contrast, do allow for some customization. The C++ implementation accomplishes this by overloading the
< operators between two
The Rust implementation does this by applying some macros to the structs
Coord. It’s fairly simple to do and saves us a lot of additional work of sorting and filtering the arrays.
Another smaller difference in Rust and C++ favor is that being able to use
usize for the coordinates, in C++ and Rust respectively, made the use of
floor operation unnecessary. In TypeScript is use the
Number type which includes decimals, so the
Math.floor operation is required. The following snippets show how the top left block position is identified in the three implementations.
Filling the Board
All three implementations use the recursive algorithm outlined in the previous post. So the implementations are mostly the same. Rust is a bit different due to it’s more restrictive memory rules. Rust has unique restrictions on references and borrowing. These restrictions allow guarantees of memory safety without having a garbage collector and help prevent some classes of memory errors in multi-threaded programs.
The primary restriction with regards to filling our Sudoku board is that only one reference to a mutable value is allowed at any one time. This makes the recursive algorithm a little more complicated because we can’t pass a mutable reference to the recursive step.
In particular, the member cell.neighbors could not be accessed directly by the function
SudokuBoard::doFillCells Instead they needed to be cloned, fortunately, this is trivial.
Clone macro enables the
cell.neighbors vector to be cloned as a full collection. This makes the memory restrictions less honorous at a source code level, though figuring out this solution was a bit of a pain. In my opinion, the reference, ownership and borrowing rules represent the biggest obstacle for learning / working with Rust.
Having data structures and algorithms that support user-defined types also made filling the board a bit simpler. A sub-operation is figuring out what options are available for the current cell given the neighbor values. The TypeScript implementation, using
lodash, is a little unnatural.
It’s not too verbose, but it requires two separate operations to perform a set difference. First, all the neighbor values have to be sorted uniquely, and then the difference can be taken. The
lodash difference operation requires the elements to be in order, and unique. If there are duplicates, then there will be remaining instances.
In C++ and Rust versions are more straightforward.
The Rust version is easy to parse, while the C++ version might look a little funky if you are unfamiliar with the argument order of STL algorithm functions and iterators. However, both allow the desired operation to be expressed directly as set operations.
It would be possible to implement a set difference operation that worked as expected with TypeScript arrays, but that’s the point. These operations are part of the Rust and C++ standard library and have high-quality implementations.
Despite a more substantial history writing Typescript, I found it more straightforward to implement what I wanted in C++.
Set support for user-defined types, STL algorithms, and having more than a single number type allowed the program to be more expressive. The Rust implementation was a little frustrating due mostly to the most restrictive memory rules.