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

Worksheet 2 Solutions

MCS 275 Spring 2021 - David Dumas

1. Double letters

This is the first of two exercises aimed at counting "double letters", like the o in "cook" or the "i" in "Hawaii".

Write a function double_letters_basic(text) that accepts a string text and counts the number of instances of a character in that string being equal to the one after it. It should return the count as an integer.

For this exercise, it doesn't matter whether the character is a letter or not, and runs of more than two copies will be counted multiple times. Thus, for example:

  • double_letters_basic("aardvark") returns 1 because of the aa at position 0
  • double_letters_basic("space wasps---most of whom are not hostile!!") returns 3 because of the -- at position 11, the -- at position 12, and the !! at the end
  • double_letters_basic("the raccoon nook keepers in Mississippi cooked the books") returns 9
  • double_letters_basic("Oolong") returns 0 because it has no repeated characters; the initial O and subsequent o are not the same character.

To test your function, put it into a script that runs in on these test strings, prints the results, and then also waits for the user to enter a string in the terminal (using input()) and counts double letters in that string as well.

In [6]:
# MCS 275 Spring 2021 Worksheet 2 problem 1
# Jennifer Vaccaro and David Dumas
# We declare that we are the only authors of this program and
# that we followed the rules given in the course syllabus.

def double_letters_basic(text):
    """Returns an integer count of any 
    repeated characters from the input text"""
    count = 0
    previous_char = ""
    for c in text:
        if c == previous_char:
            count += 1
        previous_char = c
    return count

examples = ["aardvark", 
            "space wasps---most of whom are not hostile!!",
            "the raccoon nook keepers in Mississippi cooked the books",
            "Oolong"]

for s in examples:
    print("double_letters_basic(\"{}\") returns {}".format(s,double_letters_basic(s)))

print()
text = input("Enter text to pass to double_letters_basic:")
print("double_letters_basic(\"{}\") returns {}".format(text,double_letters_basic(text)))
double_letters_basic("aardvark") returns 1
double_letters_basic("space wasps---most of whom are not hostile!!") returns 3
double_letters_basic("the raccoon nook keepers in Mississippi cooked the books") returns 9
double_letters_basic("Oolong") returns 0

Enter text to pass to double_letters_basic:Hello everyone!!
double_letters_basic("Hello everyone!!") returns 2

Here is alternative solution that uses the function zip() to iterate over pairs of adjacent characters.

In [7]:
# MCS 275 Spring 2021 Worksheet 2 problem 1
# David Dumas
# I declare that I wrote this solution myself
# and followed the rules in the syllabus.

def double_letters_basic(text):
    """Count repeated characters in `text`"""
    count=0
    for ccur,cnext in zip(text,text[1:]):
        if ccur == cnext:
            count += 1
    return count

examples = ["aardvark", 
            "space wasps---most of whom are not hostile!!",
            "the raccoon nook keepers in Mississippi cooked the books",
            "Oolong"]
for s in examples:
    print("double_letters_basic(\"{}\") returns {}".format(s,double_letters_basic(s)))

print()
text = input("Enter text to pass to double_letters_basic:")
print("double_letters_basic(\"{}\") returns {}".format(text,double_letters_basic(text)))
double_letters_basic("aardvark") returns 1
double_letters_basic("space wasps---most of whom are not hostile!!") returns 3
double_letters_basic("the raccoon nook keepers in Mississippi cooked the books") returns 9
double_letters_basic("Oolong") returns 0

Enter text to pass to double_letters_basic:Hello everyone!!
double_letters_basic("Hello everyone!!") returns 2

2. Double letters, improved version

Write a function double_letters(text,letters="abcdefghijklmnopqrstuvwxyz") that is an improved version of the double letter count from problem 1, with the following changes and new features:

  • The whole string is converted to lower case before any counting is done, so that repeated letters are case-insensitive.
  • Repeated characters are ignored unless they belong to the string letters, which can be given as an argument, but which defaults to the letters a-z.
  • If a letter appears three or more times in a row, it is not considered a double letter at all and does not contribute to the count.

