Nice Exercises
- Searching the friend moving in an infinite 3-D grid
First let us define a grid : Consider 3-D space. Every (i,j,k) where
i,j,k are integers, corresponds to a node. A node is adjacent to those
nodes whose two out of three co-ordinates are same as that of given node
and the third co-ordinate differs by +1 or -1. So every node is adjacent to
exactly six nodes.
Your friend is standing at a node somewhere in a 3-D grid. After every second
he moves to one out of the six neighboring nodes. Your objective is to locate
your friend. You have a control panel using which after every second you can
chose some node in the grid and determine whether your friend is there or not.
You will get answer yes/no. Give an effective scheme to locate
your friend,provided he changes his direction atmost a finite number of
times(however large it may be).