**Posted:** April 26th, 2011 | **Author:** Joey | **Filed under:** Whatever | 1 Comment »
A little over a year ago, I posted the browser statistics for my wife’s website. In a futile attempt to keep this blog alive, I’m posting some new stats from the last year. It is good news all around, it looks like IE6 is finally dying. Just over 1.5% of the total users coming to her site use IE6

The original post has more explanation of the numbers, but if you are just interested in the change, here are the graphs for last year.

**Posted:** April 14th, 2010 | **Author:** Joey | **Filed under:** Whatever | **Tags:** computer science, laundry, sorting | 3 Comments »
I’m kind of embarrassed to admit that it wasn’t until this year that I started regularly doing the laundry. I did my own laundry when I lived on my own, but that was 10 years ago. Doing laundry for four different people was new to me. Folding jeans, shirts, towels, sheets, etc., that stuff didn’t bother me. But I’d put off doing the socks until we were all running out. I hated folding socks.

I should say it wasn’t so much the folding of the socks that I didn’t like, that was easy enough. It was having to find the other half of the pair for a given sock. The other articles of clothing were simple; grab something, either fold it or put it on a hanger, and move on. But folding socks took *forever*.

My original strategy was clearly inefficient. It went something like this:

- Grab a sock
- Do I have another sock waiting for a match of this type?
- If not, set the sock aside until I come across another sock of that type
- If yes, are the socks in the same phase of their life cycle?
- If not, set the sock aside until I come across another of that type and equally worn out
- If so, great! Fold’em and move on!

- Go back to step 1

For a small quantity of socks, these steps were OK. But usually, it sucked. Time to put my computer science degree to use.

Since I was procrastinating, let’s be conservative and say I’d have a week’s worth of socks for four people to take care of. That is 56 socks in a basket in front of me. Now, if I wore only one style of sock, and so did my wife and kids, it probably wouldn’t be a problem. But we buy new socks as old ones wear out, and especially for the kids as they grow. Each of us probably has about three to four different styles of socks we wear. Of course, I favor the newer, more comfortable ones, but the styles are still mixed up throughout the week. So for a given sock, there are probably 3-5 matching socks out of the basket of 56 that can be paired up with that sock. It should be obvious why my algorithm sucked.

$socks = array($sock1, $sock2, /* ... */, $sock56);
$unmatched = array();
foreach ($socks as $sock) {
$matchFound = false;
foreach($unmatched as $other) {
if ($sock->type == $other->type && $sock->wornOut == $other->wornOut) {
// Yay! Found a match! Remove them from the "unmatched" array
foldPair($sock, $other);
$matchFound = true;
break;
}
}
if (!$matchFound) {
// Add this sock to the list of unmatched socks
$unmatched[] = $sock;
}
}

Best case scenario: I grab a sock, put it in the unmatched array, grab the next sock and it matches the only sock in the unmatched array. `O(n)`.

Worst case scenario: I grab a sock, put it in the unmatched array, grab the next sock, no matches, and put that one in the unmatched array also, repeating until half of my socks are unmatched. Then I start matching the socks one by one until they are all folded. `O(n^2)`

One day as I was folding socks, it dawned on me: divide and conquer! My problem was that I was trying to mentally keep track of all my unmatched socks, but my mind could only keep track of so many variations. But if you put a small enough set of socks in front of me, picking out the matches was trivial and could be done in linear time.

Now for the basket of 56 socks, I first pick a really simple feature of the socks in front of me, and split them up according to that feature. For example, about half of our socks have gold fabric around the toes. Perfect! Gold toes over here, the rest over there. From there I split them up depending on if they are ankle-length socks or not. Then whether or not the socks are ribbed. And then if they belong to an adult or not. By this point, I’ll have reduced the size of the sets of the socks to a number that I can see all at once, and pairing and folding these socks is a breeze.

Now my sock folding algorithm is `O(n*log(n))`. I am pleased to report that I no longer dread folding socks. In fact, today I asked J.D. (my 8 year old son) to help me fold some laundry. I dumped a basked of socks in front of him and said, “Fold these.” He had given up before he even started. Then I grabbed about six socks, and said, “How about you just fold these, would that be easier?” He agreed and didn’t have a problem with folding just six of them. Then I took the opportunity to teach my kid about divide and conquer, and he actually seemed to enjoy it. After we did the socks together, I grabbed another basket of his and his brother’s clothes, dumped them in front of them, and asked, “Now how are you gonna divide these up?”

Later at dinner, I said to him, “Tell mom what you learned today.” “Divide and conquer!” I felt so proud.

**Update:**

After reading this, Hayden told me I was still doing it inefficiently. She explained to me that I still looked at each sock multiple times before ever categorizing and folding it. When she does it, she goes through each sock once and puts them into the right pile immediately. I wanted to be right, so I told her she is still doing divide and conquer, and that ultimately our strategies had the same running time. But she was right, and I was wrong.

Once you’ve sorted the socks enough times, you already know what piles you’ll end up with. You no longer need a comparison sort, like mine was. In fact, she was doing divide and conquer still, but it was a bucket sort. Her method really is closer to O(n). I guess I have some new sock-folding goals to set my sights on.

## Recent Comments