Ludium
Sign In
Introduction to Computer Science using Python
Computation & Python Basics
01Algorithms as Recipes02The Six Operations Behind Every Program03Primitives, Syntax, and Semantics04Objects, Types, and Type Casting05Expressions, Operators, and Types06Assignment vs. EqualityProblem set0/10Practice∞
01Objects, Names, and Assignment02String Concatenation, Repetition, and len()03String Indexing and Slicing04String Immutability and the print() Function05User Input, Type Conversion, and f-strings06Comparisons, Booleans, and Logical Operators07Conditionals: if, elif, and elseProblem set0/10Practice∞
Control Flow & Iteration
01Conditional Branching: if, elif, and else02Iteration and the While Loop03While Loops, Counters, and Infinite Loops04While Loop Variables and Running Products05The for Loop and range()06The Accumulator Pattern and range()Problem set0/10MIT problem set0/2Practice∞
01The break Statement: Exiting a Loop Early02Looping Over Strings and the in Operator03Guess-and-Check: Exhaustive Enumeration04for Loops, Boolean Flags, and Cube Roots05Nested Loops and Brute-Force Search06Floats, Binary, and Floating-Point ErrorProblem set0/10Practice∞
Numbers & Algorithms
01Converting Integers to Binary (and Negatives)02Why 0.1 Can't Be Stored: Fractions in Binary03How Floats Are Stored, and Why You Never Use ==04Successive Approximation and the Loop That Never EndsProblem set0/10Practice∞
01Why Approximation Search Hits a Wall02Halving the Search Space at Every Step03Coding Bisection Search for Square Roots04Fixing Bisection Search for Numbers Below One05Newton-Raphson: Sliding Down the Tangent LineProblem set0/10MIT problem set0/1Practice∞
Functions & Abstraction
01Abstraction and Decomposition: Why Your Phone Is a Black Box02What a Function Really Is: The Specification and Its Four Parts03Writing Your First Function: From a Sentence to is_even04How a Function Call Becomes Its Value: Parameters vs. Arguments05Return vs. Print: The Mysterious None, and Functions in Real Code06Building sum_odds: Plan on Paper, Then Catch the Off-by-One BugProblem set0/10Practice∞
Scope & Higher-Order Functions
01return vs. print, and the Hidden None That Reveals a Bug02Turning Bisection Square Root Into a Reusable Function03Environments and Scope: The Rule Behind UnboundLocalError04A Function Is an Object: Naming, Passing, and Tracing Calls05Higher-Order Functions: Building apply(criteria, n)Problem set0/10Practice∞
Lambdas & Sequences
01Writing Anonymous Functions With Lambda02Tracing Nested Calls with the Environment Model03Tuples: An Ordered, Mixed-Type Sequence04Why Tuples Are Immutable: Nesting and Iteration05Tuple Unpacking: One-Line Swaps and Many Returns06The Star (*args), Lists, and Pythonic LoopsProblem set0/10MIT problem set0/3Practice∞
Mutating Lists
01Lists Mutate, Tuples Don't: The Name vs the Object02append: Growing a List and the None Trap03Dot Notation: Building and Filtering Lists04split and join: Converting Between Strings and Lists05sort vs. sorted: Mutate in Place or Return a New List06Writing Functions That Mutate a List In Place07Appending While Looping, and extend vs append08Reassignment vs Mutation, Proven with id()Problem set0/10MIT problem set0/1Practice∞
Aliases & Copies
01Cloning with L[:]: Mutating a List In Place02del, pop, and remove: Three Ways to Delete03The Loop That Skips: Removing While Iterating04Aliases vs Clones: Why L2 = L1 Is Not a Copy05Shallow vs Deep Copy: copy.copy and copy.deepcopyProblem set0/10Practice∞
Comprehensions, Testing & Debugging
01List Comprehensions: Your Build-a-List Loop in One Line02Reading Any Comprehension: Iterable, Expression, Condition03Default Parameters: Defaults Last, Keywords at the Call Site04Returning a Function Object: return g, Not return g()05Catching a Returned Function: Two Names, One Object06Unit, Regression, and Integration Testing07Black Box vs Glass Box: Where Test Cases Come From08Debugging by Bisection: Print Statements as EvidenceProblem set0/10Practice∞
Exceptions & Assertions
01try and except: Catching an Exception Instead of Crashing02Named Exception Handlers, else, finally, and raise03raise ValueError and assert: Enforcing Your Docstring04One Empty List, Four Designs: Crash, None, Default, AssertProblem set0/10Practice∞
Dictionaries
01Why Lists Fail at Lookup: Parallel Lists and Nested Search02Dictionaries: Custom Keys, Curly Braces, and KeyError03Mutating a Dictionary: Add, Overwrite, del, and in04keys(), values(), items(): Three Windows Into a Dictionary05Hashing and Immutable Keys: Why a List Can't Be a Key06Case Study: Building a Word Frequency Dictionary07Ranking Words by Deleting Them: The Cost of MutationProblem set0/10MIT problem set0/8Practice∞
Recursion
01Multiplying With Only Addition: From Loops to a Smaller Copy02Writing mult_recur: Base Case, Recursive Step, and the Call Stack03Divide and Conquer: The Regrade Chain and Writing power_recur04Recursive Factorial Acted Out: Environments and When to RecurseProblem set0/10Practice∞
01fib_recur: Two Recursive Calls and an Exploding Call Tree02Memoization: One Dictionary Cuts 11 Million Calls to 6503Counting Basketball Scores: Three Base Cases, Three Branches04Recursion on Lists: Peel One Element, Trust the Rest05Debugging a Recursive Search: Print, Fix, and Return Types06Nested Lists: Flatten, Search, and Why Loops Fall Short07Reversing a List Recursively: The Brackets That Make It Legal08deep_rev: One Type Test Reverses Every LayerProblem set0/10MIT problem set0/3Practice∞
Classes & Objects
01Class vs Instance: The Blueprint Behind Every Object02Choosing Data and Behavior: Elevators, Employees, and Stacks03class Coordinate(object): Implementing a Type vs Using It04The __init__ Constructor: Why Every Method Starts With self05Creating Instances: Coordinate(3, 4), Dot Notation, and Memory06Methods and the Dot Operator: distance, and How self Gets BoundProblem set0/10MIT problem set0/3Practice∞
Composition & Dunder Methods
01Data Attributes vs Parameter Names: What self Guarantees02Returning a Value vs Mutating the Object: Writing to_origin03Composition and ValueError: A Circle Made of Coordinate Objects04Before the Dot Becomes self: Writing a SimpleFraction Class05Every Operator Is a Method: Meet Python's Dunder Names06The __str__ Method: You Decide What print Shows07Overloading * and float() for a Fraction Class08Inside reduce: a Nested gcd and the Branch That Returns an intProblem set0/10Practice∞
Inheritance
01Data and Procedural Attributes: Building the Animal Class02Getters, Setters and __str__: Why the Method Outlives the Attribute03Attribute Abuse From Outside, and a Dictionary of Animal Objects04make_animals: Walking Two Lists in Step to Build a List of Objects05Hierarchies and Subclasses: The Three Moves a Subclass Can Make06class Cat(Animal): Inheriting __init__ and the Chain Python Climbs07Overriding __init__: Person Calls Animal.__init__ By Name08Student, a Subclass of a Subclass, and the Rabbit Class Variable09__add__ and __eq__ on Rabbits: Operator Overloading With Shared IDsProblem set0/10MIT problem set0/5Practice∞
An Object-Oriented Case Study
01Designing a Workout Class: __init__ Makes Five Attributes From Three02Two State Dictionaries: __dict__ on the Class and on the Object03A Getter That Estimates: Class Variables, None, and datetime04parser.parse and Where a Class Variable Actually Lives05class RunWorkout(Workout): Inheritance and super().__init__06One __str__ in the Parent, Three Kinds of Workout Printing07A Subclass Where Its Parent Goes, and Positional Argument Order08Overriding get_calories: How Python Picks Which Method Runs09__eq__ With super(), and the Last Word on Building ClassesProblem set0/10MIT problem set0/4Practice∞
Program Efficiency
01Correct Isn't Fast: time.time() and Three Functions Built to Be Measured02Timing Nine Input Sizes, and Four Reasons the Seconds Measure the Machine03One Unit per Operation: Costing Three Functions by Hand, Then in Code04Ten Times the Input, a Hundred Times the Work: Reading Operation CountsProblem set0/10Practice∞
01A Finer Clock: time.perf_counter and a Runtime That Never Moves02Which Parameter Costs Time? compound, sum_of, and One Linear Shape03Brute Force, Bisection, or in: Timing Three Searches to 100 Million04A Loop Inside a Loop: the diameter Function and Quadratic Growth05Counting Operations: Exact Formulas and a Program That Counts Itself06Order of Growth: What to Measure, Which Input, and the Worst Case07Big O: An Upper Bound That Only Has to Hold Past the Crossover08Big Theta: Bounded From Both Sides, Keep Only the Dominant Term09Reading Theta Off the Loops: Two Laws and Six Complexity ClassesProblem set0/10Practice∞

