Self-organizing bookcase

This is what my bookcase looked like before:

Books unsorted

And this is what it looks like now:

Books sorted

Much better!

So how does a geek organize his books? He uses a technique called self-organizing maps (SOM).

I basically took a high resolution photo of my bookcase (the first picture shown) and then cut out all the book spines and saved them as separate images.¬†After doing that I had 347 little images. I used the ImageMagick command-line tool to resize all these images to a 1×1 picture. I figured that the single pixel in these images would more or less approximate the average spine color. The RGB values of these pixels were then used to train a 1 dimensional SOM. After training, the best-matching unit on the SOM for each bookspine was determined telling me how I should reorder my books.

And yes, I realize that there are easier ways to sort books by color ūüėČ

Queen’s Day

The eight queens puzzle is the problem of placing eight chess queens on an¬†8×8 chessboard such that none of them are able to capture any other using the standard chess queen’s moves. This puzzle can be generalized to the problem of placing n queens on a nxn chessboard. This c++ program¬†finds solutions to this problem using a recursive backtracking algorithm.

Binary is the new Sudoku

A couple of days ago somebody sent me an e-mail asking if I could write a program that generates binary puzzles. I didn’t know what binary puzzles were, but a search in google quickly led me to this site. Apparently, the “Binary”¬†is a new kind of logic puzzle that involves only the numbers zero and one.

The goal is to fill in the grid with zeros and ones with the following restrictions:

  • There are as many zeros as ones in every row and every column.
  • No more than two of the same numbers can be next to or under each other.
  • Rows or columns with the same content are not allowed.

Every puzzle has a unique solution, which in this case is:

The program I wrote uses the following algorithm to generate new puzzles. First it fills a grid with random zeros and ones in such a way that all restrictions apply. Then it removes numbers randomly while making sure that the puzzle maintains exactly one solution. When it has removed the right amount of numbers the puzzle is shown on screen. Click here to download the jar (source files are included) and read on for instructions on how to use the program.

Continue reading

Bridge and torch puzzle

Four people need to cross a bridge at night which only supports two people at the same time. Person A needs 1 minute to cross the bridge, B needs 2 minutes, C needs 5 minutes¬†and D needs 10 minutes. When two people cross the bridge they move at the slowest person’s pace.¬† They have a torch which has battery left for only 17 minutes. They can’t cross the bridge without light. How can they manage to cross the bridge?

One might guess that an obvious solution would be to let the fastest person (A) shuttle each other person over the bridge and return alone with the torch. This would give the following schedule:

A, B -> 2
A <- 1
A,C -> 5
A <- 1
A,D -> 10

The total duration of this schedule would be 19 minutes, so the torch would run out of battery while person A and D are still on the bridge.

The optimal solution consists of letting the two slowest people (C and D) cross the bridge together, giving the following schedule:

A, B -> 2
B <- 2
C,D -> 10
A <- 1
A,B -> 2

Which gives a total crossing time of exactly 17 minutes.

Writing a prolog program to solve this kind of river crossing problems is a walk in the park. Check it out if you want to know an alternative solution.

Mathematician’s Birthday Calendar

In my previous post I described a way of doing web scraping using XPath and VB. I showed how to get stock quotes from the web into Excel using this method. Recently I used the same method to get a list of birthdays of mathematicians. The data was scraped from Wikipedia lemmas like January_1,¬†January_2, etc. looking for lines containing the word “mathematician”. If you’re a math enthusiast you can get the calendar from here. Check out the code if you want to make a similar thing for physicists.