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

Quiz 2 Solutions

MCS 275 Spring 2021 - Emily Dumas

Solutions by Jennifer Vaccaro

Problem 2: Perfect square floor - 4 points

Write a function square_floor(n) that takes a positive integer n and returns the largest perfect square that is less than or equal to n.

For example:

  • square_floor(9) should return 9, because 3**2 = 9 <= 9 but 4**2 = 16 > 9.
  • square_floor(20) should return 16 because 4**2 = 16 <= 20 but 5**2 = 25 > 20

Put this function in a file quiz2prob2.py (with the usual required header and file-level docstring) and submit it. The file quiz2prob2.py doesn't need to do anything other than defining that single function.

In [ ]:
# MCS 275 Quiz 2 Problem 2
# Jennifer Vaccaro
# I have created this code in accordance with the course syllabus.

def square_floor(n):   
    """Finds the largest square smaller than the given integer"""
    ans_sqrt = int(n**0.5) # Take the square root, then convert to an integer
    return ans_sqrt**2 # Square and return

In this solution, it may be helpful to recall that when int() converts a float to an integer, it discards any fractional part, e.g. int(1.02) and int(1.999) both return 1.

Problem 3: Longest run - 4 points

Write a function longest_run_length(text) that takes a string text and returns an integer which is the length of the longest consecutive block of any single character in the string.

The function should consider any character, and use case-sensitive comparisons.

Therefore:

  • longest_run_length("heliotrope!!") should return 2 because "!" appears twice in a row, and no character appers 3 or more times in a row
  • longest_run_length("Distinguished raccoons") should return 3 because there are three spaces in a row in the string, and no character appears 4 times in a row
  • longest_run_length("") should return 0
  • longest_run_length("Eels have a complicated life cycle with many stages") should return 1 because the string is not empty, but no character appears twice (or more) in a row

Put this function in a file quiz2prob3.py (with the usual required header and file-level docstring) and submit it. The file quiz2prob3.py doesn't need to do anything other than defining that single function.

Note: It is expected that you can make this function pretty easily by modifying the solution to one of the problems on Worksheet 2.

In [15]:
# MCS 275 Quiz 2 Problem 3
# Jennifer Vaccaro
# I have created this code in accordance with the course syllabus.

def longest_run_length(text):
    """Given a text string, returns the length of the longest sequence of repeated characters"""
    last_char = ""
    current_run = 1
    longest_run = 0
    # Compare each character to the previous character
    # Count the number of consecutive repeats
    for c in text:
        if c == last_char:
            current_run += 1
        else:
            current_run = 1
        if current_run > longest_run:
            longest_run = current_run #update longest_run
        last_char = c
    # Return the value of the longest run
    return longest_run

Problem 4: RATS classifier - 4 points

Recall the RATS process described in Worksheet 2. This associated to any integer n a sequence of numbers, such as n=12 leading to the sequence 12, 33, 66, 123, 444, 888, 1677, 3489, 12333, 44556, ....

In Worksheet 2 you wrote a program to compute this sequence for one starting value, and to stop if a cycle was found. When we determine whether a certain starting value leads to a cycle, we'll say that we have classified the that starting value. So the Worksheet 2 program classifies a single starting value provided by the user.

Modify the program developed in Worksheet 2 so that instead of classifying one starting value, it tries each value of n between 1 and 100 (inclusive) and prints what it finds for each one. Each line of output should show the starting value and the observed behavior. The modified program shouldn't require any command line arguments or keyboard input.

When it is run, the first six lines of output should be:

1: No periodic sequence found in 150 iterations
2: No periodic sequence found in 150 iterations
3: Ends at periodic sequence [444, 888, 1677, 3489, 12333, 44556, 111, 222]
4: No periodic sequence found in 150 iterations
5: No periodic sequence found in 150 iterations
6: Ends at periodic sequence [444, 888, 1677, 3489, 12333, 44556, 111, 222]

and the last two lines of output should be:

99: Ends at periodic sequence [117, 288]
100: No periodic sequence found in 150 iterations

Note the slightly different way of printing the output compared to Worksheet 2.

Call this program quiz2prob4.py (with the usual required header and file-level docstring) and submit it.

In [16]:
# MCS 275 Quiz 2 Problem 4
# Jennifer Vaccaro
# I have adjusted this code from course worksheet solutions in accordance with 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)) 
    sum_digits.sort() 
    sorted_sum_str = "".join(sum_digits)
    return int(sorted_sum_str)

