How to solve the Rope Bridge problem with an algorithm?

Question

Hi, I was wondering if this rope bridge problem could be solved with a graphing algorithm search:

My gut feeling says DFS but how should I define the states? (That is if DFS is even the way to go.)

Rope Bridge

Answer 1

This task is supposed to be solved without a computer.

However, if you generalize the case, then, I suppose, you can do it with graph searching, but you should take the size of the graph into account. If each vertex is the "state", then the number of this states estimates as 2^N⋅L, where N is the number of people, and L is the length of the flashlight. Each state contains information, which side is each person at, and of remaining flashlight duration. If there's a path from initial state to one of those states where everyone's on the camp's side, then this path is the solution.

That's the most obvious way to create states, but maybe you can do it in a more efficient way (current number of states, hence the runtime, is exponential to the input size).

However, for the sizes that small as in the sample you provided, exponential runtime (with graphs) is acceptable. The interviewer may even like it, if you suggest programmatic solution instead of doing it by hand.

Answer 2

You might want to look at EWD 1255.