Learning the Table from a Log

A factory machine reports its state once an hour, for example "run", "idle" or "fault". The log of each shift is a list of states in time order. An engineer wants to model the machine as a Markov chain and needs its transition table: for each state a, the probability that the next hour's state is b.

Write estimate_table(shifts), where shifts is a list of shift logs. Return a dict of dicts: table[a][b] is the number of times state a was directly followed by state b, divided by the number of times a was directly followed by anything. Only count consecutive hours within a shift (the last hour of one shift is not followed by the first hour of the next). Include only entries that occurred at least once, and only states that were followed by something at least once.

The setup provides machine_log(shifts, hours, seed), which simulates a machine for shifts shifts of hours hours each.

Examples

Input:  shifts = [["run", "run", "idle", "run", "fault", "idle", "run", "run"]]
Output: {"run": {"run": 0.5, "idle": 0.25, "fault": 0.25}, "idle": {"run": 1.0},
         "fault": {"idle": 1.0}}
Explanation: "run" is followed by something 4 times (by run, idle, fault and run),
so run -> run is 2 / 4. The final "run" has no next hour and is not counted.

Input:  shifts = [["run", "fault"], ["idle", "run", "run"], ["fault"]]
Output: {"run": {"fault": 0.5, "run": 0.5}, "idle": {"run": 1.0}}
Explanation: "fault" never has a next hour within a shift, so it has no row.

Constraints

• 0 <= len(shifts) <= 1000, each shift has 0 to 10**4 entries, 10**5 entries in total at most
• floats are compared with a tolerance of 1e-6; the order of the keys does not matter

Goals

• Estimate a transition table by counting transitions
• Divide by the number of times each state had a successor, not by how often it occurred
• Keep separate sequences separate