Creating a C/C++ implementation

[DallasMcNeil]

Hi everyone,

I am considering creating a pure C/C++ port of tnoodle for unofficial use. As I see it, Java libraries are difficult to integrate into other applications. Mainly, relying on a JVM to be installed, and other challenges calling Java code from other languages. Years ago, when I creating a timer, I used tnoodle-js. But this seems to have fallen into obscurity and is no longer available. Currently, I can't find any suitable javascript or C implementations of tnoodle that can be readily adopted by application developers.

A C implementation and interface can be integrated in a wide range of scenarios, without the need for Java to be installed. It's fair to say that C can be run just about anywhere and be called from nearly anything. For example, C functions can be interfaced in scripting languages such as Python and Lua. C can be compiled to web assembly and can be used in web apps. Ideally, I'd like to provide all functionality in this port, and regression test against tnoodle for accuracy. That way, application developers can more easily integrate tnoodle scrambles into their work.

This is only a project I'm thinking of undertaking, but I was wondering if the software team was aware of any existing C/javascript implementations, or any known hurdles in doing this? I understand maintaining another version isn't ideal. Is tnoodle-lib development relatively static now, or are there upcoming changes? Looking forward to hearing your thoughts. :)

Thanks
Dallas

[gregorbg]

Hello Dallas,

Thank you for bringing up this discussion, it's quite an interesting debate. Unfortunately, it's also quite a big can of worms in terms of scope and implications for the WCA software and competition workflow. I'll try to structure my thoughts a bit through the use of sections.

Current state of TNoodle

History

The existing Java library is essentially still an exact copy of the scrambling part of a Java timer called CalCubeTimer (or CCT for short) written by Jeremy et al. in the very early days of speedcubing. CCT was a Java timer because of platform interoperability, and its scrambling portion just "happened to be adapted" by the WCA at a time when things were much, much less formal than nowadays.

What about TNoodle-JS

TNoodle-JS in particular was a side-project that was made possible by using GWT to cross-compile Java code into JavaScript. Over time, it became increasingly hard to maintain because GWT itself is only very sporadically maintained and seems to be on the brink of becoming abandonware, so it wasn't worth WST's time.

Offline mode and compatibility

Another big reason why we decided to keep stuff in Java even when doing a rewrite was (yet again) OS interoperability. Delegates use Windows, macOS, Chromebooks and even sometimes Linux alike, and we don't want to go through the pain of providing binary builds for all of these architectures let alone teaching non-IT-friendly Delegates how to discern between them. Having a Java codebase also allows us to run an offline webapp with relative ease, which continues to be essential for competitions where the venue has bad or no Internet signal even in 2022. (Yes, happens.)

Implications of a rewrite

Historic developments

On a high level, doing a rewrite would probably only seem to replace the scrambling core, i.e. "redoing the function that takes a puzzle name as input and returns a scramble string as output". In reality, TNoodle-LIB contains a lot of small quirks and fixes, some of which we learned about "the hard way" (i.e. by TNoodle being responsible for incidents at competitions because the scramble distribution was wrong or filtering was too easy). Examples include, but are not limited to:

• Skewb scrambler producing states that were too easy
• 2x2 not computing optimal solutions optimally
• FMC scrambles have grown to use R' U' F paddings, which are more complicated than just "compute a regular scramble and prepend three moves"
• BLD scrambles use rotations or block moves to break puzzle orientation

These examples are mostly documented only in the memories of the people who went through the pain of fixing them, so considering all of the subtleties will be hard when attacking a full rewrite.

Optimal solvers

The general approach of solving twisty puzzles by means of a "standard" state space search (which you can of course apply all sorts of crazy optimisations to, hence the quotes) has its limitations or drawbacks for some puzzles. TNoodle uses optimised solvers for

• The "kids package", i.e. 2x2, Pyra, Skewb
• 3x3 via the famous Kociemba Two-Phase algorithm
• 4x4 via Threephase, an adaptation of Two-Phase for bigger cubes
• Square-1 via a custom solver

Most of these optimal solvers were implemented by Chen Shuang, who to this day probably remains the only person on this planet to fully understand their code. Re-implementing them in C(++) will require a significant amount of effort because the code is too complex to "just copy/paste".

Perspectives for a rewrite

If I haven't scared you off until now, I'd like to end this wall of text by stating that a "pure" rewrite of the TNoodle engine is probably not the right thing to do, in that it will again create an isolated, stand-alone component that has to be maintained by the WST. The good news is that there are pieces of software out there which come pretty close to doing what we want them to do. From the top of my head, there's

• https://github.com/josef-jelinek/acube (Although that is again written in Java)
• https://github.com/cubing/twsearch

Ideally, we would want to contribute to a project like twsearch to fine-tune it to a degree where it's usable for TNoodle. It will benefit the whole cubing community, would relieve the WST from the burden of maintaining its own scrambler implementations (and "only" maintaining the frontend for TNoodle that Delegates can download, which is enough work already) and would open the doors for more people to contribute, document and test our scrambler as well as use it in non-official hobby projects.

