Programming Task 3: Robot Rally

• You are working in teams of four (two sets of partners). This will require workplace-style maturity.
• These tasks will test your ability to put notions into practice within a team setting.
• Submit your teams' working code to andy at novocin.com prior to your scheduled review.
• I will run the code on real inputs using ideone.com with the C++11 environment.
• Presentation day will consist of a scheduled 45 minute meeting.
• At that meeting I will run the code.
• I will select one person from your team using a random integer, that person will explain the code and answer my questions.
• I will assign a grade that day for all of you based on the randomly selected team member's explanation.
• It is your responsibility to make sure that everyone on your team understands the concepts behind your solution.
• Coding in C++ is a soft requirement of the course, this method allows the coding aspects of the project to be spread while ensuring some practical awareness.

The Programming tasks for this assignment:

This assignment involves guiding a robot through a treasure cave. You are going to be given an ASCII map of a \( 20 \times 20\) rectangular grid cave. Each cell in the grid is surrounded by four corner + symbols. East/west walls are marked by a |, north/south walls are marked by a -, and a space where a wall would be means an open corridor. Each cell has one of four symbols in it: .,$,s, or x. There will be only one s in the top left cell, one x in the bottom right cell, and four $ treasures scattered about the cave. All other (394) cells will have a . inside.

A sample input:

      
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|s .|.|.|.|.|. . .|. .|. . . . . . .|. .|
+ +-+ + + + +-+ +-+-+ +-+-+-+ +-+-+ +-+ +
|. . .|. .|$ .|. . . . .|. . . .|. . . .|
+-+-+ +-+ + +-+ +-+-+-+ +-+ + + +-+ +-+ +
|. .|.|. . . . . .|. . . . .|.|.|. .|. .|
+ +-+ +-+ +-+ + +-+-+-+ + +-+-+-+-+ +-+ +
|. . . . .|. .|. .|.|. .|.|. . .|. .|. .|
+ +-+-+-+ + +-+ + + + + +-+-+-+ +-+-+-+ +
|.|. . . .|. .|.|.|.|.|. . .|. . .|.|. .|
+ +-+-+ + + +-+-+-+ +-+ +-+-+-+-+ + +-+ +
|.|.|.|.|.|.|. .|. . . . .|. . .|. . . .|
+-+ + + +-+ +-+ +-+ +-+-+-+-+-+ +-+-+ + +
|. . . .|. .|. . . . .|. . . . . .|. .|.|
+-+-+-+ + +-+-+ +-+ + + +-+ +-+ + +-+-+ +
|. . .|.|.|. . .|. .|.|.|. .|. .|. . . .|
+ +-+-+ +-+-+-+ + + +-+-+-+-+-+-+-+ +-+ +
|. . . . . .|. .|.|.|.|. . . . . . .|. .|
+-+-+-+ +-+-+-+-+ +-+ +-+-+-+-+-+ + +-+ +
|$ . . . .|$|.|.|.|.|.|.|. .|.|. .|.|. .|
+-+-+ +-+-+ + + +-+ + + +-+ + +-+-+-+-+ +
|.|.|.|.|.|.|. . .|. . . . . . . . .|. .|
+ + +-+ + + + +-+ +-+ + +-+-+ + +-+ +-+ +
|.|. . .|. . .|.|. . .|.|. . .|.|. . . .|
+ +-+ +-+-+-+-+ + +-+-+ +-+-+-+-+-+-+-+ +
|. . . . . . . . .|.|. .|. . . .|.|. . .|
+-+-+ +-+-+-+-+-+-+ + + +-+-+ +-+ + +-+ +
|.|. .|. . $ . . . . .|.|. . . . .|.|. .|
+ +-+-+ +-+ + +-+-+ + +-+-+-+ + +-+ +-+-+
|. . . . .|.|.|. .|.|.|.|.|.|.|. . . . .|
+-+-+ +-+-+ +-+-+ +-+-+ + + + + +-+ +-+-+
|. . .|. . . .|. . .|. .|. . .|.|. . . .|
+-+-+ +-+-+ + +-+-+ + +-+-+-+-+-+ + + +-+
|. . .|. . .|.|.|. . . . . . . . .|.|. .|
+ + +-+-+-+-+-+ +-+ + +-+-+ + +-+-+ +-+-+
|.|.|. .|. .|. . . .|.|. . .|.|. . . . .|
+ +-+ +-+-+ +-+-+ + + +-+ + +-+ +-+-+ +-+
|.|.|.|. . . .|. .|.|.|. .|.|.|.|. . . .|
+-+ + +-+-+-+ +-+ +-+ + +-+ + +-+ +-+ +-+
|. . . . . . . . . .|.|.|. .|. . .|. . x|
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      
    

1. Input: an ascii map of a cave, as described above. (Here are more sample files: above_maze, maze2, maze3.)

   Output: the fastest route out of the cave (ignoring any treasure) (from s to x). Each line should contain one of four directions "up", "down", "left", "right".

   Sample output (For the above input. As a text file: fast_output.txt.)

             
   down
   right
   right
   down
   down
   right
   right
   up
   right
   right
   right
   up
   right
   right
   right
   right
   down
   right
   right
   up
   right
   up
   right
   right
   right
   down
   right
   right
   down
   down
   down
   down
   down
   down
   down
   down
   down
   down
   down
   left
   left
   down
   down
   down
   down
   down
   right
   down
   down
   right
             
          

   Restrictions: If your solution runs into a wall then your robot and grade explode.

   Notes: I will test your code on a randomly generated cave. The caves are assumed to be connected (you can reach any cell). Explain the choices and the complexity of your code.

2. Input: A cave map, matching the above specifications.

   Output: A route out of the cave which uses no more than 100 steps (your robot is running out of battery power) but captures as many treasures as possible. The first line of output should be the number of steps followed by a space followed by the amount of treasure you captured. After that the output will be of the same format as question 1 (one of four directions on each line).

   Sample output with treasure: (as a text file: money_output.txt)

      
   72 2
   down
   right
   right
   down
   down
   right
   right
   down
   left
   down
   down
   down
   down
   down
   left
   left
   left
   right
   right
   right
   up
   up
   up
   up
   up
   right
   up
   up
   right
   up
   down
   right
   right
   up
   right
   right
   right
   right
   down
   right
   right
   up
   right
   up
   right
   right
   right
   down
   right
   right
   down
   down
   down
   down
   down
   down
   down
   down
   down
   down
   down
   left
   left
   down
   down
   down
   down
   down
   right
   down
   down
   right
      
   

   Notes: There might be multiple acceptable answers to this question which escape the cave and attain the same amount of treasure. If you can choose the answer which uses less power/moves/gas I will prefer that. Again, don't blow up.