Brain-Teaser 688: Job allocation
From The Sunday Times, 22nd September 1974 [link]
Ashley, Bill, Charles, David, and Edward are (not necessarily in that order), a dustman, a grocer, a miner, a blacksmith, and an artist, and all live on the right hand side of Strife Lane, in even numbered houses. All five are of different ages and no man has reached the age of retirement (65). All of course are upright and honest citizens, and never tell lies. However, I had forgotten what job each man did, where he lived, and how old he was, and so, to help me, each man volunteered the following statements:
Ashley:
(1) The artist lives at No. 10, next to Charles;
(2) Nobody lives next to the grocer, although Bill is only two doors away.Bill:
(3) I am the only man whose age is indivisible by 9;
(4) I am 4 years older than Ashley;Charles:
(5) The blacksmith’s age is 5 times his house number;David:
(6) The miner lives 4 houses higher up the road from me;
(7) The miner’s age is 3 times the dustman’s house number, but he is two-thirds the dustman’s age;Edward:
(8) The dustman is twice as old as David;
(9) I am the oldest man in the street.At what number does Ashley live?
How old is the grocer?
Who is the artist?
This puzzle is included in the book The Sunday Times Book of Brain-Teasers: Book 1 (1980). The puzzle text above is taken from the book.
[teaser688]
Frits are discussing. 
S2T2 
Jim Randell 8:48 am on 4 February 2021 Permalink |
I wrote a MiniZinc model to solve this puzzle, and then used the minizinc.py wrapper to format the output.
This Python program runs in 178ms.
from enigma import irange, printf from minizinc import MiniZinc model = """ include "globals.mzn"; % indices for A, B, C, D, E int: A = 1; int: B = 2; int: C = 3; int: D = 4; int: E = 5; % house numbers array [1..5] of var int: n; % even numbers constraint forall (i in 1..5) (n[i] > 0 /\ n[i] mod 2 = 0); % all different constraint all_different(n); % ages array [1..5] of var 16..64: a; % all different constraint all_different(a); % jobs var 1..5: Du; var 1..5: Gr; var 1..5: Mi; var 1..5: Bl; var 1..5: Ar; % all different constraint all_different([Du, Gr, Mi, Bl, Ar]); % (1) "the artist lives at number 10, next to C" constraint n[Ar] = 10; constraint n[C] = 8 \/ n[C] = 12; % (2) "nobody lives next to the grocer, although B is only 2 doors away" constraint forall (i in 1..5 where i != Gr) (abs(n[Gr] - n[i]) != 2); constraint abs(n[Gr] - n[B]) = 4; % (3) "B is the only one whose age is not divisible by 9" constraint forall (i in 1..5) (a[i] mod 9 != 0 <-> i = B); % (4) "B is 4 years older than A" constraint a[B] = a[A] + 4; % (5) "Bl age is 5x his house number" constraint a[Bl] = 5 * n[Bl]; % (6) "Mi lives 4 houses further up the road than D" constraint n[Mi] = n[D] + 8; % (7) "Mi's age is 3x Du's house number; but Mi is 2/3 Du's age" constraint a[Mi] = 3 * n[Du]; constraint 3 * a[Mi] = 2 * a[Du]; % (8) "Du is 2x D's age" constraint a[Du] = 2 * a[D]; % (9) "E is the oldest" constraint forall (i in 1..5 where i != E) (a[i] < a[E]); solve satisfy; """ p = MiniZinc(model) name = [ "", "Ashley", "Bill", "Charles", "David", "Edward" ] for (n, a, Du, Gr, Mi, Bl, Ar) in p.solve(result="n a Du Gr Mi Bl Ar"): j = { Du: "Dustman", Gr: "Grocer", Mi: "Miner", Bl: "Blacksmith", Ar: "Artist" } for i in irange(1, 5): printf("{name}: house = {n}; age = {a}; job = {j}", name=name[i], n=n[i], a=a[i], j=j[i])Solution: Ashley lives at number 18. The grocer is 63. David is the artist.
The complete solution:
LikeLike
Frits 11:52 am on 11 February 2021 Permalink |
@Jim, you didn’t code that B’s age may not be not divisible by 9.
LikeLike
Jim Randell 11:59 am on 11 February 2021 Permalink |
@Frits: Oh yes.
I’ll update line 48 to:
LikeLike
Frits 9:38 pm on 11 February 2021 Permalink |
“if stop: continue”
My first version started looping over house numbers (where a maximum house number had to be specified). Looping over ages first eliminates this problem.
from itertools import permutations # indices Ashley ... Edward (A, B, C, D, E) = (0, 1, 2, 3, 4) # "B is 4 years older than A (which is a multiple of 9)" b_ages = [x for x in range(22, 65) if x % 9 != 0 and (x - 4) % 9 == 0] acde_ages = tuple(permutations(range(18, 65, 9), 4)) jobs_indices = list(permutations(range(5))) # update list hn for key <k> if value <v> doesn't exist yet in hn def update(k, v): if v in hn: return False else: hn[k] = v return True # start with ages divisble by 9 for p4 in acde_ages: # "Bl age is 5x his house number" if all(x % 5 != 0 for x in p4): # at least one age must be a multiple of 5 b_ages = [x for x in b_ages if x % 5 == 0] for b in b_ages: # "B is 4 years older than A" if b != p4[0] + 4: continue # b must be placed at 2nd spot ag = (p4[0], b) + p4[1:] # "E is the oldest" if ag[E] != max(ag): continue # "Du is 2x D's age" if (2 * ag[D]) not in ag: continue # indices for Du, Gr, Mi, Bl, Ar for (Du, Gr, Mi, Bl, Ar) in jobs_indices: # "Mi is 2/3 Du's age" if 3 * ag[Mi] != 2 * ag[Du]: continue # "Bl age is 5x his house number" if ag[Bl] % 5 != 0: continue # "Mi's age is 3x Du's house number" if ag[Mi] % 3 != 0: continue # "Du is 2x D's age" if ag[Du] != 2 * ag[D]: continue # initialize house numbers hn = [0, 0, 0, 0, 0] # "the artist lives at number 10, next to C" hn[Ar] = 10 if not update(Du, ag[Mi] // 3): continue if not update(Bl, ag[Bl] // 5): continue if hn[C] and hn[C] not in {8, 12} : continue for loop in range(2): # "Mi lives 4 houses further up the road than D" if hn[Mi] == 0 and hn[D]: if not update(Mi, hn[D] + 8): break elif hn[Mi] and hn[D] == 0: hn[D] = hn[Mi] - 8 if hn[Mi] < 10 or not update(D, hn[Mi] - 8): break elif hn[Mi] and hn[D]: if hn[Mi] != hn[D] + 8: break # B is only 2 doors away from grocer" if hn[B]: if hn[Gr]: if abs(hn[B] - hn[Gr]) != 4: break else: Gr_opts = [] if hn[B] + 4 not in hn: Gr_opts.append(hn[B] + 4) if hn[B] > 5 and hn[B] - 4 not in hn: Gr_opts.append(hn[B] - 4) if len(Gr_opts) == 1: if not update(Gr, Gr_opts[0]): break elif len(Gr_opts) == 0: break else: if hn[Gr]: B_opts = [] if hn[Gr] + 4 not in hn: B_opts.append(hn[Gr] + 4) if hn[Gr] > 5 and hn[Gr] - 4 not in hn: B_opts.append(hn[Gr] - 4) if len(B_opts) == 1: if not update(B, B_opts[0]): break elif len(B_opts) == 0: break # "nobody lives next to the grocer" if hn[Gr] and any(abs(x - hn[Gr]) == 2 and x != 0 for x in hn): break # "the artist lives at number 10, next to C" if hn[C] and hn[C] not in {8, 12} : break else: # no break # all house numbers determined? if 0 in hn: continue jobs = {Du: "Dustman", Gr: "Grocer", Mi: "Miner", Bl: "Blacksmith", Ar: "Artist"} print(" Ashley", ) print(" | Bill") print(" | | Charles") print(" | | | David") print(" | | | | Edward") print("house number", tuple(hn)) print("age ", ag) print(" | | | | ", jobs[4]) print(" | | | ", jobs[3]) print(" | | ", jobs[2]) print(" | ", jobs[1]) print(" ", jobs[0])LikeLike
Frits 12:58 pm on 10 August 2021 Permalink |
@Jim,
Did you choose for MiniZinc because it allows for an unrestrained house number range?
LikeLike
Jim Randell 3:35 pm on 10 August 2021 Permalink |
@Frits: That was probably the main reason. Also using a declarative solver like MiniZinc meant I didn’t have to worry about what order to attack the problem in.
LikeLike
Frits 2:13 pm on 10 August 2021 Permalink |
@Jim,
If I add
var 2..6: q = Ar + 1;
then variable q is not in the result set.
Is this a MiniZinc issue or a wrapper issue?
LikeLike
Jim Randell 3:29 pm on 10 August 2021 Permalink |
@Frits:
The wrapper just parses the MiniZinc output and turns it into Python objects. So if MiniZinc doesn’t output a value it is not available in Python.
But you should be able to use a constraint to get the value output by default:
LikeLike