PA4: SoDuckYou

Picture a pond split into patches of different colors. You have a flock of ducks, and they are very particular about where they sit:

• every row gets exactly one duck,
• every column gets exactly one duck,
• every patch gets exactly one duck,
• and no two ducks may touch, not side by side and not corner to corner.

Put the ducks down so that all four rules hold at once, and you've solved the level. It sounds easy on a 4 × 4 pond. On a 6 × 6 pond with a patch that winds all the way around the others, it takes some real thinking.

Play SoDuckYou in your browser to get a feel for it before you write any code.

In this PA, you write the referee. Your code counts the ducks in each patch, reports every row, column, and patch that has the wrong number, finds every pair of ducks that are too close, and reads the levels from a file. The main block, already written for you, turns those four functions into a game you can play. And as in PA2, you also write the tests that prove your referee is right, and you submit them with your code.

What you'll practice

• Building a dictionary with a dictionary comprehension, and counting into it.
• Counting with get() so a missing key doesn't crash, and looping over a dictionary's items() in sorted order.
• Writing a loop inside a loop to compare every pair of items in a list (Week 12).
• Reading a JSON file, and pulling the fields you need out of a list of dictionaries (Week 12).

Get set up

Download these files and save them in the Week11 folder inside ~/CS149:

• soduckyou.py, the module with your four functions
• levels.json, the levels, which the program reads in Part D
• test_soduckyou.py, the test file you fill in for Part E
• play_soduckyou.py, a driver that lets you play the game in a window, refereed by your own code (you don't need to read or change it, and you don't submit it)

Open soduckyou.py and look around. All four functions are already there, each with type hints and a docstring that says exactly what it takes and what it returns, and each body is just pass. Your job is to replace those pass lines with real code. Read each docstring all the way through, example included, before you start that function. The main block at the bottom is written for you; leave it alone.

Put your name and today's date in place of YOUR NAME and THE DATE at the top of both .py files. Gradescope checks.

How the pond is stored

A pond is a list of strings, one string per row and one letter per square. Squares with the same letter make up one patch:

grid = ["ABBC",        #   0 1 2 3
        "ABBC",        # 0 A B B C
        "ABBD",        # 1 A B B C
        "ADDD"]        # 2 A B B D
                       # 3 A D D D

Rows and columns are numbered from 0, so grid[2][3] is the letter of the square in row 2, column 3: "D". A duck is a tuple (row, column), and the ducks on the pond are a list of those tuples. [(0, 1), (1, 3)] is a duck in row 0, column 1 (patch B), and another in row 1, column 3 (patch C).

Part A: count the ducks with count_patches

count_patches(grid, ducks) returns a dictionary from each patch's letter to how many ducks are in it. Every patch has to be in the dictionary, even one with no ducks, so you need to know all the letters before you count. Here is a quick way to get them: join the rows into one long string, then make a set of its characters.

>>> set("".join(["AAB", "ACB"]))
{'A', 'B', 'C'}

Start the dictionary with a dictionary comprehension that gives every letter a count of 0. Then loop over the ducks once, look up the letter under each one, and add 1 to that letter's count.

>>> count_patches(["ABBC", "ABBC", "ABBD", "ADDD"], [(0, 1), (1, 2), (3, 0)])
{'A': 1, 'B': 2, 'C': 0, 'D': 0}

To check Part A, write test_count_patches in test_soduckyou.py (see Part E) and run pytest. Don't run soduckyou.py itself yet: until Part D reads the levels file, its main block stops with a TypeError. That is expected, not a sign you broke something.

Part B: report the broken rules with rule_breaks

rule_breaks(grid, ducks) returns a list of messages, one for every row, column, and patch that doesn't have exactly one duck:

>>> rule_breaks(["ABBC", "ABBC", "ABBD", "ADDD"], [(0, 1), (1, 2), (3, 0)])
['Row 2 has 0 ducks', 'Column 3 has 0 ducks', 'Patch B has 2 ducks', 'Patch C has 0 ducks', 'Patch D has 0 ducks']

The order matters: rows from the top, then columns from the left, then patches in alphabetical order. A solved pond returns [].

For rows and columns, count the ducks in each one with two dictionaries, using get() so the first duck in a row doesn't crash:

rows[row] = rows.get(row, 0) + 1

Then loop over every row number with range, and use get() again, because a row with no ducks never got a key. For the patches, call your Part A, and loop over sorted(...) of its items() to get each letter and its count together, in alphabetical order.

Part C: find ducks that are too close with touching (Week 12)

Two ducks touch when their rows are at most 1 apart and their columns are at most 1 apart. That covers all eight squares around a duck: the four beside it and the four on its corners.

touching(ducks) returns every pair of ducks that touch, as tuples of two ducks:

>>> touching([(0, 1), (2, 0), (1, 2), (3, 1)])
[((0, 1), (1, 2)), ((2, 0), (3, 1))]

To compare every duck with every other duck, you need a loop inside a loop. The outer loop picks a duck by its index i, and the inner loop picks a duck after it, with range(i + 1, len(ducks)). Starting the inner loop after i means a duck is never compared with itself, and each pair comes up only once, in the order of the list.

Part D: read the levels with load_levels (Week 12)

