Sunday, December 28, 2014

The Compex Cubes Puzzle

Often during the holidays, I do a little programming project based on something that just strikes my fancy. For example, one year I merged a bunch of dictionaries and then ran the words through DNS to see if they were available as domain names.

This year, my Mother -- Provider of Perfect Presents -- gave one of my sons an interesting puzzle called the "Complex Cube". It has 54 T-shaped wooden parts, each made of 4 unit cubes, and the challenge is to assemble them into a 6x6x6 cube.

I played with it a little bit, and soon got to the point where I realized it might be faster to write a program to analyse the problem, so given that I am a lazy person, I wrote a python script to solve it. It's really pretty simple, you just start at the bottom and scan across the rows and columns in each row, placing blocks in each empty position.

There are some easy optimizations you can do, like realizing there are only 12 possible block rotations you need to try because of assumptions you can make about positions you have already filled in, but the script still took anywhere from 5 minutes to 5 hours to generate a solution, even after doing some cute hacks to make it faster (like not using recursion, but keeping track of things with a state stack).

Then I realized that if I limit the search to solutions that are reflectively symmetric, the search space becomes much smaller, because I'm only solving a puzzle with 27 blocks instead of 54. Solution time goes down to under a minute and the solution looks nicer.

However, the output left a little to be desired...

Level 1
| P I N N N Q |
| L I M N H O |
| E I J K H H |
| E E G F H D |
| E A F F F D |
| A A A B C D |
Level 2
| P P M Z Q Q |
| L I M K X O |
| L J J K X O |
| V W G K X Y |
| T U G B C D |
| R R R B C S |

...and so on. So I got the idea of playing around with the Processing language to see if I could visualize it better. The result was a little script that displays the cube in 3D, lets you rotate and zoom it, and animates the solutions.

Needless to say, it took me twice as long to write the Processing visualization script as it did to write the Python solvers, and it probably took me twice as long to write the solvers as it would have taken to just solve the puzzle by hand.

But then, as I said above, I'm lazy... :)

You can find the scripts here if you'd like to play with them. Processing is built on top of Java and quite fun to play with.

Sunday, September 7, 2014

A Google Apps Sheet for STV Elections

I've been using Google apps like Sheets in my Kickstarter project, but one thing Sheets doesn't do is complex surveys. While you can link a survey to a sheet, the survey question types are pretty basic, and in particular it does not let you do a ranked survey (in other words, "here are N options, pick any number of them that you like and place them in order of preference.")

When I was on the EVE Online Council of Stellar Management, I became quite the election-systems nerd, because I was pushing hard for a reform of the election system. So just for fun, I decided to see if I could implement a Multiple-Choice Ballot in Google Apps.

What I ended up was a sheet with a bunch of embedded scripts that lets you:

  • Create a Multiple-Choice Ballot with optional additional questions (radios, dropdowns and fields) and voter validation.
  • Store the results in a sheet.
  • Export the results in the standard .blt ballot format used by many election systems.
  • And best of all, run the election using the Simple-STV and Wright-STV systems.
You can find the template sheet at Just make a copy of it in your own Google Drive and start playing with it.


Wednesday, February 5, 2014

Clever Combining CSV Files to Cure KickStarter Conundrums

I recently ran a successful KickStarter for a Bubblegum Crisis Ultimate Edition (you can still sign up here), and in the aftermath ran into an annoying problem.

KickStarter lets you run a Backer Survey after the project is funded, and that's how backers tell you things like their names, addresses and so on. A typical KickStarter will have many different "support levels" providing different benefits.

Annoyingly, KickStarter forces you to design a survey format for each individual support level, with no way of cloning surveys. But what really got me steamed was the discovery that when you export the survey results, you get a CSV file for each survey, and the format of that CSV file depends on the items in each individual survey.

That makes it a royal pain in the ass to import the data into your own database -- I mean, I had 38 CSV files, each with its own ordering of fields. Plus given that people take their time filling out the surveys (2 months later and they're still trickling in), I was going to be doing the import multiple times.

To solve this, I wrote a quick little python script,, that reads in an entire directory of CSV files, extracts all the unique field names from them, and then outputs a single file containing all the rows of data, with a column for each unique field. In cases where a row does not have an entry for a particular field, it gets a blank entry. Also, if a file contains multiple columns that have the same name, the data in them is combined into a single column, separated by the | delimiter.

Added: optional count field name; if present, each unique line is emitted only once, with the last field being a count of the number of occurrences. If not present, the source file name is appended.

You can find it here:

You use it like this:

python [source directory] [destination csv file] {optional count field name}


Update: I also whipped up a standalone AllCSV app that does the same thing; available for both Mac and Windows. It does not currently do the occurrence counting.