Playground
Some interactive demos of things I find interesting. I hope you do too!
The Caesar cipher is one of the oldest ciphers around. In order to encrypt a message you shift every letter by a fixed amount. For example, a shift by 3 implies that A becomes D, B becomes E etc. Julius Caesar used this for military orders, as he did not want other people reading his messages. The entire security rests on keeping the shift secret.
Try it
Breaking it
It is not hard to break this cipher as there are only 25 possible keys. A computer checks all of them before you finish reading this sentence. Even by hand you can crack any Caesar message in under a minute. Just try each shift until something reads as English. This is called brute force: no cleverness required, just try everything.
What does this say? Try all possible shifts below — one of them will be readable English.
Say you are going on a work trip and you have one bag with a weight limit of 30. You have ten items to choose from, each with a different weight and usefulness. Each item is either in the bag or it is not, so there are 210 = 1024 possible combinations. How do you find the best one without checking all of them?
A genetic algorithm solves this without checking every option. The basic idea is to throw a bunch of random guesses at the problem and let them compete. You keep the good ones, mix them together, and occasionally flip something at random. You repeat this over many generations until the population converges on a good answer. There is no formula or gradient, just selection pressure. For this problem the optimal value is 52. Hit Run and watch it figure it out.
Items
Evolve
How it works
Each candidate solution is a row of 10 bits, one per item. A 1 means the item goes in the bag and a 0 means it stays out. There are 210 = 1024 possible combinations, but the algorithm finds a good one without checking all of them.
The fitness of a solution is the total value of all items in the bag, as long as the total weight stays under 30. If it goes over, the score gets a penalty. The more you overshoot, the worse the score. Overweight solutions can still survive and reproduce, since they sometimes carry useful item combinations.
Selection picks parents by drawing three candidates at random and keeping the best one. Crossover takes two parents, cuts them at a random point, and swaps the tails so the offspring gets a mix of both. Mutation randomly flips each bit with 5% probability so the search does not get stuck. The best solution from each generation always survives intact.
Say you are dealt pocket aces and your opponent has king-queen suited. You want to know how likely each of you is to win. You could work it out exactly by going through every possible way the remaining cards could fall, but before the flop that is over a million combinations.
Instead you just sample. You deal the remaining cards randomly, see who wins, and repeat 50 000 times. The fraction of times each player wins is a very good estimate of their true odds. Pick two hands, optionally add some board cards, and hit Simulate.
Hands
How it works
Each iteration takes the known cards, fills in the rest of the deck at random, and runs the board to completion. It records who wins and moves on to the next sample. After 50 000 iterations the win counts are divided by the total to get a percentage. More iterations give a more accurate estimate, but 50 000 is already very close to the true value.
At the end of each runout, both players have 7 cards. To find the best hand you check all 21 possible five-card combinations and keep the highest ranked one.