Paper by the ream

A paper merchant's day book records only the conversions the trade says out loud: a ream in quires, a quire in sheets. Customers ask for the others.

The problem

The day book is a list of entries. ["ream", "quire", 20.0] means one ream is 20 quires, and it reads backwards too — one quire is a twentieth of a ream. The book is consistent: two chains between the same pair never disagree.

A query [a, b] asks how many b make one a. Answer it from the book, or -1.0 where the book cannot: a measure it never names, or two measures with no chain of entries between them. Round each answer to six decimal places.

Input. book — a list of [first, second, count] entries. queries — a list of [a, b] pairs.

Output. A list of floats, one per query.

Example.

book = [["ream", "quire", 20.0], ["quire", "sheet", 25.0]]
queries = [["ream", "sheet"], ["sheet", "ream"], ["quire", "quire"],
           ["ream", "bale"]]
  ->  [500.0, 0.002, 1.0, -1.0]

A ream is 20 quires and a quire 25 sheets, so a ream is 500 sheets and a sheet a five-hundredth of a ream. A named measure converts to itself at 1.0, and bale is nowhere in the book, so the merchant will not quote it.

A second example, two chains that never meet:

book = [["bundle", "ream", 2.0], ["crate", "carton", 6.0]]
queries = [["bundle", "carton"], ["crate", "carton"]]   ->  [-1.0, 6.0]

Both measures in the first query are in the book. That is not enough — no entry joins the bundle side to the crate side.

Constraints.

• 1 <= len(book) <= 5000 and 1 <= len(queries) <= 1000
• every count is a positive float
• measure names are lowercase words
• the book never contradicts itself

Hints

Approach

Brute force

Answer each query by trying every chain of entries between the two measures. A chain visits a measure at most once, so with M measures there are up to (M - 1)! of them — 3.6·10⁵ for ten measures, and the book runs to thousands.

The insight

Every entry is an edge whose count multiplies along a route, and a consistent book gives the same product on every route between two measures — so one walk out of a, carrying the product so far, answers the query.

Consistency is the precondition, and it is what lets the walk mark a measure seen on first arrival: a later arrival comes another way but carries the same number, so refusing it loses nothing. Without it the answer would depend on which way the walk went.

Algorithm

1. Build a dictionary of measure → list of (neighbour, rate), storing count one way and 1 / count the other.
2. For a query, return -1.0 if either measure is missing from it.
3. Push (a, 1.0) on a stack and mark a seen.
4. Pop a measure with the product that reached it; if it is b, that product, rounded, is the answer.
5. Push every unseen neighbour with the product times its rate, marking on push.
6. An empty stack means separate chains: -1.0.

Complexity

Time O(Q · (M + E)) — one walk per query, over at most every measure and entry. Space O(M + E) for the dictionary, plus one walk's stack and seen set.

Solution

"""Paper by the ream — walk the day book, carrying the product so far."""


def conversions(book):
    """Each entry gives two arrows: a -> b at k, and b -> a at 1 / k."""
    rates = {}
    for first, second, count in book:
        rates.setdefault(first, []).append((second, count))
        rates.setdefault(second, []).append((first, 1.0 / count))
    return rates


def between(rates, start, wanted):
    """How many `wanted` make one `start`, or -1.0 if the book cannot say."""
    if start not in rates or wanted not in rates:
        return -1.0
    stack = [(start, 1.0)]
    seen = {start}
    while stack:
        measure, factor = stack.pop()
        if measure == wanted:
            return round(factor, 6)
        for nxt, rate in rates[measure]:
            if nxt not in seen:
                seen.add(nxt)        # a consistent book agrees on every route, so take one
                stack.append((nxt, factor * rate))
    return -1.0


def solve(book, queries):
    rates = conversions(book)
    return [between(rates, a, b) for a, b in queries]


_CHAIN = [["m%d" % i, "m%d" % (i + 1), 2.0 if i % 2 == 0 else 0.5] for i in range(2000)]

TESTS = [
    (([["ream", "quire", 20.0], ["quire", "sheet", 25.0]],
      [["ream", "sheet"], ["sheet", "ream"], ["quire", "quire"], ["ream", "bale"]]),
     [500.0, 0.002, 1.0, -1.0]),
    (([["bundle", "ream", 2.0], ["crate", "carton", 6.0]],
      [["bundle", "carton"], ["crate", "carton"]]),
     [-1.0, 6.0]),
    (([["bale", "ream", 3.0]], [["ream", "bale"], ["bale", "ream"]]),
     [0.333333, 3.0]),
    (([["ream", "quire", 20.0], ["quire", "sheet", 25.0]], [["sheet", "quire"]]),
     [0.04]),
    (([["ream", "quire", 20.0]], [["bale", "bale"]]),          # unknown, even against itself
     [-1.0]),
    # 2000 conversions in one chain: the walk must not use the call stack.
    ((_CHAIN, [["m0", "m2000"], ["m0", "m1"]]), [1.0, 2.0]),
]

Pitfalls

• Answering 1.0 for a measure the book never names. ["bale", "bale"] looks like a free win; the merchant has no bale, so it is -1.0.
• Adding the counts instead of multiplying them. The first example then reports 45 sheets to the ream rather than 500.
• Storing only the direction the entry was written in. Every query that reads a chain backwards comes back -1.0, ["sheet", "ream"] included.

Variants

• The cask ledger — claims that say only same or different, with no factor to carry.
• Representing a graph — why a dictionary keyed by name is the adjacency list here.