A robot, let's say, Steve, is in the bottom left corner of a rectangular room, the size of which is unknown. His goal is to travel to the top left corner of the room and stop there. There are random walls present in the room. There always is a way to the corner.

Steve can do the following:

  1. Move forward.
  2. Turn left, right and around.
  3. Detect if a wall is in front of him or not.
  4. Detect if he is facing to the left, right, up or down.
  5. Put/pick up a diamond in/from the slot he is standing in.
  6. Detect if there is a diamond where he is standing.
  7. Steve has an infinite numbers of diamonds.
  8. Steve cannot count (that is, he functions as a finite state machine).

What I've thought of so far is using the right-handed method using which Steve will always arrive at the top right corner, but detecting it is the major problem, as there can be other places in the room with walls to the right and top. Consider this case, for example:

A room example

"S" represents Steve. His destination is (10, 8), but as we can see, there are 7 other places in the room which can be mistaken for the destination by simply checking for the bordering walls.

  • $\begingroup$ Does your robot know tath the destination is (10,8)? From your question is not clear... $\endgroup$ – Yamar69 Oct 11 at 11:13
  • $\begingroup$ @Yamar69 No, the world size is unknown as well $\endgroup$ – Nick Oct 11 at 12:54
  • $\begingroup$ Does your robot need to know that he reached the top right corner? $\endgroup$ – Yuval Filmus Oct 11 at 14:47
  • $\begingroup$ Can the robot lay down multiple diamonds in the same room? If it can it should be possible for it to perform (basic) arithmetic. $\endgroup$ – eru-cs Oct 11 at 15:09
  • $\begingroup$ @eru-cs He can lay down as much diamonds as we want and yes, arithmetics is not a problem, I already have the algorithms(and the code) for addition, subtraction, multiplication and division $\endgroup$ – Nick Oct 11 at 17:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.