Spring Break Project: Enigma machine

You may remember that a while back, I went on an indefinite hiatus due to the pressures of balancing classwork, projects and professional stuff. In light of that trying time, I've convinced myself that I should attempt to pair my projects with my classwork where it's applicable in order to stay afloat. That being said, my next project in Programming Languages will be in Prolog. I've only seen a few samples of Prolog code in action, it seems to be driven largely by logic. Of course everyone says this, but I always thought every programming language was driven by logic! Anyways, the kind of logic Prolog operates on seems to be more like Syllogism in Philosophy. For example:

• All men are mortal
• Socrates is a man
• Therefore Socrates is mortal.

 After a quick google search, I can see that this is also represented in Prolog, which the following:

• All dogs are canines
• All canines are mammals

?- deduction(all(dogs, canines), all(canines, mammals), C).
 
{C = some(mammals, dogs)}
{C = all(dogs, mammals)}
{C = some(dogs, mammals)}

• Therefore: Some mammals are dogs, all dogs are mammals, and some dogs are mammals.

Nice.  So the next is, what do I think I'm going to do in this language? I was thinking about making an Enigma Machine in Prolog. Honestly, I'd rather write a program that generates Engima Machines (for an alphabet of any size, with any number of customized rotors, etc...) BUT, I don't want to get too ambitious. At the end of the day I'd rather be a guy who does more than he says. However, in light of my recent passion for Scheme/Racket, I think I might save the generator for that language. We'll see how it goes. I think the outline will look much like this:

• Create a simple Enigma machine for 3 letters, then 4 (three rotors, odd and even reflector plates) in Racket.
  
• Create an Enigma machine for all 26 letters of the alphabet in Racket. Then in Prolog.
  
• Then, if time permits, work on an Enigma generator in Racket.

This way my assignment is covered, and I can also hone my functional programming skills some more. I'll be sure to update my github as I make progress.

Improving Monty Hall: Cdr, Wdr, Shldr

Hansei time.

I've managed to get some good feedback on my Monty Hall implementation, both on the internet and in the classroom. In particular, my Programming Languages Professor was kind enough to point out that, in my 10^6 example, that most of the computational time was being spent on the generation of the revealed list of gameshows, not the execution. This was aligned with criticisms that I should reconsider making a struct of a struct be the centerpiece of the program... and I agree. After all, this program was written totally just for me understand how on earth the relationship between staying and switching was possible. Therefore I try to produce what felt like the most accurate simulation possible-- being presented a random set of 3 doors with the prize (a Monty), randomly selecting a door  (within Choice), the host informing me that another door contains a goat (host-reveal) and then the program picking up whether staying or switching would win the game.

However, now that I understand what the results should be, and how to get there, I can start trimming up the program significantly to be a lot more lean. The first solution I propose is dissolving Monty and Choice, and simply making gameshow a list of 6 items. After all, Monty and Choice are both three values that would function well as a list anyways. We could consider the Choice "part" of the list to be the first half, and then the Monty to be the second half. This would require a lot of diligence in writing functions, but may significantly cut down on time. I'll give it a try over break, and possibly even benchmark the two against each other. : )

You can't beat Monty Hall

Recently, I was introduced by my girlfriend to the Monty Hall Problem-- an age old probability which places you as a game show contestant, with the opportunity of winning a sports car. There are doors, and all you have to do is select which one of the three doors contains the car-- because the other two contain goats. The story goes that you choose a door, and then Monty Hall, the imagined host of this gameshow, reveals one of the doors containing a goat. At this point you're given the opportunity to stay with your current door, or to switch to the other door.

The controversy of this problem is that while it is assumed that you have 50/50 chance at winning the sports car, it is in fact more likely that you will win if you switch. 

If you are not familiar with the problem, this will likely when you begin to doubt. Thankfully, you're not alone, as I too found myself in disbelief that such a simple scenario could be any more than it seems. While I was able to find solace thanks to the brilliant folks at Numberphile, I still felt that the best way to prove to myself that this was true was to create a computer simulation.

I immediately got to work in Racket-- one of my languages of study in my Programming Languages course-- forming an effective simulation for any size of games. This was accomplish through the use of several structs, namely

• Monty, three binary digits representing which door contains the car;
• Choice, three digits representing the player's random choice where
• 1 represents the player's randomized choice
• 0 represents the door that was not chosen
• -1 represents the door the host revealed to have a goat.
•  Gameshow, which is composed of a Choice and a Monty.

From this point it was all about being able to initiate each struct, form each struct into a list, randomize each struct, and form a list composed of each struct. This sometimes required that functions simply passed fewer arguments to "handler" functions that either formed the structs into lists, or called substructs.

Once I had finished, the moment of truth was quit exhilarating. I watched the results compile, and sure enough, the distribution very closely modeled 1:3 for staying and 2:3 for switching. Below are two screenshots of models I used, the first being of size 10^3, and then 10^6 (which took quite a while on my crappy hardware!).

 

This got me really excited about constructing a computer cluster and using parallelism to tackle these huge problems. 

Of course, I've made my code available at Github for those of you who would like to give it a try. Soon, I'll be reproducing the code in Haskell for a presentation in class Friday. I'll be trying to model it as close as possible, so hopefully anyone can use it to "benchmark" (the term must always be used lightly) Haskell and Racket. As part of my presentation, I plan to do the same.