Posts Tagged ‘programming’

Monty Python Hall: A Monty Hall simulator in Python

March 25th, 2019


Public domain illustration from Wikipedia
 

The infamous Monty Hall problem goes something like this: Monty Hall, the host of TV game show “Let’s Make A Deal” shows a contestant three doors. Behind one door is a new car. If the contestant picks that door, they win the car.

The other two doors have a goat behind them, which are not prizes. I guess this puzzle falls apart if you for some reason find a goat more valuable than a car. Anyway, point is the door with the car behind it is the prize.

Once the contestant picks a door, the host Mr. Hall opens a second door to reveal a goat. Now Mr. Hall asks the contestant to select one of two options:

  1. Stay with the original door they picked
  2. Switch to a different door (the one remaining door that is not open)

Here’s where most of us get tripped up: it shouldn’t matter, right? There are only two remaining doors, one has a car behind it and the other a goat. Why does it matter if you stay or switch doors?
 

What’s going on?

As it turns out the odds in this situation are counterintuitively not 50%. When the contestant initially selected a door the odds they selected the prize door were one out of three. But this changes once Mr. Hall opens a door to reveal a goat using his prior knowledge. We know Mr. Hall will never open a door with a car behind it, and he will never open the same door the contestant initially selected.

The contestant’s initial choice remains fixed in time: one out of three. Now that a door revealing a goat has been opened the initial choice is still one out of three. But if the contestant switches doors, something unexpected happens — their new choice has a two out of three chance of winning.

If this problem sounds familiar you probably heard about it in Parade magazine back in the 90′s when columnist Marilyn vos Savant spent years covering this problem. It’s also been tested on Mythbusters. For a quick explanation check out AsapSCIENCE’s video on YouTube.
 

Another approach

Like many people, I often find probability mathematics baffling — and the Monty Hall problem is no exception.

When I was a kid I remember visiting The Exploratorium here in San Francisco and coming across a simple computer exhibit that simulated dice rolls. I’d never considered before that when you roll one six sided die the probability of landing on each side is equal, but when you roll two dice and add the numbers together, the probability of rolling any number between two and twelve are not equal. There’s only one way to roll a two or a twelve, but plenty of ways of getting, for example, an eight.

The exhibit drew a graph of the number of times it simulated a two-dice roll, with a bar for each possible outcome. After some number of rolls it always looked like a hill with most of the rolls in the middle range and fewer at the higher and lower numbers.

Since I was learning to program at the time, this idea of taking a mathematical problem and breaking it down into a computer simulation really appealed to me. In fact when I got home I wrote my own version of the dice roll simulator in QBasic. In only an hour or two I managed to put together a working dice roll simulator complete with a bar graph, just like the exhibit at The Exploratorium.

A computer simulation isn’t a mathematical proof of course, but it’s a good sanity check to validate a hypothesis.

Thinking about the Monty Hall problem again recently I thought I’d take that approach I’d learned as a kid and write a simple program to simulate it and tally up the results.
 

Monty Hall problem in Python

As a software engineer I mostly work in Python these days. It’s a fairly easy to understand language so I thought it’d be perfect for simulating the Monty Hall problem. That’s how I came up with “Monty Python Hall,” a Monty Hall problem simulator in Python. The idea is to run the Monty Hall three door problem any number of times and tally up the results at the end.

Once you’ve installed a Python interpreter on your system you can try out my Monty Hall simulator from the command line. Clone the repo, open the directory in a console and type “python run.py” and you’ll see an output like this:

Games run: 1000
Games won stayed: 351
Games won switched: 683

If you edit the source you can change the number of games run, but the result always comes out about the same: the contestant wins 2/3 of the time if they switch, and only 1/3 of the time if they stay.

I designed the program to prioritize simplicity over efficiency, so if you run it too many times it may be slower than you expect. For example look at the way the host selects a door:

while host_choice == player_choice or host_choice == car_at:
    host_choice = pick_random_door(num_doors)

This is more complex than it needs to be; the host’s choice is simulated randomly until it meets the required conditions.

