Lego safe

Keep your geeky gadgets safe!

Project Euler, problem 31

I solved another Project Euler problem today using constraints. The problem was to figure out how many ways you can combine English coins to form £2. Here's the constraint variant.

currency(List, Sum) :-
     List = [N1,N2,N5,N10,N20,N50,N100,N200],
     200 #= N1 + N2 * 2 + N5 * 5 + N10 * 10 + N20 * 20 + N50 * 50 + N100 * 100 + N200 * 200,
     N1 #>= 0, N2 #>= 0, N5 #>= 0, N10 #>= 0,
     N20 #>= 0, N50 #>= 0, N100 #>= 0, N200 #>= 0,
     fd_labeling(List).

ways(Sum, Number) :-
     findall(List, currency(List, Sum), Ways),
     length(Ways).

Note that you have to explicitly inform the solver to use 0 or more coins of each denomination.

Edit: replaced "Sum" with 200 in the currency/2 predicate.

Ljud och ljusspel i Engelska parken

Har ni vägarna förbi Uppsala så måste ni gå och besöka Engelska parken kvällstid nu i november:

A tribute to John Williams

A really impressive four-voice a capella tribute to John Williams:

260 bytes ought to be enough for anyone, right!

I'm approaching the point were I'm just going to assume that Windows is a game-console which can be used to play Grand Theft Auto on, and just ignore the fact that people actually want to use it as a "normal" operating system. If anyone walks in to my office and talks about windows, I'll just look at them with a puzzling look on my face.

What pushed me a little closer this time was that my colleague managed to break out nightly build (just as we're about to build a snapshot for other departments to start using) by checking in a directory. This directory, called "launches", caused Subversion to fail in a checkout step during the nightly build complaining that "The filename or extension is too long". WTF! IDIOTS!

Ubuntu 8.10

I installed Intrepid Ibex this morning on my HP 6710b laptop, and I have to say that I am impressed. It took around an hour (most of the time downloading and installing packages) and after rebooting It Just Worked. One reboot.

It also automatically detected my external monitor automatically (well, I had to switch of the "mirror screens" option in the screen resolutions settings). So now I have three monitors, two for my laptop, and one for my PC. I can use the same keyboard by connecting the PC using Synergy.

I haven't tried any of the new shiny features, such as creating an USB stick with Ubuntu on it, though. (Too bad Emacs still does not come by default with xft font support. I'll just have to get that manually.)

Constraint programming

I've exercises the programming part brain by solving problems at ProjectEuler.net now and then. Has some fun problems which usually don't take too much time to solve (I haven't gotten to the difficult ones yet...). Today I finally got to exercise my knowledge of constraint-programming in Prolog. My master's thesis was about implementing multithreading in Prolog, and my supervisor is a die-hard constraint programmer, so he would never forgive me if I solved the problem by brute force. :-)

The problem in question is Problem 9: find the only Pythagorean triplet {X,Y,Z} such that X + Y + Z = 1000. Here's the constraint solution:

triplet([X, Y, Z]) :-
     X #\= 0, Y #\= 0, Z #\= 0,
     X**2 + Y**2 #= Z**2,
     X + Y + Z #= 1000,
     fd_labeling([X, Y, Z]).

It isn't the shortest solution, but it has a clearness to it which is just amazing. It almost feels like cheating. (If you want to try it, you can use GNU Prolog).