.py files containing your code.This homework assignment must be submitted in Gradescope by Noon central time on Tuesday January 23, 2024.
Collaboration is prohibited, and you may only access resources (books, online, etc.) listed below.
This assignment corresponds to Worksheet 2, which involves some Python review and object-oriented programming.
The materials you may refer to for this homework are:
This homework assignment has 3 problems, numbered 2 and 3. The grading breakdown is:
| Points | Item |
|---|---|
| 4 | Autograder |
| 5 | Problem 2 |
| 5 | Problem 3 |
| 14 | Total |
The part marked "autograder" reflects points assigned to your submission based on some simple automated checks for Python syntax, etc. The result of these checks is shown immediately after you submit.
Ask your instructor or TA a question by email, in office hours, or on discord.
Homework problem numbers will always start at 2, because Gradescope uses "Problem 1" to report the Autograder results---i.e., a few automated checks of whatever you submit for the other problems.
This will happen on every assignment this semester.
Put the code you write for this problem in hwk2prob2.py.
A word chain is a list of words (which we'll represent as a list of Python strings) where the last letter of each word is the same as the first letter of the next word. For example, this is a word chain:
["optimistic", "crustaceans", "suspend", "disbelief", "furtively"]Of course any list with zero or one words would be considered a word chain, because there's nothing to check.
However, the following is not a word chain
["intense", "evaluation", "never", "reveals", "anything", "great"]because the last letter of reveals differs from the first letter of the next word, anything.
The second list shown above does have some slices that are word chains, though. For example, if the list ["intense", ... , "great"] shown above is called L, then the following are a few examples of slices of it that are word chains:
L[1:3] = ["evaluation", "never"]
L[0:4] = ["intense", "evaluation", "never", "reveals"]
L[4:5] = ["anything"]
L[4:6] = ["anything", "great"](This list is not exhaustive. There are other slices of L that form word chains.)
Consider the following question: Given a list of words, what is the longest word chain that it contains as a slice?
Write a function longest_word_chain(L) that takes a list L of words (strings) and returns a list of strings that is a slice of L, is a word chain, and which has the longest length among slices of L that are word chains.
It's possible that there could be a "tie" for longest word chain in L. In that case, the function can return any slice that's a word chain of maximal length.
Here are some examples of what a working answer might return. Each example notes whether there are other possible correct return values.
longest_word_chain(["greet","our","regal","lycanthropy","enthusiast"])
Unique correct answer: This is the only valid return value for example 1.
longest_word_chain(["ungrateful","elephants","talk","about","university","tuition"])
Multiple correct answers: Any slice of length one would be correct for example 2, so the other correct return values would be:
['elephants']or
['talk']or
['about']or
['university']or
['tuition']longest_word_chain(["incomprehensibilities"])
Unique correct answer: This is the only valid return value for example 3
longest_word_chain([])
Unique correct answer: This is the only valid return value for example 4
longest_word_chain(["accidental","inventions","sometimes","make","excellent","coffee"])
Multiple correct answers: There are two slices of length 2 that form word chains, so there is one other return value that would also be correct for example 5:
['make', 'excellent']Note: This function has slightly more verbose comments than we'd expect from a homework submission. That was done because the solutions are meant to serve as learning material, and are often consulted when some aspect of the problem has been challenging or confusing.
def longest_word_chain(L):
"""
Takes a list of strings and returns (one of) the longest slices of that
list that forms a word chain, i.e. has the property that each word ends
with the same character that the next word begins with.
"""
if len(L) == 0:
return []
# We'll scan the list in order, keeping track of whether we're in
# a chain at each moment. When a chain ends, we check if it set
# a new record for longest.
# Data tracked during scan
longest_chain_seen = []
current_chain = []
# Scan loop
for word in L:
# Does this word continue the current chain?
if len(current_chain)==0 or word[0]==current_chain[-1][-1]:
# yes, so we add it
current_chain.append(word)
else:
# We can't add `word` to current_chain, so
# we'll start a new chain. But first we
# check to see if `current_chain` is the
# longest seen so far.
if len(current_chain) > len(longest_chain_seen):
longest_chain_seen = current_chain
# This word begins a new chain
current_chain = [ word ]
# Note longest_chain_seen only gets updated in the loop when a
# non-chain word is found. That means we'll miss a chain that goes
# all the way to the end of the list if we don't update once more.
if len(current_chain) > len(longest_chain_seen):
longest_chain_seen = current_chain
return longest_chain_seen
Put the code you write for this problem in hwk2prob3.py.
Imagine an organization that maintains a fleet of blimps, and which must hire and maintain personnel records for the people who operate those blimps.
In this imaginary organization, there is a strict promotion ladder for blimp operators, with the following titles listed from most junior to most senior:
That means a person hired as a Trainee can only be promoted to Junior pilot, a Junior pilot can only be promoted to Pilot, etc. Also, a person who holds the title of Chief blimpologist cannot get any further promotion.
There are also two titles used for people who are not current employees of the organization:
Create a class BlimpOperator to represent a blimp operator in the personnel system of this organization. The constructor should have one required argument, name, which is the full name of the person. The constructor should allow a second argument, title, that gives the person's title. If title is not given, the default value "Trainee" should be used. Both name and title should be stored as attributes of the object (with those names).
For example, the class might be instantiated as
X = BlimpOperator("Lilianna Rogers","Senior pilot")
or
Y = BlimpOperator("Memphis Cardenas") # will be a trainee
In addition to the constructor, the class should have the following methods, none of which expect any arguments (other than self):
promote - Changes title to the next higher rank in the promotion ladder, if the person is a current blimp operator who can be promoted. If they are a Blimp operator emeritus or a Former employee, does nothing.demote - Changes title to the next lower rank in the promotion ladder, if the person is a current blimp opeartor who is not a Trainee. If they are a Trainee, Blimp operator emeritus, or a Former employee, does nothing.terminate - If the person is a current employee, change the title to Former employee, otherwise do nothing.retire - If the person is a current employee, change the title to Blimp operator emeritus, otherwise do nothing.Here are some examples of the expected behavior of the class.
D = BlimpOperator("David Dupage",title="Senior pilot")
D.name
D.title
D.promote()
D.title # after promotion
D.promote()
D.title # can't promote any further, so it didn't change
D.retire()
D.title
D.terminate()
D.title # termination didn't do anything, because we called it when not employed
E = BlimpOperator("Eithan Ortega")
E.name
E.title # was automatically set to Trainee
Our solution uses a class attribute to store the list of titles, but it would be fine to use an instance attribure or global variable for the same purpose.
class BlimpOperator:
"Personnel record of a person currently or previously employed to operate blimps"
# Possible titles of current employees in order of seniority
ladder = ["Trainee", "Junior pilot", "Pilot", "Senior pilot", "Chief blimpologist"]
def __init__(self, name, title="Trainee"):
"Initialize a new record by name and title"
self.name = name
self.title = title
def promote(self):
"Promote this person to the next rank, if possible"
# only need to act if they are in the promotion ladder
if self.title in self.ladder:
# They're in the promotion ladder
# Compute position of title above current
i = self.ladder.index(self.title) + 1
if i < len(self.ladder):
# current title is not the highest, so promote
self.title = self.ladder[i]
def demote(self):
"Demote this person by one rank, if possible"
if self.title in self.ladder:
# They're in the promotion ladder
# Compute position of title below current
i = self.ladder.index(self.title) - 1
if i >= 0:
# current title is not the lowest, so demote
self.title = self.ladder[i]
def terminate(self):
"If a current employee, set title to 'Former employee'"
if self.title in self.ladder:
self.title = "Former employee"
def retire(self):
"If a current employee, set title to 'Blimp operator emeritus'"
if self.title in self.ladder:
self.title = "Blimp operator emeritus"