Back to AI Coding

Word Bag Maximizer

One way to clear each phase. Compare the approach with your own, then try the patterns yourself.

src/char_set.py
"""Phase 1 fixes:
  * Duplicate detection has to actually flip `_valid`.
  * Non-alphabetic characters (digits, whitespace, punctuation) must be
    ignored entirely — neither counted nor treated as duplicates.
"""

from typing import Set


class CharSet:
    """Alphabet footprint of a single word."""

    def __init__(self, word: str):
        self._word = word
        self._valid = True
        self._chars: Set[str] = set()
        for ch in word:
            ch = ch.lower()
            # Bug fix 2: skip non-letters (digits, whitespace, punctuation
            # are documented as ignored).
            if not ('a' <= ch <= 'z'):
                continue
            if ch in self._chars:
                # Bug fix 1: a duplicate letter must mark the word invalid.
                self._valid = False
            self._chars.add(ch)

    @property
    def word(self) -> str:
        return self._word

    def is_valid(self) -> bool:
        return self._valid

    def size(self) -> int:
        return len(self._chars)

    def chars(self) -> Set[str]:
        return self._chars

    def overlaps(self, other: "CharSet") -> bool:
        return bool(self._chars & other._chars)
src/word_bag.py
"""Phase 1 fix: `score()` reports the count of UNIQUE LETTERS in the
bag, not the number of words held."""

from typing import List, Set
from char_set import CharSet


class WordBag:
    """Running accumulator of selected words and their union of chars."""

    def __init__(self):
        self._chars: Set[str] = set()
        self._words: List[str] = []

    def can_add(self, cs: CharSet) -> bool:
        if not cs.is_valid():
            return False
        for ch in cs.chars():
            if ch in self._chars:
                return False
        return True

    def add(self, cs: CharSet) -> None:
        self._words.append(cs.word)
        for ch in cs.chars():
            self._chars.add(ch)

    def remove(self, cs: CharSet) -> None:
        self._words.pop()
        for ch in cs.chars():
            self._chars.discard(ch)

    def score(self) -> int:
        # Bug fix: number of unique characters across all picked words,
        # not the number of words.
        return len(self._chars)

    def words(self) -> List[str]:
        return list(self._words)

Discuss