One final possible alternative would be a rewrite in Kotlin Multiplatform, which can compile to C/machine code, Java and JS at the same time. It's basically a type-safe version of writing straight C code and can probably reach the same order of magnitude in terms of runtime efficiency, but we would be back at square one in terms of "doing our own thing".

Hope this helps! 😄

[DallasMcNeil]

Hi Gregor,

Thanks for your detailed reply and sharing some context around tnoodle-lib. I can see this is a more complicated topic than I first thought.

I think for the reasons you've listed, we wouldn't want to move away from using the JVM for tnoodle-lib officially. Considering the range of environments it needs to run in and "just work". I personally don't like Java/JVM (hence why I'm interested in a rewrite) but it gets the job done well. A Kotlin rewrite could be considered as you suggested, which would allow for native libraries and JS. If we were completely happy with tnoodle-lib, I'd lean towards that as a project. It solves the non-official integration problems and still works for tnoodle. I'm personally not too interested in that conversion project, since I don't have any experience with Kotlin, but it's a good idea. But that's if we were happy with tnoodle-lib.

It seems the much larger issue is who maintains our scramble library. It's far from ideal to have code that only the author can understand. Correct me if I'm wrong, but does any maintainer know how the depths of tnoodle-lib works? As you said, porting code line by line to C++/Kotlin, doesn't fix that fundamental problem, and we are still left with something difficult to maintain and evolve if needed. It could be best to take some of the other scramble programs you shared, flesh out, and adopt them instead. But if it all works for now, it might be best not to rock the boat and keep it as is, until some technology makes it easier, or the WCA sees a need for a new scramble library.

[gregorbg]

Ideally, we do want to move away from tnoodle-lib officially, but that's actually a very long and winding road. You asked whether there's a (current) maintainer who understands the depths of how tnoodle-lib works, and the answer is actually No. I don't think there is one single person on the planet who knows all of the intricacies of this codebase, which just serves to show how important a rewrite would actually be.

Taking a step back towards the larger picture, I've lost count how many times people asked me how they can implement TNoodle into their projects to get "WCA-grade scrambles". The common misconception seems to be that because we sanction our own scrambling library, the other libraries out there are not "good enough" for the WCA. The simple truth is that we're historically stuck with this big hunk of code that nobody on the current Software Team fully understands and platform compatibility requirements make it hard to just move away. Other libraries like the mark2 scrambler for JS probably provide even more efficient scrambles because they're more actively maintained; they only lack specific features like BLD random orientation.

With all that in mind, I'd still argue that there are two paths moving forward:

1. Re-implementing our own thing in Kotlin, which can emit Native, JS and JVM code.
2. Adapting twsearch above. using the WASM output as embedded dependency to provide platform-independent Java bundles.

Either approach will require us to understand the existing optimal solvers, namely min2phase, threephase and sq12phase. They would have to be documented on a very low level, i.e. explain what they do in a mathematical fashion as well as keep an eye on coding tricks and quirks that are implemented there. In addition, we also need to understand the min2phase interfaces used to provide features such as "searching only for R U F' solutions" or "breaking orientation at the end of the scramble".

Would you be interested in taking on such a task and "exploring" the codebase to understand and document it? You can look at the code in the current subfolders for the optimal solvers (names as written above) to get an impression of what this work would entail.

[gregorbg]

On second thought, min2phase is already quite well-documented in the sense that "there are enough people on planet earth who know what 2-phase does". There's also https://github.com/cs0x7f/min2phase/blob/master/Algorithm.md which details our min2phase fork by Chen Shuang.

We would still have to kinda figure out what threephase and sq12phase do, at the very least on a high level (i.e. mathematical reasoning).

[gregorbg]

Yet another possible area where you could contribute: Comb through the GitHub commit history and find all "Whoops, this went terribly wrong at competitions" commits. Try to find out what happened, how it was fixed and whether we should pay attention to the fix (for example, if a specific optimal solver like Skewb was just mathematically wrong at one point, we don't need to consider it because a generic state space search won't have these kinds of issues if it's well-tested.)

[DallasMcNeil]

I agree, there seems to be a large focus on 'WCA-grade" scrambles. I was specifically asked to use tnoodle scrambles in my timer, even though I used mark2, from memory.

I think adapting an existing project would be best. twsearch, mark2 or it's evolution cubing.js https://github.com/cubing/cubing.js seem like well fleshed out and actively supported options. JS is universal and a local web app could be used in future for tnoodle, or porting the algorithms to another language like Kotlin to support JVM and other platforms. It would be a matter of gathering the requirements for tnoodle (like all the competition incidents and hotfixes added) and applying them to an existing library/or composition of libraries.

My maths knowledge is not up to scratch to reverse engineer any scramble algorithms, but hopefully the authors of any scramble libraries could help document their work. I would be happy to look through the commit history and find the hotfixes and document them. That gives us the key requirements for a future replacement, if not now, then one day.