#include /* There are five houses in five different colours starting from left to right. In each house lives a person of a different nationality. These owners all drink a certain type of beverage, smoke a certain brand of cigarette and keep a certain type of pet. No two owners have the same pet, smoke the same brand or drink the same beverage. The question is: WHO OWNS THE FISH??? Hints: 1. The Brit lives in the red house 2. The Swede keeps dogs as pets 3. The Dane drinks tea 4. The green house is on the left of the white house 5. The green house's owner drinks coffee 6. The person who smokes Pall Mall rears birds 7. The owner of the yellow house smokes Dunhill 8. The man living in the centre house drinks milk 9. The Norwegian lives in the first house 10. The person who smokes Marlboro lives next to the one who keeps cats 11. The person who keeps horses lives next to the person who smokes Dunhill 12. The person who smokes Winfield drinks beer 13. The German smokes Rothmans 14. The Norwegian lives next to the blue house 15. The person who smokes Marlboro has a neigbor who drinks water Solution below by Paul Hsieh (c) 2006 */ #define glue3aux(a,b,c) a##b##c #define glue3(a,b,c) glue3aux(a,b,c) #define decls(ename,prefix,name1,name2,name3,name4,name5) \ enum ename { \ glue3(prefix,_,UNKNOWN) = -1, \ glue3(prefix,_,name1) = 0, \ glue3(prefix,_,name2) = 1, \ glue3(prefix,_,name3) = 2, \ glue3(prefix,_,name4) = 3, \ glue3(prefix,_,name5) = 4 \ }; \ static char * glue3(prefix,_str,[5]) = { \ #name1, #name2, #name3, #name4, #name5 \ }; decls (color,C,RED,GREEN,BLUE,WHITE,YELLOW) decls (pets,P,DOGS,BIRDS,CATS,HORSES,FISH) decls (nationality,N,BRIT,SWEDE,DANE,NORWEGIAN,GERMAN) decls (cigarettes,X,PallMall,Dunhill,Marlboro,Winfield,Rothmans) decls (drink,D,tea,coffee,milk,beer,water) struct { enum color c; enum pets p; enum nationality n; enum cigarettes x; enum drink d; } houses[5]; #define findfns(ename,record) \ static int glue3(idx_,ename,_find) (enum ename v) { \ int i; \ for (i=0; i < 5; i++) if (v == houses[i].record) return i; \ return -1; \ } findfns (color,c) findfns (pets,p) findfns (nationality,n) findfns (cigarettes,x) findfns (drink,d) #define condfns(cidx,ename,which,record,prefix,assoc) \ static int glue3(cond_,cidx,_test) (void) { \ int idx = glue3(idx_,ename,_find) (which); \ if (idx >= 0 && \ houses[idx].record != glue3(prefix,_,assoc) && \ houses[idx].record != glue3(prefix,_,UNKNOWN)) \ return 0; \ return 1; \ } condfns ( 1,nationality,N_BRIT,c,C,RED) condfns ( 2,nationality,N_SWEDE,p,P,DOGS) condfns ( 3,nationality,N_DANE,d,D,tea) condfns ( 5,color,C_GREEN,d,D,coffee) condfns ( 6,cigarettes,X_PallMall,p,P,BIRDS) condfns ( 7,color,C_YELLOW,x,X,Dunhill) condfns (12,cigarettes,X_Winfield,d,D,beer) condfns (13,nationality,N_GERMAN,x,X,Rothmans) static int cond_4_test (void) { int idxg = idx_color_find (C_GREEN); int idxw = idx_color_find (C_WHITE); return (idxg >= 0 && idxw >= 0 && idxg >= idxw) ? 0 : 1; } static int cond_8_test (void) { return (houses[2].d != D_UNKNOWN && houses[2].d != D_milk) ? 0 : 1; } static int cond_9_test (void) { return (houses[0].n != N_UNKNOWN && houses[0].n != N_NORWEGIAN) ? 0 : 1; } #define condnextdoorfns(idx,ename0,which0,ename1,which1) \ static int glue3(cond_,idx,_test) (void) { \ int idx0 = glue3(idx_,ename0,_find) (which0); \ int idx1 = glue3(idx_,ename1,_find) (which1); \ return (idx0 >= 0 && idx1 >= 0 && \ idx0 != idx1 + 1 && idx0 + 1 != idx1) ? 0 : 1; \ } condnextdoorfns(10,cigarettes,X_Marlboro,pets,P_CATS) condnextdoorfns(11,pets,P_HORSES,cigarettes,X_Dunhill) condnextdoorfns(14,nationality,N_NORWEGIAN,color,C_BLUE) condnextdoorfns(15,cigarettes,X_Marlboro,drink,D_water) static int isLegal (void) { return cond_1_test () && cond_2_test () && cond_3_test () && cond_4_test () && cond_5_test () && cond_6_test () && cond_7_test () && cond_8_test () && cond_9_test () && cond_10_test () && cond_11_test () && cond_12_test () && cond_13_test () && cond_14_test () && cond_15_test (); } #define singletonfns(ename,prefix,record) \ static int glue3(singleton_,ename,_check) (int lim) { \ int i, j; \ for (i=1; i < lim; i++) { \ if (glue3(prefix,_,UNKNOWN) == houses[i].record) continue; \ for (j=0; j < i; j++) { \ if (glue3(prefix,_,UNKNOWN) == houses[j].record) continue; \ if (houses[i].record == houses[j].record) return 0; \ } \ } \ return 1; \ } singletonfns (color,C,c) singletonfns (pets,P,p) singletonfns (nationality,N,n) singletonfns (cigarettes,X,x) singletonfns (drink,D,d) #define dumpfns(prefix,record) \ static void glue3(prefix,_dump,(void)) { \ int i, idx; \ printf ("\t\n\t\t"); \ for (i=0; i < 5; i++) { \ if (0 <= (idx = houses[i].record)) \ printf ("%s", glue3(prefix,_str,[idx])); \ else \ printf ("UNK"); \ } \ printf ("\n\t\n"); \ } dumpfns(C,c) dumpfns(P,p) dumpfns(X,x) dumpfns(N,n) dumpfns(D,d) void dump (void) { printf ("\n\n\n"); C_dump (); N_dump (); P_dump (); X_dump (); D_dump (); printf ("
\n\n"); } static int solve_drink (int i) { int j; for (j=0; j < 5; j++) { houses[i].d = j; if (singleton_drink_check (i+1) && isLegal ()) { if (i+1 >= 5) { dump (); return 1; } else { if (solve_drink (i+1)) return 1; } } } houses[i].d = D_UNKNOWN; return 0; } #define solvefn(ename0,ename1,prefix,record) \ static int glue3(solve,_,ename0) (int i) { \ int j; \ for (j=0; j < 5; j++) { \ houses[i].record = j; \ if (glue3(singleton_,ename0,_check) (i+1) && isLegal ()) { \ if (i+1 >= 5) { \ if (glue3(solve,_,ename1) (0)) return 1; \ } else { \ if (glue3(solve,_,ename0) (i+1)) return 1; \ } \ } \ } \ houses[i].record = glue3(prefix,_,UNKNOWN); \ return 0; \ } solvefn (cigarettes,drink,X,x) solvefn (nationality,cigarettes,N,n) solvefn (pets,nationality,P,p) solvefn (color,pets,C,c) static void initHouses (void) { int i; for (i=0; i < 5; i++) { houses[i].c = C_UNKNOWN; houses[i].p = P_UNKNOWN; houses[i].n = N_UNKNOWN; houses[i].x = X_UNKNOWN; houses[i].d = D_UNKNOWN; } } int solve (void) { initHouses (); return solve_color(0); } int main () { solve (); return 0; }