Project 2¶

MCS 275 Spring 2021 - Emily Dumas¶

Instructions:¶

Deadline¶

This project must be submitted to Gradescope by 6:00pm CST on Friday, February 26, 2021.

Collaboration policy & academic honesty¶

This project must be completed individually. Seeking or giving aid on this assignment is prohibited; doing so constitutes academic misconduct which can have serious consequences. The only resources you are allowed to consult are the ones listed below. It is very important to follow these rules. 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.

Resources you are allowed to consult¶

• All documents and videos posted to the course web page (including lecture slides, lecture videos, the Python tour)
• Course textbooks

What to do if these instructions are unclear¶

Contact the instructor or TA by email, or visit office hours.

What to do if you're stuck¶

Contact the instructor or TA by email, or visit office hours.

Grading breakdown¶

This is a summary of how the 25 points on the project will be divided.

Conceptual overview¶

This project focuses on recursion, both as a programming tool and as a concept that is used in mathematical definitions. This project is also more theoretical than Project 1. Instead of providing long and highly detailed instructions for many classes and methods, this project asks you to write just a few functions that do more complicated things.

The project is based on some definitions of types of strings, which were made up for this project. You'll need to review the definitions below carefully to complete the project.

Eggs¶

For the purposes of this assignment, we'll say that a string is an egg if its length is 3, and if the last two characters are equal. Thus:

• "egg" is an egg
• "fee" is an egg
• "755" is an egg
• "888" is an egg (no requirement that the first character is different!)
• "wit" is not an egg (last two characters not equal)
• "stratospheric" is not an egg (length not equal to 3)
• "id" is not an egg (length not equal to 3)
• "x" is not an egg (length not equal to 3)
• The empty string is not an egg (length not equal to 3)

Note that another way to describe an egg is to say that it can be written as A+B+B where A and B are one-character strings.

(The reason for the name is that "egg" is a common noun in English that is an example of this class of strings.)

Supereggs¶

We say that a string is a superegg if it is possible to write the string as a concatenation A + B + B where A and B are nonempty strings satisfying:

1. A is either a single character or is itself a superegg, and
2. B is a single character

Notice that this definition is recursive (supereggs are defined in terms of other supereggs). Here are some examples.

