Category Archives: fun

TourBus 2: The Tourbusening

I’m speaking at Utah Open Source Conference! I will use up 55 minutes of your remaining lifetime talking about web load testing.

I am, of course, going to dust off TourBus. It was such a simple app that there wasn’t really anything to show off at MWRC 2009 and I am pleased to say that there still isn’t!

But you could help change that. Check out TourBus on GitHub, or better yet fork it and dig in.

Some features I hope to add in the next month:

  1. AMF support (testing Flex apps, anyone?)
  2. Proxy logging (tour the website yourself in a browser, then playback your browser session)
  3. Better (read: ANY) specs!
  4. Rails plugin, complete with generators and rake tasks
  5. Reporting and statistical analysis

Seriously, what’s not to like? Get in there and get forking!

P.S. For those of you watching the MWRC 2009 video and wondering, “Will I ever get the chance to see those ridiculous sideburns in person?” the answer is oh my goodness yes.

Sudoku: Math Is Hard, Let’s Go Shopping

I’ve been researching others’ techniques for generating sudoku puzzles, and I have come to the conclusion that nobody actually knows how to do it.

Seriously, if you Google for “generating sudoku puzzles”, most of the methods boil down to “randomly throw numbers at the board and see if it’s a sudoku”. Oh, there’s some cleverness you can do to try to intelligently preserve the randomness of a partially-complete sudoku puzzle (like not randomly putting a 9 into a column that already has one) but at the end of the day all of the solutions basically amount to bogosort.

I promised yesterday that I’d reveal the identity board math. I had planned a big reveal here with lots of mathy explanationing, but the math just isn’t that exotic. There’s a trick to it, but that’s about it. Here’s the math:

A Sudoku board of dimension n is n2xn2 digits, and has nxn sectors, each with n2 digits. Let’s write a function to find the number at position x, y on the board. The whole trick to my F(x,y) math is simply this: the numbers in every sector other than (0,0) are rotations or shifts of the numbers in sector (0,0).

Make sense? Here. The numbers in sector(0,0) are simply the digits 1..n2, arranged in a grid, so that’s easy:

F(x,y): y*n+x

And the math for every other sector is simply a selection into sector 0, 0. Specifically, for F(x,y) outside of sector (0,0), choose the F(x’,y’) IN sector 0,0 such that

