Chris Lamb

Four men in a mine

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)" ;

I'm fun at parties.

Chris Lamb is a freelance software developer and the current Debian Project Leader. You can read other posts by me, see software I have written or read more about me. You can also follow me @lolamby.

Tags: Hacks

Planets: ALUG UWCS Debian WUGLUG

Saturday 24th July 2010

One comment