On October 1st, 2016 my dad and I are going to be running the first ever Botgeddon event. It’s happening at the Rocklin Mini Maker at Sierra River College. For more information, go to http://botgeddon.com.

Last weekend, OkCupid has launched CrazyBlindDate, which is a website that allows you to go on blind dates with people in your area. There have already been a few discussions about it on Hacker News and other websites, so I’m not going to discuss the web site itself because most of those conversations have already been talked about.

I checked out the site after getting an invitation in my inbox. On the landing page it presents you a list of people that you could go on a blind date with, which showed their first name, date and time of the date, a location, and a scrambled picture of the person. The reason a date is considered blind is because you don’t know anything about your date, or what they look like. Providing minimal details about them is a good way to do this, and having some sort of picture of them to see that they are a real person.

At first glance, I thought the picture was generated from multiple pictures and selected for parts of the picture that had the person’s face on it somehow. Upon closer inspection, I realized that the sub-pictures seemed to be connected somehow, and suspected that it was probably a form of a 15-puzzle and it would be pretty easy to unscramble. After trying it out manually in paint.net, I was able to unscramble one of the pictures within a few minutes. Most of the time was spent trying to figure out how to get it to split the image into 16 layers that I could individually drag around.

At this point, since I’m a programmer, I wondered how hard it would be to write a program automatically figure out how to arrange them. I fired up Visual Studio and started a new project. The first step would be to get the images and split them into their 16 separate image parts. This ended up being fairly simple after figuring out how to use the imaging library in WPF since I haven’t used it in a while.

var bmpImg = new BitmapImage(new Uri(baseFileName, UriKind.Absolute));
var baseImage = BitmapFactory.ConvertToPbgra32Format(bmpImg);

int pieceHeight = (int)(baseImage.Height / 4);
int pieceWidth = (int)(baseImage.Width / 4);

for (int x = 0; x < 4; x++)
{
for (int y = 0; y < 4; y++)
{
var bmp = BitmapFactory.New(pieceHeight, pieceWidth);
bmp.Blit(new Rect(0, 0, pieceWidth, pieceHeight), baseImage, new Rect(x * pieceWidth, y * pieceHeight, pieceWidth, pieceHeight));
imagePieces.Add(bmp);
}
}

The next step was to figure out how related each tile was to the other ones. To do this, I took each pair of images and calculated the average color difference between the pixels that would be adjacent to each other if it was the correct placement. In the code snippet below, a is to the left of b, so using the far right pixels of a and the far left pixels of b. The idea for this is that if you took adjacent pixels in the original image, they should be close in color for the most part, unless they were part of a sharp edge, which shouldn’t happen too often.

foreach (var a in Enumerable.Range(0, imagePieces.Count))
{
foreach (var b in Enumerable.Range(0, imagePieces.Count))
{
var aImg = imagePieces[a];
var bImg = imagePieces[b];
leftRightScores[new Tuple<int, int>(a, b)] = Enumerable.Range(0, pieceHeight)
.Average(i => ColorDiff(aImg.GetPixel(pieceWidth - 1, i), bImg.GetPixel(0, i)));
}
}

After this was done, the goal is now to place the 16 tiles in the correct arrangement, which would be the one without any errors caused by having a tile next to one that wasn’t its correct neighbor. I thought about using brute force to figure the best score from all of the possibilities, but realized that there were 16! ~= 20,900,000,000,000 combinations, which is more than is feasible to do. This means I need to turn to a heuristic.

My first try was to be greedy and place a random tile initially in the middle of a larger grid (9×9), and then pick the tile that matches best with that one next to it, and then repeat until all the tiles have been placed. Unfortunately, that didn’t work very well.

My next idea was to use a recursive search algorithm that was able to prune large subsets of the search tree out, like the common solution to the Eight Queen’s Problem we had to do in one of the computer science classes I took at college. Basically, you recursively try to place each piece in the next available slot, and stop trying if there are too many errors. Some simplified code for this is below (note that this is missing some variables that are passed in to make it simpler in this post)

private double RecursiveSolver(IList remaining, int[,] fullMap)
{
var score = Evaluate(fullMap);

if (score < THRESHOLD || !remaining.Any()) return score; double alpha = double.MaxValue; int[,] best = null; foreach (var next in remaining) { var mapCopy = (int[,])fullMap.Clone(); mapCopy[x, y] = next; double s = RecursiveSolver(remaining.Where(i => i != next).ToList(), mapCopy);
if (s < alpha)
{
alpha = s;
best = mapCopy;
}
}

for (int xx=0; xx<4; xx++)
for (int yy=0; yy<4; yy++)
fullMap[xx, yy] = best[xx, yy];

return alpha;
}

