count_patches() and rule_breaks()CS 149 · Use → / space to advance, ← to go back, N for notes, T for theme
A pond is split into lettered patches. Place ducks so that:
This 4 × 4 pond, “Puddle,” is solved. Check each rule.
Four functions, each one checking part of the rules. The game itself is already written.
| Part | Function | Job |
|---|---|---|
| A | count_patches(grid, ducks) | How many ducks are in each patch? |
| B | rule_breaks(grid, ducks) | Which rows, columns, patches don't have exactly one? |
| C | touching(ducks) | Which ducks are too close? (later) |
| D | load_levels(filename, size) | Read levels from a JSON file (later) |
| E | test_soduckyou.py | Your tests: write each one as you finish its part |
Each function starts as pass with a full docstring. Read the docstring, example included, before you start.
Check your work with pytest, not by running soduckyou.py: its main block crashes with a TypeError until Part D works. That's expected.
grid: a list of stringsgrid = ["ABBC", # row 0 "ABBC", # row 1 "ABBD", # row 2 "ADDD"] # row 3
grid[2] is the string "ABBD" (picks the row)grid[2][3] is "D" (then picks the column)len(grid) rows and len(grid) columnsQuick check: grid[3][0]? "A"
ducks: a list of pairsducks = [(0, 1), (1, 2), (3, 0)]
(row, column)list[tuple[int, int]], “a list of tuples of two ints”[] is a pond with no ducks yet| duck | row | col | its letter |
|---|---|---|---|
| (0, 1) | 0 | 1 | grid[0][1] → "B" |
| (1, 2) | 1 | 2 | grid[1][2] → "B" |
| (3, 0) | 3 | 0 | grid[3][0] → "A" |
count_patches(grid, ducks)def count_patches(grid: list[str], ducks: list[tuple[int, int]]) -> dict[str, int]:
Returns a new dictionary: patch letter → number of ducks in it.
>>> count_patches(["ABBC", "ABBC", "ABBD", "ADDD"],
... [(0, 1), (1, 2), (3, 0)])
{'A': 1, 'B': 2, 'C': 0, 'D': 0}
Every patch in the grid is a key, including patches with 0 ducks. C and D have no ducks, and they're still there.
Key order doesn't matter: two dicts are == if they have the same keys and values.
No ducks yet → every patch, all 0
>>> count_patches(["ABBC", "ABBC", "ABBD", "ADDD"], [])
{'A': 0, 'B': 0, 'C': 0, 'D': 0}
Solved pond → every patch, all 1
>>> count_patches(["ABBC", "ABBC", "ABBD", "ADDD"],
... [(0, 1), (1, 3), (2, 0), (3, 2)])
{'A': 1, 'B': 1, 'C': 1, 'D': 1}
Your turn, a different pond:
>>> count_patches(["AABB", "ACBB", "CCDD", "CCDD"], ... [(0, 0), (1, 1), (3, 3)])
{'A': 1, 'B': 0, 'C': 1, 'D': 1}
Index into each tuple…
scores = [("Ana", 90), ("Ben", 72)]
for pair in scores:
print(pair[0], "got", pair[1])
…or unpack it right in the for. Same output, easier to read:
for name, score in scores:
print(name, "got", score)
Ana got 90 Ben got 72
Each time through, the next tuple is split across the variables, left to right:
name, score = ("Ana", 90).
The number of variables must match the size of the tuple, or Python raises a ValueError.
Your ducks are pairs too, so pick good names: row and col.
Build a whole dictionary in one expression:
{ key: value for item in sequence }
>>> {w: len(w) for w in ["duck", "goose"]}
{'duck': 4, 'goose': 5}
>>> {n: n * n for n in range(4)}
{0: 0, 1: 1, 2: 4, 3: 9}
>>> {ch: 0 for ch in "xyz"}
{'x': 0, 'y': 0, 'z': 0}
It's shorthand for this loop:
result = {}
for ch in "xyz":
result[ch] = 0
Getting all the letters in a grid: join the rows, then make a set.
>>> "".join(["AAB", "ACB"])
'AABACB'
>>> set("".join(["AAB", "ACB"]))
{'A', 'B', 'C'}
Why loop over ducks, not over every square? Only squares with ducks change a count, and step 1 already gave the empty patches their 0.
| duck | letter | counts |
|---|---|---|
| start | {A:0, B:0, C:0, D:0} | |
| (0, 1) | "B" | {A:0, B:1, C:0, D:0} |
| (1, 2) | "B" | {A:0, B:2, C:0, D:0} |
| (3, 0) | "A" | {A:1, B:2, C:0, D:0} |
rule_breaks(grid, ducks)def rule_breaks(grid: list[str], ducks: list[tuple[int, int]]) -> list[str]:
Same two parameters as Part A. Returns a list of messages, one per row, column, or patch that does not 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']
"Row 2 has 0 ducks", always “ducks”Solved → nothing to report
>>> rule_breaks(PUDDLE, [(0, 1), (1, 3), (2, 0), (3, 2)]) []
Two ducks in row 0 (columns and patches are fine)
>>> rule_breaks(PUDDLE, [(0, 0), (0, 3), (2, 1), (3, 2)]) ['Row 0 has 2 ducks', 'Row 1 has 0 ducks']
Touching isn't this function's job (that's Part C):
>>> rule_breaks(["AB", "BB"], [(0, 0), (1, 1)]) []
Your turn: rule_breaks(["AB", "BB"], [(0, 1), (1, 1)])
['Column 0 has 0 ducks', 'Column 1 has 2 ducks', 'Patch A has 0 ducks', 'Patch B has 2 ducks']
dict.get(key, default)Square brackets crash on a missing key:
>>> tally = {"duck": 2}
>>> tally["goose"]
KeyError: 'goose'
get returns the default instead:
>>> tally.get("goose", 0)
0
>>> tally.get("duck", 0)
2
That makes counting into an empty dictionary safe:
tally = {}
for bird in ["duck", "goose", "duck"]:
tally[bird] = tally.get(bird, 0) + 1
# {'duck': 2, 'goose': 1}
“No key yet” and “a count of 0” come out the same. And get never adds a key. A bird that never showed up still isn't in tally, so ask with get again when you read the counts.
items() gives the key, value pairs, so unpack them just like the scores:
tally = {"goose": 1, "duck": 2}
for bird, count in tally.items():
print(bird, count)
sorted() on a list of pairs sorts by the first item, the key:
>>> sorted({"C": 0, "A": 1, "B": 2}.items())
[('A', 1), ('B', 2), ('C', 0)]
Put them together to visit every key alphabetically, with its value:
for bird, count in sorted(tally.items()):
print(bird, count)
duck 2 goose 1
Part B needs its patch messages A to Z, and Part A hands you a dictionary of patch counts…
1. Count. Two empty dictionaries, one for rows and one for columns. Loop over the ducks and count each duck's row and column with get().
2. Rows. Loop over every row number with range(len(grid)). If its count (with get, default 0) isn't 1, add a message.
3. Columns. Same thing for every column number.
4. Patches. Call count_patches. Loop over its sorted items. If a count isn't 1, add a message.
5. Return the list.
Why range and not the row dictionary's keys? An empty row never got a key, and an empty row is exactly what you need to report.
| after step 1 | |
|---|---|
| rows | {0: 1, 1: 1, 3: 1} |
| cols | {1: 1, 2: 1, 0: 1} |
| check | message |
|---|---|
| row 2: get → 0 | Row 2 has 0 ducks |
| col 3: get → 0 | Column 3 has 0 ducks |
| B → 2, C → 0, D → 0 | Patch B / C / D … |
ducks = [(0, 1), (1, 2), (3, 0)]
grid[col][row]: row comes firstrows[row] += 1 on a new row → KeyErrorrange, so empty rows are never reported"Col 3", "duck", missing spaces. Must match exactlyprinting messages instead of returning the listreturn inside a loop, so it quits after the first itemgrid or ducks; build new dicts and lists insteadrule_breaks; that's Part C.count(), .index(), any(), all(), lambda, generator expressions, and any import except json.
Comprehensions, get(), keys(), values(), items(), sorted(), and abs() are fine.
In test_soduckyou.py, replace each pass with at least three asserts, each against an answer you worked out by hand.
def test_count_patches():
"""Check the ducks in each patch."""
assert count_patches(
PUDDLE, [(0, 1), (1, 2), (3, 0)]
) == {"A": 1, "B": 2, "C": 0, "D": 0}
...
$ pytest
Good cases: the docstring example, no ducks, a solved pond, an empty row or column, two ducks in one row, a patch with no duck.
.py filescount_patches docstring; trace the example by handtest_count_patches, then count_patches; run pytestrule_breaksruff check, then submit both files to Gradescope after each partBefore you leave: can you solve this one?
Part A comprehension + loop over pairs Part B get() + range + sorted items