CMPT 120 Assignment 4

1. In a file myrange.py, write a recursive version of the range function. Your function should be:
   def myrange(start, end, step): …

   You can assume that start<=end and that step>0. Under those conditions, your function should always return the same list as range(start, end, step).

2. In a file selectionsort.py, write a recursive version of the selection sort algorithm. Your function should be:
   def selection_sort(lst, start, end): …

   The recursive step should be to get the smallest item in lst[start:end+1] into lst[start]. Once this is done, you can recursively sort the list from start+1 to end.

3. In a file binary.py, write a recursive function bin_to_int that takes an unsigned binary value (as a string like "100101") and converts it to an integer (37 in the example).

   This can be done recursively for any length binary string. In the example, notice that the first 5 characters of the string ("10010") convert to the integer 18, and the last character ("1") becomes 1. The whole string converts to 37 = 2×18 + 1.

   So, you should first convert the first n-1 bits to a decimal value, double it, and add the last bit.

For this assignment, your job is to create an algorithm and program to control a robot. Name your program robot.py.

The robot can move around a grid of squares. Its job is to move around the grid and collect coins.

The goal is for the robot to collect all of the coins (round things) while avoiding the blocks (square things) and not falling off the edge of the board.

You don't have to draw the board: the provided module will do that for you. Your job is to design and implement an algorithm that will let the robot complete its task.

The robot basically has two things it can do: move and check its sensors. The robot can move one square in any direction (north, south, east, or west). Its sensors can tell you what it sees in any of these directions (a coin, the edge of the board, or a block) and how far away it is.

Using only these basic operations, you have to write a program to navigate the robot to collect the coins.

Doing this in general (with a lot of blocks in the way) is quite hard and you aren't expected to solve the full problem. Start by solving the problem with no blocks in the way and work up from there.

Implementing

A module “robotlib” has been provided. You'll have to download the robotlib.pyc file. Save this file in the same directory as your program and you should be able to import it.

A collection of hints has been provided.

Your code should be easy to read and understand.

If you want to describe what cases your algorithm will handle or the limitations you know about, create a text file about.txt and do it there. You can use this to give whatever kind of description you think is appropriate to the markers. You don't have to include this, but it would be a chance to describe anything you think is clever, or that we might not notice. You could also describe known problems (like “the robot always gets stuck if…”).

When you're done, create a ZIP file containing all of the files you created for this assignment and submit it with the submission server. Don't submit the robotlib module.

(Thanks to Devan Yim for the icons that are used when drawing the board.)