Why? I think it’s more interesting to let people play around with the program, and the simpler the logic the easier it is to modify.

For example what if you change the number of doors? It needs to be at least three for the contestant and host’s choice to work. But what if there were ten doors? In my version of the program the host opens one door with a goat behind it no matter how many doors there are. But what if the host opens half the doors with goats behind them? Or all of the doors except the one that may hide a car?

My implementation of the Monty Hall simulator in Python is available under the free, open source MIT license. I encourage you to try it and modify it as you see fit.

If you find this useful in any way feel free to send me an email. I’d love to hear about it!
 

Find this project on Github

My own QML TreeView

February 15th, 2015

It’s Valentine’s Day and here’s the point where I have to confess my love as a software engineer for QML. It’s a markup language for building simple modern UIs with Javascript controls, and can be bound to C++ and Python via Qt. Since it’s based on Qt it runs on pretty much any modern desktop or mobile platform you can think of.

But like any relationship, sometimes one is left wanting for more. Sure, QML is great but it has flaws that are hard to overlook. For example, there’s no “tree view” component (think: file system UIs, Windows RegEdit, etc.) which is a deal breaker for some use cases.

That deficiency ends today.

I’ve been busily working on my own tree view implementation, which you can find on GitHub. It supports drag and drop rearranging and folder creation with a mouse or touch interface. Like the iOS home screen, folders are limited to one level (i.e. no subfolders.)

Here’s the sample test harness in action:

The trick? It’s all a standard QML ListView with a special type of delegate, my own RearrangeableDelegate.

The items can be rearranged by pressing (or long-pressing, see update below) on them, then dragging to the desired space. If you position it between two items a line appears, and releasing the mouse positions the item at that location. Positioning on top of an item causes the two items to pop out into a new folder. Dragging the last item out of a folder deletes the folder. If you want to have special items at the top of the list that can’t be rearranged, that’s supported via the numStationary property.

Everything is designed to be styled to your liking. Want to change the drag border, the opener image, the indentation, etc? Easy! Just set some of RearrangeableDelegate’s existing properties and you’re good to go.

The UI state of each item is stored in the list model itself, which provides an easy (if somewhat hacky) way of maintaining the UI state with a database or settings file. Here’s what you need to provide, subject to change:

ListElement {
    // Unique id (integer)
    uid: 1;

    // Used for drag and drop UI. (Persistence not required.)
    dropTarget: "none";  

    // True if a folder, else false
    isFolder: false;     

    // -1 if not in a folder, else the uid of the parent
    parentFolder: -1;    

    // For folders, this indicates whether their children are
    // displayed. Otherwise, indicates if visible.
    folderOpen: true;
}

Best part: I’m giving away the entire thing for free under the MIT license, which ought to satisfy pretty much everyone (except for Richard Stallman.) Take my code and do what thou wilt. If you encounter a bug please file a new issue or fix it on your own and submit a Pull Request. Either way I — and perhaps other QML developers — will be eternally grateful for your ongoing efforts to make up for this missing QML component.

 
UPDATE: After convincing Hryx to do some user testing, we decided that long-pressing wasn’t discoverable enough for a desktop. So now there’s a flag called dragOnLongPress to control this behavior. By default it’s set to false so that a long press isn’t required to move an item around. You can set it to true in situations where a long press to move makes sense, such as on touch and mobile devices.

Programming in Vala

January 18th, 2011

As some of you may know, I work for an open source software non-profit called Yorba. Our best known product is Shotwell, a photo management application that’s similar to Picasa or iPhoto, but created for Linux. It’s the default photo app these days in both Ubuntu and Fedora.

What many of our users don’t know is we don’t develop our software in C or C++… we use Vala.

So what the hell is Vala?

The cool thing about Vala is that it’s a fully compiled, statically typed OOP language designed to be built for Gtk applications. The syntax is very similar to Java or C#, but the garbage collection is based entirely on reference counting. In other words, you get the simplicity of a modern language with the speed of a fully compiled program. Vala bindings are already available for Gtk, Gdk, GLib, Gee, and many other libraries. Or you can create your own bindings when needed by creating a Vapi file. There’s a documentation program, Valadoc, which generates pretty HTML documentation for your classes.

