Question

Men, women and gupi live on the planet Alphaomega. Imagine you are travelling by a self driving car on this planet and you need to pass the city Beth. The road goes through this city and you cannot bypass it. There are only two entrances to the city – one from the side you are coming and another from the opposite side. Besides, you know that an evil gupi is sitting at one of the intersections in Beth. When a human being comes close to him, he kidnaps this person and makes the human being his slave. Fortunately, this gupi is lazy and he kidnaps only those who come close to him. The distance in one block is safe for you because your car can feel the presence of the gupi one block ahead of it. At the same time, other inhabitants of Beth cannot help you because you don’t know their language and they don’t know your language. Besides, you don’t have a map of the city Beth.

a) Is it always possible to go through the city? Prove that your answer is correct.

b) If it is always possible to go through the city, design an algorithm for your car for doing this.

c) If it is not always possible to go through the city, design an algorithm for your car that will allow you to go through the city when it is possible or to return back when it is impossible.

Answer 1

It is possible to go through the city, because we can detect the presence of guppi from one block away and hence we can choose another path.

There is one case, in which, passing the city becomes impossible, that is when guppi is sitting at the last intersection from which we need to pass through.

Algorithm for passing the city whenever possible and returning if not.

while( the city is not passed)

if( block_ahead there is guppy )

if(block_ahead is the last_intersection_to_pass)

return back from the city

if(block_ahead is not the last intersection)

return and try different route

if( block_ahead there is no guppy)

keep_moving