Thus, for example:

  • double_letters("aardvark") returns 1 because of the double a at position 0
  • double_letters("space wasps---most of whom are not hostile!!") returns 0 because there are no double letters; --- is a non-letter repeated 3 times, and !! is a non-letter repeated twice
  • double_letters("the raccoon nook keepers in Mississippi cooked the books") returns 9
  • double_letters("Oolong") returns 1 because of the double o at position 0
  • double_letters("Keep writing those cool Python scripts",letters="efg") returns 1 because of the double e at position 1; the double o is not counted because this call specifies that only the letters e, f, and g should be counted.

Built a test program like in problem 1.

Suggestion: Try to build a solution that doesn't use any indexing (no range(len(...)) and no text[i] anywhere) and which only makes a single scan through the characters of the string. That is, you can do it with one loop that looks like for c in text:.

In [8]:
# MCS 275 Spring 2021 Worksheet 2 problem 1
# Jennifer Vaccaro and David Dumas
# We declare that we are the only authors of this program and
# that we followed the rules given in the course syllabus.

def double_letters(text, letters="abcdefghijklmnopqrstuvwxyz"):
    """Returns an integer count of any 
    repeated letters from the input text"""
    text = text.lower()
    count = 0 # total number of double letters seen so far
    consecutive_duplicates = 0
    previous_char = ""

    # Look at each character from the string and keep
    # track of the number of consecutive duplicates 
    # that have been seen.
    for c in text:
        if c == previous_char:
            # This character duplicates the previous one
            consecutive_duplicates += 1
        else:
            # This character is different from the previous
            # one, so we know previous_char was repeated exactly 
            # consecutive_duplicates+1 times.
            if previous_char in letters and consecutive_duplicates==1:
                # Exactly one duplicate of a character in letters
                # is the definition of a double letter
                count += 1
            consecutive_duplicates = 0
        previous_char = c

    # Check for double letter at the end of the string
    # (which wouldn't be seen by the loop, since it only
    #  checks for one when a different character is seen)
    if previous_char in letters and consecutive_duplicates == 1:
        count += 1
    return count

examples = ["aardvark", 
            "space wasps---most of whom are not hostile!!",
            "the raccoon nook keepers in Mississippi cooked the books",
            "Oolong"]

for s in examples:
    print("double_letters(\"{}\") returns {}".format(s,double_letters(s)))

# Example with custom letter list
s="Keep writing those cool Python scripts"
print("double_letters(\"{}\",letters=\"efg\") returns {}".format(s,double_letters(s,letters="efg")))
    
print()
text = input("Enter text to pass to double_letters:")
print("double_letters(\"{}\") returns {}".format(text,double_letters(text)))
double_letters("aardvark") returns 1
double_letters("space wasps---most of whom are not hostile!!") returns 0
double_letters("the raccoon nook keepers in Mississippi cooked the books") returns 9
double_letters("Oolong") returns 1
double_letters("Keep writing those cool Python scripts",letters="efg") returns 1

Enter text to pass to double_letters:Hello everyone!!
double_letters("Hello everyone!!") returns 1

3. Robot class module

Create a module called robots (in a file robots.py) that contains definitions of two classes that represent robots that move on a square grid according to certain rules.

Class WanderBot represents a robot that wanders aimlessly. It has a constructor that takes two integer arguments, x,y, which are integer coordinates of its initial position that are stored as attributes. The constructor also creates an attribute alive which is set to True and never changes. There is one method, update(), which takes no arguments. When called, update() will move the robot either up, down, left, or right one unit, selecting among these at random.

Tip: You can import random to get random number related features in your program. Then, random.randint(...) or random.choice(...) can handle the selection process. The docs for these functions can be found here.

Class MarchBot represents a robot that marches at a constant speed for a period of time, and then self-destructs. It has a constructor that takes two arguments x,y, which are the initial coordinates, and several optional arguments which have default values:

  • dx, default value 1, the horizontal movement per step
  • dy, default value 0, the vertical movement per step
  • maxstep, default value 10, the number of steps before self-destruct The constructor stores all of these as attributes, in addition to creating an attribute alive which is set to True. There is one method, update(), which takes no arguments. Calling update() will add dx to x and dy to y the first maxstep times it is called, after which it will set alive to False and do nothing.

Make a script that imports the module robots and uses it to simulate the motion of four robots that start at random positions, two WanderBots and two MarchBots, printing the state of the simulation at each step. It should use these lines of code to update the robot positions:

for bot in botlist:
    bot.update()