x’ = ((x+y/n)%n

y’ = ((y+x/n)%n

So at the end of the day the whole function looks like this in ruby:

def idfx(x, y, n)
  if x<n && y<n
    y*n+x
  else
    idfx( ((x+y/n)%n, ((y+x/n)%n )
  end
end

I should point out that I am operating under the belief that a sudoku puzzle is like a Rubik’s Cube: that a set of transformations can be performed on a valid puzzle that leave the puzzle changed but always valid, and that you can turn any sudoku puzzle into any other sudoku puzzle via these transformations. If I am right, I can take my identity puzzle board and shuffle it using these transformations, and just like scrambling a Rubik’s Cube I will be left with a unique and interesting puzzle that is, most importantly, still valid.

I have proven the first half of my assumption–there are transformations that will change a sudoku without affecting its validity. What I haven’t proven is the second half. I cannot yet transform puzzles arbitrarily. It may not be possible at all, but right now I’m simply hoping that I don’t know enough transformations yet.

Sudoku: Creating Identity Boards

I’m building a Sudoku generator. There’s just enough wicked math in there to make things interesting. One thing that caught my attention was that there is a sort of “identity” board that you should be able to build for any dimension of sudoku. For the standard 3×3 matrix, it looks like this:

+------+------+------+
| 1 2 3| 4 5 6| 7 8 9|
| 4 5 6| 7 8 9| 1 2 3|
| 7 8 9| 1 2 3| 4 5 6|
+------+------+------+
| 2 3 1| 5 6 4| 8 9 7|
| 5 6 4| 8 9 7| 2 3 1|
| 8 9 7| 2 3 1| 5 6 4|
+------+------+------+
| 3 1 2| 6 4 5| 9 7 8|
| 6 4 5| 9 7 8| 3 1 2|
| 9 7 8| 3 1 2| 6 4 5|
+------+------+------+

The way you write an identity board is this: You write the digits 1..9 in order in the top left sector and across the top line of the puzzle. If you look at it in terms of triplets, however, you build the top line by copying the 2nd triplet row (4 5 6) and then the 1st triplet row (7 8 9) across the top line.

The second row starts with (4 5 6) so you naturally continue with (7 8 9) in the next sector, and then roll around to the beginning to end with (1 2 3). The third row then follows naturally: (7 8 9) (1 2 3) (4 5 6).

You can build the entire board this way if you do the same thing vertically. Copying the first sector’s columns down the board’s first column, you get (1 4 7), (2 5 8), (3 6 9). Do this across the entire board and you end up with the completed puzzle.

The really neat part of this for me is that it works with any dimension of sudoku. For example, here’s a 2×2 and a 4×4 identity board built the same way:

+-----+-----+
| 0 1 | 2 3 |
| 2 3 | 0 1 |
+-----+-----+
| 1 0 | 3 2 |
| 3 2 | 1 0 |
+-----+-----+

+---------+---------+---------+---------+
| 0 1 2 3 | 4 5 6 7 | 8 9 A B | C D E F |
| 4 5 6 7 | 8 9 A B | C D E F | 0 1 2 3 |
| 8 9 A B | C D E F | 0 1 2 3 | 4 5 6 7 |
| C D E F | 0 1 2 3 | 4 5 6 7 | 8 9 A B |
+---------+---------+---------+---------+
| 1 2 3 0 | 5 6 7 4 | 9 A B 8 | D E F C |
| 5 6 7 4 | 9 A B 8 | D E F C | 1 2 3 0 |
| 9 A B 8 | D E F C | 1 2 3 0 | 5 6 7 4 |
| D E F C | 1 2 3 0 | 5 6 7 4 | 9 A B 8 |
+---------+---------+---------+---------+
| 2 3 0 1 | 6 7 4 5 | A B 8 9 | E F C D |
| 6 7 4 5 | A B 8 9 | E F C D | 2 3 0 1 |
| A B 8 9 | E F C D | 2 3 0 1 | 6 7 4 5 |
| E F C D | 2 3 0 1 | 6 7 4 5 | A B 8 9 |
+---------+---------+---------+---------+
| 3 0 1 2 | 7 4 5 6 | B 8 9 A | F C D E |
| 7 4 5 6 | B 8 9 A | F C D E | 3 0 1 2 |
| B 8 9 A | F C D E | 3 0 1 2 | 7 4 5 6 |
| F C D E | 3 0 1 2 | 7 4 5 6 | B 8 9 A |
+---------+---------+---------+---------+

The neatness of this pleased me, but when I tried to implement it in code it got hopelessly complicated very fast. On the drive home from work last week, I found an elegant mathematical function to produce this board. Can you guess it? I’ll post it tomorrow. If you can’t wait, dig around in my twitter feed–the entire function is less than 72 characters.

Math Joke 3

Until last week I only knew 2 good math jokes. But then I heard this one! Without further ado, I hereby inflict it upon you:

An engineer, a physicist and a mathematician are chatting over lunch when the engineer says, “I just don’t get problems in higher dimensions. I mean, stuff in 3 dimensions I can visualize quite easily, but how do you visualize something with more?”

The physicist shrugs and says “You just have to imagine integrating. For example, if you have an object in three dimensions and integrate it over time, you have added a fourth dimension, time. It’s like taking an object’s position and integrating it to get the object’s velocity. You can do it again with time, to get the object’s acceleration, or with another dimension; each integration changes the units appropriately.”

The engineer thinks for a minute and says, “That’s okay for a few dimensions, but what about some of the really wacky stuff like 17 dimensions?”

The mathematician looks up and says, “Oh, that’s really easy, actually. Just imagine an n-dimensional space and set n=17.”

Math Joke 2

Until last week I knew exactly 2 funny math jokes. Now I know three. I’ll post the third one tomorrow. Here’s the second one.

An engineer, a physicist, and a mathematician are asleep in a hotel when the curtains in each of their rooms catch fire. (Inexplicably, and all at the same time. Don’t ask why, it’s not important.)

The engineer wakes up and sees the fire, runs into the bathroom, fills the wastebasket with water, comes back and throws it on the fire. The fire goes out immediately, but there’s quite a bit of water damage.

The physicist wakes up and sees the fire, and pauses to estimate the rate at which the curtains are being consumed. He runs into the bathroom, fills the wastebasket with exactly 1.7 liters of water, comes back and carefully pours it on the fire. There’s a bit more fire and smoke damage due to the delay, but not a drop of water is spilled unnecessarily.

The mathematician wakes up and sees the fire, and pauses to contemplate the problem. Then he calmly walks into the bathroom. He turns on the faucet and strikes a match, then douses the match under the running water. He examines the match closely for a minute, then says, “Ah yes, this problem has a solution.” And then he goes back to bed.

Math Joke 1

Until yesterday I knew exactly 2 funny math jokes. Now I know three. Here’s the first one.

Two math professors are arguing in a cafe about the education level of the average person. One insists that the average person has little grasp of mathematics beyond arithmetic. The other asserts that the average person knows at least rudimentary calculus. They pass their lunch in fruitless debate.

Finally, the first professor goes to the bathroom. The second professor waves the waitress over. “I am having a bit of a debate with my friend here. When he returns, I’ll ask you a question. If you answer with the exact phrase ‘one third x cubed’, I’ll leave a ten dollar tip.”

“Ten bucks? You bet,” says the waitress.

The first professor returns. The second professor announces, “Here, I’ll prove it to you.” He turns to the waitress and asks, “What is the integral of x squared?”

“One third x cubed,” replies the waitress. They both laugh and the second professor leaves the $10 tip.

As they’re leaving, the waitress mutters, “…plus a constant.”