levels.json holds a list of levels, and each level is a dictionary:

[
    {"name": "Puddle", "size": 4, "grid": ["ABBC", "ABBC", "ABBD", "ADDD"]},
    {"name": "Mud Hole", "size": 4, "draft": true, "grid": ["AABB", "AABB", "CCDD", "CCDD"]},
    {"name": "Pond", "size": 5, "grid": ["AAAAA", "AAABC", "DEBBB", "DDBBB", "DDBBB"]}
]

json.load(file) turns the whole file into that list of dictionaries in one call. load_levels(filename, size) then keeps the levels of the size the player asked for, skips the drafts, and returns a dictionary from each level's name to its grid. Most levels don't have a "draft" key at all, so level["draft"] would crash on them; use get(), as in Part B.

Part E: prove it with test_soduckyou.py

Open test_soduckyou.py. It imports your four functions and has one test function for each, test_count_patches, test_rule_breaks, test_touching, and test_load_levels, with a docstring suggesting what to test. PUDDLE at the top is there for you to use in your tests. Replace each pass with at least three assert statements, each checking one call against an answer you worked out yourself:

def test_count_patches():
    assert count_patches(PUDDLE, [(0, 1), (1, 2), (3, 0)]) == {"A": 1, "B": 2, "C": 0, "D": 0}
    ...

Write each test as you finish its part: the first two this week, and the last two next week. Your test_load_levels can read levels.json by name, the way the main block does; Gradescope runs your tests next to its own copy.

Run your tests from the terminal, in your Week11 folder:

cd Week11
pytest

or click the beaker icon in VS Code's Testing view.

Gradescope grades your tests in three ways, once all four test functions have their asserts:

• They must pass on a correct soduckyou.py. A test that fails there has a wrong expected value. Gradescope runs your tests against the correct solution here, not against your own code.
• They must fail on a soduckyou.py whose functions return nonsense, so every test has to check what a function returns.
• They must catch bugs. Gradescope plants a mistake in a correct soduckyou.py, one function at a time, and at least one of your tests has to fail on each. The mistakes are the kind people really make in this PA.

Test it before you submit

Run pytest after every change, and submit to Gradescope after each part. If a test fails, read the message: it shows the value your function returned next to the one your test expected. Before you decide the function is wrong, work out the answer by hand once more, because sometimes the test is the one with the mistake. Gradescope's messages name the part and what it checked.

When all four work, run soduckyou.py, and play the level below by typing the inputs shown. You should see exactly this (the duck takes up two spaces, so the columns still line up in Thonny):

Welcome to SoDuckYou!
Pond size (4, 5, or 6): 4
Levels: Puddle, Splash
Level: Lake
No such level. Level: Puddle
Row and column (blank to quit): 0 1

  0 1 2 3
0 A 🐥B C
1 A B B C
2 A B B D
3 A D D D
- Row 1 has 0 ducks
- Row 2 has 0 ducks
- Row 3 has 0 ducks
- and 6 more
Row and column (blank to quit): 1 2

  0 1 2 3
0 A 🐥B C
1 A B 🐥C
2 A B B D
3 A D D D
- Ducks at (0, 1) and (1, 2) are touching
- Row 2 has 0 ducks
- Row 3 has 0 ducks
- and 6 more
Row and column (blank to quit): 1 2

  0 1 2 3
0 A 🐥B C
1 A B B C
2 A B B D
3 A D D D
- Row 1 has 0 ducks
- Row 2 has 0 ducks
- Row 3 has 0 ducks
- and 6 more
Row and column (blank to quit): 1 3

  0 1 2 3
0 A 🐥B C
1 A B B 🐥
2 A B B D
3 A D D D
- Row 2 has 0 ducks
- Row 3 has 0 ducks
- Column 0 has 0 ducks
- and 3 more
Row and column (blank to quit): 2 0

  0 1 2 3
0 A 🐥B C
1 A B B 🐥
2 🐥B B D
3 A D D D
- Row 3 has 0 ducks
- Column 2 has 0 ducks
- Patch D has 0 ducks
Row and column (blank to quit): 3 2

  0 1 2 3
0 A 🐥B C
1 A B B 🐥
2 🐥B B D
3 A D 🐥D
You solved it! Every duck has its own space.

Typing a square that already has a duck takes the duck back off, as the third move does. Then try Splash, and the 5 × 5 and 6 × 6 levels, on your own.

Rules

Submission

Submit both soduckyou.py and test_soduckyou.py to the Gradescope assignment PA4 SoDuckYou, then commit and push your Week11 folder (how). Upload both files every time, even if test_soduckyou.py is still the starter version: if either one is missing, Gradescope stops with test_soduckyou.py not found (or soduckyou.py not found) and grades nothing. Don't upload levels.json or play_soduckyou.py; Gradescope has its own copy of the levels, and it turns away any file it isn't expecting. Gradescope also checks that your name and the date are in both docstrings, and that ruff check is clean on both files.

Where the idea comes from

SoDuckYou is our take on Meowdoku, a mobile puzzle game by Oakever Games in which you place cats instead of ducks. The rules go back to a pencil puzzle called Star Battle, and you may also know them from LinkedIn's daily Queens. The levels in levels.json were made for this PA, and each one has exactly one solution.