The program's output should show which robots are alive, where they are, and whether they have just activated self-destruct (i.e. if alive has just changed from True to False in the most recent step). Format it as follows:

Step 0
4 bots at positions:
1,2
1,5
2,-3
3,1

Step 1
4 bots at positions:
1,3
0,5
2,-2
3,0

...

Step 5
4 bots at positions:
1,6 (self-destruct in progress)
-1,2
1,-4
3,-4

Step 6
3 bots at positions:
-2,2
0,-4
3,-5
...

Bonus round ideas:

  • Make it so that when robots that collide (two or more occupy the same position for a step), all but one of the robots at that position are destroyed. Make it a random choice which one survives.
  • Make it possible to give the robots names as an optional argument to the constructor, and report the name in the output of the simulation.
In [ ]:
# MCS 275 Spring 2021 Worksheet 2 problem 3 robots.py
# Jennifer Vaccaro
# I declare that I am the sole author of this program and
# that I followed the rules given on the quiz and the
# course syllabus.

'''Module robots contains definitions of two robot classes'''
import random


class WanderBot():
    '''Robot that wanders aimlessly'''
    def __init__(self, x, y):
        '''Defines initial position attributes, and sets alive to True'''
        self.x = x
        self.y = y
        self.alive = True
    
    def update(self):
        '''Moves the robot one unit up, down, left, or right'''
        dx, dy = random.choice([(1,0), (0,1), (-1,0), (0,-1)])
        self.x += dx
        self.y += dy

class MarchBot():
    '''Robot that marches at a constant speed, then self-destructs'''
    def __init__(self, x, y, dx=1, dy=0, maxstep=10):
        '''Defines initial position, marching direction, and steps before self-destruction'''
        self.x = x
        self.y = y
        self.dx = dx
        self.dy = dy
        self.maxstep = maxstep
        self.alive = True
    
    def update(self):
        '''Updates position by dx and dy, or destructs robot if maxstep == 0'''
        if self.maxstep>0:
            self.x += self.dx
            self.y += self.dy
            self.maxstep -= 1
        else:
            self.alive = False
In [ ]:
# MCS 275 Spring 2021 Worksheet 2 problem 3 make_robots.py
# Jennifer Vaccaro
# I declare that I am the sole author of this program and
# that I followed the rules given on the quiz and the
# course syllabus.

import robots
import time

bot1 = robots.WanderBot(5,5)
bot2 = robots.WanderBot(-5,-5)
bot3 = robots.MarchBot(5,-5,dy=2,maxstep=8)
bot4 = robots.MarchBot(-5,5,dx=1,dy=-1)

botlist = [bot1,bot2,bot3,bot4]

step = 0
while len(botlist)>0:
    print("Step {} -- {} bots at positions:".format(step, len(botlist)))
    for bot in botlist:
        bot.update()
        if bot.alive:
            print("{},{}".format(bot.x, bot.y))
        else:
            print("{},{} (self-destruct in progress)".format(bot.x,bot.y))
            botlist.remove(bot)
    step += 1
    time.sleep(1.0)
    

4. RATS

This problem is about a method to generate a sequence of integers that was introduced by mathematician John Horton Conway. It is called Reverse, Add, Then Sort or RATS.

Starting from an integer n, like 1446, the process is as follows:

  1. Reverse the digits of the number (6441)
  2. Add this reversed number to the original number (1446 + 6441 = 7887)
  3. Sort the digits of the result from smallest to largest (7788), dropping any zeros that appear at the beginning.

The RATS sequence is obtained by applying this process over and over again. For example, starting from 1446 you get:

1446
7788
15666
12378
69999
156999
115566
17778
14559
111
222
444
888
1677
3489
...

Write a program rats.py to generate the RATS sequence starting from an integer given as its first command line argument.

The first version of the program should just print a certain number of terms of the sequence (say, 50).

Then, add a feature that looks for a repeating cycle. For example, if a certain number appears twice in the sequence, then the sequence will simply repeat everything between those two instances forever. Here's an example, starting with 1225:

