🐥

SoDuckYou

Getting started on Parts A & B:
count_patches() and rule_breaks()

CS 149 · Use → / space to advance, ← to go back, N for notes, T for theme

The puzzle

A pond is split into lettered patches. Place ducks so that:

  • every row has exactly one duck
  • every column has exactly one duck
  • every patch has exactly one duck
  • no two ducks touch, not even corner to corner

This 4 × 4 pond, “Puddle,” is solved. Check each rule.

You write the referee

Four functions, each one checking part of the rules. The game itself is already written.

PartFunctionJob
Acount_patches(grid, ducks)How many ducks are in each patch?
Brule_breaks(grid, ducks)Which rows, columns, patches don't have exactly one?
Ctouching(ducks)Which ducks are too close? (later)
Dload_levels(filename, size)Read levels from a JSON file (later)
Etest_soduckyou.pyYour 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.

Parameter 1grid: a list of strings

grid = ["ABBC",    # row 0
        "ABBC",    # row 1
        "ABBD",    # row 2
        "ADDD"]    # row 3
  • One string per row, one letter per square
  • Same letter = same patch
  • grid[2] is the string "ABBD" (picks the row)
  • grid[2][3] is "D" (then picks the column)
  • Square pond: len(grid) rows and len(grid) columns

Quick check: grid[3][0]? "A"

Parameter 2ducks: a list of pairs

ducks = [(0, 1), (1, 2), (3, 0)]
  • Each duck is a tuple (row, column)
  • Type hint: list[tuple[int, int]], “a list of tuples of two ints”
  • No duck appears twice
  • The list can be empty: [] is a pond with no ducks yet
  • The list is in the order the player placed them, not sorted
duckrowcolits letter
(0, 1)01grid[0][1] → "B"
(1, 2)12grid[1][2] → "B"
(3, 0)30grid[3][0] → "A"

Part Acount_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.

Part AMore examples

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}

ToolLooping over a list of pairs

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

How unpacking works

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.

ToolDictionary comprehensions

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'}

Part AThe plan

  1. Start the dictionary with a comprehension: every letter in the grid → 0
  2. Loop over the ducks once, unpacking each into row and column
  3. Look up the letter under that duck in the grid
  4. Add 1 to that letter's count
  5. Return the dictionary

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.

ducklettercounts
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}

Part Brule_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']
  • Order: rows top to bottom, then columns left to right, then patches A to Z
  • Rows and columns are numbered from 0
  • Exact wording: "Row 2 has 0 ducks", always “ducks”

Part BMore examples

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']

Try it: click squares to place ducks


      

      

    

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

ToolDictionary items, in order

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…

Part BThe plan

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}
checkmessage
row 2: get → 0Row 2 has 0 ducks
col 3: get → 0Column 3 has 0 ducks
B → 2, C → 0, D → 0Patch B / C / D …

ducks = [(0, 1), (1, 2), (3, 0)]

Common mistakes

  • grid[col][row]: row comes first
  • Only adding a patch key when a duck lands on it, so empty patches go missing
  • rows[row] += 1 on a new row → KeyError
  • Looping over the row dictionary instead of range, so empty rows are never reported
  • Patches in dictionary order instead of sorted order
  • Typos in messages: "Col 3", "duck", missing spaces. Must match exactly
  • printing messages instead of returning the list
  • return inside a loop, so it quits after the first item
  • Changing grid or ducks; build new dicts and lists instead
  • Checking for touching ducks in rule_breaks; that's Part C

Not allowed in soduckyou.py

.count(), .index(), any(), all(), lambda, generator expressions, and any import except json. Comprehensions, get(), keys(), values(), items(), sorted(), and abs() are fine.

Part ETest as you go

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

Your tests are graded three ways

  • Pass on a correct solution: a wrong expected value fails
  • Fail on functions that return nonsense
  • Catch planted bugs, like the ones on the last slide

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.

Get started now

  1. Put your name and the date in both .py files
  2. Read the count_patches docstring; trace the example by hand
  3. Write test_count_patches, then count_patches; run pytest
  4. Same for rule_breaks
  5. Run ruff check, then submit both files to Gradescope after each part

Before you leave: can you solve this one?

Part A comprehension + loop over pairs   Part B get() + range + sorted items