Whose Cracked Egg?

A bakery buys its eggs from several farms. It knows what share of its eggs comes from each farm and how often an egg from that farm arrives cracked. A cracked egg turns up in the kitchen. Where did it most likely come from?

farms is a dictionary from a farm's name to a pair (share, crack_rate): the fraction of all eggs that come from that farm (the shares add up to 1) and the probability that one of its eggs is cracked. Write cracked_egg(farms) that returns a tuple (p_cracked, chances, likeliest):

• p_cracked is the probability that a random egg is cracked;
• chances is a dictionary from each farm to the probability that a cracked egg came from that farm;
• likeliest is the farm with the largest of these probabilities (on a tie within 1e-12, the one that comes first in farms).

If no egg can be cracked (every rate is 0), return (0.0, None, None).

Examples

Input:  farms = {"Hilltop": (0.7, 0.01), "Meadow": (0.2, 0.03), "Brook": (0.1, 0.06)}
Output: (0.019, {"Hilltop": 0.3684210526315789, "Meadow": 0.3157894736842105,
                 "Brook": 0.3157894736842105}, "Hilltop")
Explanation: per 1000 eggs, Hilltop sends 700 with 7 cracked, Meadow 200 with 6 and
Brook 100 with 6. That is 19 cracked eggs, 7 of them from Hilltop, although Hilltop
has the lowest crack rate.

Constraints

• 1 to 50 farms; shares are positive and add up to 1; rates are between 0 and 1
• floats are compared with a tolerance of 1e-6

Goals

• Combine shares and rates into an overall probability (the law of total probability)
• Turn P(cracked | farm) into P(farm | cracked) with Bayes' rule
• See that a large supplier can be the likeliest source despite a low rate