CMU 15-110 Fall 2018: Principles of Computing
Homework 6 (Due Tuesday 16-Oct at 8pm)
- Team vs Solo:
As usual, this hw has a collaborate team portion, and a solo portion. Please see the syllabus for details. - Starter code:
To start the solo hw, download this file: hw6.py Then, edit that file you downloaded!
Team Hw6
- This part of the hw is team-based and collaborative.
- Here are the topics and activities we covered:
- Collaborative Code Tracing
- Collaborative Coding: Data Analysis + CSV Files
- Collaborative Discussion: Spectacular Software Failures (Big Bugs)
Solo Hw6
- This part of the hw is solo and not collaborative. See the syllabus for details.
- Note: unless otherwise stated, functions must be non-destructive. This is true on this hw and in fact in general (all future hw's, quizzes, and exams).
- colCount(L, col, value) [10 pts]
Note: this function will be helpful when solving the next exercise!
Write the function colCount(L, col, value) that takes a non-empty 2d list L, a column index, and a value, and returns a count of the number of times that value occurs in that column of L. For example:
That is true because the value 5 occurs 2 times in column 1 of the given 2d list. Also, if the column index does not exist, return 0 (do not crash). And you may assume L has at least one row and at least one column. See the test cases in the starter code for some examples.assert(colCount([ [1, 2, 3], [4, 5, 6], [5, 5, 5] ], 1, 5) == 2) - getScattergoriesScores(L) [20 pts]
Hint: Be sure to use the previous function when solving this exercise!
Background: In a round of Scattergories, players are given a list of categories, and a starting letter, and they make a list of words, one for each category, each starting with the given starting letter.
For example, this 2d list may represent the result of a round of Scattergories with a start-letter of 'b':
A player scores +1 for each word of theirs that is unique for that category -- so each word where no other player had that same word in that same category. There are a few more rules than this one, but here we'll just stick with the one rule.[ [ 'Player', 'Dog breed', 'City', 'Color', ], [ 'John', 'bulldog', 'boston', 'beige' ], [ 'Joan', 'basset', 'berlin', 'brown' ], [ 'Jane', 'basset', 'boston', 'brown' ], [ 'Jan', 'beagle', 'bruges', 'blue' ] ]
For example, in the round above, John scores points for bulldog and beige, but not for boston, since Jane also had boston. So John scored 2 points. Here are all the outcomes:
We can represent this result in a 2d list, like so:John scored 2 points (boston was a duplicate) Joan scored 1 point (basset and brown were duplicates) Jane scored 0 points (all Jane's answers were duplicates) Jan scored 3 points (none of Jan's answers were duplicates)
With this in mind, write the function getScattergoriesScores(L) that takes a 2d list of a Scattergories round, as described above, and returns a 2d list of the scores for that round, as also described above. For example:[ [ 'John', 2 ], [ 'Joan', 1 ], [ 'Jane', 0 ], [ 'Jan', 3 ] ]
You may assume that there is at least one player and at least one category, and that all the categories and players names start with an uppercase letter, and that all the players' words are in lowercase.assert(getScattergoriesScores([ [ 'Player', 'Dog breed', 'City', 'Color', ], [ 'John', 'bulldog', 'boston', 'beige' ], [ 'Joan', 'basset', 'berlin', 'brown' ], [ 'Jane', 'basset', 'boston', 'brown' ], [ 'Jan', 'beagle', 'bruges', 'blue' ] ]) == [ [ 'John', 2 ], [ 'Joan', 1 ], [ 'Jane', 0 ], [ 'Jan', 3 ] ]) - getScattergoriesWinners(L) [20 pts]
Hint: Be sure to use the previous function when solving this exercise!
Write the function getScattergoriesWinners(L) that takes the same 2d list as getScattergoriesScores(L), but this function returns a sorted list of the winner or winners of the round. For example, we saw above that Jan got 3 points, and everyone else got fewer, so:
Now, if Jan had said 'berlin' instead of 'bruges', then she and John would have both scored 2 and tied, so:assert(getScattergoriesWinners([ [ 'Player', 'Dog breed', 'City', 'Color', ], [ 'John', 'bulldog', 'boston', 'beige' ], [ 'Joan', 'basset', 'berlin', 'brown' ], [ 'Jane', 'basset', 'boston', 'brown' ], [ 'Jan', 'beagle', 'bruges', 'blue' ] ]) == [ 'Jan' ])assert(getScattergoriesWinners([ [ 'Player', 'Dog breed', 'City', 'Color', ], [ 'John', 'bulldog', 'boston', 'beige' ], [ 'Joan', 'basset', 'berlin', 'brown' ], [ 'Jane', 'basset', 'boston', 'brown' ], [ 'Jan', 'beagle', 'berlin', 'blue' ] ]) == [ 'Jan', 'John' ]) - bonus/optional: isLatinSquare(L) [2.5 pts]
Bonus/Optional: Write the function isLatinSquare(L) that takes a 2d list and returns True if it is a Latin square (see here) and False otherwise. - bonus/optional: isKnightsTour(L) [2.5 pts]
Background: A "knight's tour" (see here) in chess is a sequence of legal knight moves such that the knight visits every square exactly once. We can represent a (supposed) knight's tour as an NxN list of the integers from 1 to N**2 listing the positions in order that the knight occupied on the tour. If it is a legal knight's tour, then all the numbers from 1 to N**2 will be included and each move from k to (k+1) will be a legal knight's move. With this in mind, write the function isKnightsTour(board) that takes such a 2d list of integers and returns True if it represents a legal knight's tour and False otherwise.
For example, here is a legal 8x8 knight's tour:
And here is a legal 3x4 knight's tour:L = [ [ 38, 41, 18, 3, 22, 27, 16, 1], [ 19, 4, 39, 42, 17, 2, 23, 26], [ 40, 37, 54, 21, 52, 25, 28, 15], [ 5, 20, 43, 56, 59, 30, 51, 24], [ 36, 55, 58, 53, 44, 63, 14, 29], [ 9, 6, 45, 62, 57, 60, 31, 50], [ 46, 35, 8, 11, 48, 33, 64, 13], [ 7, 10, 47, 34, 61, 12, 49, 32] ]L = [ [ 8, 11, 6, 3], [ 1, 4, 9, 12], [ 10, 7, 2, 5] ]