Dave Smith's Blog

M&Ms are yummy. At work we have ginormous bags of M&Ms to snack on. One day I reached into the bag and pulled out a handful (about 8 M&Ms). I happily munched until there were 4 left. Lo and behold! The remaining 4 were all blue. “What are the odds,” I asked myself. So I set out to find the answer.

I started by figuring out how many different M&M colors there were. My bag had 6:

• red
• green
• blue
• brown
• yellow
• orange

Then I assumed that there were an equal number of each color in the bag (that may not actually be true, but it makes the problem a tad easier to solve).

Armed with this information, I started up the wayback machine to go back to Computer Science 235, when, back in my college days, I studied probability. This is when I realized that I had forgotten pretty much everything I knew about probability, except dice rolling odds (which I use in Risk to conquer the world). So it turned out that memory lane wasn’t that helpful after all.

At this point I decided that I should compute the odds of choosing a handful of 8 M&Ms at random with at least 4 blue ones, this being a prerequisite of having 4 blue ones left in my hand after eating the other 4. To do this, I first drew 8 boxes on my white board, to represent the 8 M&Ms I could draw at random. This helped me reason about the problem. For any given box, I have a 1 in 6 chance of drawing a blue M&M. If I draw a blue one for a given box, that leaves 3 more I would need to also randomly draw. So I started enumerating a few permutations that could make this happen:

And so on. I realized pretty quick that there were too many permutations to enumerate so it was time to get analytical. I started to reason this way:

In position 1, I have a 1 in 6 chance of choosing blue, but I don’t really care which position the blue M&M lands in. I also know that, if I get lucky and chose blue in position 1, that does not impact my odds of choosing blue in position 2. So each position is independent. What that means is I have a 1 in 6 chance of choosing blue the first time, and again the second time, and the third time, and the fourth time. But, and this is the kicker, I don’t have to choose blue for the first 4. It just has to be any 4.

So if I were to compute the odds of choosing all 8 blue, it would look something like this:

1/6 x 1/6 x 1/6 x 1/6 x 1/6 x 1/6 x 1/6 x 1/6.

That’s a good starting point. Since we don’t have to choose all 8, but only 4, blue M&Ms, we can just throw out 4 of the terms, so we end up with this:

1/6 x 1/6 x 1/6 x 1/6

This is when I started getting confused. I started to wonder if maybe the 8 don’t have anything to do with the problem at all. Maybe the odds of choosing 8 at random, eating 4, and being left with only blue are the same odds as just randomly choosing 4 blue M&Ms.

This is when I ditched the analytical in favor of the empirical. As much as I wanted to eat 10,000 M&Ms to prove my hypothesis, I decided to write a small computer program to randomly choose 8 M&Ms from a virtual bag, randomly eat 4 of the virtual M&Ms, and then see if the remaining M&Ms were all blue. This I did, and ran it 5,000,000 times. The result: 0.077% of the time, I had 4 blue M&Ms left. That’s right, 0.077% is the same as 1/6 x 1/6 x 1/6 x 1/6. So I conclude that the odds are the same, and the problems are, in fact, equivalent.

So I beat the odds that day when I had 4 blue M&Ms left. Without even trying, I did something whose odds were 1,296 to 1, against. I should have gone to Vegas that afternoon.

P.S. The odds of having 4 M&Ms left that are all the same color (any color) are 6 times easier: 1 in 216.

P.P.S. If you want to see the source code (warning: it’s C++), just ask.

My new Parkzone Habu ducted fan jet arrived in the mail this week. I put it together and provide this walkthrough for the benefit of those who have not yet purchased their Habu (hint: just do it).

Stay tuned for the flight report in a couple weeks.

Parkzone Habu Walk Through from djsmith on Vimeo.

Update: Here’s the maiden flight video footage. Enjoy!

My office has a piece-of-junk Comcast cable modem that often needs to be rebooted. I got tired of walking back to the network closet, so I bought a USB relay for $30.

Yeah, I could have simply bought a better modem, but where’s the fun in that?

Here’s a photo of the relay board:

After connecting it to the modem’s power, I wrapped it in heat shrink:

And its final resting place where it will happily power cycle my cable modem for its entire useful life:

I put the relay between the modem’s power adapter and the modem itself, and connected the relay to my Linux server’s USB port for control. Once connected, the Linux kernel happily registered it as /dev/ttyUSB0 (it uses an FTDI chip for its USB-to-Serial translation, which is supported by all modern Linux kernels).