Coding challenges on inheritance — MIT problem set

Problem 1Overriding __init__: Person Calls Animal.__init__ By Name

One Time Pads: A PlaintextMessage and Its Ciphertext

MIT 6.100L Introduction to CS and Programming Using Python, Fall 2022 · Problem set 4, Part B, 2.3) PlaintextMessage — __init__, get_pad and get_ciphertext · Dr. Ana Bell · CC BY-NC-SA 4.0 · MIT publishes no solution for this set; the worked solution is ours

Write the constructor __init__(self, input_text, pad=None) and the getters get_pad(self) and get_ciphertext(self) of MIT's PlaintextMessage class, a child class of the Message class you built in unit 17.

For this problem set, we will use a parent class called Message, which has two child classes: PlaintextMessage and EncryptedMessage.

  • Message contains methods that both plaintext and encrypted messages will need to use. For example, a method to get the text of the message. The child classes will inherit these shared methods from their parent.
  • PlaintextMessage contains methods that are specific to a plaintext message, such as a method for generating a one time pad or encrypting a message.
  • EncryptedMessage contains methods that are specific to a ciphertext, such as a method to decrypt a message given a one time pad.

Your finished Message class is in the starter as given code. Fill in these methods of the PlaintextMessage class according to the specifications in the docstrings:

  • __init__(self, input_text, pad=None)
    • You should use the parent class constructor (using super()) in this method to make your code more concise. (super().__init__(input_text) runs the parent's __init__ on this object. It is the short form of Message.__init__(self, input_text), the call-the-parent-by-name form Person used for Animal.__init__.)
    • The syntax pad=None indicates an optional argument that can be omitted and the specified default value of None is passed in instead. For example, PlaintextMessage('test') and PlaintextMessage('test', [0,15,3,9]) are both valid constructors but the former should generate a random pad and the latter should use the specified pad.
    • You should save a copy of pad as an attribute and not pad directly to protect it from being mutated.
    • A PlaintextMessage object has three attributes: the message text; the pad (a list of integers, determined by pad, or generated randomly using self.generate_pad() if pad is None); and the ciphertext (a string, input_text encrypted using the pad).
  • get_pad(self): this should return a copy of self.pad to prevent someone from mutating the original list.
  • get_ciphertext(self): used to access the ciphertext produced by applying the pad to the message text.

generate_pad and change_pad are the next two challenges, so leave their stubs as they are. Still write the branch of __init__ that calls self.generate_pad() when pad is None: one test checks it with a subclass of PlaintextMessage whose generate_pad returns a fixed pad, so it works before you have written the real one.

MIT has also implemented a __repr__ method so that when you print out your PlaintextMessage objects it returns a nice human readable result. Please do not change it.

p = PlaintextMessage('hello', [3, 0, 10, 11, 4])
print(p.get_text())  # hello
print(p.get_pad())  # [3, 0, 10, 11, 4]
print(p.get_ciphertext())  # kevws
print(PlaintextMessage('test', [0, 15, 3, 9]).get_ciphertext())  # ttv}
print(p)  # PlaintextMessage('hello', [3, 0, 10, 11, 4])
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
import random


# --- given: the Message class, completed in unit 17 (do not edit) ---

class Message(object):
    def __init__(self, input_text):
        '''
        Initializes a Message object

        input_text (string): the message's text

        a Message object has one attribute:
            the message text
        '''
        self.message_text = input_text

    def __repr__(self):
        '''
        Returns a human readable representation of the object
        DO NOT CHANGE

        Returns: (string) A representation of the object
        '''
        return f'''Message('{self.get_text()}')'''

    def get_text(self):
        '''
        Used to access the message text outside of the class

        Returns: (string) the message text
        '''
        return self.message_text

    def shift_char(self, char, shift):
        '''
        Used to shift a character as described in the pset handout

        char (string): the single character to shift.
                    ASCII value in the range: 32<=ord(char)<=126
        shift (int): the amount to shift char by

        Returns: (string) the shifted character with ASCII value in the range [32, 126]
        '''
        # the 95 printable characters have ASCII values 32..126: number them 0..94,
        # shift, wrap around with % 95 (never negative in Python), then map back
        position = ord(char) - 32
        new_position = (position + shift) % 95
        return chr(new_position + 32)

    def apply_pad(self, pad):
        '''
        Used to calculate the ciphertext produced by applying a one time pad to the message text.
        For each character in the text at index i shift that character by
            the amount specified by pad[i]

        pad (list of ints): a list of integers used to encrypt the message text
                        len(pad) == len(the message text)

        Returns: (string) The ciphertext produced using the one time pad
        '''
        ciphertext = ''
        for i in range(len(self.message_text)):
            ciphertext += self.shift_char(self.message_text[i], pad[i])
        return ciphertext

# --- end of given code ---


class PlaintextMessage(Message):
    def __init__(self, input_text, pad=None):
        '''
        Initializes a PlaintextMessage object.

        input_text (string): the message's text
        pad (list of ints OR None): the pad to encrypt the input_text or None if left empty
            if pad is not None then len(pad) == len(self.input_text)

        A PlaintextMessage object inherits from Message. It has three attributes:
            the message text
            the pad (list of integers, determined by pad
                or generated randomly using self.generate_pad() if pad is None)
            the ciphertext (string, input_text encrypted using the pad)
        '''
        pass

    def __repr__(self):
        '''
        Returns a human readable representation of the object
        DO NOT CHANGE

        Returns: (string) A representation of the object
        '''
        return f'''PlaintextMessage('{self.get_text()}', {self.get_pad()})'''

    def generate_pad(self):
        '''
        Generates a one time pad which can be used to encrypt the message text.

        The pad should be generated by making a new list and for each character
            in the message chosing a random number in the range [0, 110) and
            adding that number to the list.

        Returns: (list of integers) the new one time pad
        '''
        pass

    def get_pad(self):
        '''
        Used to safely access your one time pad outside of the class

        Returns: (list of integers) a COPY of your pad
        '''
        pass

    def get_ciphertext(self):
        '''
        Used to access the ciphertext produced by applying pad to the message text

        Returns: (string) the ciphertext
        '''
        pass

    def change_pad(self, new_pad):
        '''
        Changes the pad used to encrypt the message text and updates any other
        attributes that are determined by the pad.

        new_pad (list of ints): the new one time pad that should be associated with this message.
            len(new_pad) == len(the message text)

        Returns: nothing
        '''
        pass

Scratchpad— run any Python to test ideas
1
2
3
4
5
# Scratchpad — run any Python here to test ideas.
# Anything you write below stays separate from the problem's tests.

print("hello, world")

Python runtime ready in a moment
Python runtime ready in a moment
Visible tests · 3Examples — click to expand
?
the handout's example: hello with the pad [3, 0, 10, 11, 4]
?
MIT's tester: a PlaintextMessage keeps its text, because __init__ calls the parent constructor
?
MIT's tester: get_pad and get_ciphertext for 'he,(llo)'
Hidden tests · 6Bodies hidden — pass/fail only
?
Hidden test 1
?
Hidden test 2
?
Hidden test 3
?
Hidden test 4
?
Hidden test 5
?
Hidden test 6