A document from MCS 275 Spring 2023, instructor Emily Dumas. You can also get the notebook file.

MCS 275 Spring 2023 Homework 4 Solutions

  • Course Instructor: Emily Dumas
  • Contributors to this document: Johnny Joyce

Instructions:

  • Complete the problems below, which ask you to write Python scripts.
  • Upload your python code directly to gradescope, i.e. upload the .py files containing your work.

Deadline

This homework assignment must be submitted in Gradescope by Noon central time on Tuesday February 7, 2023.

Collaboration

Collaboration is prohibited, and you may only access resources (books, online, etc.) listed below.

Content

This assignment is about object-oriented programming, especially subclasses and inheritance. It focuses on the material of worksheet 4.

Resources you may consult

Most relevant:

Less likely to be relevant, but also allowed:

Point distribution

This homework assignment has 2 problems, numbered 2 and 3. The grading breakdown is:

Points Item
3 Autograder
6 Problem 2
6 Problem 3
15 Total

The part marked "autograder" reflects points assigned to your submission based on some simple automated checks for Python syntax, etc. The result of these checks is shown immediately after you submit.

What to do if you're stuck

Ask your instructor or TA a question by email, in office hours, or on discord.

Problem 1 doesn't exist

In Gradescope, the score assigned to your homework submission by the autograder (checking for syntax and docstrings) will be recorded as "Problem 1". Therefore, the numbering of the actual problems begins with 2.

This will happen on every assignment this semester. Starting on the next homework, I won't comment on this practice in the homework, and will just omit problem 1.

Get bots.py

Both problems on this assignment involve adding subclasses to bots.py. So you'll need to grab a copy of that example module to modify in this project:

The second file (plane.py) is used by bots.py but won't be modified for this assignment.

When you submit this homework, upload the modified file bots.py and nothing else.

Problem 2: HoverBot

Make a subclass HoverBot of Bot whose constructor expects to be given another Bot instance (the target), and which then always makes sure it remains near that robot, but moves randomly around it. So it "hovers" near a given robot.

Specifically, "hovering" should mean that the target robot and the HoverBot always have positions that differ by one of $\langle 1,0\rangle$, $\langle -1,0\rangle$, $\langle 0,1\rangle$, $\langle 0,-1\rangle$. The HoverBot constructor should accept an argument target that is expected to be an instance of Bot. This argument should be stored as an instance attribute (self.target).

Any time the HoverBot needs to make a decision about its position (e.g. in the constructor or in update), it should check the target position and add a random vector from the list given above to decide on its own position. It should not modify the target robot at all.

Solution

In [ ]:
class HoverBot(Bot):
    """Bot that hovers near another given bot"""
    
    symbol = "H"
    steps = [
        plane.Vector2(1, 0),
        plane.Vector2(-1, 0),
        plane.Vector2(0, 1),
        plane.Vector2(0, -1),
    ]
    
    def __init__(self, target):
        """`target` argument is the bot that HoverBot should hover near"""
        
        self.target = target
        position = self.target.position + random.choice(self.steps)
        super().__init__(position)
        
        
    def update(self):
        """Keep current position 1 away from target"""
        
        # Copy target's position and offset by 1
        self.position = self.target.position + random.choice(self.steps)

Example of HoverBot behavior

Here's an example of how HoverBot should behave. In this case it is asked to hover near a PatrolBot. Notice the two move around but their positions always differ by $\langle 1,0\rangle$, $\langle -1,0\rangle$, $\langle 0,1\rangle$, or $\langle 0,-1\rangle$.

In [17]:
import bots
import plane

B1 = bots.PatrolBot(
    position=plane.Point2(0,0),
    direction=plane.Vector2(2,1),
    n=10
)
B2 = bots.HoverBot(target=B1)

for _ in range(10):
    print("PatrolBot at {}".format(B1.position))
    print("HoverBot at {}".format(B2.position))
    print("Difference={}\n".format(B2.position-B1.position))
    B1.update()
    B2.update()
PatrolBot at Point2(0,0)
HoverBot at Point2(1,0)
Difference=Vector2(1,0)

PatrolBot at Point2(2,1)
HoverBot at Point2(1,1)
Difference=Vector2(-1,0)

PatrolBot at Point2(4,2)
HoverBot at Point2(5,2)
Difference=Vector2(1,0)

PatrolBot at Point2(6,3)
HoverBot at Point2(7,3)
Difference=Vector2(1,0)

PatrolBot at Point2(8,4)
HoverBot at Point2(8,3)
Difference=Vector2(0,-1)

