If you somehow got here and have no idea what's going on, it all started with this video from stand-up maths.
To build:
- Make sure you have dotnet 7.0
- Update the file paths in Util.cs
- Run the following where
<root>is the root path of the repo and<RID>is your platform (e.g. win-x64, linux-x64).
cd <root>/Wordle5x5CSharp
dotnet publish -r <RID> -c Release
To test, make sure you use the generated code in the publish folder! Assuming you are using hyperfine, run:
hyperfine bin/Release/net7.0/win-x64/publish/Wordle5x5CSharp.exe
!!! IMPORTANT !!!
Don't just run dotnet build --configuration Release! Because the benchmark only tests a single iteration, this does not give .NET enough time to apply JIT optimizations so we need to use ahead-of-time compiliation to get decent results. This makes an almost 5x performance difference on my own PC. For more information, see here.
One other strange performance quirk I've noticed is that when running on Linux in a VM on VirtualBox, there is a noticeable slowdown based on the size of the console window. For best results, please switch to a console only TTY if running on Linux (ctrl + alt + F3 on Ubuntu).
This implementation just steals a bunch of good ideas from other smarter people and doesn't really have any creative ideas of its own. I just wanted to see how a C# version would compare. You can take a look at this spreadsheet here to see how other people solved it. At a high level, this code is probably closest to this Java version. The optimizations used in this implementation are:
- Graph representation
- Bitwise word representation
- Anagram filtering
- Words indexed by contained characters
- Uses character frequency
- Pruning character sets that were already tried
- Recursive
- Parallelized
- Knuth's Algorithm X (I don't even know what this is)