I'm playing a game where an Enigma M3 cipher is being used. It isn't meant to be played this way, but I'm finding it fun. For the current clue, the plug board for the cipher isn't known.
A plug board string looks like this: "bq cr di ej kw mt os px uz gh"
Here are the rules for this particular plug board:
I'm trying to generate all possible combinations in javascript but struggling. Or rather, I'm struggling to do this in the most efficient way.
Since I know the answer-plug-board is likely in English, it's probably pretty short; it's difficult to come up with long phrases under the above constraint. So it's better to try shorter answers first.
What's the most efficient algorithm to do this in javascript?
The number of results will quickly become astronomical, but if the purpose is to just start generating them and keep going for as long as time allows, then a generator seems a useful tool here.
To keep track which letters have already been used, you could use a bit map (with 26 bits) where a 1 bit indicates the letter is still unused.
Here is a possible implementation:
// Produce pairings of an exact (even) size
function* generatePairingsOfSize(size, alphabet) {
if (size == 0) return yield "";
// Visit each 1-bit (which represents an available letter)
for (let bits1 = alphabet; bits1; bits1 &= bits1 - 1) {
const bit1 = bits1 & -bits1; // This is the bit
for (let bits2 = alphabet ^ bit1; bits2; bits2 &= bits2 - 1) {
const bit2 = bits2 & -bits2; // ...and a second, distinct bit
// Get the character pair that is represented by these two bits:
const s = String.fromCharCode(97 + 31 - Math.clz32(bit1)) + String.fromCharCode(97 + 31 - Math.clz32(bit2));
// Use recursion to extend smaller strings with the above pair
for (const result of generatePairingsOfSize(size-2, alphabet ^ bit1 ^ bit2)) {
yield s + " " + result;
}
}
}
}
// Produce pairings of all possible sizes (theoretical maximum is 26)
function* generatePairings() {
const alphabet = (1 << 26) - 1; // A 1-bit per letter of the alphabet
for (let size = 0; size <= 26; size += 2) {
yield* generatePairingsOfSize(size, alphabet);
}
}
// Get an iterator:
const iter = generatePairings();
// Demo: Using a timer to see the progress:
function loop () {
const {done, value} = iter.next();
if (done) return;
console.log(value);
setTimeout(loop);
}
loop();
If you are sure (not just "likely") that the combination should be an English word from a given dictionary, then just iterate that dictionary sorted by length, omitting words that have duplicate letters. If it can be a combination of English words, then store combinations of words (that don't exceed the maximum length) by their combined length, and iterate those.