Switch branches/tags
Nothing to show
Find file History
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Failed to load latest commit information.


/r/DailyProgrammer #188 Hard


I put quite a bit of work into this one. I saw others posting genetic algorithms, but every time I looked at their code I couldn't help but notice it wasn't genetic at all. Random variation without recombination is more of a random hill-climbing instead. This one tries to implement a true genetic algorithm with recombination and mutation. But note, I haven't studied or even read how it's supposed to work, I've only heard some rather vague details and ran with it.

I also noticed people using the cipher itself as the genetic material. I didn't think that was quite right, small genetic changes can make drastic changes to the output. Maybe that's better, but I went a different route. I took the plugboard on the enigma machine as an inspiration. On the enigma machine (ignoring the wheels), the output is scrambed by a plugboard that matches one letter to another, just like this cipher. As part of the codebook, you'd configure the plugboard in a certain way. The configuration of this plugboard is my genetic material. To make this a bit more interesting, there are 26 layers of plugboard and you rotate the alphabet every time after applying the plugboard. This is 13 pairs of letters, 26 layers or 338 bits of DNA (43 bytes, with 6 junk bits at the end). Plenty of genetic material.

I did this in Ruby, perhaps not the best choice if I wanted speed, but it's running on jRuby with (on this machine) 8 threads and seems to be chugging along nicely. But of course I implemented String#alphabetic? in the most insane and slow way, and that just happens to be the one crucial method, so it can certainly be improved on.

It can also output CSV, maybe I'll make some pretty charts!