Mario (less comfortable)

Background

Recall Mario, the classic 1985 video game wherein the player, as Mario, runs and jumps his way through a mushroom kingdom, collecting coins and avoiding obstacles, all in an effort to save a princess.

In this problem, you don’t need to write any code for the game itself. Instead, let’s write some code to print a half-pyramid of blocks like you might see in the game itself, using hashes (#) for blocks, per the below, where the top-left of the game’s screen is deemed to be at the top-left of your terminal window.

#
##
###
####
#####
######
#######
########

This particular half-pyramid is eight rows tall and eight columns wide.

Demo

Getting Started

Log into cs50.dev, click on your terminal window, and run:

cd
mkdir mario
cd mario
code mario.py

That creates a new folder called mario, moves into it, and opens a new, empty file called mario.py for you to edit.

Specification

Implement a program, in mario.py, that recreates this half-pyramid using hashes for blocks, wherein the half-pyramid’s height should be a non-negative integer between 1 and 8, inclusive.

• Prompt the user for the pyramid’s height with input().
• Convert what the user typed to an integer with int(), and validate it yourself: if it isn’t a valid integer, or is outside the range 1 through 8, print an error (or simply say nothing) and prompt again. Keep prompting until the user gives you a valid height. Converting a non-numeric string like "foo" with int() raises a ValueError if you don’t guard against it, so think about how you’ll catch or avoid that before it crashes your program.
• Once you have a valid height, generate (with the help of print and one or more loops) the half-pyramid itself.
• Take care to align the bottom-left corner of your half-pyramid with the left-hand edge of your terminal window, and make sure there’s no trailing whitespace at the end of any row.

How to Test

Confirm that your program behaves as follows.

• If the user’s input is -1, your program should reject it and prompt the user again for a valid height.
• If the user’s input is 0, your program should likewise reject it.

• If the user’s input is 1, your program should output:

  #
  

• If the user’s input is 2, your program should output:

  #
  ##
  

• If the user’s input is 8, your program should output an eight-row pyramid like the one shown above.
• If the user’s input is 9 (or anything greater than 8), your program should reject it and prompt again; only after that should it accept a valid height like 8.
• If the user’s input is foo (not a number at all), your program should reject it without crashing, and prompt again.
• If the user presses Enter without typing anything, your program should treat that the same as any other invalid input: reject it and prompt again.

Style and Submission

Run these one at a time, from inside your mario folder.

Check your style:

style50 mario.py

Check your correctness:

check50 cs50/problems/2024/x/sentimental/mario/less

Submit your work:

submit50 cs50/problems/2024/x/sentimental/mario/less

Glossary

• algorithm — A finite sequence of steps that solves a problem or completes a task. Can be written in English, pseudocode, or code.
• loop — A statement that runs one or more statements, often repeatedly. (AP calls this iteration.)
• conditional statement — A statement that controls the flow of execution depending on some condition. Informally, this is usually an if statement, which might include an elif and an else. (AP calls this selection.)
• boolean expression — An expression whose value is either True or False.

Pathfinder

Translate to ASCII Hex ref

Click a letter to guess the next one.

A41	B42	C43	D44	E45	F46
G47	H48	I49	J4A	K4B	L4C
M4D	N4E	O4F	P50	Q51	R52
S53	T54	U55	V56	W57	X58
Y59	Z5A	SP20	!21	?3F

Full ASCII / hex table →

Background

In The Martian, Mark Watney is stranded on Mars with no way to talk to NASA directly. The only working camera nearby is on the old Pathfinder rover, and all NASA can do with it is aim it: pan left or right, tilt up or down. That’s not nothing, though. Mark lays a grid of hexadecimal digits, 0 through F, out where the camera can see it: 16 signs spaced 22.5 degrees apart in a full circle around the rover, one for each digit. NASA rotates the camera to one grid position, and Mark reads off one hex digit. Two digits make one byte, and one byte, run through ASCII, is one character. Rotate, pause, rotate, pause, and a sentence spells itself out one letter at a time.

Watch the scene (starts around 3:40, runs to about 4:00).

Try 484921 above to see how it works, then see the specification below for what your own program needs to do.

Getting Started

Log into cs50.dev, click on your terminal window, and run:

cd
mkdir pathfinder
cd pathfinder
code pathfinder.py

That creates a new folder called pathfinder, moves into it, and opens a new, empty file called pathfinder.py for you to edit.

Specification

Implement a program, pathfinder.py, that decodes a hexadecimal transmission from Mars back into the message it spells out.

• Print Transmission: (with a trailing space, no newline) and prompt the user for a string of hex digits with input().
• You can assume the transmission is well-formed: an even-length string of hexadecimal digits (0-9, A-F), with no spaces or other characters mixed in.
• Every two characters is one byte. Convert each byte to the character it represents in ASCII, and build up the decoded message one byte at a time.
• Print the decoded message, followed by a newline.

Usage

Your program should behave like the demo below.

$ python pathfinder.py
Transmission: 535441545553
STATUS

$ python pathfinder.py
Transmission: 4849204D4F4D
HI MOM

$ python pathfinder.py
Transmission: 4E4F542044454144
NOT DEAD

Hints

To Get Full Credit

It’s more important that you submit a working solution than that you do everything below. Submit early, then keep improving and resubmit as many times as you like.

• Structure your program with at least one function besides main(). You might write one to decode the transmission, or one to convert a single byte to a character; that part’s up to you.
• At the end of the program, add a comment describing any challenges you ran into or what you’d improve if you did this again. A sentence or two is fine.

Bonus

For extra credit: NASA isn’t the only one who needs to send a message. If your program is run with a single command-line argument, -e, have it encode instead of decode: print Message: (with a trailing space, no newline), prompt for a line of plain text with input(), and print its hex encoding instead, uppercase, two digits per character, with no spaces between them.

$ python pathfinder.py -e
Message: Hello
48656C6C6F

Your program should still decode as before when run with no arguments; check50 needs that to still pass.

Style and Submission

Run these one at a time, from inside your pathfinder folder.

Check your style:

style50 pathfinder.py

Check your correctness:

check50 porttack/cs50/problems/py/pathfinder

Submit your work:

submit50 porttack/cs50/problems/py/pathfinder

Glossary

• hexadecimal — Base-16, using 0 through 9 and A through F. Four bits per digit, so one byte is exactly two hex digits.
• byte — Eight bits. Enough to hold one of 256 values.
• ASCII — A table assigning a number from 0 to 127 to each of a small set of characters. int() and chr() move between a hex byte and the character it represents.
• string — A type that represents sequences of characters.

Palindromes

Background

A palindrome is a word that reads the same forwards and backwards, like “mom” or “racecar.” In this problem, you’ll write a program that reads in a sentence and counts how many of its words are palindromes.

This problem was originally written for this class’s C track by a past student, and is adapted here for Python.

This is just a single-word checker to build your intuition. Your program needs to handle a whole sentence at once, which is a bit more work; see the specification below.

Getting Started

Log into cs50.dev, click on your terminal window, and run:

cd
mkdir palindromes
cd palindromes
code palindromes.py

That creates a new folder called palindromes, moves into it, and opens a new, empty file called palindromes.py for you to edit.

Specification

Implement a program, in palindromes.py, that reads a sentence from the user and prints how many of its words are palindromes.

• Prompt the user for a sentence with input().
• A word counts as a palindrome if it reads the same forwards and backwards, ignoring case. Mom and mom are the same word for this purpose.
• Ignore punctuation attached to a word. civic. and kayak? should be treated as civic and kayak.
• A single letter, like a or I, does not count as a palindrome, even though it trivially reads the same both ways. Only words of two or more letters count.
• Words are separated by whitespace.
• Print the total number of palindromic words in the sentence, followed by a newline.

Usage

Your program should behave per the examples below. The underlined text is what a user has typed.

$ python palindromes.py
Sentence: My mom has a cat!
1

$ python palindromes.py
Sentence: Do you want to kayak with my mom and me?
2

$ python palindromes.py
Sentence: no palindromes here
0

Hints

• .split() breaks a sentence into a list of words, wherever there’s whitespace.
• A word’s punctuation isn’t part of the word, so you’ll need to strip it off before comparing. str.isalpha() can help you check which characters are letters and which aren’t.
• Python can reverse a string with slicing: word[::-1].
• Converting both a word and its reverse to the same case, with .lower(), takes care of “Mom” vs. “mom” for you.

Style and Submission

Run these one at a time, from inside your palindromes folder.

Check your style:

style50 palindromes.py

Check your correctness:

check50 porttack/cs50/problems/py/palindromes

Submit your work:

submit50 porttack/cs50/problems/py/palindromes

Glossary

• string — A type that represents sequences of characters.
• substring — A contiguous portion of a string.
• index — An integer value used to select an item in a sequence, such as a character in a string. In Python indices start from 0.
• boolean expression — An expression whose value is either True or False.

Square

Background

In Mario (less comfortable), you built a half-pyramid out of hash (#) characters. In this problem, you’ll build a square instead, but a hollow one: hashes around the edge, spaces in the middle.

This shows what your program’s output should look like for any size and character; it doesn’t validate input the way your program needs to.

Learning Objectives

• Repetition with loops
• Input validation
• Boolean expressions and conditionals
• print() with and without a trailing newline
• A function beyond main()

Specification

Implement a program, square.py, that builds a hollow square of hash characters.

• Prompt the user to enter a square size.
• Validate that the size is an integer between 2 and 8, inclusive. If the user enters something that isn’t an integer, or an integer outside that range, don’t print an error message: just prompt again.
• Once you have a valid size, print a hollow square of that size using hash (#) characters: hashes along the top row, the bottom row, the first column, and the last column, with spaces everywhere else in between.

For example, a size of 3 should print:

###
# #
###

And a size of 4 should print:

####
#  #
#  #
####

To Get Full Credit

It’s more important that you submit a working solution than that you do everything below. Submit early, then keep improving and resubmit as many times as you like.

• Structure your program with at least one function besides main(). You might write one to build the square, or one to prompt for and validate the size; that part’s up to you.
• At the end of the program, add a comment describing any challenges you ran into or what you’d improve if you did this again. A sentence or two is fine.

Usage

Your program should behave like the demo below.

$ python square.py
Size: 0
Size: -1
Size: 9
Size: 2
##
##

$ python square.py
Size: 4
####
#  #
#  #
####

Bonus

For extra credit: if you run your program with a single command-line argument that’s exactly one character, use that character instead of # when printing the square.

$ python square.py x
Size: 3
xxx
x x
xxx

Your program should still work fine with zero arguments; check50 needs that to still pass.

Getting Started

Log into cs50.dev, click on your terminal window, and run:

cd
mkdir square
cd square
code square.py

That creates a new folder called square, moves into it, and opens a new, empty file called square.py for you to edit.

Style and Submission

Run these one at a time, from inside your square folder.

Check your style:

style50 square.py

Check your correctness:

check50 porttack/cs50/problems/py/square

Submit your work:

submit50 porttack/cs50/problems/py/square

Glossary

• algorithm — A finite sequence of steps that solves a problem or completes a task. Can be written in English, pseudocode, or code.
• loop — A statement that runs one or more statements, often repeatedly. (AP calls this iteration.)
• conditional statement — A statement that controls the flow of execution depending on some condition. Informally, this is usually an if statement, which might include an elif and an else. (AP calls this selection.)
• boolean expression — An expression whose value is either True or False.

Caesar

Background

Implement a program that encrypts messages using Caesar’s cipher.

$ python caesar.py 13
plaintext:  HELLO
ciphertext: URYYB

(plaintext: has an extra trailing space so it lines up under ciphertext: below it.)

This only encrypts, since that’s all the assignment asks for. Use it to check your own program’s output against, once you’ve started writing caesar.py.

Walkthrough

Getting Started

Log into cs50.dev, click on your terminal window, and run:

cd
mkdir caesar
cd caesar
code caesar.py

That creates a new folder called caesar, moves into it, and opens a new, empty file called caesar.py for you to edit.

Specification

Design and implement a program, caesar.py, that encrypts messages using Caesar’s cipher.

• Your program must accept a single command-line argument, a non-negative integer. Let’s call it k for the sake of discussion.
• If your program is executed without any command-line arguments, or with more than one, print an error message of your choice and exit immediately with a status code of 1 (exit(1)). The message’s exact wording doesn’t matter and isn’t checked; only the exit code is. The Usage examples below just show one message you could use.
• You can assume that, if a user does provide a command-line argument, it will be a non-negative integer. No need to check that it’s numeric, but you do need to convert it to an int yourself.
• Do not assume that k will be less than or equal to 26. Your program should work for any non-negative k. Even if k is greater than 26, alphabetical characters in your input should remain alphabetical characters in your output. For instance, if k is 27, A should become B, not some non-alphabetical character, provided you wrap around from Z back to A.
• Your program must print plaintext: (with a trailing space, no newline) and then prompt the user for a string of plaintext with input().
• Your program must print ciphertext: (with a trailing space, no newline) followed by the plaintext’s corresponding ciphertext, with each alphabetical character in the plaintext rotated by k positions. Non-alphabetical characters should be printed unchanged.
• Your program must preserve case: capitalized letters, though rotated, must remain capitalized; lowercase letters, though rotated, must remain lowercase.
• After outputting the ciphertext, print a newline.

Usage

Your program should behave per the examples below. As above, plaintext: carries an extra trailing space so both labels line up.

$ python caesar.py 1
plaintext:  HELLO
ciphertext: IFMMP

$ python caesar.py 13
plaintext:  hello, world
ciphertext: uryyb, jbeyq

$ python caesar.py 13
plaintext:  be sure to drink your Ovaltine
ciphertext: or fher gb qevax lbhe Binygvar

$ python caesar.py
Usage: python caesar.py k

$ python caesar.py 1 2 3 4 5
Usage: python caesar.py k

Hints

argv is a list of strings representing the command-line arguments; len(argv) tells you how many there are. You’ll need to import both argv and exit:

from sys import argv, exit

Once you’ve confirmed there’s exactly one argument, you can access it with argv[1], and convert it to an integer with int(argv[1]).

You can iterate over the characters in a string, printing each one without a trailing newline, with code like:

for c in p:
    print(c, end="")

You may also find Python’s ord() and chr() functions useful for rotating letters. Letters are contiguous in ASCII: ord("a") through ord("z") are 26 numbers in a row (and separately, so are ord("A") through ord("Z")). Subtracting the first one turns a letter into a position from 0 to 25, which you can rotate and wrap with % 26, then turn back into a letter by adding the first one back and calling chr().

Style and Submission

Run these one at a time, from inside your caesar folder.

Check your style:

style50 caesar.py

Check your correctness:

check50 porttack/cs50/problems/py/caesar

Submit your work:

submit50 porttack/cs50/problems/py/caesar

Glossary

• algorithm — A finite sequence of steps that solves a problem or completes a task. Can be written in English, pseudocode, or code.
• loop — A statement that runs one or more statements, often repeatedly. (AP calls this iteration.)
• ASCII — A table assigning a number from 0 to 127 to each of a small set of characters. ord() and chr() move between a character and its ASCII number.
• encryption — Encoding data so only holders of the key can read it. A Caesar cipher is a very weak form of this: the key is just a number from 0 to 25, so it can be broken by trying every one.
• modulus operator — The % operator, which works on integers and returns the remainder when one number is divided by another. It’s what wraps the alphabet around from Z back to A. (AP calls this MOD.)

Readability

Background

Some writing is easy to read. Some takes real effort. Longer words and longer sentences tend to push a text toward the harder end, and over the years people have turned that observation into a whole family of “readability tests,” each one a formula for estimating which is which. In 1975, Meri Coleman and T. L. Liau came up with one of them: feed it a passage of English text, and it estimates the U.S. grade level a reader would need to understand it, based on nothing more than how long the words and sentences tend to be. No dictionary, no grammar check, just averages.

It’s not a perfect measure. A sentence can be long and still be easy, or short and still be dense. But it’s a genuinely useful first pass, and it’s the same kind of estimate you’ll find behind the “readability” score in a word processor or a librarian’s reading-level guide on a book jacket.

This mirrors the formula so you can play with real text before you write any code, but it’s more forgiving than your program needs to be (it shrugs off extra spaces and blank lines). Your program should follow the word-counting rule in the spec exactly, not this demo’s looser version.

Walkthrough

Before you start writing code, step through this with the class. It scans a real sentence one character at a time, so you can see exactly when a letter, a word, or a sentence gets counted, before you have to write that logic yourself.

Click into the box, then use the buttons below it, the arrow keys, or Page Up/Down to move between its 7 steps. On step 3, the spacebar steps the character scan itself.

Getting Started

Log into cs50.dev, click on your terminal window, and run:

cd
mkdir readability
cd readability
code readability.py

That creates a new folder called readability, moves into it, and opens a new, empty file called readability.py for you to edit.

Starter Code

Paste this into readability.py to start from. It’s the same four-function shape as the walkthrough: three counters and a function for the formula, each one currently just a stub with pass for a body.

The three counters each carry a couple of >>> examples, the same doctest format you’ve already seen in Think Python. They’ll fail until you replace pass with real code; run python3 -m doctest readability.py from inside your readability folder to check them.

def main():
    text = input("Text: ")
    letters = count_letters(text)
    words = count_words(text)
    sentences = count_sentences(text)
    index = coleman_liau(letters, words, sentences)
    # round index, then print one of the three outputs


def count_letters(text):
    """
    Returns the number of letters in text.

    >>> count_letters("cat")
    3
    >>> count_letters("You're")
    5
    """
    pass


def count_words(text):
    """
    Returns the number of words in text.

    >>> count_words("cat dog")
    2
    >>> count_words("sister-in-law is one word")
    4
    """
    pass


def count_sentences(text):
    """
    Returns the number of sentences in text.

    >>> count_sentences("Wait! Really?")
    2
    """
    pass


def coleman_liau(letters, words, sentences):
    """
    Returns the Coleman-Liau grade level for the given letter, word,
    and sentence counts.
    """
    pass


if __name__ == "__main__":
    main()

Specification

Implement a program, readability.py, that computes the approximate grade level needed to comprehend a piece of text.

• Print Text: (with a trailing space, no newline) and prompt the user for a string of text with input().
• Compute the number of letters, words, and sentences in the text, using these rules:
  • A letter is any character a through z or A through Z. Digits, punctuation, and spaces are not letters, and neither is an apostrophe.
  • A word is any sequence of characters separated by spaces. You can assume the text has no leading or trailing spaces, and never has two spaces in a row.
  • A sentence ends with a period, an exclamation point, or a question mark. Count one of those characters as one sentence, wherever it appears.
• From those three counts, compute two averages:
  • L, the average number of letters per 100 words.
  • S, the average number of sentences per 100 words.

• Compute the Coleman-Liau index:

  index = 0.0588 * L - 0.296 * S - 15.8
  

• Round the index to the nearest whole number before deciding what to print.
  • If the rounded index is less than 1, print Before Grade 1.
  • If the rounded index is 16 or more, print Grade 16+.
  • Otherwise, print Grade N, where N is the rounded index.
• After printing, output a newline.

Usage

Your program should behave per the examples below.

$ python readability.py
Text: See Spot run. Spot runs fast.
Before Grade 1

$ python readability.py
Text: Turtles carry their homes on their backs and can live for over a hundred years.
Grade 7

$ python readability.py
Text: When students submit their problem sets, check50 automatically verifies whether the program's observed behavior matches the staff-written expectations for a range of sample inputs, and style50 separately reports on formatting.
Grade 16+

A few more to try, spanning the full range from Before Grade 1 up to Grade 16+:

Hints

To Get Full Credit

It’s more important that you submit a working solution than that you do everything below. Submit early, then keep improving and resubmit as many times as you like.

• Structure your program with more than one function besides main(). The starter code’s four-function shape, one function each for letters, words, sentences, and the formula itself, is a reasonable way to do it, but you’re free to rename or reorganize as long as the same decomposition idea holds: more than one function doing real work.
• Each counting function should take the text and return a number. None of them should print anything themselves; only main() should decide what to print, and only once, at the end.
• At the end of the program, add a comment describing any challenges you ran into or what you’d improve if you did this again. A sentence or two is fine.

Style and Submission

Run these one at a time, from inside your readability folder.

Check your style:

style50 readability.py

Check your correctness:

check50 cs50/problems/2024/x/sentimental/readability

Submit your work:

submit50 cs50/problems/2024/x/sentimental/readability

Glossary

• Coleman-Liau index — A readability formula that estimates a U.S. grade level from the average number of letters and sentences per 100 words, without looking at word meaning or grammar.
• function — A named, reusable block of code. Can take parameters and return a value.
• parameter — A value a function accepts as input, named in its definition.
• return value — The value a function hands back to whatever called it, using a return statement. Different from printing, which only displays something and hands nothing back.
• average — A single number summarizing a set of values. Here, letters and sentences are each expressed as an average per 100 words, rather than a raw count, so texts of different lengths can be compared fairly.

Battery Gauge

Background

A fresh AA alkaline battery is rated at 1.5V, but “rated” isn’t the same as “reads.” Straight off the shelf, a fresh cell often measures a little higher, sometimes 1.6V or more. As it discharges under use, the voltage sags, and by around 1.2V most devices start acting flaky: dimmer lights, sluggish motors, a wall clock running slow. Below that, the cell still has some chemistry left in it, but not enough to trust.

This problem asks you to write a program that takes a voltage reading and a battery’s nominal (rated) voltage, and reports back one of three things: that the battery is low, that it’s a plain percentage of nominal, or that it’s reading unusually strong. Structurally, this is close to a classic problem about a fuel tank and a fraction: parse two numbers, do some division, and turn the result into a human-readable reading. If you’ve seen that problem before, or asked an AI to solve it for you, the shape will look familiar, but read the specification below closely anyway. A couple of the rules here work differently, on purpose.

This shows what your program’s output should look like for valid input; it doesn’t validate or reject anything the way your program needs to. See the specification below for the actual rules.

Getting Started

Log into cs50.dev, click on your terminal window, and run:

cd
mkdir battery
cd battery
code battery.py

That creates a new folder called battery, moves into it, and opens a new, empty file called battery.py for you to edit.

Starter Code

Paste this into battery.py to start from. gauge_reading is stubbed out with pass and two >>> examples, the same doctest format you’ve already seen in Think Python; run python3 -m doctest battery.py from inside your battery folder to check them. They’ll fail until you replace pass with real code, and you should add one more example of your own, for the LOW case. If every example passes, the command prints nothing at all; silence means you’re good. A failure prints a diff of what it expected versus what your code returned.

Notice the first example passes in 89.6, not a whole number. gauge_reading should round to the nearest integer itself rather than trust its caller to have already done it; that way it gives a correct reading no matter where in your program the rounding ends up happening.

main is left as a comment on purpose. The retry loop is the actual point of this problem, and a docstring can’t check it the way it can check gauge_reading (see the note further down about why), so there’s no starter shape to hand you there beyond the reminder of what it needs to do.

# Student Initials:
"""
Battery Gauge

Slug: porttack/cs50/problems/py/battery
Doctests: python3 -m doctest battery.py
"""


def main():
    # Prompt, then validate inside a try/except loop per the
    # specification below. Once you have a valid reading, print what
    # gauge_reading() returns.
    pass


def gauge_reading(percent):
    """
    Returns the gauge reading for percent, a percentage of nominal
    voltage. Rounds percent to the nearest integer itself, so it's
    fine to pass in a number that isn't rounded yet.

    >>> gauge_reading(89.6)
    '90%'
    >>> gauge_reading(105)
    'GOOD (105%)'
    """
    pass


if __name__ == "__main__":
    main()

Specification

Implement a program, battery.py, that reads a battery’s voltage and reports its charge.

• Prompt the user for input with input("Voltage: "). The user will enter two numbers separated by a slash, X/Y, where X is the measured voltage and Y is the battery’s nominal (rated) voltage. Neither is guaranteed to be a whole number: 1.35/1.5 is valid input, not just 3/4.
• Compute the reading as a percentage of nominal, X / Y * 100, rounded to the nearest integer.
• If the percentage is 80 or less, print LOW (N%), where N is the percentage. For example, LOW (50%).
• If the percentage is 100 or more, print GOOD (N%). Unlike a fuel tank, a battery can genuinely read above its nominal voltage and still be a valid reading, so don’t reject it. For example, GOOD (104%).
• Otherwise (the percentage is between 81 and 99, inclusive), print just N%, with no label. For example, 73%.
• X must not be negative. A negative voltage isn’t a real reading; prompt again.
• Y must be a positive number. If it’s zero or negative, prompt again.
• If the user’s input isn’t in the X/Y format, or X or Y isn’t a number at all, prompt again.
• In every “prompt again” case above, don’t print an error message, just silently ask again with the same "Voltage: " prompt.

Usage

Your program should behave like the demo below.

$ python battery.py
Voltage: -1/1.5
Voltage: abc/1.5
Voltage: 1.35/1.5
90%

$ python battery.py
Voltage: 1.2/1.5
LOW (80%)

$ python battery.py
Voltage: 2.25/1.5
GOOD (150%)

Hints

If exceptions still feel unfamiliar, CS50’s own lecture on the topic is a solid general reference: CS50P - Lecture 3 - Exceptions. It’s the same lecture that introduces the fuel tank problem mentioned above, so it covers try/except and raise from the ground up. The hints below are specific to this problem, not a substitute for it, and they build on each other in order: if you’re not sure where to start, work through them top to bottom rather than jumping to the last one.

To Get Full Credit

It’s more important that you submit a working solution than that you do everything below. Submit early, then keep improving and resubmit as many times as you like.

• Fill in gauge_reading with real code, and add one more >>> example of your own to its docstring, for the LOW case. It’s a pure function, no input, no exceptions, so it doctests cleanly. Don’t try to do the same for the retry loop in main: a docstring can’t express “type this, then that raises an exception,” so it doesn’t doctest well at all. We’ll cover testing code that raises exceptions later on, with a different tool.
• At the end of the program, add a comment describing any challenges you ran into or what you’d improve if you did this again. A sentence or two is fine.

Style and Submission

Run these one at a time, from inside your battery folder.

Check your style:

style50 battery.py

Check your correctness:

check50 porttack/cs50/problems/py/battery

Submit your work:

submit50 porttack/cs50/problems/py/battery

Glossary

• exception — An error Python raises while a program is running, as opposed to one caught before the program starts (like a syntax error). ValueError and ZeroDivisionError are both exceptions.
• try/except — A block that attempts some code (try) and, if it raises an exception, runs different code instead of crashing (except), catching one or more listed exception types.
• raise — A statement that triggers an exception yourself, on purpose. Lets you route a rule Python doesn’t enforce on its own (like “this number can’t be negative”) through the same except block that catches Python’s built-in exceptions.
• ZeroDivisionError — The exception Python raises when code divides by zero.
• ValueError — The exception Python raises when a function gets an argument of the right type but an inappropriate value, such as int("abc") or float("abc").

Lineup (less comfortable)

Background

A queue shows up everywhere once you notice the shape: the checkout line at a store, a printer working through a stack of print jobs, a line of people waiting for a bathroom pass. Whoever got there first gets served first. Nobody cuts, and nobody new joins anywhere but the back. That rule has a name: first in, first out, or FIFO.

This problem asks you to build a FIFO line for a much more fun occasion: you’re running the music table at the school dance, and classmates keep texting you song requests. You can’t play them all at once, so you add each request to the back of the lineup as it comes in, and whenever one song ends, you pull the next one off the front. The two operations that make a queue a queue, adding to the back and removing from the front, have their own names too: enqueue and dequeue. That’s what you’ll implement.

This shows the idea: whichever request has waited longest plays next, and the lineup never holds more than 5 songs at once. It doesn’t match your program’s exact commands or wording; see the specification below for those.

Getting Started

Log into cs50.dev, click on your terminal window, and run:

cd
mkdir lineup_less
cd lineup_less
code lineup_less.py

That creates a new folder called lineup_less, moves into it, and opens a new, empty file called lineup_less.py for you to edit.

Starter Code

Paste this into lineup_less.py to start from. enqueue and dequeue are stubbed out with pass and doctest examples; run python3 -m doctest lineup_less.py from inside your lineup_less folder to check them. They’ll fail until you replace pass with real code.

main is left as a comment on purpose, same as it was in Battery Gauge: the command loop is the actual point of this problem, and a docstring can’t check a loop the way it can check a pure function.

# Student Initials:
"""
Lineup (less comfortable)

Slug: porttack/cs50/problems/py/lineup_less
Doctests: python3 -m doctest lineup_less.py
"""

CAPACITY = 5


def main():
    # Loop, prompting "Command: " each time, until the input is
    # "DONE". See the specification below for exactly what ADD and
    # PLAY need to do, and what to print for each case.
    pass


def enqueue(lineup, song):
    """
    Adds song to the back of lineup if there's room (fewer than
    CAPACITY songs already waiting). Returns True if song was added,
    False if lineup was already full and song was not added.

    >>> lineup = []
    >>> enqueue(lineup, "Sunroof")
    True
    >>> lineup
    ['Sunroof']
    """
    pass


def dequeue(lineup):
    """
    Removes and returns the song at the front of lineup. Returns
    None, and leaves lineup unchanged, if lineup is empty.

    >>> lineup = ["Sunroof", "Flowers"]
    >>> dequeue(lineup)
    'Sunroof'
    >>> lineup
    ['Flowers']
    >>> dequeue([])
    """
    pass


if __name__ == "__main__":
    main()

Specification

Implement a program, lineup_less.py, that runs the song request line for the dance.

• Keep the lineup itself in a plain list, starting empty. CAPACITY is already defined as 5.
• Loop, prompting exactly "Command: " each time.
• If the input is exactly DONE, stop looping. Print nothing else.
• If the input starts with ADD followed by at least one more character, everything after that first space is the song title, spaces and all. For example, ADD Anti Hero requests the song Anti Hero, not just Anti.
  • If the lineup has fewer than 5 songs waiting, call enqueue and print Added: <song>.
  • If the lineup is already full, print Lineup is full and don’t add the song.
• If the input is exactly PLAY:
  • If the lineup isn’t empty, call dequeue and print Now playing: <song>.
  • If the lineup is empty, print Nothing to play.
• Anything else, a blank line, ADD with nothing after it, a misspelled command, lowercase add, prints Huh? and prompts again. Don’t crash on unexpected input.
• enqueue and dequeue should never print anything or read input themselves. All the printing happens in main, based on what they return.

Usage

Your program should behave like the demo below.

$ python lineup_less.py
Command: ADD Anti-Hero
Added: Anti-Hero
Command: ADD Flowers
Added: Flowers
Command: PLAY
Now playing: Anti-Hero
Command: PLAY
Now playing: Flowers
Command: PLAY
Nothing to play
Command: DONE

$ python lineup_less.py
Command: ADD A
Added: A
Command: ADD B
Added: B
Command: ADD C
Added: C
Command: ADD D
Added: D
Command: ADD E
Added: E
Command: ADD F
Lineup is full
Command: DONE

Hints

To Get Full Credit

It’s more important that you submit a working solution than that you do everything below. Submit early, then keep improving and resubmit as many times as you like.

• Fill in enqueue and dequeue with real code, and add one more >>> example of your own to each docstring covering a case not already shown (the full lineup for enqueue, for instance). Both are pure enough to doctest cleanly. Don’t try to doctest main; same reasoning as Battery Gauge, a loop that reads input doesn’t fit the format.
• At the end of the program, add a comment describing any challenges you ran into or what you’d improve if you did this again. A sentence or two is fine.

Style and Submission

Run these one at a time, from inside your lineup_less folder.

Check your style:

style50 lineup_less.py

Check your correctness:

check50 porttack/cs50/problems/py/lineup_less

Submit your work:

submit50 porttack/cs50/problems/py/lineup_less

Once this is working, try the more comfortable version: Lineup (more comfortable) picks up right where this leaves off, the same lineup, plus a history of everything that’s already played.

Glossary

• queue — A data structure where items come out in the same order they went in: first in, first out (FIFO). A line of people works the same way.
• enqueue — Adding an item to the back of a queue.
• dequeue — Removing and returning the item at the front of a queue.
• FIFO — “First in, first out.” The rule that makes a queue a queue: whatever’s been waiting longest comes out first.

Lineup (more comfortable)

Background

This is the more comfortable version of Lineup (less comfortable): same DJ booth, same song request line. If you haven’t done that yet, start there; this problem assumes you already have working ADD and PLAY commands, just rebuilt here with a different tool.

Two things are new. First, the lineup itself moves from a plain list to deque, the queue class built into Python’s collections module. Second, you’re adding a running history of everything that’s already played, so you can answer the question that always comes up at a dance: “wait, what was that song two songs ago?” History works backwards from the lineup: the answer you want first is the most recent song, then the one before that, and so on. Something that comes out most-recently-added-first instead of first-in-first-out is called a stack, and its two operations are push (add to the top) and pop (remove from the top).

This shows the idea: the lineup itself behaves exactly like it did in Lineup, and Back walks backwards through what already played, most recent first. It doesn’t match your program’s exact commands or wording; see the specification below for those.

Getting Started

Log into cs50.dev, click on your terminal window, and run:

cd
mkdir lineup_more
cd lineup_more
code lineup_more.py

That creates a new folder called lineup_more, moves into it, and opens a new, empty file called lineup_more.py for you to edit.

Starter Code

Paste this into lineup_more.py to start from. enqueue and dequeue are already filled in for you this time, the same logic as Lineup, just working on a deque instead of a list. push and pop are the new parts, stubbed out with pass and doctest examples; run python3 -m doctest lineup_more.py from inside your lineup_more folder to check them.

main is left as a comment on purpose, same as always: the command loop is the actual point of this problem, and a docstring can’t check a loop the way it can check a pure function. Yes, that means rewriting the ADD/PLAY handling you already built in Lineup; this time it also has to handle BACK.

# Student Initials:
"""
Lineup (more comfortable)

Slug: porttack/cs50/problems/py/lineup_more
Doctests: python3 -m doctest lineup_more.py
"""

from collections import deque


CAPACITY = 5


def main():
    # Loop, prompting "Command: " each time, until the input is
    # "DONE". Same ADD and PLAY behavior as Lineup, plus BACK. On a
    # successful PLAY, also call push to add that song to history.
    # See the specification below for exactly what to print for each
    # case.
    pass


def enqueue(lineup, song):
    """
    Adds song to the back of lineup if there's room (fewer than
    CAPACITY songs already waiting). Returns True if song was added,
    False if lineup was already full and song was not added.

    >>> lineup = deque()
    >>> enqueue(lineup, "Sunroof")
    True
    >>> list(lineup)
    ['Sunroof']
    """
    if len(lineup) >= CAPACITY:
        return False
    lineup.append(song)
    return True


def dequeue(lineup):
    """
    Removes and returns the song at the front of lineup. Returns
    None, and leaves lineup unchanged, if lineup is empty.

    >>> lineup = deque(["Sunroof", "Flowers"])
    >>> dequeue(lineup)
    'Sunroof'
    >>> list(lineup)
    ['Flowers']
    """
    if not lineup:
        return None
    return lineup.popleft()


def push(history, song):
    """
    Adds song to the top of history, a plain list.

    >>> history = ["Anti-Hero"]
    >>> push(history, "Flowers")
    >>> history
    ['Anti-Hero', 'Flowers']
    """
    pass


def pop(history):
    """
    Removes and returns the song on top of history (the one played
    most recently). Returns None, and leaves history unchanged, if
    history is empty.

    >>> history = ["Anti-Hero", "Flowers"]
    >>> pop(history)
    'Flowers'
    >>> history
    ['Anti-Hero']
    >>> pop([])
    """
    pass


if __name__ == "__main__":
    main()

Specification

Implement a program, lineup_more.py, that runs the song request line for the dance, same as Lineup, plus a history of what already played.

• Keep the lineup itself in a deque, starting empty. CAPACITY is already defined as 5. enqueue and dequeue are already implemented for you above.
• Keep a second collection, history, a plain list, also starting empty, for songs that have already played.
• Loop, prompting exactly "Command: " each time.
• If the input is exactly DONE, stop looping. Print nothing else.
• If the input starts with ADD followed by at least one more character, everything after that first space is the song title, spaces and all.
  • If the lineup has fewer than 5 songs waiting, call enqueue and print Added: <song>.
  • If the lineup is already full, print Lineup is full and don’t add the song.
• If the input is exactly PLAY:
  • If the lineup isn’t empty, call dequeue, print Now playing: <song>, and call push to add that same song to history.
  • If the lineup is empty, print Nothing to play.
• If the input is exactly BACK:
  • If history isn’t empty, call pop and print Last played: <song>.
  • If history is empty, print Nothing has played yet.
  • BACK only reports what already played; it never changes the lineup, and a song popped off history doesn’t go back on it.
• Anything else, a blank line, ADD with nothing after it, a misspelled command, lowercase input, prints Huh? and prompts again. Don’t crash on unexpected input.
• push and pop should never print anything or read input themselves. All the printing happens in main, based on what they return.

Usage

Your program should behave like the demo below.

$ python lineup_more.py
Command: ADD Anti-Hero
Added: Anti-Hero
Command: ADD Flowers
Added: Flowers
Command: PLAY
Now playing: Anti-Hero
Command: PLAY
Now playing: Flowers
Command: BACK
Last played: Flowers
Command: BACK
Last played: Anti-Hero
Command: BACK
Nothing has played yet
Command: PLAY
Nothing to play
Command: DONE

$ python lineup_more.py
Command: ADD A
Added: A
Command: ADD B
Added: B
Command: ADD C
Added: C
Command: ADD D
Added: D
Command: ADD E
Added: E
Command: ADD F
Lineup is full
Command: DONE

Hints

The Python docs for collections.deque are a solid reference if the note above left you curious: collections.deque. The hints below are specific to this problem.

To Get Full Credit

It’s more important that you submit a working solution than that you do everything below. Submit early, then keep improving and resubmit as many times as you like.

• Fill in push and pop with real code, and add one more >>> example of your own to each docstring covering a case not already shown. Both are pure enough to doctest cleanly, same as enqueue and dequeue above them. Don’t try to doctest main; a loop that reads input doesn’t fit the format.
• At the end of the program, add a comment describing any challenges you ran into or what you’d improve if you did this again. A sentence or two is fine.

Style and Submission

Run these one at a time, from inside your lineup_more folder.

Check your style:

style50 lineup_more.py

Check your correctness:

check50 porttack/cs50/problems/py/lineup_more

Submit your work:

submit50 porttack/cs50/problems/py/lineup_more

Glossary

• queue — A data structure where items come out in the same order they went in: first in, first out (FIFO). A line of people works the same way.
• enqueue — Adding an item to the back of a queue.
• dequeue — Removing and returning the item at the front of a queue.
• FIFO — “First in, first out.” The rule that makes a queue a queue: whatever’s been waiting longest comes out first.
• deque — Short for “double-ended queue,” and the name of the class in Python’s collections module built to add or remove items from either end quickly, no matter how long it gets.
• stack — A data structure where the most recently added item comes out first: last in, first out (LIFO). A stack of trays in a cafeteria works the same way; you take from the top, not the bottom.
• push — Adding an item to the top of a stack.
• pop — Removing and returning the item on top of a stack.
• LIFO — “Last in, first out.” The rule that makes a stack a stack, the opposite of a queue’s FIFO.

Inheritance

Background

A person’s blood type is determined by two alleles (different forms of the same gene). There are three possible alleles, A, B, and O, and everybody has two of them, possibly the same, possibly different. Each of a child’s parents randomly passes down one of their own two alleles, so a child’s blood type depends on their parents’, which depends on their parents’, and so on back through the family.

That’s a recursive relationship, and this problem asks you to implement it that way: a function that builds a family going back some number of generations, and a function that prints the whole tree out.

Before that, one thing about Python dictionaries worth knowing: a dictionary’s value doesn’t have to be a string or a number, it can be another dictionary.

>>> book = {"title": "Hidden Figures", "author": {"first": "Margot", "last": "Lee Shetterly"}}
>>> book["author"]["last"]
'Lee Shetterly'

That’s how you’ll represent a person: a dict whose "parents" value holds that person’s own two parents, each one a person dict in turn.

This is the same algorithm your program will implement, in JavaScript instead of Python. Click it a few times; the tree is different every time, since alleles are chosen at random.

Getting Started

Log into cs50.dev, click on your terminal window, and run:

cd
mkdir inheritance
cd inheritance
code inheritance.py

That creates a new folder called inheritance, moves into it, and opens a new, empty file called inheritance.py for you to edit.

Starter Code

Paste this into inheritance.py to start from. main is already written for you; it’s just two lines. random_allele, create_family, and print_family are stubbed out with pass and doctest examples; run python3 -m doctest inheritance.py from inside your inheritance folder to check them. They’ll fail until you replace pass with real code.

# Student Initials:
"""
Inheritance

Slug: porttack/cs50/problems/py/inheritance
Doctests: python3 -m doctest inheritance.py
"""

import random


ALLELES = ["A", "B", "O"]
GENERATIONS = 3


def main():
    family = create_family(GENERATIONS)
    print_family(family)


def random_allele():
    """
    Returns one randomly chosen allele from ALLELES.

    >>> import random
    >>> random.seed(0)
    >>> random_allele()
    'B'
    >>> random_allele()
    'B'
    >>> random_allele()
    'A'
    """
    pass


def create_family(generations):
    """
    Recursively builds a family going back the given number of
    generations, returning the person in the youngest generation as a
    nested dict: {"parents": [parent0, parent1], "alleles": [a, b]}.
    generations == 1 is the base case: no parents, two random alleles.

    >>> import random
    >>> random.seed(0)
    >>> create_family(1)
    {'parents': [None, None], 'alleles': ['B', 'B']}
    """
    pass


def print_family(person, generation=0):
    """
    Prints person and all their ancestors, one line per person,
    indented four spaces per generation. Doesn't return anything.

    >>> person = {
    ...     "parents": [
    ...         {"parents": [None, None], "alleles": ["A", "O"]},
    ...         {"parents": [None, None], "alleles": ["B", "O"]},
    ...     ],
    ...     "alleles": ["A", "B"],
    ... }
    >>> print_family(person)
    Child (Generation 0): blood type AB
        Parent (Generation 1): blood type AO
        Parent (Generation 1): blood type BO
    """
    pass


if __name__ == "__main__":
    main()

Specification

Implement a program, inheritance.py, that builds a random family tree and prints out everyone’s blood type.

• ALLELES and GENERATIONS are already defined for you: the three possible alleles, and how many generations back to go (3, matching the child, their two parents, and their four grandparents).
• random_allele() returns one allele chosen at random from ALLELES. random.choice() does exactly this.
• create_family(generations) builds and returns one person, going back the given number of generations:
  • Base case, generations == 1: return a person with "parents": [None, None] and two alleles from random_allele(). This is the oldest generation in the tree; they have no parents of their own to inherit from.
  • Recursive case, generations > 1: call create_family on generations - 1 twice, once for each parent. Then build this person’s "alleles" by choosing one allele at random from each parent’s own two, random.choice(parent["alleles"]). Build the parents before you build this person; you can’t choose from a parent’s alleles until that parent exists.
• print_family(person, generation=0) prints person, then recursively prints each of their parents (parent 0 before parent 1), each one generation deeper:
  • Each line reads <Label> (Generation <N>): blood type <XY>, where <XY> is person’s two alleles joined together with no space between them.
  • Each line is indented 4 spaces per generation: generation 0 isn’t indented at all, generation 1 is indented 4 spaces, generation 2 is indented 8 spaces, and so on.
  • The label is Child at generation 0, Parent at generation 1, and Grandparent at generation 2. (Generations past 2 aren’t part of the base spec, but see the Bonus below.)
  • If a person’s parent is None (the base case), don’t print anything for that parent, and don’t recurse into it.
• main (already written for you) calls create_family(GENERATIONS) and prints the result with print_family.

Usage

Since alleles are chosen at random, your output won’t match this exactly, but it will have the same shape. This is one real run:

$ python inheritance.py
Child (Generation 0): blood type BA
    Parent (Generation 1): blood type AB
        Grandparent (Generation 2): blood type AA
        Grandparent (Generation 2): blood type AB
    Parent (Generation 1): blood type BA
        Grandparent (Generation 2): blood type BO
        Grandparent (Generation 2): blood type AO

Hints

To Get Full Credit

It’s more important that you submit a working solution than that you do everything below. Submit early, then keep improving and resubmit as many times as you like.

• Fill in random_allele, create_family, and print_family with real code, and add one more >>> example of your own to each docstring covering a case not already shown. All three are pure enough to doctest cleanly.
• At the end of the program, add a comment describing any challenges you ran into or what you’d improve if you did this again. A sentence or two is fine.

Bonus

For extra credit: make the number of generations configurable instead of fixed at 3. If your program is run with a single command-line argument, an integer, use that many generations instead of GENERATIONS. This is exactly where the “Great-“ label rule from the hint above pays off: if you hardcoded "Grandparent" for generation 2, this is where it’ll show.

$ python inheritance.py 4
Child (Generation 0): blood type AA
    Parent (Generation 1): blood type BA
        Grandparent (Generation 2): blood type BO
            Great-Grandparent (Generation 3): blood type AB
            Great-Grandparent (Generation 3): blood type AO
        Grandparent (Generation 2): blood type AA
            Great-Grandparent (Generation 3): blood type AA
            Great-Grandparent (Generation 3): blood type AA
    Parent (Generation 1): blood type OA
        Grandparent (Generation 2): blood type OB
            Great-Grandparent (Generation 3): blood type OO
            Great-Grandparent (Generation 3): blood type BB
        Grandparent (Generation 2): blood type AO
            Great-Grandparent (Generation 3): blood type BA
            Great-Grandparent (Generation 3): blood type AO

Your program should still default to 3 generations when run with no arguments; check50 needs that to still pass.

Style and Submission

Run these one at a time, from inside your inheritance folder.

Check your style:

style50 inheritance.py

Check your correctness:

check50 porttack/cs50/problems/py/inheritance

Submit your work:

submit50 porttack/cs50/problems/py/inheritance

Glossary

• nested dict — A dictionary whose value for some key is itself another dictionary, rather than a string, number, or list.
• allele — One of the possible forms a gene can take. Blood type in this problem is determined by two alleles, A, B, or O, one inherited from each parent.
• base case — The condition in a recursive function that stops the recursion and returns directly, without calling itself again. Here, generations == 1.
• recursive case — The branch of a recursive function that calls itself again, on a smaller version of the problem. Here, building each parent by calling create_family on one fewer generation.