Part I: Recursion Practice

In a file recursion.py, write these recursive functions:

1. 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 list(range(start, end, step)).

2. 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 ("100101"), notice that the first 5 characters of the string ("10010") convert to the integer 18, and the last character ("1") becomes 1. Therefore, 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.

Part II: Programming

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

The goal is for the robot to collect all of the coins while avoiding the blocks 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.py file. Save this file in the same directory as your program and you should be able to import it.

Have a look at the documentation for robotlib for information on how to work with 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…”).

Submitting

Submit all of your work through CourSys. Don't submit the robotlib module: we already have it.