Artificial Intelligence

Question and Assignment

The Flashlight Puzzle

Four people are on one side of a bridge. They wish to cross to the other side, but the bridge can only take the weight of two people at a time. It is dark and they only have one flashlight, so they must share it in order to cross the bridge. Assuming each person moves at a different speed (able to cross in 1, 2, 5 and 10 minutes, respectively), find a series of crossings that gets all four across in the minimal amount of time.

Solution

the point of this question is to find the fastest way to take 4 people to the other side of bridge
A : 1 minute
B : 2 minutes
C : 5 minutes
D : 10 minutes

Code implementation using DrSceme

State representation must identify the locations of each person and the flashlight
((1 2 5 10) left ())
note : must be careful of permutations/ pertukaran urutan
e.g., (1 2 5 10) = (1 5 2 10) so must make sure there only one representation per set
Solution : maintain the list in sorted order, so only one permutation is possible
only 3 possible moves:
1. if the flashlight is on left and only 1 person on left, then
move that person to the right (cost is time it takes for that person)
2. if flashlight is on left and at least 2 people on left, then
select 2 people from left and move them to right (cost is max time of the two)
3. if the flashlight is on right, then
select a person from right and move them to left (cost is time for that person)
Heuristic:
H: number of people in wrong place

bla bla