Icosian game

The Irish mathematician William Rowan Hamilton is probably best known for discovering quaternions. He is also the inventor of the Icosian game.

The game’s objective is to find a path around a dodecahedron such that every vertex is visited once, no edge is visited multiple times, and the path ends in de same vertex it started from. Instead of using a 3d dodecahedron, the game was distributed as a pegboard with holes at the vertices of the 2d dodecahedral graph.

The game was meant to be played by two people. The first player would set up the challenge by placing the first five pegs in any five consecutive holes and then the second player would be required to place the remaining fifteen pegs consecutively in such a way that the succession would be cyclical.

One of the few remaining copies (from the collection of the puzzle museum)

In graph theory, a path that visits every vertex of a graph once is now known as a Hamiltonian path. A path that visits every vertex once and that ends in the same vertex as it started off from is called a Hamiltonian cycle. So playing this game is essentially searching for a Hamiltonian cycle in the dodecahedral graph.

The Icosian game was never a commercial success, probably because it’s too easy. I wrote some Prolog code to solve this game and explore possible solutions. Entering solve_icosian_puzzle. and pressing ; repeatedly will yield possible solutions.

Suppose you want to explore how the cycle that starts with the vertices Q, R, S, N, P could be continued, you would enter:

icosian_puzzle_edges(Adj), Tour = [q,r,s,n,p|Rest], hamiltonian_cycle(Adj,Tour), print_icosian_solution(Tour).

This game might remind you of the Travelling Salesman Problem (TSP). Finding a Hamiltonian cycle can be considered a special case of the TSP, namely, one where each pair of vertices with an edge between them has distance 1, while vertex pairs without an edge between them are separated by a distance of infinity.

Bart the bartender

I just released a new chatbot called Bart on the Facebook Messenger platform. It can help you find cocktail recipes, tells jokes, and engages in smalltalk.

Check out the video below or chat with Bart here http://m.me/bart.the.bartender. Be sure to like its Facebook page https://www.facebook.com/bart.the.bartender!

The dialogflow.com platform takes care of intent classification and named-entity recognition. The chatbot uses TheCocktailDB to search for recipes. The dialogue manager, a Prolog program that runs on my VPS, handles the state and flow of the conversation. It’s the same dialogue manager that I also used in other chatbots like Dr. Stat.

Supercharging the Nabaztag

The Nabaztag is a WiFi enabled ambient device shaped like a bunny. It has moveable ears, a speaker, several LEDs, and a button on its head. The second generation (the one I have) also has a microphone, an RFID sensor, and supports MP3 audio streams.

These Nabaztag bunnies rely on a server to function. Originally the company that produced these things provided for one but after they went bankrupt in 2009, thousands of these devices were rendered useless.

Luckily, various alternative servers were developed. These servers often make use of plugins to give the connected bunnies certain abilities. Extending your bunny with new capabilities requires some programming skills if there is no existing plugin that already does what you want.

I developed my own Nabaztag server in Prolog that you can download from this repository. Instead of making use of plugins to extend a Nabaztag’s capabilities, my server simply forwards all events to an IFTTT webhook. The server also exposes an API to do things like play audio, flash LEDs, move the ears, do TTS, etc. This API can be called from the IFTTT platform.

Continue reading →

Dr. Stat

This is a demo of my chatbot called Dr. Stat.

It can answer questions about statistics and help a user select an appropriate statistical technique.

I’ve been working on this for quite a while now. Chatbots certainly aren’t anything new, but chatbots that are useful and display a more ‘natural’ way of conversing are rare.

I chose the domain of statistics for two reasons. Firstly, many of my students (and researchers I know) struggle with statistical concepts and I wanted to create something that would make their lives easier. Secondly, this domain has proven to be suitable for trying out different ideas about dialogue management.

Read on for a transcript with annotations.

Continue reading →

Skyline puzzle

One of my coworkers brought the following puzzle to work:

The puzzle is called Skyline and it’s a packing puzzle. The objective is to place the metal rod in one of the holes in the base and place the nine wooden pieces around it. It was designed by Jean Claude Constantin. When solved, the puzzle looks something like this:

Sometimes with these kinds of puzzles it’s quicker to write a program that finds a solution than trying to solve it by hand. Check out this github repository for a Prolog program that finds solutions for a given rod location.

To use this program open the file skyline.pl in your favorite Prolog interpreter (e.g. SWI-Prolog) and execute the following:

?- print_solution(pos(4,4)).
+-------+
|ggeeeeh|
|gggdehh|
|ggiddhh|
|iii ddh|
|iiicfff|
|bicccff|
|baaaaaf|
+-------+
true

You can press ; to find alternative solutions. The pos(X,Y) part refers to the location of the metal rod.

MLP in C++11

In this post I present my Christmas gift to the world: A multilayer perceptron written in C++11.

I mainly wrote this to get some practice with some of the new C++11 features such as variadic templates and lambda functions. It uses template metaprogramming to construct (but not train) the neural network at compile time. You can download the code from its github repository. It’s lacking proper documentation, but I’ve included two examples that should get you started: the xor problem and Fisher’s Iris data set.

Happy Holidays.

Win32 PPlot

A while ago I was looking for a simple lightweight C++ library that could produce some basic charts. I found the PPlot library which easily integrates with different GUI toolkits and also comes with bindings for Ruby and Python. To make the library usable with different GUI frameworks the drawing part has been abstracted to a Painter class. For each GUI framework a different Painter class must be implemented. The library comes with ready made implementations for GUI toolkits like wxWidgets and Qt. However, I wanted to use the PPlot library in a pure Win32 application and had to implement my own Painter class. Check out the result here.

Chip-8 emulator

I’ve always been interested in emulators and just finished my Chip-8/SCHIP emulator. Chip-8 is an interpreted programming language that was first used on some early homecomputers and later on the HP48 calculator. The emulator allows you to play some retro games like pong and invaders.

The emulator is written in C++ and is available for download here. Besides the program and source code I’ve also included some games that seem to work OK. The original machines that ran a chip-8 interpreter had a 16 key hex-keypad that looked like this:

1 2 3 C
4 5 6 D
7 8 9 E
A 0 B F

This keypad is emulated on the PC keyboard like this:

1 2 3 4
Q W E R
A S D F
Z X C V

Happy gaming!

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.

Checkers game

Long, long time ago, when I was still a full time student, I became first in a checkers tournament with a program I wrote. Alas, those days of glory are over.

Looking back, the program was pretty simple. Choosing an efficient board representation made generating the moves a piece of cake. My program didn’t make use of any opening libraries or endgame strategies, it just implemented minimax search with alpha-beta pruning.

Although my program wasn’t very sophisticated, I still think it was pretty sweet and felt disappointed when I realized I had lost the source code. That’s why I decided to implement this game again only this time in Java (the original was written in C++). Check out my code here.