The search space is too large to enumerate.
A substitution key is a permutation of the alphabet, which makes exhaustive search impractical. The solver needed to search that space efficiently and score candidate plaintext without wasting time inside the hot loop.
What I owned
I rewrote the solver in C++17, structured the search as independent chains, and moved repeated scoring work out of the sampling loop.
- Metropolis-Hastings sampling with simulated annealing.
- Precomputed bigram counts and log probabilities.
- Independent parallel chains with shared best-result updates.
- CMake command-line tools for scrambling and deciphering text.
Key decisions
Keep chains independent
Each thread explores from its own state. The threads synchronize only when a chain finds a new best result.
Precompute the scoring model
Bigram probabilities are prepared before sampling so candidate evaluation can stay small and predictable.
How I tested it
- CMake builds the decipher and scramble command-line tools.
- Sample ciphertext and output files exercise known substitution ciphers.
- Parallel chains update a mutex-protected best result.
Built with: C++17, MCMC, Threads, CMake