A document from MCS 275 Spring 2023, instructor David Dumas. You can also get the notebook file.

MCS 275 Spring 2023 Project 2 - Word Chiseler

  • Course instructor: David Dumas

Instructions

Deadline is 6pm central on Friday 24 February 2023.

Collaboration policy and academic honesty

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.

Topic

This project involves a game played with a list of words. You will write a Python module containing functions related to analyzing the game.

Resources you are allowed to consult

  • Documents and videos posted to the course web page
  • Any of the optional textbooks listed on the course web page

Ask if you are unsure whether a resource falls under one of these categories, or if you think I missed an essential resource.

What to do if you are stuck

Contact the instructor or your TA by email, in office hours, or on discord.

Playing word chiseler

The rules

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:

  1. You can only ever remove the first word or last word from the list, and
  2. If at any point the first and last words on the list don't share any letters, then the game ends and you lose.

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!

Sometimes you just can't 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.

Describing a winning strategy

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 name

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.

The module 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.

Function 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 w2
  • False otherwise.

Must not print anything to the terminal.

Function 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.

Example:

winning_strategy( [ "DAMAGED", "CAT", "FIGURINE" ] )

might return

["FIGURINE", "CAT", "DAMAGED"]

or

["FIGURINE", "DAMAGED", "CAT"]

since those are both winning strategies.

Example:

winning_strategy( [ "NO", "WAY", "TO", "SUCCEED" ] )

would return

None

since this game cannot be won.

Function 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.

Example:

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.

Example:

winning_strategy( [ "NO", "WAY", "TO", "SUCCEED" ] )

would return

[]

since this game has no winning strategies.

Function 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.

Function 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:

  • If the game cannot be won, an exception is raised.
  • If the game can be won, a sample play session that results in a win is printed to the terminal.

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: ONE

That 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.

IMPORTANT RULES YOUR CODE MUST FOLLOW

Your project must follow the rules in the MCS 275 coding standards document. In addition:

  • The only file you submit should be chiseler.py.
  • That file should be a module that doesn't do anything when imported other than defining functions. (For example, it shouldn't run tests or print anything when it is imported.)
  • Have functions in chiseler.py call one another if/when it is appropriate, rather than needlessly duplicating code.

How your project will be graded

Autograder: 35 points

The autograder tests your program and grades it based on its behavior.

Manual review: 15 points

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.

Final word: Write a test program!

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.

Revision history

  • 2023-02-12 Initial publication