kumbunterland posed this question in the park yesterday:
There are four men in a coal mine. This exit is narrow so that no more than 2 men can exit at the same time. In addition, there is only one torch and they can't leave the mine without it.
Each man walks at a different speed. The first man takes one minute to exit the mine the bridge distance, the second takes two minutes, the third takes five, and the fourth takes eight minutes.
If two men walk together they must walk at the slower speed. For example, if person #1 and person #3 go together, they will leave the mine in 5 minutes. Then, person #1 could return back to return the torch to the others (taking another one minute) so they can use it to exit again.
The coal mine will collapse in exactly 15 minutes; you must find a way to allow all the men to leave the mine within this time.
Unfortunately, swi-prolog is broken on the N900, so I wasn't able to solve it right then:
solution(Men, Bound, Out) :- torchInside(Men, [], [], Log), totalDuration(Log, 0, Duration), Duration =< Bound, swritef(Out, '%w (%w minutes)', [Log, Duration]). % We use torch{Inside,Outside} predicates like a state machine. torchInside(A, B, Log, X) :- % Move two people from inside -> outside the mine combination(2, A, S), subtract(A, S, A1), append(S, B, B1), torchOutside(A1, B1, [S|Log], X). torchOutside([], _, Log, Log). torchOutside(A, B, Log, X) :- % Move someone from outside -> inside the mine combination(1, B, S), subtract(B, S, B1), append(S, A, A1), torchInside(A1, B1, [S|Log], X). % Utilities: totalDuration([], X, X). totalDuration([H|T], Acc, X) :- max_list(H, Max), NewAcc is Acc + Max, totalDuration(T, NewAcc, X). combination(0, _, []). combination(N, [H|T], [H|Comb]) :- N > 0, N1 is N - 1, combination(N1, T, Comb). combination(N, [_|T], Comb) :- N > 0, combination(N, T, Comb).
?- solution([1, 2, 5, 8], 15, X). X = "[[2, 1], [2], [5, 8], [1], [1, 2]] (15 minutes)" ; X = "[[1, 2], [1], [5, 8], [2], [1, 2]] (15 minutes)" ; false.
I'm fun at parties.