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

Worksheet 2

MCS 275 Spring 2021 - David Dumas

Coding challenges instead of new material (again)

Normally, a worksheet covers the material from the previous week and from Monday's lecture.

However, there is no lecture on Monday this week, and we spent the first week on review of prerequisite material. Therefore, like the first worksheet, this one must focus on coding exercises that can be completed with MCS 260-level Python experience.

The problems on this worksheet are a bit more complex and open-ended than Worksheet 1, and aim to cover some topics not seen on the last worksheet.

Worksheet 3 will be the first "normal" one of MCS 275.

Instructions

Complete these coding exercises. Each one asks you to write one or more programs or modules. Even though these are not collected, you should get into the habit of following the coding standards that apply to all graded work in MCS 275.

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.

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:.

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.

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.

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:





                                 ...............                                
                           ..***@@@@@@@@@@@@@@@@@***..                          
                       ..**@@@@@@@******.******@@@@@@@**..                      
                     .*@@@@@**...               ...**@@@@@*.                    
                  .**@@@@*..                         ..*@@@@**.                 
                .*@@@@*..                               ..*@@@@*.               
               .*@@@*.                                     .*@@@*.              
             .*@@@*.                                         .*@@@*.            
            .*@@@*.                                           .*@@@*.           
           .*@@*.                                               .*@@*.          
          .*@@*.                                                 .*@@*.         
         .*@@*.                                                   .*@@*.        
         .@@@*.                                                   .*@@@.        
        .*@@*.                                                     .*@@*.       
        .*@@*.                                                     .*@@*.       
        .@@@*                                                       *@@@.       
        .@@@.                                                       .@@@.       
        .@@@*                                                       *@@@.       
        .*@@*.                                                     .*@@*.       
        .*@@*.                                                     .*@@*.       
         .@@@*.                                                   .*@@@.        
         .*@@*.                                                   .*@@*.        
          .*@@*.                                                 .*@@*.         
           .*@@*.                                               .*@@*.          
            .*@@@*.                                           .*@@@*.           
             .*@@@*.                                         .*@@@*.            
               .*@@@*.                                     .*@@@*.              
                .*@@@@*..                               ..*@@@@*.               
                  .**@@@@*..                         ..*@@@@**.                 
                     .*@@@@@**...               ...**@@@@@*.                    
                       ..**@@@@@@@******.******@@@@@@@**..                      
                           ..***@@@@@@@@@@@@@@@@@***..                          
                                 ...............