I ran into this interesting puzzle over at techInterview.org, which is a site dedicated to the kind of mental puzzles interviewers at certain companies love to ask job candidates. The puzzle is:
A 5*5 array is initialized to all 1s. Each cell can be either 0 or 1. When you flip a cell (m,n) (say from 1 to 0) all its four neighbors(left, right, up and down) flip. You need to change the array into all ZEROs by flipping the cells. How many minimum flips are required?
If I was really clever, I'd insert a Javascript widget here that let you play the game (assuming that Blogger even allows that), but I think the description is probably clear enough.
What was fun about the puzzle to me is that there are a huge number of states that the puzzle can be in, but it's obvious that there just has to be a better way to find a solution than just thrashing around blindly.
I was out sick from work yesterday, and in between naps, I tried working on the puzzle. Unfortunately, I just wasn't able to get much traction on the problem by trying to figure it out logically. Once I got frustrated enough, I resorted to a brute-force search of the solution space, which found 4 solutions, all of which were reflections and rotations of the same moves.
Leaving aside whether it's really very fair to ask for a "minimal" solution to a puzzle that only has one solution, it wasn't until I was copying the solution out of the terminal window that I saw the symmetry trick that makes it work.
Normally, when I'm trying to solve something like this, which just "has" to have a simple solution, I start by solviung a much simpler version, then try to scale up to the original problem as stated. For some reason, that process simply didn't occur to me yesterday. Had I tried starting with a 2x2 matrix and working my way up, I probably would have seen a pattern in the solutions pretty easily, and solved the puzzle by hand in a few minutes.
What did occur to me was that the total number of states, while large, was still well within the range where an exhaustive search would be reasonable. Once I had the program written to search for solutions, I ran it, and it finished suspiciously quickly. It turned out I had a bug, along the lines of using 2^25 instead of 2^26-1 in a critical place. I fixed that, re-ran it, and it still took less than 10 seconds. What the heck?
I tend to forget that the computers we have these days are so darn fast. Despite the fact that I'd done nothing to optimize that algorithm I was using, the PC was cranking along at 1 or 2 billion instructions a second, evaluating the 33,554,431 possible solutions at a speed of a few million iterations a second.
It's easy to think "this computer is so slow", when you're waiting multiple seconds for it to wake from sleep, or for some crazy Java applet to load, but when I see the results of the machine just cranking on some simple calculation, I'm just amazed at the power there.
If you want to see my thought process while I was working on this puzzle, you can read the techInterview discussion here, though my solution is there, so don't read it if you don't want to be spoiled. I'll probably post my code here later, so you can see what kind of C code I write when nobody's watching, and while I'm sick to my stomach :-)
Wednesday, February 27, 2008
Friday, February 22, 2008
Monkey madness!
It seems like in every job I take, I eventually end up developing an API, or a programming language, or a macro processor, or something similar. I don't know if this is characteristic of the sorts of jobs I take, or if it's just a reflection of the sort of approach I tend to take to solving problems. I suspect both factors are at play.
My latest foray into tool development started innocently enough. At Zing, we develop software and hardware for portable entertainment devices. Examples would be MP3 players, satellite radios, and portable internet radio streaming devices.
Anyway, one of the guys on the development team suggested that we ought to implement a bit of software to simulate the actions of a user - pressing buttons, spinning the scroll wheel, changing the volume, that sort of thing. Apparently Palm used a similar system (called a Gremlin) to flush out some of the more obscure timing-related bugs in their software.
Our version was called the UI Monkey (after the Infinite Monkey Theorem). The initial implementation was fairly straightforward, generating random user-input events and feeding them into the event queue on the device.
Then someone wanted a way to record and play back events, so we could do some testing automation. That was straightforward enough, though anyone who's implemented UI automation on such a low level can tell you than the resulting scripts are very fragile, in that any tiny change to the UI will break the script.
Once I had the basic framework in place, more requests came in, everything from "can we have the monkey scripts check for success?", to "how about implementing a way to repeat a bunch of actions over and over?". Since the whole Monkey code structure was based on sending and receiving UI events, other features had to be hacked in as "special" events, which each had their own syntax. After I had finished "goto", and had started working on some other features, I decided it was time to take a step back from the ledge and re-evaluate my options.
Despite the great amount of interest expressed in UI automation, nobody else was using the system I'd created. Given the sheer impenetrability of the syntax, I can't really blame them, but it was a little disappointing. I decided it was time to come up with something a little less insane, and a bit more appropachable.
The one thing I was pretty sure of was that I didn't want to implement my own scripting language from scratch. While designing your own language is an interesting project, and gives you a lot of power, it always takes a lot longer than you'd expect, and you're never really done. Implementing a "Monkey library" on top of a more-standard language seemed like a better bet.
I considered using C# as our UI scripting language. Unfortunately, C# requires a fair amount of boilerplate code just to make a basic loadable assembly, and a lot of the folkks that want to do scripting aren';t familiar with the development tools. So, some kind of scripting language seemed to be in order. As it turns out, we already have a scripting language interpreter embedded into our product (which is another story, and a great example of the Law Of Unintended Consequences at work).
So, I threw out all of the crazy hacky code I had been writing, and re-built the Monkey on top of Lua, a light-weight scripting language. Instead of an event recording and playback system, we now have a set of event-related primatives, and a real programming language to call them from, with functions, for loops, if-then-else, and variables. The integration of the Lua and C++/C# code was pretty easy, as well.
My latest foray into tool development started innocently enough. At Zing, we develop software and hardware for portable entertainment devices. Examples would be MP3 players, satellite radios, and portable internet radio streaming devices.
Anyway, one of the guys on the development team suggested that we ought to implement a bit of software to simulate the actions of a user - pressing buttons, spinning the scroll wheel, changing the volume, that sort of thing. Apparently Palm used a similar system (called a Gremlin) to flush out some of the more obscure timing-related bugs in their software.
Our version was called the UI Monkey (after the Infinite Monkey Theorem). The initial implementation was fairly straightforward, generating random user-input events and feeding them into the event queue on the device.
Then someone wanted a way to record and play back events, so we could do some testing automation. That was straightforward enough, though anyone who's implemented UI automation on such a low level can tell you than the resulting scripts are very fragile, in that any tiny change to the UI will break the script.
Once I had the basic framework in place, more requests came in, everything from "can we have the monkey scripts check for success?", to "how about implementing a way to repeat a bunch of actions over and over?". Since the whole Monkey code structure was based on sending and receiving UI events, other features had to be hacked in as "special" events, which each had their own syntax. After I had finished "goto", and had started working on some other features, I decided it was time to take a step back from the ledge and re-evaluate my options.
Despite the great amount of interest expressed in UI automation, nobody else was using the system I'd created. Given the sheer impenetrability of the syntax, I can't really blame them, but it was a little disappointing. I decided it was time to come up with something a little less insane, and a bit more appropachable.
The one thing I was pretty sure of was that I didn't want to implement my own scripting language from scratch. While designing your own language is an interesting project, and gives you a lot of power, it always takes a lot longer than you'd expect, and you're never really done. Implementing a "Monkey library" on top of a more-standard language seemed like a better bet.
I considered using C# as our UI scripting language. Unfortunately, C# requires a fair amount of boilerplate code just to make a basic loadable assembly, and a lot of the folkks that want to do scripting aren';t familiar with the development tools. So, some kind of scripting language seemed to be in order. As it turns out, we already have a scripting language interpreter embedded into our product (which is another story, and a great example of the Law Of Unintended Consequences at work).
So, I threw out all of the crazy hacky code I had been writing, and re-built the Monkey on top of Lua, a light-weight scripting language. Instead of an event recording and playback system, we now have a set of event-related primatives, and a real programming language to call them from, with functions, for loops, if-then-else, and variables. The integration of the Lua and C++/C# code was pretty easy, as well.
Subscribe to:
Posts (Atom)