Assignment 2 - Treasure Hunting

Simple Treasure Hunt

Karel is somewhere in a completely enclosed rectangular room that contains a treasure represented by one beeper. Program Karel to find the treasure, pick it up, and turn himself off.

    .   .   .   .   .   .   . 
      +-------------------+
  4 .  .   .   .   .   .  . 
                         
  3 .  .   .   .   o   .  . 
                         
  2 .  .   >   .   .   .  . 
      +-------------------+
  1 .   .   .   .   .   .   .
   +----------------------------
     1   2   3   4   5   6   7  

The Path to Success

There is a trail of beepers that indicates a path to the treasure. The treasure is represented by a pile of two beepers. Each beeper in the path is reachable from the previous beeper by the execution of one move, and there is no gap. The path will never cross itself, and is always at least one block away from the world boundaries. With the exception of the treasure, there is never more than one beeper on each corner. Karel is positioned facing the first beeper in the path to the treasure. Program Karel to find the treasure, pick it up, and turn himself off.

  7 .   .   .   .   .   .   .   .
   
  6 .   o   o   o   o   o   .   .
   
  5 .   o   .   .   .   o   .   .
   
  4 .   o   o   .   .   o   .   .
   
  3 .   .   o   .   .   o   o   2
   
  2 >   o   o   .   .   .   .   .
   
  1 .   .   .   .   .   .   .   . 
   +--------------------------------
     1   2   3   4   5   6   7   8   9  

Treasure Hunting with Clues

This time, the treasure is marked by a corner containing five beepers. Other corners (including the corner on which Karel starts) contain clues, with each clue indicating in which direction Karel should proceed. The clues are as follows: 1 beeper means Karel should go north, 2 means west, 3 means south, and 4 means east. Karel should follow the clues until he reaches the treasure corner where the robot should turn itself off.

St.
  9 .   .   .   .   .   .   .   .   . 
   
  6 .   4   .   .   3   .   .   .   .
   
  5 .   .   .   .   .   .   .   .   .
   
  4 .   .   5   .   .   .   .   2   .
   
  3 .   .   .   .   .   .   .   .   .
   
  2 .   ^   .   .   4   .   .   1   .
   
  1 .   .   .   .   .   .   .   .   .
   +---------------------------------------
     1   2   3   4   5   6   7   8   9  10

The lonely Treasure

Somewhere in Karel's world is a treasure, represented by a single beeper. There is nothing else in that world but the treasure. Karel's starting position can be anywhere. Program Karel to find the treasure and turn himself off.

Extra Credit: Dangers of Treasure Hunting

There is a menace in Karel's world - an infinite pile of beepers. If Karel accidentally tries to pick up an infinite pile of beepers, he is forever doomed to pick beepers from the pile. Karel's current situation places him in grave danger from such a pile. The robot is standing just in front of three rooms: one is north-west, one is straight ahead, and one is north-east (see figure). Only one of these rooms has the dreaded infinite pile of beepers. Karel must decide which room is the safe room, enter it, and pick all of the beepers. To help the robot decide which room is safe, Karel can use the middle pile of beepers right in front of him. If this third pile has an even number of beepers, the save room is the eastern room. If the pile has an odd number of beepers, the safe room is the western room. Program Karel to pick the beepers in the safe room and turn himself off.

  3 .   .   .   .   .   .   .   . 
          +---    ---+
  2 .   .  o   o   o  .   .   . 
          +---    ---+
  1 .   .   .   ^   .   .   .   . 
   +-------------------------------
     1   2   3   4   5   6   7   8 

(bgw)