The threshold variable above is the only thing that needed tweaking. I tried doing it manually by hand, but if it was too large, then it would never finish since there were so many paths to take. If the number was too low, then it would finish really fast but with no solutions. To fix this, I dynamically determine what the threshold should be by starting with a small threshold, and gradually increase it until the algorithm finishes. I got the idea for this from iterative deepening, but it’s not quite the same process.

double beta = 0.000001;
do
{
fullMap = new int[4,4] { ... }; // initialized to -1
RecursiveSolver(Enumerable.Range(0, 16).ToList(), fullMap, beta);
beta *= 1.05;
}
while (!FullyDone(fullMap));

And finally, with all of this, I have some reconstructed images.

As you can see, some of them didn’t work right, since the images had a solid colored border, which the algorithm thought were perfect matches. If I were going farther, I would try to fix this, but as you can see, it does a pretty good job of reconstructing the images. Note that I’ve blurred out their faces to protect their identities.

I’m not entirely sure what I think about having done this, but it does make me personally feel less likely to use the service since I know that I can see their pictures, and that kind of defeats the purpose of it being a blind date if I can use their picture to select which ones I am interested in.

The source code is available on github for those that are interested.

I just got back from the BattleBots event this past weekend. It was pretty fun, and I got to see a few good fights, but it was somewhat stressful to have to run the brackets for the 15lb robots. On the plus side, they allowed recording of the 15lb weight class, so I got a few good fights, which I will put on youtube, like this fight of Blender Mini and a vertical spinner (I think it was exterminator). I hadn’t planned on going, but Marc Devidts mentioned that BattleBots needed someone to manage the brackets, so I figured I could help out. I must say that given the choice, I would much rather help out at RoboGames, since there isn’t a high-wired tv production crew in charge of things, and there are a lot more people that get to enjoy the fights.

When I got back home on Saturday, my dad had come to my house and surprised me by finishing up the decoration for my projector room. It’s been a long time coming, but I’m glad it’s finally finished, except for a few minor tweaks, like getting speaker stands and covering over the windows so they don’t shine through the curtains in the day.

Next on my list of things to do is the RoboGames event. I’d like to finish up the new version of Emsee Frypants for it, as well as make some tweaks to our Sentry Gun (like getting a new frame that doesn’t weigh 90 pounds).

Over this weekend, Joe and I decided at the last minute to take the carcass of Emsee Frypants and fix it up enough to be able to compete at the Fifth annual Smackdown in Sactown event. We were going to be there anyways since I was running the brackets, and we wanted to bring the Sentry Guns and our 30 pound robot to the event, and figured it’d be fun to take Frypants back for one last spin (no pun intended).

Fry me a River

I Also decided to throw together an all-new robot, which I decided to name Pretty Fry for a White Guy (which didn’t actually end up competing). It was a series of bad things that happened Saturday night, and I kept Joe up really late to build it (sorry). Primarily, the problem was my machining abilities, or rather, lack thereof. On top of that, I was having receiver issues, brushless motor controller problems, and brushed motor controller issues. I borrowed a new brushless controller at the event, and decided to run it with only one wheel working. However, as soon as it got in the arena the receiver freaked out and the weapon motor got stuck on and it was out of control in the arena. It ended up losing one of the brushless motor screws, and overheating the motor a little bit (I think it’s fine though), so I didn’t end up getting to compete with it. The robot wasn’t very competitive, anyway.

Frypants & Trophie

Joe decided that, since he rebuilt it, he got to drive it. Normally I would disagree, but I figured why not, so he ended up driving it. In an unlucky first round matchup, Frypants ended up facing what I thought was the robot to beat at the event, Rector. After a minute or so, Rector was mostly disabled: the parts of the robot that were supposed to be inside weren’t inside anymore. However, he was still able to move a little bit, and Frypants knocked himself into the edge of the pit on the final hit, and was unable to recover. Joe drove valiantly through the remainder of the losers bracket and ended up winning the event. Driving Frypants isn’t the most difficult thing to do, I mean, point the dangerous bits at the other robot, and drive towards them; however, there are definitely hazards of driving in the Sacramento State arena with a weaponed robot (namely don’t knock yourself into the pit), and he did a good job of driving, so I commend him for that.

You can read Joe’s report of the event at his web site.

I don’t mean to keep posting funny videos, but check out this trailer for a Norweigan zombie movie. One question I have though is why do the zombies run so fast. I’m calling zombie bull on that!