# Iterate start_n from 1-100 inclusive
for start_n in range(1,101):
    # Instead of using a user input, use start_n to run RATS.
    max_generations = 150
    rats_list = [start_n]
    n = start_n
    periodic = False
    for _ in range(max_generations):
        n = next_rats(n)
        if n in rats_list:
            print("{}: RATS ends 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("{}: RATS has no periodic sequence after {} iterations".format(start_n, max_generations))
1: RATS has no periodic sequence after 150 iterations
2: RATS has no periodic sequence after 150 iterations
3: RATS ends in a periodic sequence [444, 888, 1677, 3489, 12333, 44556, 111, 222]
4: RATS has no periodic sequence after 150 iterations
5: RATS has no periodic sequence after 150 iterations
6: RATS ends in a periodic sequence [444, 888, 1677, 3489, 12333, 44556, 111, 222]
7: RATS has no periodic sequence after 150 iterations
8: RATS has no periodic sequence after 150 iterations
9: RATS ends in a periodic sequence [117, 288]
10: RATS has no periodic sequence after 150 iterations
11: RATS has no periodic sequence after 150 iterations
12: RATS ends in a periodic sequence [444, 888, 1677, 3489, 12333, 44556, 111, 222]
13: RATS has no periodic sequence after 150 iterations
14: RATS has no periodic sequence after 150 iterations
15: RATS ends in a periodic sequence [444, 888, 1677, 3489, 12333, 44556, 111, 222]
16: RATS has no periodic sequence after 150 iterations
17: RATS has no periodic sequence after 150 iterations
18: RATS ends in a periodic sequence [117, 288]
19: RATS has no periodic sequence after 150 iterations
20: RATS has no periodic sequence after 150 iterations
21: RATS ends in a periodic sequence [444, 888, 1677, 3489, 12333, 44556, 111, 222]
22: RATS has no periodic sequence after 150 iterations
23: RATS has no periodic sequence after 150 iterations
24: RATS ends in a periodic sequence [444, 888, 1677, 3489, 12333, 44556, 111, 222]
25: RATS has no periodic sequence after 150 iterations
26: RATS has no periodic sequence after 150 iterations
27: RATS ends in a periodic sequence [117, 288]
28: RATS has no periodic sequence after 150 iterations
29: RATS ends in a periodic sequence [4444, 8888, 16777, 34589, 112333, 444455, 889999, 1788899, 1177777, 4558889, 13444447, 77888888, 156667777, 233444489, 1112278888, 11999, 11119, 1223]
30: RATS ends in a periodic sequence [444, 888, 1677, 3489, 12333, 44556, 111, 222]
31: RATS has no periodic sequence after 150 iterations
32: RATS has no periodic sequence after 150 iterations
33: RATS ends in a periodic sequence [444, 888, 1677, 3489, 12333, 44556, 111, 222]
34: RATS has no periodic sequence after 150 iterations
35: RATS has no periodic sequence after 150 iterations
36: RATS ends in a periodic sequence [117, 288]
37: RATS has no periodic sequence after 150 iterations
38: RATS ends in a periodic sequence [4444, 8888, 16777, 34589, 112333, 444455, 889999, 1788899, 1177777, 4558889, 13444447, 77888888, 156667777, 233444489, 1112278888, 11999, 11119, 1223]
39: RATS ends in a periodic sequence [444, 888, 1677, 3489, 12333, 44556, 111, 222]
40: RATS has no periodic sequence after 150 iterations
41: RATS has no periodic sequence after 150 iterations
42: RATS ends in a periodic sequence [444, 888, 1677, 3489, 12333, 44556, 111, 222]
43: RATS has no periodic sequence after 150 iterations
44: RATS has no periodic sequence after 150 iterations
45: RATS ends in a periodic sequence [117, 288]
46: RATS has no periodic sequence after 150 iterations
47: RATS ends in a periodic sequence [4444, 8888, 16777, 34589, 112333, 444455, 889999, 1788899, 1177777, 4558889, 13444447, 77888888, 156667777, 233444489, 1112278888, 11999, 11119, 1223]
48: RATS ends in a periodic sequence [444, 888, 1677, 3489, 12333, 44556, 111, 222]
49: RATS ends in a periodic sequence [4444, 8888, 16777, 34589, 112333, 444455, 889999, 1788899, 1177777, 4558889, 13444447, 77888888, 156667777, 233444489, 1112278888, 11999, 11119, 1223]
50: RATS has no periodic sequence after 150 iterations
51: RATS ends in a periodic sequence [444, 888, 1677, 3489, 12333, 44556, 111, 222]
52: RATS has no periodic sequence after 150 iterations
53: RATS has no periodic sequence after 150 iterations
54: RATS ends in a periodic sequence [117, 288]
55: RATS has no periodic sequence after 150 iterations
56: RATS ends in a periodic sequence [4444, 8888, 16777, 34589, 112333, 444455, 889999, 1788899, 1177777, 4558889, 13444447, 77888888, 156667777, 233444489, 1112278888, 11999, 11119, 1223]
57: RATS ends in a periodic sequence [444, 888, 1677, 3489, 12333, 44556, 111, 222]
58: RATS ends in a periodic sequence [4444, 8888, 16777, 34589, 112333, 444455, 889999, 1788899, 1177777, 4558889, 13444447, 77888888, 156667777, 233444489, 1112278888, 11999, 11119, 1223]
59: RATS has no periodic sequence after 150 iterations
60: RATS ends in a periodic sequence [444, 888, 1677, 3489, 12333, 44556, 111, 222]
61: RATS has no periodic sequence after 150 iterations
62: RATS has no periodic sequence after 150 iterations
63: RATS ends in a periodic sequence [117, 288]
64: RATS has no periodic sequence after 150 iterations
65: RATS ends in a periodic sequence [4444, 8888, 16777, 34589, 112333, 444455, 889999, 1788899, 1177777, 4558889, 13444447, 77888888, 156667777, 233444489, 1112278888, 11999, 11119, 1223]
66: RATS ends in a periodic sequence [444, 888, 1677, 3489, 12333, 44556, 111, 222]
67: RATS ends in a periodic sequence [4444, 8888, 16777, 34589, 112333, 444455, 889999, 1788899, 1177777, 4558889, 13444447, 77888888, 156667777, 233444489, 1112278888, 11999, 11119, 1223]
68: RATS has no periodic sequence after 150 iterations
69: RATS ends in a periodic sequence [156, 78]
70: RATS has no periodic sequence after 150 iterations
71: RATS has no periodic sequence after 150 iterations
72: RATS ends in a periodic sequence [117, 288]
73: RATS has no periodic sequence after 150 iterations
74: RATS ends in a periodic sequence [4444, 8888, 16777, 34589, 112333, 444455, 889999, 1788899, 1177777, 4558889, 13444447, 77888888, 156667777, 233444489, 1112278888, 11999, 11119, 1223]
75: RATS ends in a periodic sequence [444, 888, 1677, 3489, 12333, 44556, 111, 222]
76: RATS ends in a periodic sequence [4444, 8888, 16777, 34589, 112333, 444455, 889999, 1788899, 1177777, 4558889, 13444447, 77888888, 156667777, 233444489, 1112278888, 11999, 11119, 1223]
77: RATS has no periodic sequence after 150 iterations
78: RATS ends in a periodic sequence [78, 156]
79: RATS has no periodic sequence after 150 iterations
80: RATS has no periodic sequence after 150 iterations
81: RATS ends in a periodic sequence [117, 288]
82: RATS has no periodic sequence after 150 iterations
83: RATS ends in a periodic sequence [4444, 8888, 16777, 34589, 112333, 444455, 889999, 1788899, 1177777, 4558889, 13444447, 77888888, 156667777, 233444489, 1112278888, 11999, 11119, 1223]
84: RATS ends in a periodic sequence [444, 888, 1677, 3489, 12333, 44556, 111, 222]
85: RATS ends in a periodic sequence [4444, 8888, 16777, 34589, 112333, 444455, 889999, 1788899, 1177777, 4558889, 13444447, 77888888, 156667777, 233444489, 1112278888, 11999, 11119, 1223]
86: RATS has no periodic sequence after 150 iterations
87: RATS ends in a periodic sequence [156, 78]
88: RATS has no periodic sequence after 150 iterations
89: RATS has no periodic sequence after 150 iterations
90: RATS ends in a periodic sequence [117, 288]
91: RATS has no periodic sequence after 150 iterations
92: RATS ends in a periodic sequence [4444, 8888, 16777, 34589, 112333, 444455, 889999, 1788899, 1177777, 4558889, 13444447, 77888888, 156667777, 233444489, 1112278888, 11999, 11119, 1223]
93: RATS ends in a periodic sequence [444, 888, 1677, 3489, 12333, 44556, 111, 222]
94: RATS ends in a periodic sequence [4444, 8888, 16777, 34589, 112333, 444455, 889999, 1788899, 1177777, 4558889, 13444447, 77888888, 156667777, 233444489, 1112278888, 11999, 11119, 1223]
95: RATS has no periodic sequence after 150 iterations
96: RATS ends in a periodic sequence [156, 78]
97: RATS has no periodic sequence after 150 iterations
98: RATS has no periodic sequence after 150 iterations
99: RATS ends in a periodic sequence [117, 288]
100: RATS has no periodic sequence after 150 iterations