CS50 2023 - Week6 Python

概要

Week6では、Pythonについて学びます。
講義の主な内容は、関数、引数、戻り値、変数、ブール式、条件分岐、ループ、モジュール、そしてパッケージです。

5週にわたり学び続けたC言語を離れ、Pythonの学習が始まります。
しかし、それに伴いWeek6はProblem Setの数が増えているため、本ページではこれまで以上にコード例に焦点を絞って記していきます。

---

Lab 6

World Cup

ワールドカップでどの国が勝利するかを予測するシミュレーションプログラムを作成します。

以下は実際に渡しが提出したコードです。

tournament.py

# Simulate a sports tournament

import csv
import sys
import random

# Number of simluations to run
N = 1000


def main():
    # Ensure correct usage
    if len(sys.argv) != 2:
        sys.exit("Usage: python tournament.py FILENAME")

    teams = []
    # TODO: Read teams into memory from file
    with open(sys.argv[1], "r") as file:
        reader = csv.DictReader(file)
        for row in reader:
            teams.append({"team": row["team"], "rating": int(row["rating"])})

    counts = {}
    # TODO: Simulate N tournaments and keep track of win counts
    for i in range(N):
        winner = simulate_tournament(teams)
        if winner in counts:
            counts[winner] += 1
        else:
            counts[winner] = 1

    # Print each team's chances of winning, according to simulation
    for team in sorted(counts, key=lambda team: counts[team], reverse=True):
        print(f"{team}: {counts[team] * 100 / N:.1f}% chance of winning")


def simulate_game(team1, team2):
    """Simulate a game. Return True if team1 wins, False otherwise."""
    rating1 = team1["rating"]
    rating2 = team2["rating"]
    probability = 1 / (1 + 10 ** ((rating2 - rating1) / 600))
    return random.random() < probability


def simulate_round(teams):
    """Simulate a round. Return a list of winning teams."""
    winners = []

    # Simulate games for all pairs of teams
    for i in range(0, len(teams), 2):
        if simulate_game(teams[i], teams[i + 1]):
            winners.append(teams[i])
        else:
            winners.append(teams[i + 1])

    return winners


def simulate_tournament(teams):
    """Simulate a tournament. Return name of winning team."""
    # TODO
    while len(teams) > 1:
        teams = simulate_round(teams)
    return teams[0]["team"]


if __name__ == "__main__":
    main()

answers.txt

Times:

10 simulations: 0m0.028s
100 simulations: 0m0.030s
1000 simulations: 0m0.050s
10000 simulations: 0m0.104s
100000 simulations: 0m0.731s
1000000 simulations: 0m7.958s

Questions:

Which predictions, if any, proved incorrect as you increased the number of simulations?: TODO

With a small number of simulations, randomness cannot be eliminated,
and three teams are selected at random from the highly rated teams.

Suppose you're charged a fee for each second of compute time your program uses.
After how many simulations would you call the predictions "good enough"?: TODO

It seems like the predictions stabilized after about 1000 simulations

---

Problem Set 6

これまでC言語で提出してきた課題のいくつかをPythonで再び作成します。これらの課題名には、Sentimentalという接頭語が付きます。

Week1のHello、Mario、CashまたはCreditが選出されています。そして、Week2からはReadabilityが加わります。

Week1の時と同じく、Marioはless comfortableとmore comfortableから選べます。CashとCreditはどちらか一方だけの提出となります。

ここでは、Mario (less comfortable)とCashのコード例を示します。

Sentimental / Hello

# TODO
answer = input("What's your name? ")
print(f"hello, {answer}")

Sentimental / Mario (Less)

# TODO
from cs50 import get_int

# Prompt the user for the height until a valid input is entered
while True:
    h = get_int("Height: ")
    if h >= 1 and h <= 8:
        break

# For each row in the height of the pyramid
for i in range(h):
    print(" " * (h - 1 - i), end="")
    print("#" * (i + 1))