4466
1111
2222
4444
8888
16777
34589
112333
444455
889999
1788899
1177777
4558889
13444447
77888888
156667777
233444489
1112278888
11999
11119
1223
4444
8888
16777
34589
112333
444455
889999
1788899
1177777
4558889
13444447
77888888
156667777
233444489
1112278888
11999
11119
1223
4444
8888
16777
34589
112333
444455
889999
1788899
1177777
4558889
13444447
77888888
156667777
233444489
1112278888
11999
11119
1223
4444
8888
16777
34589
112333
444455
889999
1788899
1177777
4558889
13444447
77888888
156667777
233444489
1112278888
...

The program should detect the repetition and print a message like:

RATS starting with 1225 ends in a periodic sequence: [11999, 11119, 1223, 4444, 8888, 16777, 34589, 112333, 444455, 889999, 1788899, 1177777, 4558889, 13444447, 77888888, 156667777, 233444489, 1112278888]"

or

RATS starting with 1 did not show a periodic sequence after 150 terms.
In [11]:
# MCS 275 Spring 2021 Worksheet 2 problem 4
# Jennifer Vaccaro
# I declare that I am the sole author of this program and
# that I followed the rules given on the quiz and the
# course syllabus.

def reverse_int(n):
    """Reverse the digits of integer n and return
    the resulting integer"""
    n_str = str(n)
    # Note: int() drops leading zeros automatically, so
    # e.g. int("0012") returns 12
    return int(n_str[::-1])

def next_rats(n):
    '''Reverses, adds, then sorts an integer n'''
    sum_int = n + reverse_int(n)
    sum_digits = list(str(sum_int)) # list of digits as characters; use a list so we can sort
    sum_digits.sort() 
    # Note: sorted order of "0",...,"9" is same as that of 0,...,9, so it is OK to sort
    # the digits as a list of characters instead of a list of ints!
    sorted_sum_str = "".join(sum_digits) # join characters into a single string
    return int(sorted_sum_str)

max_generations = 150
start_n = int(input("Enter the starting integer for RATS:"))
rats_list = [start_n]
n = start_n
periodic = False
for _ in range(max_generations):  # Conventional to use _ as name of a variable that is never used
    print(n)
    n = next_rats(n)
    if n in rats_list:
        print("RATS starting with {} end in a periodic sequence {}".format(start_n, rats_list[rats_list.index(n):]))
        periodic = True
        break
    else:
        rats_list.append(n)

if not periodic:
    print("No periodic sequence found in {} rats iterations".format(max_generations))
Enter the starting integer for RATS:1225
1225
4466
1111
2222
4444
8888
16777
34589
112333
444455
889999
1788899
1177777
4558889
13444447
77888888
156667777
233444489
1112278888
11999
11119
1223
RATS starting with 1225 end in a periodic sequence [4444, 8888, 16777, 34589, 112333, 444455, 889999, 1788899, 1177777, 4558889, 13444447, 77888888, 156667777, 233444489, 1112278888, 11999, 11119, 1223]

NOTE: If you try 1225 as the starting point, you'll get a message slightly different from the one suggested in the problem statement. That's OK. An eventually periodic sequence can be described in many correct ways. For example, QYUDABCABCABCABCABC... could be correctly described in either of these ways:

  • A string that ends in A,B,C repeating forever
  • A string that ends in C,A,B repeating forever

5. Text circles

Write a program circle.py that takes one command line argument, r, and then prints 40 lines of text, each containing 80 characters. The output should make a picture of a circle, using characters as pixels. When r=20 the circle should be slightly too big to fit in the block of text, and when r=1 it should be nearly too small to have any empty space inside.

For example, here is possible output for r=5:
















                                   @@@@@@@@@@@                                  
                                 @@@@       @@@@                                
                               @@@             @@@                              
                              @@@               @@@                             
                             @@@                 @@@                            
                             @@@                 @@@                            
                             @@@                 @@@                            
                              @@@               @@@                             
                               @@@             @@@                              
                                 @@@@       @@@@                                
                                   @@@@@@@@@@@

