Python Lab 7: Feudalism
Due Wednesday, October 20th by 11:45pm
Introduction
To get started, open IDLE and then create a New File via the File menu.
We suggest you immediately save this file in the directory you created to manage all your
Python Labs this semester (e.g., CSCI101/PythonLabs). Save this file as
Lab7-feudalism.py.
This is a challenging assignment—please read this ENTIRE document before starting the lab.
Assignment
In the ~1000 years of the middle ages, because there was no centralized government after the fall of the
Western Roman Empire, most of Western Europe (as we know it today) operated on a political system called Feudalism.
The feudal system consisted of 3 main classes: upper, middle, and lower, with upper being the highest class and
lower being the lowest class. Within each class, there were further distinctions between levels. For example, a
Baron ruling over a Fief might be considered a member of the middle-upper class while the local Lord and Lady
would be considered lower-upper. The Queen and King ruling the entire Fiefdom would be considered upper-upper
class. It follows that upper-upper is higher than middle-upper which is higher than lower-upper; however, all of the upper
classes are higher than all of the middle classes (e.g. all members of the lower-lower-upper class are above all members of
the upper-upper-upper-middle class).
Within a class such as middle-lower, there can be further distinctions as well, leading to classes such as upper-middle-lower-middle-lower.
When comparing classes, once you have reached the lowest level of detail, you should assume that all further classes
are the same as the middle level of the previous level of detail. For example, upper is equivalent to middle-middle-middle-upper
and lower-middle is equivalent to middle-middle-middle-lower-middle.
Input
Input begins with a positive integer p ≤ 100 indicating the number of people to consider. Each of the next p lines
consists of the name of the person followed by a colon and a space, followed by the class of the person. The class
is a nonempty sequence of at most 5 of the words “upper”, “middle”, and “lower” separated by dashes (“-”),
followed by a space, followed by the word “class”.
Output
Output the list of names from the highest class to the lowest class. If two (or more) people have the same or equivalent
classes, they should be listed alphabetically by name (i.e., use the names to break ties. It is guaranteed that no
two people will have the same name).
Hints
- This is a challenging lab conceptually, but does not require as much code as some previous labs you have
worked on (e.g., binary-hex-decimal). This means that 1 hour of planning can save you 30 hours of programming,
so please (for your own sake) spend 1 hour planning/pseudocoding how you will solve this problem before writing any code.
- You will need to store each person’s name and class within a single data structure—consider using a tuple or a list.
You will then create a 2D data structure (a list of people) that you can sort using Python’s built in sort functions (sort() or sorted()).
- Since this is a 2D data structure, you will need to tell the sort function how to sort the list of people
(by name, class, or both). This can be easily solved using a lambda function (i.e., a key). If I was storing each
person as a list of [name, class], and I wanted to sort my list of people by class, name, or both, then I would use the following
lines of code, respectively:
- sorted_by_class = sorted(my_list, key=lambda person: person[1])
- sorted_by_name = sorted(my_list, key=lambda person: person[0])
- sorted_by_class_then_name = sorted(my_list, key=lambda person: (person[1], person[0]))
In the first case, I am telling the sort function to sort by the second element in each “person list”, i.e., the class.
In the second case, I am telling the sort function to sort by the first element, i.e., the name.
In the last case, I am telling the sort function to sort by the second element, and if there's two with the same second element, use the first element to break the tie.
- You cannot simply sort by the names of the classes—this will NOT work. Instead spend some time writing
examples and sorting them to determine a way to model the classes as something you can sort (think math!).
- Please start this lab early and make liberal use of office hours to help you solve this problem. The U-CLIMB mentors will also
be hosting an ALS the week before fall break on pseudocode development. They will help you create pseudocode for this lab
(and you get 4 points of extra credit for attending, which is effectively 50% extra credit on this lab)! Check piazza for rooms and times.
Lab I/O Format
Throughout this semester we use a specific Lab Input/Output Format. This format is described below:
- When prompting for input, use the prompt string
WORD>, where WORD
is a single, uppercase word which describes the input. For example, this
lab might choose: NUM_PEOPLE> and PERSON>
(for each person).
- When providing output that will be graded, start the line with
OUTPUT. Think of this as "boxing your answer"
on a math worksheet; it lets us quickly find your answer. Our grading
script will skip any output lines that do not start with
OUTPUT.
- You are welcome (and should!) have other output lines that do not begin
with OUTPUT; while our grading script will ignore
these, good programmers include print statements that are informational
to the user of the program.
- A submission without exactly correct output formatting will receive an
AUTOMATIC ZERO. This is because Gradescope is automated—it does not
look at your code, only the results, and thus the format of the results must
be consistent for all students.
Example Execution #1
Input the number of people to sort:
NUM_PEOPLE> 5
PERSON0> nemo: middle-middle-lower-middle class
PERSON1> queenofhearts: upper-upper-upper class
PERSON2> minesmarket: lower-lower class
PERSON3> unclemike: upper-upper-lower-middle class
PERSON4> marlin: middle-middle-lower-middle class
After sorting, the list from highest to lowest is as follows:
OUTPUT queenofhearts
OUTPUT unclemike
OUTPUT marlin
OUTPUT nemo
OUTPUT minesmarket
Example Execution #2
Input the number of people to sort:
NUM_PEOPLE> 6
PERSON0> charlie: middle-lower class
PERSON1> arthur: middle class
PERSON2> devon: upper-middle class
PERSON3> fred: upper-lower class
PERSON4> eleanor: middle-lower class
PERSON5> beatrice: upper-upper class
After sorting, the list from highest to lowest is as follows:
OUTPUT beatrice
OUTPUT devon
OUTPUT arthur
OUTPUT fred
OUTPUT charlie
OUTPUT eleanor
Example Execution #3
Input the number of people to sort:
NUM_PEOPLE> 6
PERSON0> lisa: upper-lower-middle-lower-lower class
PERSON1> matthew: middle-upper-lower-middle-upper class
PERSON2> jennifer: upper-upper-middle-upper class
PERSON3> joseph: lower-middle-lower class
PERSON4> courtney: middle-upper-lower-middle-upper class
PERSON5> david: lower-lower-middle-upper-lower class
After sorting, the list from highest to lowest is as follows:
OUTPUT jennifer
OUTPUT courtney
OUTPUT matthew
OUTPUT david
OUTPUT joseph
OUTPUT lisa
Gradescope Submission Nuances
When you submit your Python file to Gradescope, multiple different test cases
are run on your code. Passing all of the tests results in a 100% on the autograded
portion of the lab.
You are allowed to submit to Gradescope four times (or less) for this lab. Please ignore the automated email from Gradescope, that information is incorrect.
The maximum grade of your submissions will be your grade for the lab. Note: If
your code doesn’t work (e.g., a syntax error exists, or an error is thrown in
execution), then you will receive an AUTOMATIC ZERO. You should test your
code before submitting to ensure it executes correctly.
NOTE: This lab is 75% autograded (6 points) and 25% manually graded (2 points). The manually graded portion will be
based on the following:
- 0.25 points - Good commenting practices - do you explain your thought process and comment general sections.
- 0.25 points - Suitable/appropriate variable names - not 1 letter, does it properly describe what it contains.
- 1.50 points - Efficiency - Your algorithm should have a maximum worst case complexity of O(n2).
Comments
All Python files should include a header with your name,
section, assignment info, references (i.e., who did you collaborate
with on this assignment?; what resource did you use?), and approximate
time taken to do the assignment. Be sure to cite any
allowed external references used to complete the assignment.
Any code without this header will lose 1 point. Here's an
example:
# John Henke
# CSCI 101 – Section D
# Python Lab 7
# References: Megan (instructor) helped me debug
# Time: 75 minutes
Submission
Once you are satisfied with your solution to this lab, you need to submit the
file to Gradescope. In Gradescope, go to CSCI 101 > Lab7 and upload
Lab7-feudalism.py.
Note: this lab is worth 8 points. To receive full credit, your code must
execute in Python 3, and you must submit a single file (your Python code file).
Whenever you submit something to Gradescope, we strongly recommend you
always double check what you submitted actually got submitted
correctly (e.g., did the file upload correctly? did you submit the correct
file? etc.) If your submission is incorrect, it's on you.
|
