This project must be completed individually. We want to evaluate you on the basis of what you can do by consulting the resources listed below, and without help from anyone other than course staff. Seeking or giving aid on this assignment is prohibited (except for asking course staff); doing so constitutes academic misconduct which can have serious consequences. If you are unsure about whether something is allowed, ask. The course syllabus contains more information about the course and university policies regarding academic honesty.
This project involves a game played with a list of words. You will write a Python module containing functions related to analyzing the game.
Ask if you are unsure whether a resource falls under one of these categories, or if you think I missed an essential resource.
Contact the instructor or your TA by email, in office hours, or on discord.
Before we talk about the programming project, you need to learn about a puzzle game I've named "word chiseler". In this one-player game, you are given a list of words such as
SKILLED TRAINER OF FIELD MICE
Your goal is to remove words from the list, one at a time, until no words remain. At that point you win. But along the way you need to follow these rules:
To illustrate, let's try this on the example above. Starting with
SKILLED TRAINER OF FIELD MICE
we see the first and last words have letters in common (E and I), so we haven't lost yet! We have a choice of removing the first word (SKILLED) or the last word (MICE). Suppose we remove MICE. Then we are left with
SKILLED TRAINER OF FIELD
Here again, the first and last words have letters in common (E, I, and L), so we can keep going. For our next move we can remove SKILLED or FIELD. Suppose we choose FIELD. We are left with
SKILLED TRAINER OF
and at that point we've lost because SKILLED and OF do not have any letters in common.
However, if we had made different choices, we could have won! To see this, let's start over again.
SKILLED TRAINER OF FIELD MICE
Remove MICE.
SKILLED TRAINER OF FIELD
We can continue, since SKILLED and FIELD have letters E, I, and L in common. Remove SKILLED.
TRAINER OF FIELD
We can continue, since TRAINER and FIELD have letters E and I in common. Remove TRAINER.
OF FIELD
We can continue, since OF and FIELD have letter F in common. Remove OF.
FIELD
Since we're down to just one word, that word is both "the first word" and "the last word", and so of course it shares letters with itself. We are therefore allowed to remove it, and we win!
Suppose we play this game with starting list
HIRSUTE BOWL ENTHUSIAST
We can make a first move, since HIRSUTE and ENTHUSIAST share several letters. But then we end up with either
HIRSUTE BOWL
or
BOWL ENTHUSIAST
and so in either case we've lost.
If you win at word chiseler, it means you removed each word that was in the original list. The only question is the order in which they were removed. Thus you can describe a winning strategy by listing the words in the order removed. That winning strategy will contain the same words as the original list, but in a different order.
For example, the successful game
PERHAPS WE SHOULD BUY FOURTEEN RED ONIONS
PERHAPS WE SHOULD BUY FOURTEEN RED
WE SHOULD BUY FOURTEEN RED
SHOULD BUY FOURTEEN RED
SHOULD BUY FOURTEEN
SHOULD BUY
BUY
would be described by the winning strategy
ONIONS, PERHAPS, WE, RED, FOURTEEN, SHOULD, BUY
meaning ONIONS was removed in the first turn, followed by PERHAPS, then WE, then RED, then FOURTEEN, then SHOULD, and finally BUY. This strategy completely specifies the gameplay, though it isn't immediately obvious that the rules of the game have been followed. One could easily write down a list that contains all the words from the game, but in an order that breaks one of the rules.
The game is called "word chiseler" because a chisel is a tool with a sharp edge that is used for removing bits of material from the surface of an object (often, a piece of wood) to achieve a desired shape. Analogously, by removing words from the beginning or end of the word list, we're "chiseling away" at the list.
chiseler¶For this project, you'll write a module chiseler (in a file chiseler.py) that contains functions related to the game Word Chiseler. The functions to be included in that module are listed below.
share_letter(w1,w2)¶Takes two strings, w1 and w2. Returns a boolean:
True if there is a character that appears in both w1 and w2False otherwise.Must not print anything to the terminal.
winning_strategy(L)¶Has a single required argument, a list L whose elements are strings. (May have optional arguments as well, if that helps you solve the problem.)
Assuming L is the starting list of a game of word chiseler, this function should search for a winning strategy and return it as a list of words to remove (in the order they are removed). If the game has more than one winning strategy, the function should just return one of them.
If the game cannot be won, this function returns None.
Must use recursion.
Must not print anything to the terminal.
winning_strategy( [ "DAMAGED", "CAT", "FIGURINE" ] )
might return
["FIGURINE", "CAT", "DAMAGED"]
or
["FIGURINE", "DAMAGED", "CAT"]
since those are both winning strategies.
winning_strategy( [ "NO", "WAY", "TO", "SUCCEED" ] )
would return
None
since this game cannot be won.
all_winning_strategies(L)¶Has a single required argument, a list L whose elements are strings. (May have optional arguments as well, if that helps you solve the problem.)
Assuming L is the starting list of a game of word chiseler, this function should return a list of all winning strategies for that game. If the game cannot be won, the return value would be an empty list [].
In case there are multiple winning strategies, they are allowed to appear in any order. However, assuming L has no repeated words, each winning strategy is only allowed to appear in the list returned by all_winning_stragies once---duplicates of the same strategy are prohibited. (If L has repeated words, it's tricker to define what is meant by "duplicates", so we won't test it in that condition.)
Must use recursion.
Must not print anything to the terminal.
all_winning_strategies( [ "DAMAGED", "CAT", "FIGURINE" ] )
might return
[["FIGURINE", "CAT", "DAMAGED"], ["FIGURINE", "DAMAGED", "CAT"]]
since those are the two possible winning strategies for this game.
winning_strategy( [ "NO", "WAY", "TO", "SUCCEED" ] )
would return
[]
since this game has no winning strategies.
num_winning_strategies(L)¶Has a single required argument, a list L whose elements are strings. (May have optional arguments as well, if that helps you solve the problem.)
Assuming L is the starting list of a game of word chiseler, this function should return the total number of winning strategies. If the game cannot be won, the return value should be 0.
show_solved_game(sentence)¶Takes a string sentence (e.g. "I find it easier to make one string"). Converts all characters in sentence to upper case and splits at spaces to get a list of words (e.g. ["I","FIND","IT","EASIER","TO","MAKE","ONE","STRING"]) for use in a game of word chiseler.
Then, the behavior depends on whether the resulting word list gives a game of word chiseler that is possible to win:
The format for printing the game as follows:
I FIND IT EASIER TO MAKE ONE STRING
Remove: I
FIND IT EASIER TO MAKE ONE STRING
Remove: FIND
IT EASIER TO MAKE ONE STRING
Remove: IT
EASIER TO MAKE ONE STRING
Remove: EASIER
TO MAKE ONE STRING
Remove: STRING
TO MAKE ONE
Remove: TO
MAKE ONE
Remove: MAKE
ONE
Remove: ONEThat is, the full word list is printed (separated by spaces, no brackets or commas) on one line, followed by a description of the next move (as Remove: followed by the word to be removed) on another line, and this repeats until the game has been won.
This function does not return any value; it only displays output on the terminal.
Your project must follow the rules in the MCS 275 coding standards document. In addition:
chiseler.py.chiseler.py call one another if/when it is appropriate, rather than needlessly duplicating code.The autograder tests your program and grades it based on its behavior.
I will review your code and look for adherence to the coding standards and other rules given above, and check for proper use of recursion when requested.
I suggest you write a script that imports chiseler and tests the functions in it. If you do not test your functions locally, and instead rely on the autograder as the sole means of testing your project, debugging will be much slower and more difficult.