When connecting the power, I used the “C” and “NC” ports (“C” = “Common” and “NC” = “Normally Closed”). I didn’t use the “NO” port (“NO = “Normally Open”) because I don’t want my modem powering off just because the relay loses power (e.g., when the Linux box reboots).

This simple shell script power cycles the modem, which I run nightly using cron:


#!/bin/bash
device=/dev/ttyUSB0
printf '\xFF\x01\x01' >$device # Power off
sleep 60
printf '\xFF\x01\x00' >$device # Power on


I noticed that I needed to let the modem sleep for longer than 10 seconds, or there are problems on the network. In particular, our Outlook clients seem to lose their brains to our (off-site) Exchange server unless I sleep for longer. I used 60 seconds just to be safe.

The next step is to setup another cron job on my Linux box that will power cycle the modem if it ever discovers that it can’t reach the internet, or that its internet bandwidth is degraded.

I also wrote a small C++ program for Windows (about 20 lines) just to test the relay. It worked fine, but Linux was a lot easier to setup (no compiler necessary). In the time it took me to write that stupid C++ program, I was able to create both a working Python script and working shell script to do the same job (and Linux didn’t even require me to know the baud rate).

By the way, I would have avoided this whole exercise if my modem, like many others, had a software controllable reboot (some can be rebooted with wget, but not mine).

Happy (hardware) hacking!

Seriously. I don’t know how I ever created a Qt user interface without using stylesheets. This was, by far, the best idea Trolltech ever had.

For today’s show-and-tell, I give you a nifty-looking QSlider with some nice gradient style applied to it:

The handle has a nice hover effect, the bar has a moving gradient as you slide the slider, and it looks good when disabled. Notice also the rounded corners. No image files were harmed in the making of this widget.

Here’s the stylesheet code (I used Qt’s example as a starting point).

QSlider::groove:horizontal {
border: 1px solid #bbb;
background: white;
height: 10px;
border-radius: 4px;
}