The entire Vala package is available under an LGPL license, which is a free software/open source license. You’ll never have to worry about Microsoft or Oracle stepping on your toes.

Here’s the “Hello World” app from the Vala tutorial.

class Demo.HelloWorld : GLib.Object {
    public static int main(string[] args) {
        stdout.printf("Hello, World\n");
        return 0;
    }
}

Save your file as hello.vala. You can compile from the command line with:
valac hello.vala
Now watch closely… the Vala compiler actually just creates a .c file! It’s what’s called a “source compiler” in that it converts source code from one language to source code in a different language.

Next, valac automatically invokes GCC to compile the .c file into an executable binary.

Run your demo code with:
./hello

Simple, huh?

Vala syntax includes the language constructs you’d expect in 2011, including:

  • interfaces
  • single inheritance
  • non-nullable variables
  • foreach loops
  • delegates
  • signals
  • reflection
  • built-in multidimensional arrays
  • type inference

There’s plenty more sample code and tutorials on Gnome’s Vala site.

Documentation for some of the most common library bindings is available at Valadoc.org.

Okay, ready for the bad news? Despite being a relatively feature-complete language, there’s really no perfect IDE for Vala yet. If you’re used to powerful graphical debuggers, class browsers, and jumping around the code like in Eclipse and Visual Studio, you’re out of luck.

The only Vala IDEs at the moment are:

  • MonoDevelop: A great start, but for the features it’s rather heavy.
  • Valide: I was never able to get this one to even compile! But the screenshots look promising.
  • Valencia: This is Yorba’s GEdit plugin, which provides only barebones Vala functionality on top of GEdit, including jump to definition and autocomplete.

So there you go, that’s Vala. It’s still a young language, but it takes away the headaches of developing Gtk apps in C, and it doesn’t have the uncomfortable legacies of C++. Give it a shot!

Accelerated 2D graphics with OpenGL and SDL: part 1

October 13th, 2010

As some of you know, I’m working on an old-school puzzle game with Hryx. This game makes use of OpenGL’s graphics capabilities, but not for 3D graphics. Nope, the game is entirely two dimensional.

So why OpenGL? Because it’s really, really fast on most systems. Much faster than the slowpoke graphics in SDL.

This is going to be part one of a two part series on doing 2D graphics using OpenGL. And step one? Getting some 2D sprites loaded.

Loading the sprite with SDL_image
Now since we’re using SDL for our game, we decided on the excellent SDL_image to do the image loading.

Using SDL_image to load a sprite into memory is absurdly easy.

string filename = "myImage.png";
SDL_Surface* surface = IMG_Load( filename.c_str() );

That’s it!

But wait… that loads the graphic into an SDL surface. We need it to be an OpenGL texture! Damn.

OpenGL textures
In OpenGL, there’s no such thing as a “sprite.” You just have “textures.” So we’ll need to take our sprite and map it to a texture. The texture will be referenced with an integer (a GLuint) rather than a pointer.

But there’s an interesting restriction we have to work around that SDL simply doesn’t have. On most systems, OpenGL textures must have dimensions are are powers of two: 2, 4, 8, 16, and so on.

So once we load our SDL_Surface, we’ll make a new surface where we’ve rounded up the dimensions to the next highest power of two. The new surface will be filled with the alpha “color” and then we can blit (copy) over the existing image to the top left corner of our new image.

SDL_PixelFormat *format = surface->format;
Uint32 width = surface->w;
Uint32 height = surface->h;
Uint32 widthPow = (unsigned) pow( 2, ceil( log( width ) / log( 2 ) ) );
Uint32 heightPow = (unsigned) pow( 2, ceil( log( height ) / log( 2 ) ) );

// Create new empty surface.
SDL_Surface* newSurface = SDL_CreateRGBSurface( SDL_SRCALPHA,
	   widthPow, heightPow, 32,
	   rmask, bmask, gmask, amask );