Sentimental / Cash

# TODO
from cs50 import get_float


def get_change():
    while True:
        x = get_float("Change owed: ")
        if x >= 0:
            return int(x * 100)


def calculate_coins(cents):
    coins = 0

    # Calculate the number of quarters to give the customer
    coins += cents // 25
    cents %= 25

    # Calculate the number of dimes to give the customer
    coins += cents // 10
    cents %= 10

    # Calculate the number of nickels to give the customer
    coins += cents // 5
    cents %= 5

    # Calculate the number of pennies to give the customer
    coins += cents

    return coins


def main():
    # Ask how much change the customer is wed
    cents = get_change()
    coins = calculate_coins(cents)
    print(coins)


main()

Sentimental / Readability

# TODO
from cs50 import get_string
import re
import math

# Prompt for user input
text = get_string("Text: ")

# String length
i = len(text)
letters = 0
# Initialize words to 1
words = 1
sentences = 0

# Loop for counting
for x in range(i):
    # Letter counting
    c = text[x]
    if c.isalpha():
        letters += 1

    # Word counting
    if c == " ":
        words += 1

    # Sentence counting
    if c in [".", "!", "?"]:
        sentences += 1

# Calculation
L = (letters / words) * 100
s = (sentences / words) * 100
subindex = 0.0588 * L - 0.296 * s - 15.8
index = round(subindex)
if index > 16:
    print("Grade 16+")
elif index < 1:
    print("Before Grade 1")
else:
    print(f"Grade {index}")

---

DNA

これはWeek6で唯一Sentimentalではない課題となります。
サンプルデータとデータベースを用いて、DNAの持ち主を特定するプログラムを作成します。Lab 5のInheritanceと少し似ていますね。

以下は実際に私が提出したコードです。

import csv
import sys


def main():
    # TODO: Check for command-line usage
    if len(sys.argv) != 3:
        print("Usage: python dna.py data.csv sequence.txt")
        sys.exit(1)

    # TODO: Read database file into a variable
    with open(sys.argv[1], "r") as csvfile:
        reader = csv.DictReader(csvfile)
        dna_data = list(reader)
        str_keys = reader.fieldnames[1:]

    # TODO: Read DNA sequence file into a variable
    with open(sys.argv[2], "r") as seqfile:
        sequence = seqfile.read()

    # TODO: Find longest match of each STR in DNA sequence
    str_counts = {key: longest_match(sequence, key) for key in str_keys}

    # TODO: Check database for matching profiles
    for dna in dna_data:
        if all(int(dna[key]) == str_counts[key] for key in str_keys):
            print(dna["name"])
            break

    else:
        print("No match")

    return


def longest_match(sequence, subsequence):
    """Returns length of longest run of subsequence in sequence."""

    # Initialize variables
    longest_run = 0
    subsequence_length = len(subsequence)
    sequence_length = len(sequence)

    # Check each character in sequence for most consecutive runs of subsequence
    for i in range(sequence_length):
        # Initialize count of consecutive runs
        count = 0

        # Check for a subsequence match in a "substring" (a subset of characters) within sequence
        # If a match, move substring to next potential match in sequence
        # Continue moving substring and checking for matches until out of consecutive matches
        while True:
            # Adjust substring start and end
            start = i + count * subsequence_length
            end = start + subsequence_length

            # If there is a match in the substring
            if sequence[start:end] == subsequence:
                count += 1

            # If there is no match in the substring
            else:
                break

        # Update most consecutive matches found
        longest_run = max(longest_run, count)

    # After checking for runs at each character in seqeuence, return longest run found
    return longest_run


main()

---

さいごに

C言語からPythonへの移行を経て、コードの構造は大幅にシンプルになったように感じます。特にSentimentalのProblem Setを通じて、その変化を実感することができました。非常に良く練られたコース構成です。
余談にはなりますが、Sentimentalという単語の選択もおしゃれで、個人的にはとても好きです。