QSlider::sub-page:horizontal {
background: qlineargradient(x1: 0, y1: 0,    x2: 0, y2: 1,
    stop: 0 #66e, stop: 1 #bbf);
background: qlineargradient(x1: 0, y1: 0.2, x2: 1, y2: 1,
    stop: 0 #bbf, stop: 1 #55f);
border: 1px solid #777;
height: 10px;
border-radius: 4px;
}

QSlider::add-page:horizontal {
background: #fff;
border: 1px solid #777;
height: 10px;
border-radius: 4px;
}

QSlider::handle:horizontal {
background: qlineargradient(x1:0, y1:0, x2:1, y2:1,
    stop:0 #eee, stop:1 #ccc);
border: 1px solid #777;
width: 13px;
margin-top: -2px;
margin-bottom: -2px;
border-radius: 4px;
}

QSlider::handle:horizontal:hover {
background: qlineargradient(x1:0, y1:0, x2:1, y2:1,
    stop:0 #fff, stop:1 #ddd);
border: 1px solid #444;
border-radius: 4px;
}

QSlider::sub-page:horizontal:disabled {
background: #bbb;
border-color: #999;
}

QSlider::add-page:horizontal:disabled {
background: #eee;
border-color: #999;
}

QSlider::handle:horizontal:disabled {
background: #eee;
border: 1px solid #aaa;
border-radius: 4px;
}

Enjoy!

I’ve encountered this problem a handful of times over the past few years using Qt’s layouts. Qt generally does a great job making sure that your Windows cannot be resized too small such that your content would be truncated. However, it seems that introducing a QStackedWidget causes a problem.

These two screenshots illustrate the issue:

Screenshot 1 The widget prior to resizing (all text appears correctly)

Screenshot 2 The user resizes the widget (the text is truncated)

Like I said above, I think the problem is caused by the QStackedWidget. Without it, Qt properly limits the widget’s minimum size such that the text cannot be truncated. I would love it if the Trolls could have a look at this issue. I’ve seen the problem since Qt 4.0, but I never reduced the problem to its base (it took a while to deduce that the QStackedWidget was the culprit).

If you’re interested, I’ve included the minimal Designer UI file that shows the problem (right click that link to save it). I used Designer 4.6.2 to create this file.

I wrote about multi-threading in Qt a while back, and how to use QThread to wrap a blocking function call “lock free”. Today we’ll talk about how to pass data into your thread. This approach can be used, for example, to tell your QThread to stop.

There are two ways to use QThread, with and without an event loop, and the preferred method for talking to a QThread depends on which of them you use.

Way 1: Without an event loop

When you’re not using an event loop, the thread’s run() method often looks like this:

void MyThread::run()
{
    forever
    {
        // Do some stuff
    }
}

Since this method does not use an event loop, there is no way to deliver a signal to your thread. So if you want to pass data into the thread, you have to use a good old fashioned mutex. Let’s look at an example showing you how to stop your thread:

void MyThread::run()
{
    forever
    {
        {
            // "mutex" and "stopRequested" are member
            // variables of MyThread:
            QMutexLocker locker(&mutex);
            if(stopRequested)
                return;
        }

        // Do some stuff
    }
}

void MyThread::stop()
{
    QMutexLocker locker(&mutex);
    stopRequested = true;
}

In this case, we have to check the stopRequested variable in a timely manner in our thread’s run() method. The longer you run between checks, the longer it will take your thread to actually stop.

Outside observers can use the finished() signal to know when your thread is actually done. So if you are in a QMainWindow, for example, and a closeEvent() happens, you can ignore the event, call MyThread::stop(), and then when the QThread::finished() signal arrives, you can actually close the window.

The downside is that the stop() call will actually block while it tries to acquire the mutex. Given the way this code is written, the blocking will probably be very short, but hey, I hate blocking. Let’s see if we can dig up a better way to do this.

Way 2: With an event loop

If you have an event loop, you can use Qt’s meta-objects to talk to your thread. Let’s look at the same example as before, only this time with no locking or blocking.

void MyThread::MyThread()
{
    moveToThread(this);
}

void MyThread::run()
{
    QTimer *timer = new QTimer();
    connect(timer, SIGNAL(timeout()),
        this, SLOT(doSomething()));
    timer->start(0);

    exec(); // starts the event loop, and doesn't
            // return until it is told to quit()
}

void MyThread::stop()
{
    if(currentThread() != this)
    {
        // The caller is running in a
        // different thread, so use Qt to
        // call stop() later, on our own thread:
        QMetaObject::invokeMethod(this, "stop",
                        Qt::QueuedConnection);
    }
    else
    {
        // Now the call has arrived from our
        // own thread, yay! We can safely
        // shut down our event loop.
        quit();
    }
}

Look mom! No locks! Now we have killed our thread, safely and gracefully. There is no chance of blocking, and we learned something about QMetaObject.

A couple items to note:

• The doSomething() method is left as an exercise for the reader, but be careful about the QTimer interval. I used 0, which means it will be firing almost constantly.
• The stop() method must be a slot in MyThread (and not just a regular method) or else invokeMethod() will return false and not actually re-invoke stop() for you.
• You can pass arguments to your thread this way, but it requires a bit more fun with QMetaObject::invokeMethod().
• You can reduce this whole thing to a magical macro that you could put at the top of your stop() method, saving you from having to write if(currentThread() == this) at the top of every method. Hint: use the __FUNCTION__ macro.
• To run this example code, you’ll need to #include these files: QThread, QTimer, QMetaObject, QMutexLocker, and QMutex
• To call quit(), it may not actually be necessary to be running on the same QThread (it works for me without the QMetaObject), but this will be required when you start passing in data to your thread. Without it, your program could do unpredictable naughty things. I can’t find anything in the docs about whether quit() is thread safe.

I’ve found this QMetaObject approach the most effective and easiest way to pass data to QThreads safely, without blocking and without locks.

Happy threading!

Today my friend Cliff showed me his first-person video R/C airplane:

This thing has every feature imaginable, which means it packs a lot of wires:

Here’s a video tour of all its features, which include the following:

• Auto fly-home if control is lost (uses GPS)
• Heads up video display of altitude, heading, and pitch
• RF beacon if the plane is lost
• Auto stabilization using FMA co-pilot
• Data logger providing an audible report of battery life and other stats
• VR goggles for watching the action
• Pan and tilt camera, controllable from the radio
• High-power transmitter (he’s flown a mile away on FPV)

The iPhone doesn’t (easily) let you change the colors of your calendar items. Couple this with the fact that there are lots of ways to setup calendar sync’ing, and it’s easy to get discouraged.

For me, my work calendar and my personal calendar both showed up as nearly the same shade of red. Fail.

Here’s how I fixed it. This only works if you have the following situation:

• iPhone OS 3.0 or newer
• Using Google Calendar with CalDAV (not Exchange)
• Note: I use Exchange for my work calendar and Google for my personal calendar, and I want them both on my iPhone with different colors

Steps to change the color (this takes about 5 minutes if nothing goes wrong).

1. Open iCal on your Mac (don’t have a Mac? Maybe Mozilla Sunbird can do this too)
2. Subscribe to your Google Calendar (instructions to do this
3. In the sidebar, notice your new calendar appears
   
4. Right-click on the new calendar and select Get Info
5. Now change the color to what you want
   
6. Do nothing, and in a couple minutes your iPhone calendar items will have the new color

If you can’t get iCal setup, don’t fret. It does work. Double check your URL you typed to subscribe to your Google Calendar. Don’t forget the “/user” at the end. Follow Google’s instructions (see link above) very closely.

Good luck!

I’ve recently seen some confusion about the terms functional and procedural in the software development community. Let me spend a moment trying to clear things up for (both of) my readers.

First of all, just because a programming language has functions, that does not mean it is functional. In fact, its confusing name has nothing to do with functions. The history of the term function, as used in the computation world, hails back to the 1930′s when Alonzo Church created Lambda Calculus to be able to use and define mathematical algorithms on paper. Later, when computers arrived on the scene, programmers adopted the term function to describe a chunk of code that could be re-used by other chunks of code. Functions, in this context, have been adopted by every programming language I know of, including assembly language. Functions are commonly referred to as “routines”, “subroutines”, or “procedures”. Some might even argue that a “method” is pragmatically identical to a function.

Here’s where the confusion begins.

This is hard to explain rigorously, but here goes anyway.

Some languages, like C, tend to encourage computer programmers to make use of functions. Programs written in these languages tend to consist of a set of functions, and a “main” function that kicks everything off. Such a language is often referred to as “procedural”, but really the term “procedural” refers to a style of programming, and does not really describe a language, per se. It is most often used as an antonym to the concept of “object oriented”. But, oddly, it has nothing to do with “functional” programming.

Other languages, like Scheme and Haskell, tend to encourage computer programmers to write code with functions that avoid internal state changes and produce no side effects when called. For example, these language discourage global variables, and particularly the calling of functions that would mutate global variables (that would be a side effect).

To sum up.

Procedural programming languages can be functional or not. Functional programming languages can be procedural or not.

Here’s a table:

If you take nothing else away from this article, take this: The C programming language is not a functional language. It’s not bad, it’s just not functional.

My brain’s been a stewing about 2010, and I just gotta let it all out. If I’m even half right, 2010 will be awesome.

1. Hulu in the Living Room

In 2010, Hulu will partner with a company like Western Digital or Popcorn Hour to release a tiny box that connects to your HDTV to watch TV shows and movies, streamed from Hulu’s servers. The box will cost less than $100, and have no monthly subscription, because its development will be subsidized by Hulu’s ad revenues. If it’s not released in 2010, it will at least be announced.

2. Cable Networks Become Record Labels

Just like iTunes changed the music industry, online media and broadband Internet access will start to change the TV industry. It remains to be seen who will be the big player (my money’s on Hulu), but one thing is for sure: Americans will have a choice when it comes to buying subscription TV services. The trend will begin in 2010, allowing consumers to get on-demand TV content for free, and will finish some time in the future with cable companies either totally transforming into something like modern record labels, or going out of business.

3. HDTV Sales Will Boom

HDTV’s have gotten so inexpensive that nearly every American household will have one by the end of 2010. This will be driven by the fact that online media will be so easily accessible that most people won’t need to buy cable, so they can easily justify the cost of a new $500 TV.

4. Qt’s Best Year

Companies who develop desktop application software that needs to run on Mac and Windows will simply have no other choice for their developers than Qt. That trend will strengthen in 2010 to the point that it’s a no-brainer decision over platform-specific choices like .NET, Cocoa, and others. Qt has matured so much over the last 5 years that its toe-hold in this market will grow to a full Nelson in 2010.

5. Model Aviation Takes Off

Model airplanes have gotten very popular and accessible. Manufacturers have pushed prices down so low that anyone can afford to get into the hobby. Batteries, R/C electronics, and planes have gotten cheaper, and planes have gotten easier to fly for the novice pilot. The entry-level model airplane market will take off in 2010.

Your Turn

Do you agree with my predictions, or am I totally off?

Have any predictions of your own?