// Fill sprite with alpha.
Uint32 alpha = 0;
alpha = SDL_MapRGBA( format, 0, 0, 0, amask );
SDL_Rect rect;
rect.x = 0;
rect.y = 0;
rect.h = heightPow;
rect.w = widthPow;
int ret = SDL_FillRect( newSurface, &rect, alpha);
surface->flags &= !SDL_SRCALPHA;

SDL_SetAlpha( newSurface, SDL_SRCALPHA, SDL_ALPHA_TRANSPARENT );

// Copy image data to our new surface.
ret = SDL_BlitSurface( surface, 0, newSurface, 0 );

Great, we got our surface loaded. Now it’s time to create an OpenGL texture, then take our SDL surface and copy it to the texture.

// This will be our OpenGL texture.
GLuint texture = 0;

// Bind the texture.
glPixelStorei(GL_UNPACK_ALIGNMENT,4);
glGenTextures(1, &texture );
glBindTexture(GL_TEXTURE_2D, texture);

// Convert surface to Open GL format.
gluBuild2DMipmaps(GL_TEXTURE_2D, 4,
	widthPow, heightPow, GL_RGBA,GL_UNSIGNED_BYTE, newSurface->pixels);

// Free our temporary SDL buffers.
SDL_FreeSurface( surface );
SDL_FreeSurface( newSurface );

Easy, huh?

Dealing with 24-bit surfaces
Up until now we’ve only dealt with is 32-bit images. One thing I hadn’t dealt with until now is 24-bit color-keyed images. A color-keyed image means you have RGB but no alpha or “A” channel to tell you what should be invisible. Instead, you just take one color (often black) and just say that it’s 100% transparent.

What we’re going to have to do is make the SDL_surface color keyed before we copy it to the OpenGL texture.

First, we’re going to need some functions for plotting individual pixels on an SDL texture. Unfortunately there’s no built in functions for this, so I stole some from this site.

Uint32 GetPixel( SDL_Surface *surface, int x, int y )
{
	Uint32 color = 0;
	char* pPosition = ( char* ) surface->pixels;
	pPosition += ( surface->pitch * y );
	pPosition += ( surface->format->BytesPerPixel * x );
	memcpy ( &color , pPosition , surface->format->BytesPerPixel );
	return color;
}

void SetPixel( SDL_Surface *surface, int x, int y, Uint32 color )
{
	char* pPosition = ( char* ) surface->pixels;
	pPosition += ( surface->pitch * y );
	pPosition += ( surface->format->BytesPerPixel * x );
	memcpy ( pPosition , &color , surface->format->BytesPerPixel );
}

Cool, now we can plot pixels! Feel free to go crazy and write a routine to draw circles or something!

But all we really need to do here is to take pixels that correspond with our color key and set the alpha channel to the alpha mask channel color.

if ( 24 == format->BitsPerPixel )
{
   Uint32 colorKey = format->colorkey;

   for ( int y = 0; y < surface->h; ++y )
   {
	   for (int x = 0; x < surface->w; x++)
	   {
		   Uint32 color = GetPixel( surface, x, y );
		   if ( color == colorKey )
		   {
			   SetPixel( newSurface, x, y, 0 );
		   }
	   }
   }
}

Putting it all together
Here is the final code to load an image file to a texture using SDL.

#include 
#include 
#include 
#include 
#include 

#if SDL_BYTEORDER == SDL_LIL_ENDIAN
   static const Uint32 rmask = 0x000000FF;
   static const Uint32 bmask = 0x0000FF00;
   static const Uint32 gmask = 0x00FF0000;
   static const Uint32 amask = 0xFF000000;
#else
   static const Uint32 rmask = 0xFF000000;
   static const Uint32 bmask = 0x00FF0000;
   static const Uint32 gmask = 0x0000FF00;
   static const Uint32 amask = 0x000000FF;
#endif

Uint32 GetPixel( SDL_Surface *surface, int x, int y )
{
	Uint32 color = 0;
	char* pPosition = ( char* ) surface->pixels;
	pPosition += ( surface->pitch * y );
	pPosition += ( surface->format->BytesPerPixel * x );
	memcpy ( &color , pPosition , surface->format->BytesPerPixel );
	return color;
}

