Skip navigation.
Home
Freedom is contagious.

Codeslinger 2010 Winners

Congratulations to Miorel Palii. He solved our 2010 programming problem right at the 2 hour mark winning the title "Fastest Codeslinger 2010". Click the story link to see the code.






Brad from Main Street Softworks presents the $500 Amazon gift certificate to Miorel.

Congratulations also go to Rohit Manokaran. He first solved the problem with C# and then converted the code to C to be the first contestant to present a winning solution with C.






Clinton Collins, GatorLUG President, presents the $200 Amazon gift certificate to Rohit.

Now for the solutions...

Commentary from Miorel on his solution

Since my Perl code is quite ugly (and no, Perl is not ugly by definition -- that's PHP!), I have prepared a commentary to go along with it.

The task was to print out a matrix of 5 rows. There are 6 properties to account for (house number, house color, nationality, pet, drink, cigar) each with 5 possible values, giving 5 ^ 6 = 15625 possible rows. Of these, we have to find the 5 rows that are consistent with all the statements, while using each of the possible values of each property exactly once.

The most naive brute force approach (iterate over all possible combinations) would clearly take too long to run. 15625 choose 5 is on the order of 10^18. Fortunately, the number of solutions we have to try isn't nearly that bad: of the 15625 possible rows many can immediately eliminated. For example, any row matching the red house to anyone other than the British man immediately contradicts the first clue. The real number of possible rows is therefore much smaller. After encoding most of the rules, I was left with only 80 possible rows. I ought to mention that I combined clues 9 and 14 to say that the second house is blue.

I got to this step fairly quickly but then I tried to encode some of the rules about vicinity. This wasn't completely possible when considering a row independently of all others rows, but I was able to represent some information like the Blends smoker is not the water drinker (because we know from clue 15 that they live next to each other). Adding the vicinity rules wasn't all that helpful at this point as it only ended up reducing the number of possible rows to 63. It was also the source of most of my bugs, causing me to think for a while that the clues are inconsistent and start rewriting the working parts of my code. I think I could have saved a lot of time, maybe even as much as an hour, if I didn't try this "improvement" and just moved on to the next step. Oh well.

With less than 100 possible rows, trying all combinations is now tractable. Separating the rows by the house number they correspond to, it's time for five nested loops! A correct solution will enforce the vicinity rules which weren't fully represented before. Also, if at any time any of the properties are duplicated (e.g. we tried to assign the same color to more than one house), we can backtrack immediately.

My final solution prints out the following matrix after about 3 seconds on my laptop:

1 water cat yellow Norwegian Dunhill
2 tea horse blue Danish Blends
3 milk bird red British PallMall
4 coffee fish green German Prince
5 beer dog white Swedish BlueMaster

The code isn't particularly elegant (sorry). It involved significant copying and pasting, and it still contains some artifacts of various other approaches I was trying. But it won me $500, so I can't really complain. Thanks contest organizers, and thanks Main Street Softworks!

#!/usr/bin/perl

use warnings;
use strict;

my @drinks = qw(tea coffee milk water beer);
my @pets = qw(dog bird cat horse fish);
my @colors = qw(red blue yellow green white);
my @countries = qw(British Swedish Danish German Norwegian);
my @cigars = qw(PallMall BlueMaster Dunhill Blends Prince);
my @homes = qw(1 2 3 4 5);

my @pos = ();
for my $drink (@drinks) {
	for my $pet (@pets) {
		for my $color (@colors) {
			for my $country (@countries) {
				for my $cigar (@cigars) {
					for my $home (@homes) {
						push @pos, " $home $drink $pet $color $country $cigar ";
					}
				}
			}
		}
	}
}

our $prop;
my @ans = ();
for(@pos) {
	$prop = $_;
	push @ans, $_ if 1
		&& f( qw(red British) ) != 1
		&& f( qw(dog Swedish) ) != 1
		&& f( qw(tea Danish) ) != 1
		&& f( qw(green coffee) ) != 1
		&& f( qw(PallMall bird) ) != 1
		&& f( qw(yellow Dunhill) ) != 1
		&& f( qw(Prince German) ) != 1
		&& f( qw(BlueMaster beer) ) != 1
		&& f( qw(milk 3) ) != 1
		&& f( qw(Norwegian 1) ) != 1
		&& f( qw(blue 2) ) != 1
		&& f( qw(Blends water) ) < 2
		&& f( qw(Norwegian blue) ) < 2
		&& f( qw(Blends cat) ) < 2
	;
}

my @house1 = grep {/ 1 /} @ans;
my @house2 = grep {/ 2 /} @ans;
my @house3 = grep {/ 3 /} @ans;
my @house4 = grep {/ 4 /} @ans;
my @house5 = grep {/ 5 /} @ans;

for my $house1 (@house1) {
	next unless 6 == uniq($house1);
for my $house2 (@house2) {
	next unless 12 == uniq($house1, $house2);
for my $house3 (@house3) {
	next unless 18 == uniq($house1, $house2, $house3);
for my $house4 (@house4) {
	next unless 24 == uniq($house1, $house2, $house3, $house4);
for my $house5 (@house5) {
	next unless 30 == uniq($house1, $house2, $house3, $house4, $house5);	
	my(@x, @y, $x, $y);
	
	@x = grep {/green/} ($house1,$house2,$house3,$house4,$house5); $x[0] =~ /^ (\d+)/; $x = $1;
	@y = grep {/white/} ($house1,$house2,$house3,$house4,$house5); $y[0] =~ /^ (\d+)/; $y = $1;
	next unless $x == $y - 1;

	@x = grep {/Blends/} ($house1,$house2,$house3,$house4,$house5); $x[0] =~ /^ (\d+)/; $x = $1;
	@y = grep {/cat/} ($house1,$house2,$house3,$house4,$house5); $y[0] =~ /^ (\d+)/; $y = $1;
	next unless abs($x - $y) == 1;

	@x = grep {/horse/} ($house1,$house2,$house3,$house4,$house5); $x[0] =~ /^ (\d+)/; $x = $1;
	@y = grep {/Dunhill/} ($house1,$house2,$house3,$house4,$house5); $y[0] =~ /^ (\d+)/; $y = $1;
	next unless abs($x - $y) == 1;

	my $matrix = "$house1\n$house2\n$house3\n$house4\n$house5\n";
	print $matrix;
}}}}}

sub f {
	my $count = 0;
	for(@_) {
		++$count if $prop =~ / $_ /;
	}
	for my $att (@_) {
		my $good = 0;
		for(@drinks, @pets, @colors, @countries, @cigars, @homes) {
			++$good if $_ eq $att;
		}
		die "$att is bad" if $good != 1;
	}
	return $count;
}

sub uniq {
	local %_ = ();
	for(@_) {
		for(/\S+/g) {
			$_{$_} = 1;
		}
	}
	my @arr = keys %_;
	return scalar @arr;
}

Rohit's C Solution (Compiles with MSVC++)

#include 

        char BRITISH = '0';
        char SWEEDISH = '1';
        char DANISH = '2';
        char NORWEGIAN = '3';
        char GERMAN = '4';

        char RED = '0';
        char BLUE = '1';
        char YELLOW = '2';
        char GREEN = '3';
        char WHITE = '4';

        char TEA = '0';
        char COFFEE = '1';
        char MILK = '2';
        char BEER = '3';
        char WATER = '4';

        char BLENDS = '0';
        char PALL = '1';
        char DUNHILL = '2';
        char PRINCE = '3';
        char BLUE_MASTER = '4';

        char HORSES = '0';
        char BIRDS = '1';
        char DOGS = '2';
        char CATS = '3';
        char FISH = '4';

#define bool int
#define false 0;
#define true 1;

        bool Check(char color[])
        {
			int i;
            bool found = false;
            for (i = 0; i < 5; i++)
            {
                if (i <4 && color[i] == GREEN && color[i + 1] == WHITE) found = true;
                if (i == 4 && !found) return false;
            }
            return true;
        }

        bool Check5(char color[], char nationality[], char beverage[], char cigar[], char pet[])
        {
			int i;
            for (i = 0; i < 5; i++)
            {
                if (nationality[i] == SWEEDISH && pet[i] != DOGS) return false;
                if (cigar[i] == PALL && pet[i] != BIRDS) return false;
                if (color[i] == YELLOW && cigar[i] != DUNHILL) return false;

				//if (cigar[i] == BLENDS && !nextTo(i, I => pet[I] == CATS)) return false;
                //if (pet[i] == HORSES && !nextTo(i, I => cigar[I] == DUNHILL)) return false;
				if (cigar[i] == BLENDS)
				{
					bool found = false;
					if(i+1<5 && pet[i+1] == CATS) found = true;
					if(i-1>=0 && pet[i-1] == CATS) found = true;
					if(!found) return false;
				}
                if (pet[i] == HORSES)
				{
					bool found = false;
					if(i+1<5 && cigar[i+1] == DUNHILL) found = true;
					if(i-1>=0 && cigar[i-1] == DUNHILL) found = true;
					if(!found) return false;
				}
            }
            return true;
        }
/*
        bool nextTo(int i, Func func)
        {
            if(i+1 < 5 && func(i+1)) return true;
            if (i - 1 >= 0 && func(i - 1)) return true;
            return false;
        }*/

        bool Check4(char color[], char nationality[], char beverage[], char cigar[])
        {
			int i;
            for (i = 0; i < 5; i++)
            {
                if (nationality[i] == BRITISH && color[i] != RED) return false;
                if (cigar[i] == BLUE_MASTER && beverage[i]!=BEER) return false;
                if (nationality[i] == GERMAN && cigar[i] != PRINCE) return false;
                //if (cigar[i] == BLENDS && !nextTo(i, I => beverage[I] == WATER)) return false;

                if (cigar[i] == BLENDS)
				{
					bool found = false;
					if(i+1<5 && beverage[i+1] == WATER) found = true;
					if(i-1>=0 && beverage[i-1] == WATER) found = true;
					if(!found) return false;
				}

            }
            return true;
        }

        bool Check3(char color[], char nationality[], char beverage[])
        {
			int i;
            //display(new string(color) + " " + new string(nationality) + " " + new string(beverage));
            for (i = 0; i < 5; i++)
            {
                if (nationality[i] == DANISH && beverage[i] != TEA) return false;
                if (color[i] == GREEN && beverage[i] != COFFEE) return false;
                if (i == 2 && beverage[i] != MILK) return false;
            }


            return true;
        }

        bool Check2(char color[], char nationality[])
        {
			int i;
            for (i = 0; i < 5; i++)
            {
                if (nationality[i] == BRITISH && color[i] != RED) return false;
                if (nationality[i] == NORWEGIAN && i!=0) return false;
                //if (nationality[i] == NORWEGIAN && !nextTo(i, I => color[I] == BLUE)) return false;
                if (nationality[i] == NORWEGIAN)
				{
					bool found = false;
					if(i+1<5 && color[i+1] == BLUE) found = true;
					if(i-1>=0 && color[i-1] == BLUE) found = true;
					if(!found) return false;
				}
            }

            return true;
        }

		char* rotate(char *s, int pos)
        {
            int start = 5 -1 - pos;
            char ch = s[start];
			int i;

            for (i = start; i < 5 - 1; i++)
            {
                s[i] = s[i + 1];
            }
            s[5 - 1] = ch;

            return s;
        }

        char* permute(char *s, int pos)
        {
            if (pos == 0) return s;

//            Console.Write(new string(s));
            rotate(s, 1);
//            Console.Write(" -> " + new string(s));
            if (pos % 2 == 0)
            {
                rotate(s, 2);
//                display( " -> " + new string(s));
            }
//            else display();
            if (pos % 6 == 0) rotate(s, 3);
            if (pos % 24 == 0) rotate(s, 4);    

            return s;
        }


		void display(char * str)
		{
			printf(str);
			printf("\n");
		}

        void main()
        {
            char _color[] = "01234";
            char _nationality[] = "01234";
            char _beverage[] = "01234";
            char _cigar[] = "01234";
            char _pet[] = "01234";
			int color, nationality, beverage, cigar,pet;



            for (color = 0; color < 120; color++)
            {
                permute(_color, color);

                //display(color);

                if (!Check(_color)) continue;

                for (nationality = 0; nationality < 120; nationality++)
                {
                    permute(_nationality, nationality);

                    if (!Check2(_color, _nationality)) continue;

                    for (beverage = 0; beverage < 120; beverage++)
                    {
                        permute(_beverage, beverage);

                        if (!Check3(_color, _nationality, _beverage)) continue;

                        //display(new string(_color) + " " + new string(_nationality) + " " + new string(_beverage));

                        for (cigar = 0; cigar < 120; cigar++)
                        {
                            permute(_cigar, cigar);

                            if (!Check4(_color, _nationality, _beverage, _cigar)) continue;

                            for (pet = 0; pet < 120; pet++)
                            {
                                permute(_pet, pet);

                                if (!Check5(_color, _nationality, _beverage, _cigar, _pet)) continue;

                                display(_nationality);
                                display(_color);
                                display(_beverage);
                                display(_cigar);
                                display(_pet);
                            }
                        }
                    }
                }
            }
        }
AttachmentSize
miorelpaliisolution.pl_.txt2.74 KB
rohitmanokaransolution.c.txt7.03 KB

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.
clintc's picture

Narendran Sivasubramanian was very close with this solution in C

Narendran was struggling to find a logic error in his code and worked it out within 1 minute of Rohit calling for the judges to look at his solution. It was very close.

#include 
/*
h[row][column]: Has the corresponding arrangement
row:  House Number
column:
0 - Nation
1 - Color of House
2 - Beverage
3 - Cigarette
4 - Pet

used[i][j]: Denotes 1 if the number i is used in the column j or if not used has -1

Algorithm:
	DFS with Back Tracking.

Nation :
0 - Britain
1 - Sweden
2 - Danish
3 - Norway
4 - German

Color:
0 - Red
1 - Green
2 - White
3 - Yellow
4 - Blue

Beverage:
0 - Tea
1 - Coffee
2 - Milk
3 - Beer
4 - Water

Cigaratte
0 - Pall Mall
1 - Dunhills
2 - Blends
3 - Blue Master
4 - Prince

Pet:
0 - Dog
1 - Bird
2 - Cats
3 - Horse
4 - Fish
*/
int h[5][5],used[5][5];
void print(int k) {
	int i,j;
	for(i=0;i<5;i++) {
		for(j=0;j<5;j++) {
			printf("%d ",h[i][j]);
		}
		printf("\n");
	}
	return;
}
int valid(int x) {
	int i,yes=0;
	for(i=0;i<5;i++) {
		//1
		if(h[i][0]==0 && (h[i][1]!=0 && h[i][1]!=-1)) return 0;
		//2
		if(h[i][0]==1 && (h[i][4]!=0 && h[i][4]!=-1)) return 0;
		//3
		if(h[i][0]==2 && h[i][2]!=0 && h[i][2]!=-1) return 0;
		//4
		if(h[i][1]==1) {
			yes=0;
			if(i+1<=4 && (h[i+1][1]!=2 && h[i+1][1]!=-1)) yes++;
			if(i+1>4)yes++;
			if(yes>=1) return 0;
		}
		//5
		if(h[i][1]==1 && h[i][2]!=1 && h[i][2]!=-1) return 0;
		//6
		if(h[i][3]==0 && h[i][4]!=1 && h[i][4]!=-1) return 0;
		//7
		if(h[i][1]==3 && h[i][3]!=1 && h[i][3]!=-1) return 0;
		//8
		if(h[2][2]!=2 && h[2][2]!=-1) return 0;
		//9
		if(h[0][0]!=3 && h[0][0]!=-1) return 0;
		//10
		if(h[i][3]==2) {
			yes=0;
			if(i+1<=4 && (h[i+1][4]!=2 && h[i+1][4]!=-1)) yes++;
			if(i>0 && (h[i-1][4]!=2 && h[i-1][4]!=-1)) yes++;
			if(i<=0) yes++;
			if(i+1>4)yes++;
			if(yes>1) return 0;
		}
		//11
		if(h[i][4]==3) {
			yes=0;
			if(i+1<=4 && (h[i+1][3]!=1 && h[i+1][3]!=-1)) yes++;
			if(i>0 && (h[i-1][3]!=1 && h[i-1][3]!=-1)) yes++;
			if(i<=0) yes++;
			if(i+1>4)yes++;
			if(yes>1) return 0;
		}
		//12
		if(h[i][3]==3 && h[i][2]!=3 && h[i][2]!=-1) return 0;
		//13
		if(h[i][0]==4 && h[i][3]!=4 && h[i][3]!=-1) return 0;
		//14
		if(h[i][0]==3) {
			yes=0;
			if(i+1<=4 && (h[i+1][1]!=4 && h[i+1][1]!=-1)) yes++;
			if(i>0 && (h[i-1][1]!=4 && h[i-1][1]!=-1))yes++;
			if(i<=0) yes++;
			if(i+1>4) yes++;
			if(yes>1) return 0;
		}
		//15
		if(h[i][3]==2) {
			yes=0;
			if(i+1<=4 && (h[i+1][2]!=4 && h[i+1][2]!=-1)) yes++;
			if(i>0 && (h[i-1][2]!=4 && h[i-1][2]!=-1)) yes++;
			if(i<=0) yes++;
			if(i+1>4) yes++;
			if(yes>1) return 0;
		}
	}
	return 1;
}
void dfs(int x) {
	int i,j,k;
	if(!valid(x)) return;
	if(x>=25) {print(x); return;}
	i=x/5; j=x%5;
	for(k=0;k<5;k++)
		if(used[k][j]==-1) {
			used[k][j]=1;
			h[i][j]=k;
			dfs(x+1);
			h[i][j]=-1;
			used[k][j]=-1;
		}
	return;
}
int main() {
	int i,j;
	for(i=0;i<5;i++) 
		for(j=0;j<5;j++)
			h[i][j]=-1,used[i][j]=-1;
	dfs(0);
	printf("Done\n");
	getch();
    return 0;
}
clintc's picture

Haskell Solutions to Codeslinger 2010

Attached are two haskell implementations for the contest problem. The Haskell team came in second place overall - about 20 minutes after the winning perl solution.

contest.hs is the implementation written during the contest by Brian Lewis and Ian Taylor.

tiny.hs is a haskell implementation based on code out on the net
(might be interesting to some).

contest.hs

import Data.List

data Position = First | Second | Third | Fourth | Fifth deriving (Eq,Enum,Show)
data Nationality = German | Norwegian | Danish | Swedish | British deriving (Eq,Enum,Show)
data Color = Red | Green | Blue | Yellow | White deriving (Eq,Enum,Show)
data Cigar = PallMall | Dunhill | Blends | Prince | BlueMaster deriving (Eq,Enum,Show)
data Drink = Tea | Coffee | Milk | Beer | Water deriving (Eq,Enum,Show)
data Pet = Dogs | Birds | Cats | Horses | Fish deriving (Eq,Enum,Show)

type Possibility = (Nationality,Color,Cigar,Drink,Pet,Position)
type Answer = (Possibility,Possibility,Possibility,Possibility,Possibility)

possibleAnswers :: [Answer]
possibleAnswers =
    [
      ( (British   , Red , ci1    , dr1 , pe1  , po1)
      , (German    , co1 , Prince , dr2 , pe2  , po2)
      , (Norwegian , co2 , ci2    , dr3 , pe3  , First)
      , (Danish    , co3 , ci3    , Tea , pe4  , po3)
      , (Swedish   , co4 , ci4    , dr4 , Dogs , po4)
      )
    | [co1,co2,co3,co4] <- permutations [Green,Blue,Yellow,White]
    , [ci1,ci2,ci3,ci4] <- permutations [PallMall,Dunhill,Blends,BlueMaster]
    , [dr1,dr2,dr3,dr4] <- permutations [Coffee,Milk,Beer,Water]
    , [pe1,pe2,pe3,pe4] <- permutations [Birds,Cats,Horses,Fish]
    , [po1,po2,po3,po4] <- permutations [Second,Third,Fourth,Fifth]
    ]

answers :: [Answer]
answers =
    [ p
    | p <- possibleAnswers
    , rule6 p
    , rule8 p
    , rule9 p
    , rule7 p
    , rule12 p
    , rule5 p
    , rule13 p
    , rule4 p
    , rule15 p
    , rule14 p
    , rule11 p
    , rule10 p
    ]

isInAnswer :: (Possibility -> Bool) -> Answer -> Bool
isInAnswer f (a,b,c,d,e) = any f [a,b,c,d,e]

isNextTo :: (Possibility -> Bool) -> (Possibility -> Bool) -> Answer -> Bool
isNextTo f g (a,b,c,d,e) = isAdjTo f g (a,b,c,d,e) || isAdjTo g f (a,b,c,d,e)

isAdjTo :: (Possibility -> Bool) -> (Possibility -> Bool) -> Answer -> Bool
isAdjTo f g (a,b,c,d,e) =
     any
       (\(x,y) -> adj x y && f x && g y)
       [(a,b),(a,c),(a,d),(a,e),(b,c),(b,d),(b,e),(c,d),(c,e),(d,e)]
   where
     adj (_,_,_,_,_,p1) (_,_,_,_,_,p2) = ((fromEnum p2) - (fromEnum p1)) == 1

rule1 a = isInAnswer p a
  where
    p (British,Red,_,_,_,_) = True
    p _ = False

rule2 a = isInAnswer p a
  where
    p (Swedish,_,_,_,Dogs,_) = True
    p _ = False

rule3 a = isInAnswer p a
  where
    p (Danish,_,_,Tea,_,_) = True
    p _ = False

rule4 a = isAdjTo f g a
  where
    f (_,Green,_,_,_,_) = True
    f _ = False
    g (_,White,_,_,_,_) = True
    g _ = False

rule5 a = isInAnswer p a
  where
    p (_,Green,_,Coffee,_,_) = True
    p _ = False

rule6 a = isInAnswer p a
  where
    p (_,_,PallMall,_,Birds,_) = True
    p _ = False

rule7 a = isInAnswer p a
  where
    p (_,Yellow,Dunhill,_,_,_) = True
    p _ = False

rule8 a = isInAnswer p a
  where
    p (_,_,_,Milk,_,Third) = True
    p _ = False

rule9 a = isInAnswer p a
  where
    p (Norwegian,_,_,_,_,First) = True
    p _ = False

rule10 a = isNextTo f g a
  where
    f (_,_,Blends,_,_,_) = True
    f _ = False
    g (_,_,_,_,Cats,_) = True
    g _ = False

rule11 a = isNextTo f g a
  where
    f (_,_,_,_,Horses,_) = True
    f _ = False
    g (_,_,Dunhill,_,_,_) = True
    g _ = False

rule12 a = isInAnswer p a
  where
    p (_,_,BlueMaster,Beer,_,_) = True
    p _ = False

rule13 a = isInAnswer p a
  where
    p (German,_,Prince,_,_,_) = True
    p _ = False

rule14 a = isNextTo f g a
  where
    f (Norwegian,_,_,_,_,_) = True
    f _ = False
    g (_,Blue,_,_,_,_) = True
    g _ = False

rule15 a = isNextTo f g a
  where
    f (_,_,Blends,_,_,_) = True
    f _ = False
    g (_,_,_,Water,_,_) = True
    g _ = False

printAnswer (a,b,c,d,e) = mapM_ print [a,b,c,d,e]

main :: IO ()
main = mapM_ printAnswer answers

tiny.hs

import Data.List
import Data.Maybe (fromJust)

-- Based on the tiny implementation of
-- Remco Niemeijer
-- http://bonsaicode.wordpress.com/2009/06/22/who-owns-the-zebra-reloaded/

indexOf :: Eq a => [a] -> a -> Int
indexOf xs x = fromJust $ elemIndex x xs

options :: String -> [[String]]
options = permutations . words

nextTo :: Int -> Int -> Bool
nextTo a b = abs (a - b) == 1

leftOf :: Int -> Int -> Bool
leftOf a b = a+1 == b

solve :: [[String]]
solve = head
    [ transpose [na,sm,dr,pe,co]
    | co <- options "Red Green Blue Yellow White"
    , let houseColor = indexOf co
    , houseColor "Green" `leftOf` houseColor "White" -- 4
    --
    , na <- options "German Norwegian Danish Swedish British"
    , let nationality = indexOf na
    , nationality "British" == houseColor "Red" -- 1
    , nationality "Norwegian" == 0 -- 9
    , nationality "Norwegian" `nextTo` houseColor "Blue" -- 14
    --
    , sm <- options "PallMall Dunhill Blends Prince BlueMaster"
    , let smokes = indexOf sm
    , nationality "German" == smokes "Prince" -- 13
    , houseColor "Yellow" == smokes "Dunhill" -- 7
    --
    , dr <- options "Tea Coffee Milk Beer Water"
    , let drinks = indexOf dr
    , houseColor "Green" == drinks "Coffee" -- 5
    , drinks "Milk" == 2 -- 8
    , smokes "BlueMaster" == drinks "Beer" -- 12
    , smokes "Blends" `nextTo` drinks "Water" -- 15
    , nationality "Danish" == drinks "Tea" -- 3
    --
    , pe <- options "Dogs Birds Cats Horses Fish"
    , let hasPet = indexOf pe
    , hasPet "Horses" `nextTo` smokes "Dunhill" -- 11
    , smokes "Blends" `nextTo` hasPet "Cats" -- 10
    , nationality "Swedish" == hasPet "Dogs" -- 2
    , smokes "PallMall" == hasPet "Birds" -- 6
    ]  

main :: IO ()
main = mapM_ (putStrLn . intercalate ", ") solve
clintc's picture

Robert Munyer solves codeslinger 2010 with lisp

From Robert:

It took me 1 hour and 33 minutes (but of course I can't know how much longer
it would have taken, under the stress of actual competition).

It takes 2 seconds to compile and run, on a circa 1999 IBM ThinkPad.

output:

The German owns the fish.

Yellow    Blue      Red       Green     White
Norwegian Danish    British   German    Swedish
Water     Tea       Milk      Coffee    Beer
Dunhill   Blends    Pall Mall Prince    Blue Master
Cats      Horses    Birds     Fish      Dogs

code:

(defun perm5 (in)
  (let ((out))
    (dolist (a in)
      (dolist (b in)
        (dolist (c in)
          (dolist (d in)
            (dolist (e in)
              (let ((x (list a b c d e)))
                (if (= 5 (length (remove-duplicates x)))
                  (push x out))))))))
    out))

(defparameter *colors*
  (remove-if-not #'(lambda (perm)
                     (and (eq 'blue (second perm))
                          (= 1 (- (position 'white perm)
                                  (position 'green perm)))))
    (perm5 '(red green white yellow blue))))

(defparameter *nations*
  (remove 'norwegian
          (perm5 '(british swedish danish norwegian german))
          :test-not #'eq
          :key #'first))

(defparameter *drinks*
  (remove 'milk
          (perm5 '(tea coffee milk beer water))
          :test-not #'eq
          :key #'third))

(defparameter *smokes*
  (perm5 '(pall\ mall dunhill blends blue\ master prince)))

(defparameter *pets*
  (perm5 '(dogs birds cats horses fish)))

(dolist (smoke *smokes*)
  (dolist (pet *pets*)
    (if (and (eq (nth (position 'pall\ mall smoke) pet) 'birds)
             (= 1 (abs (- (position 'blends  smoke)
                          (position 'cats    pet  ))))
             (= 1 (abs (- (position 'horses  pet  )
                          (position 'dunhill smoke)))))
      (dolist (drink *drinks*)
        (if (and (eq (nth (position 'blue\ master smoke) drink) 'beer)
                 (= 1 (abs (- (position 'blends smoke)
                              (position 'water  drink)))))
          (dolist (nation *nations*)
            (if (and (eq (nth (position 'swedish nation) pet  ) 'dogs  )
                     (eq (nth (position 'danish  nation) drink) 'tea   )
                     (eq (nth (position 'german  nation) smoke) 'prince))
              (dolist (color *colors*)
                (if (and (eq (nth (position 'british nation) color) 'red    )
                         (eq (nth (position 'green   color ) drink) 'coffee )
                         (eq (nth (position 'yellow  color ) smoke) 'dunhill))
                  (format t "~2%The ~~a~) owns the fish.~@
                             ~~{~%~{~10a~}~}~)~2%"
                         (nth (position 'fish pet) nation)
                         (list color nation drink smoke pet)))))))))))

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.