Implement chance of a personal best

You are given a simplified model for tracking race times on an obstacle course.

• A course has a fixed number of obstacles.
• A run records the time spent on each obstacle in order.
• A run may be complete or incomplete.
• A run collection stores many runs for the same course.

For an obstacle index i, the historical times available for that obstacle come from all other runs that reached obstacle i, including incomplete runs.

Implement the method chance_of_personal_best(run) in RunCollection.

Required behavior

Given an in-progress run:

1. Perform 10,000 simulation trials.
2. In each trial, for every obstacle not yet completed in the current run, randomly choose one historical time for that obstacle from the other runs in the collection that have a recorded time for that obstacle.
3. Combine the current run's existing obstacle times with the sampled remaining times.
4. Check whether the simulated total time is less than or equal to the current personal best.
5. Return the fraction of trials that are a personal best (or tie the personal best).

Important details

• The current personal best is the minimum total time among completed runs only.
• When sampling future obstacle times, include times from incomplete historical runs if they reached that obstacle.
• Do not sample from the in-progress run being evaluated.
• The returned value should be a floating-point probability, and with 10,000 trials it should usually be within 0.02 of the true probability.

Example

Suppose a course has 3 obstacles and the historical runs are:

• [3, 3, 2]
• [3, 3, 3]

The current in-progress run is [3, 3].

The personal best among completed runs is 8. For the last obstacle, the historical times are {2, 3}. So the simulated completed run is either [3,3,2] or [3,3,3], each with equal probability. Therefore the chance of matching or beating the personal best is about 0.5.

Starter structure

Assume classes similar to the following already exist:

• Course(title, obstacle_count)
• Run(course) with fields:
  • course
  • complete
  • obstacle_times
  • add_obstacle_time(t)
  • get_run_time()
• RunCollection(course) with field:
  • runs

Write the chance_of_personal_best method for RunCollection.

Chance of a Personal Best (Obstacle-Course Simulation)

You are tracking race times on an obstacle course.

• A course has a fixed number of obstacles (obstacle_count).
• A run records the time spent on each obstacle, in order. A run may be complete (all obstacles recorded) or incomplete (in progress / aborted).
• A run collection stores many runs for the same course. Historical times for obstacle i come from every run that reached obstacle i, including incomplete runs.

You are given an in-progress run and must compute the probability that it ends up being a new personal best or ties the current personal best, under this model: for every obstacle the in-progress run has not yet completed, its time is drawn uniformly at random from the times recorded for that obstacle across all other runs in the collection that reached it. The original framing runs 10,000 simulation trials; here you should return the exact probability that simulation converges to.

Inputs to solution:

• obstacle_data: a list of runs, each a list of ints (the obstacle times for that run, in order). A run is complete iff its length equals obstacle_count.
• current_times: a list of ints — the obstacle times the in-progress run has recorded so far (a prefix; not present in obstacle_data).
• obstacle_count: int, the number of obstacles on the course.

Rules:

1. The personal best is the minimum total time among completed runs only.
2. For each obstacle index i that the in-progress run has NOT completed (i.e. i >= len(current_times)), the pool of candidate times is [run[i] for run in obstacle_data if len(run) > i].
3. Every combination of one sampled time per remaining obstacle is equally likely. Return the fraction of combinations for which sum(current_times) + sum(sampled) <= personal_best.
4. Return a float in [0.0, 1.0].

Example: course of 3 obstacles, history [[3,3,2],[3,3,3]], in-progress run [3,3]. Personal best = 8. The last obstacle's pool is {2,3}, so the completed run is [3,3,2] (=8, beats/ties) or [3,3,3] (=9, no), each with probability 1/2 -> answer 0.5.

Constraints

• 1 <= obstacle_count
• 0 <= len(current_times) <= obstacle_count (the in-progress run is a prefix)
• At least one run in obstacle_data is complete (length == obstacle_count), so the personal best is defined.
• Every remaining obstacle index is reached by at least one historical run (otherwise the probability is 0).
• All obstacle times are positive integers.

Hints

1. The personal best is the minimum total over COMPLETED runs only (length == obstacle_count); incomplete runs never set the personal best, but their recorded obstacle times ARE valid samples for the obstacles they reached.
2. For obstacle index i, the candidate sample times are exactly run[i] for every run whose length is greater than i.
3. Instead of 10,000 random trials, compute the exact probability: every combination of one candidate per remaining obstacle is equally likely, so the answer is (# combinations with current_fixed_sum + sampled_sum <= personal_best) / (total # combinations).
4. Full enumeration is pool_size ^ remaining_obstacles in the worst case. Use a DP/convolution: keep a map from achievable remaining-sum to how many combinations produce it, and extend it one obstacle at a time.