void SetPixel( SDL_Surface *surface, int x, int y, Uint32 color )
{
	char* pPosition = ( char* ) surface->pixels;
	pPosition += ( surface->pitch * y );
	pPosition += ( surface->format->BytesPerPixel * x );
	memcpy ( pPosition , &color , surface->format->BytesPerPixel );
}

GLuint loadTexture( std::string filename )
{
	SDL_Surface* surface = IMG_Load( filename.c_str() );

	if ( NULL == surface )
	{
	   // Error!
	   return 0;
	}

	SDL_PixelFormat *format = surface->format;
	Uint32 width = surface->w;
	Uint32 height = surface->h;
	Uint32 widthPow = (unsigned) pow( 2, ceil( log( width ) / log( 2 ) ) );
	Uint32 heightPow = (unsigned) pow( 2, ceil( log( height ) / log( 2 ) ) );

	// Create new empty surface.
	SDL_Surface* newSurface = SDL_CreateRGBSurface( SDL_SRCALPHA,
		   widthPow, heightPow, 32,
		   rmask, bmask, gmask, amask );

	// Fill sprite with alpha.
	Uint32 alpha = 0;
	alpha = SDL_MapRGBA( format, 0, 0, 0, amask );
	SDL_Rect rect;
	rect.x = 0;
	rect.y = 0;
	rect.h = heightPow;
	rect.w = widthPow;
	int ret = SDL_FillRect( newSurface, &rect, alpha);
	surface->flags &= !SDL_SRCALPHA;

	SDL_SetAlpha( newSurface, SDL_SRCALPHA, SDL_ALPHA_TRANSPARENT );

	// Copy image data to our new surface.
	ret = SDL_BlitSurface( surface, 0, newSurface, 0 );

	// Change color key to alpha transparency.
	// Used for 24-bit images.
	if ( 24 == format->BitsPerPixel )
	{
	   Uint32 colorKey = format->colorkey;

	   for ( int y = 0; y < surface->h; ++y )
	   {
		   for (int x = 0; x < surface->w; x++)
		   {
			   Uint32 color = GetPixel( surface, x, y );
			   if ( color == colorKey )
			   {
				   SetPixel( newSurface, x, y, 0 );
			   }
		   }
	   }
	}

	// This will be our OpenGL texture.
	GLuint texture = 0;

	// Bind the texture.
	glPixelStorei(GL_UNPACK_ALIGNMENT,4);
	glGenTextures(1, &texture );
	glBindTexture(GL_TEXTURE_2D, texture);

	// Convert surface to Open GL format.
	gluBuild2DMipmaps(GL_TEXTURE_2D, 4,
		widthPow, heightPow, GL_RGBA,GL_UNSIGNED_BYTE,
                newSurface->pixels);

	// Free our temporary SDL buffers.
	SDL_FreeSurface( surface );
	SDL_FreeSurface( newSurface );

	return texture;
}

That’s it! Next time: displaying our new OpenGL texture on the screen as a 2d sprite.

Programming is a lot like writing

August 28th, 2009

Computer programming is a lot like writing. You use the same tools to do both (chair, computer, scraps of paper) and you have to follow a similar set of rules.

What sort of rules? There’s the strict rules, like syntax, grammar, and spelling. Then there’s the not-so-strict rules, like style and taste. Same idea, slightly different type of language.

Your program also has to “tell a story” in the sense that it’s telling the computer what to do. The stories have varying levels of complexity, but they often involve the same basic overall structure. Both tend to re-use tried and true plot devices that change the story as it goes along.

What are some differences between programming and writing?

  • No matter how great you think your program is, it will never be printed out on paper. (Unless you’re writing a book about programming, in which case you’re writing as well so ha!)

  • If nobody understand your book, it could still be a bestseller. If a computer doesn’t understand your program, nobody will buy it.
  • Writers don’t have SCO filing patent claims on their work.

Next week’s post: Driving a car into a lake is a lot like making silly analogies.