PatrolBot at Point2(10,5)
HoverBot at Point2(11,5)
Difference=Vector2(1,0)

PatrolBot at Point2(12,6)
HoverBot at Point2(12,5)
Difference=Vector2(0,-1)

PatrolBot at Point2(14,7)
HoverBot at Point2(15,7)
Difference=Vector2(1,0)

PatrolBot at Point2(16,8)
HoverBot at Point2(15,8)
Difference=Vector2(-1,0)

PatrolBot at Point2(18,9)
HoverBot at Point2(19,9)
Difference=Vector2(1,0)

Problem 3: NoBacktrackWanderBot

Add a subclass NoBacktrackWanderBot that behaves similarly to WanderBot, taking one random step up, down, left, or right on each step. However, this class has one essential difference: The step it chooses will never be the exact opposite of the step it took last time.

That is:

  • On the first call to update, this bot does exactly the same thing as a WanderBot
  • On any subsequent call to update, this bot knows the step v it took last time, and will choose a random step among the ones used by WanderBot that are not equal to -v.
    • e.g. if on step 1 the robot chooses $\langle 1,0\rangle$, then on step 2 it will choose one of $\langle 1,0\rangle$, $\langle 0,1\rangle$, $\langle 0,-1\rangle$ at random.

Note: This class can inherit directly from Bot or from any subclass thereof as you deem appropriate.

Solution

In [ ]:
class NoBacktrackWanderBot(Bot):
    """Similar to WanderBot, but does not take opposite step as last update cycle."""
    
    symbol = "\u24E6" # Unicode ⓦ (W in circle)
    
    steps = [
        plane.Vector2(1, 0),
        plane.Vector2(-1, 0),
        plane.Vector2(0, 1),
        plane.Vector2(0, -1),
    ]

    def __init__(self, position):
        """Initialize attribute `last_step` to keep track of previous step taken."""
        super().__init__(position)
        self.last_step = None
    
    def update(self):
        """Take a random step. Do not repeat previous step"""
        
        # If we've taken a step at least once so far:
        if self.last_step is not None:
            # Remove `-1 * self.last_step` from list of possibilites
            possible_steps = [v for v in self.steps if v != - self.last_step]
        else:
            # Else, we can choose any direction
            possible_steps = self.steps
        
        # Choose one of these steps at random
        v = random.choice(possible_steps)
        
        # Add v to the position of this robot
        self.move(v)
        
        # Remember step taken for next time
        self.last_step = v

Example of NoBacktrackWanderBot behavior

Here's an example of a short program that simulates a WanderBot and which points out each time the robot backtracks on its last step.

In [51]:
import bots
import plane

B = bots.WanderBot(position=plane.Point2(0,0))

position_log = []
print(B.__class__.__name__ + ":")
for _ in range(10):
    position_log.append(B.position)
    if len(position_log) > 2 and position_log[-3]==position_log[-1]:
        print("  ", B.position," (backtracked!)")
    else:
        print("  ", B.position)
    B.update()
WanderBot:
   Point2(0,0)
   Point2(0,1)
   Point2(0,0)  (backtracked!)
   Point2(0,1)  (backtracked!)
   Point2(1,1)
   Point2(1,0)
   Point2(0,0)
   Point2(1,0)  (backtracked!)
   Point2(0,0)  (backtracked!)
   Point2(-1,0)

And here is the same program using a NoBacktrackWanderBot. Note that no backtracking steps are detected.

In [52]:
import bots
import plane

B = bots.NoBacktrackWanderBot(position=plane.Point2(0,0))

position_log = []
print(B.__class__.__name__ + ":")
for _ in range(10):
    position_log.append(B.position)
    if len(position_log) > 2 and position_log[-3]==position_log[-1]:
        print("  ", B.position," (backtracked!)")
    else:
        print("  ", B.position)
    B.update()
NoBacktrackWanderBot:
   Point2(0,0)
   Point2(0,-1)
   Point2(-1,-1)
   Point2(-1,-2)
   Point2(0,-2)
   Point2(0,-1)
   Point2(1,-1)
   Point2(1,-2)
   Point2(1,-3)
   Point2(2,-3)

Epilogue

Robots walking off into the distance

With the completion of this assignment, our work on the robot simulation in MCS 275 is finally done! To celebrate, here's a picture created by the AI image generator DALL-E 2 in response to the prompt

A bunch of happy robots walking off into the distance with a sunset behind them digital art

Revision history

  • 2023-02-02 Initial publication