And here is possible output for r=15:






                                @@@@@@@@@@@@@@@@@                               
                           @@@@@@@             @@@@@@@                          
                       @@@@@                         @@@@@                      
                     @@@@                               @@@@                    
                  @@@@                                     @@@@                 
                 @@@                                         @@@                
               @@@                                             @@@              
              @@@                                               @@@             
             @@                                                   @@            
            @@                                                     @@           
           @@                                                       @@          
          @@@                                                       @@@         
          @@                                                         @@         
          @@                                                         @@         
         @@@                                                         @@@        
         @@@                                                         @@@        
         @@@                                                         @@@        
          @@                                                         @@         
          @@                                                         @@         
          @@@                                                       @@@         
           @@                                                       @@          
            @@                                                     @@           
             @@                                                   @@            
              @@@                                               @@@             
               @@@                                             @@@              
                 @@@                                         @@@                
                  @@@@                                     @@@@                 
                     @@@@                               @@@@                    
                       @@@@@                         @@@@@                      
                           @@@@@@@             @@@@@@@                          
                                @@@@@@@@@@@@@@@@@

This exercise is deliberately a little vague about how to go about this, but here is a hint: Each character you print corresponds to a certain point (x,y) in the plane, with character 40 on line 20 corresponding to (20,20). Calculating those coordinates inside of the main loop will be useful. Then, how would you decide whether to print a " " or a "@"?

Note: The reason for using 40 lines of 80 characters is that a character in the terminal is often approximately twice as tall as it is wide.

Bonus round: Modify the program so that it makes circles with softer edges, like this:





                                 ...............                                
                           ..***@@@@@@@@@@@@@@@@@***..                          
                       ..**@@@@@@@******.******@@@@@@@**..                      
                     .*@@@@@**...               ...**@@@@@*.                    
                  .**@@@@*..                         ..*@@@@**.                 
                .*@@@@*..                               ..*@@@@*.               
               .*@@@*.                                     .*@@@*.              
             .*@@@*.                                         .*@@@*.            
            .*@@@*.                                           .*@@@*.           
           .*@@*.                                               .*@@*.          
          .*@@*.                                                 .*@@*.         
         .*@@*.                                                   .*@@*.        
         .@@@*.                                                   .*@@@.        
        .*@@*.                                                     .*@@*.       
        .*@@*.                                                     .*@@*.       
        .@@@*                                                       *@@@.       
        .@@@.                                                       .@@@.       
        .@@@*                                                       *@@@.       
        .*@@*.                                                     .*@@*.       
        .*@@*.                                                     .*@@*.       
         .@@@*.                                                   .*@@@.        
         .*@@*.                                                   .*@@*.        
          .*@@*.                                                 .*@@*.         
           .*@@*.                                               .*@@*.          
            .*@@@*.                                           .*@@@*.           
             .*@@@*.                                         .*@@@*.            
               .*@@@*.                                     .*@@@*.              
                .*@@@@*..                               ..*@@@@*.               
                  .**@@@@*..                         ..*@@@@**.                 
                     .*@@@@@**...               ...**@@@@@*.                    
                       ..**@@@@@@@******.******@@@@@@@**..                      
                           ..***@@@@@@@@@@@@@@@@@***..                          
                                 ...............
In [ ]:
# MCS 275 Spring 2021 Worksheet 2 problem 5 circle.py
# Jennifer Vaccaro
# I declare that I am the sole author of this program and
# that I followed the rules given on the quiz and the
# course syllabus.

import sys

r = int(sys.argv[1])
outer_rad1 = r*1.2
inner_rad1 = r*0.9
for y in range(-20,21):
    for x in range(-40,41):
        x = x/2
        dist = (x**2 + y**2)**0.5
        if dist>inner_rad1 and dist<outer_rad1:
            print("X",end="")
        else:
            print(" ",end="")
    print() # Make a newline
In [ ]:
# MCS 275 Spring 2021 Worksheet 2 problem 5 circle_bonus.py
# Jennifer Vaccaro
# I declare that I am the sole author of this program and
# that I followed the rules given on the quiz and the
# course syllabus.

import sys

r = int(sys.argv[1])
outer_rad1 = r*1.2
inner_rad1 = r*0.9
outer_rad2 = r*1.4
inner_rad2 = r*0.8
outer_rad3 = r*1.6
inner_rad3 = r*0.7
for y in range(-20,21):
    for x in range(-40,41):
        x = x/2
        dist = (x**2 + y**2)**0.5
        if dist>inner_rad1 and dist<outer_rad1:
            print("X",end="")
        elif dist>inner_rad2 and dist<outer_rad2:
            print("x",end="")
        elif dist>inner_rad3 and dist<outer_rad3:
            print(".",end="")
        else:
            print(" ",end="")
    print() # Make a newline