• Any egg is a superegg, because you can take A and B to be single characters
• "abbcc" is a superegg, because you can write it as A+B+B with A="abb" (which is an egg, and hence a superegg) and `B="C"
• "noooooo" is a superegg; it splits as A+B+B with A="noooo" and B="o", so we just need to show that "noooo" is a superegg:
  • "noooo" is a superegg because it splits as A+B+B with A="noo" and B="o", and this A is an egg, hence a superegg.
• "7225533" is a superegg (as you can check)
• "waaa" is not a superegg. If it was, then it would need to split as A+B+B with A="wa", but that is neither a superegg nor a single character.
• "reconsidering" is not a superegg, because it doesn't end with two copies of the same character (whereas any superegg must, as B is a single character)
• "foofee" is not a superegg, because it would need to split as A+B+B with A="foof", and "foof" is neither a single character nor a superegg (because it doesn't end with two copies of the same character).

Hypereggs¶

We say that a string is a hyperegg if it is possible to write the string as a concatenation A + B + B where A and B are nonempty strings satisfying:

1. A is either a single character or is itself a hyperegg, and
2. B is either a single character or is itself a hyperegg

Examples:

• Any superegg is also a hyperegg, because you can take B to be a single character
• As a special case of the example above, any egg is also a hyperegg
• "fooss" is a hyperegg, taking A="foo" (which is a hyperegg) and B="s"
• "alooloo" is a hyperegg, taking A="a" and B="loo" (which is a hyperegg)
• "feefoofoo" is a hyperegg, taking A="fee" (which is a hyperegg) and B="foo" (which is a hyperegg)
• "aseeseetoomiimiitoomiimii" is a hyperegg (you should check this!)
• "gullability" is not a hyperegg, because there is no way to express it as A+B+B with B a nonempty string
• "deedotdot" is not a hyperegg, because the only way to express it as A+B+B with B a nonempty string is to take B="dot", and "dot" is not a hyperegg; here's why:
  • If "dot" were a hyperegg, then it would need to be expressed as A+B+B with A and B each being a single character, for otherwise the concatenation would have more than 3 characters. But then it would follow that the last two characters are equal, which is not the case for "dot".

What you need to do¶

Create a module eggs (in a file eggs.py) that contains the four functions documented below. Submit eggs.py to gradescope.

• is_egg(s)
  • Returns True if s is an egg, otherwise returns False.
  • Implemented using any method you like.
• is_superegg_iterative(s)
  • Returns True if s is a superegg, otherwise returns False.
  • Must be purely iterative (i.e. no recursion allowed).
• is_superegg_recursive(s)
  • Returns True if s is a superegg, otherwise returns False.
  • Must use recursion in an essential way (calling itself).
• is_hyperegg(s)
  • Returns True if s is a hyperegg, otherwise returns False.
  • Must use recursion in an essential way (calling itself).

For all of these functions, you can assume that the only argument, s, is a string. You do not need to do any checking to detect an argument of another type.

Also, for functions that are required to use recursion, loops are permitted in the function body. However, a purely iterative solution it not acceptable.

To receive full credit, your code must also follow the additional requirements in the next section.

Other requirements¶

This section contains rules your code must follow, in addition to it needing to do everything documented in the previous section.

Coding standards¶

Like everything you submit for credit in MCS 275, your code must follow the rules in the course coding standards document.

No extra code in eggs.py¶

The file eggs.py should define the necessary functions, and when imported as a module, it should not do anything else. That is, running the Python REPL and typing

>>> import eggs

should succeed (no exceptions), should make the functions eggs.is_hyperegg etc. availabe, and should not print or do anything else.

It is permissible to put some test code in eggs.py outside of all the function bodies as long as you put it inside a block that looks like this:

if __name__=="__main__":
    # TEST CODE HERE

(The line containing if should not be indented at all.) This allows you to create tests that will run when the file is executed as a script, e.g. with

python eggs.py

but which are not run when it is imported as a module.

No character set limitations¶

Your functions should allow anything that Python considers to be a character to appear in the string. You must not impose extra assumptions (e.g. assuming all of the characters will be in the set A-Z, a-z, or 0-9 would be an error).

Prohibited and allowed modules¶

Code you submit for this project is not allowed to import the re module. (That's a module that contains functions which perform pattern matching on strings, potentially allowing you to circumvent the difficult parts of this assignment.)

I don't think you will need to import any modules at all in your solution, but the following modules are permitted if you find them useful for any reason (perhaps for testing):

• sys
• os
• math
• random

If you want to use a module that is not listed above, contact the instructor to request approval. If approval is given, the project description will be updated accordingly. Submissions that import modules not listed on the project description will be penalized.

Sample data¶

It is strongly recommended that you test the functions in your eggs module against the following sample data. Each is a text file containing one string per line. You'll need to write your own Python script to read these files line by line and check whether your functions behave as expected on these inputs.

Remember that when you read a line of text from a text file, it usually has a newline character at the end (which needs to be removed before you check whether it is an egg/superegg/hyperegg). The recommended way to deal with this is to check for a newline character at the end of a line and remove it if present, e.g. using code like

Links to sample data files¶

• eggs.txt --- 1000 eggs, one per line
• not_eggs.txt --- 1000 strings that are not eggs, one per line. (Some lines may be blank, because the empty string is not an egg.)
• supereggs.txt --- 1000 supereggs, one per line
• not_supereggs.txt --- 1000 strings that are not supereggs, one per line. (Some lines may be blank, because the empty string is not a superegg.)
• hypereggs.txt --- 1000 supereggs, one per line
• not_hypereggs.txt --- 1000 strings that are not hypereggs, one per line. (Some lines may be blank, because the empty string is not a hyperegg.)

You'll want to download (save) these files, rather than just view them in your browser.

A diagrammed hyperegg¶

In response to a student question about Project 2, I created the following diagram showing that the string on line 643 of hypereggs.txt is in fact a hyperegg:

Each line above is a statement that it is a hyperegg, given what is known from the lines above it. The colors highlight A, B, and B.

Autograder available¶

The autograder is available in Gradescope as of 2021-02-20.

Revision History¶

• 2021-02-24 Fixed typo in explanation of hyperegg example "alooloo"
• 2021-02-23 Add hyperegg diagram
• 2021-02-20 Add info about grading breakdown and autograder release
• 2021-02-17 Sample data links added; New section about allowed/prohibited modules
• 2021-02-11 Initial publication