Problem 425445 · medium · Level 04 Non-Linear Data Structures

How Many Cakes Can We Bake?

py-dunder · multisets · operator overloading · container protocol

A bakery's planning tool keeps track of ingredients as counts: 12 eggs, 5 bags of flour, 3 blocks of butter. A shopping delivery adds to the pantry, baking takes away from it, a recipe fits in the pantry when there is enough of everything, and the question asked every morning is how many times a recipe can be made.

Write a class Pantry(items=None), where items is a dictionary from ingredient names to non-negative whole counts:

  • p["egg"] is the count of "egg", 0 if there is none; p["egg"] = 4 sets it (0 removes the ingredient). A negative count, in the constructor or in an assignment, raises ValueError.
  • len(p) is the number of different ingredients present, "egg" in p says whether there is at least one, and for name in p goes through the names present in alphabetical order.
  • p + q adds the counts; p - q subtracts them, and ingredients that reach zero or less disappear; p * k and k * p multiply every count by a whole number k >= 0.
  • recipe <= p is True when p has at least as much of every ingredient as recipe; recipe < p also requires them to differ; >= and > are the reverse.
  • p // recipe is the number of times recipe can be made from p; for an empty recipe it raises ZeroDivisionError, like dividing by zero.
  • p == q when both have the same counts; repr(p) is Pantry({...}) with the names in alphabetical order, for example Pantry({'egg': 3, 'flour': 2}).

Every operation returns a new Pantry and leaves its operands unchanged. The setup's delivery(n, seed) makes a pantry of random counts and raises(fn, *args) returns the name of the exception a call raises (or None).

Examples

Input:  stock = Pantry({"egg": 12, "flour": 5, "butter": 3})
        cake = Pantry({"egg": 4, "flour": 2, "butter": 1})
        stock // cake, cake <= stock, repr(stock - cake * 2), len(stock - cake * 3)
Output: (2, True, "Pantry({'butter': 1, 'egg': 4, 'flour': 1})", 0)

Input:  p = Pantry({"salt": 0, "milk": 2}); repr(p), list(p + Pantry({"jam": 1})), p["salt"], "salt" in p
Output: ("Pantry({'milk': 2})", ['jam', 'milk'], 0, False)

Constraints

  • Up to 5000 different ingredients; counts up to 10**9.

Goals

  • Choose operators whose meaning is obvious for the objects (`+`, `-`, `<=`, `*`, `//`)
  • Implement the container hooks `__getitem__`, `__setitem__`, `__len__`, `__contains__` and `__iter__`
  • Keep an invariant (no zero or negative counts are stored) in every operation
Starting Python…