This question has been bugging me, and now it's the weekend and I have some spare time to take a crack at it. It's actually easier than I originally thought it was (I first read it as "find the optimal workout, which requires dynamic programming).

In This House We Believe In Edwin Brady Thought

Edwin Brady defines his types first, and so do we. I like record syntax for this kind of thing, so we are all OCaml programmers on this blessed day. The record is going to contain the following:

• The current time, an integer.
• A list of remaining workouts, which starts as a 30-element cycle of 0-9.
• The other people's schedules, which can be changed by Jim.

In code:

type schedule = { use_time : int; recovery_time : int; first_use_time : int }

type frame = {
  time : int;
  remaining : int list;
  scheds : schedule list;
}

Utility Functions

OCaml's stdlib is kinda bare-bones. They're getting better about it, but they're still missing a couple of things that I miss from some of the other MLs. They're also missing the >> operator from F#, which I'm partial to.

let ( >> ) f g = Fun.compose g f

let foldl1 f sq =
  match Seq.uncons sq with
  | Some (x, xs) -> Seq.fold_left f x xs
  | None -> failwith "foldl1: empty seq"

let last xs = foldl1 (Fun.flip Fun.const) xs

let chunk n xs =
  let rec aux acc ys =
    if List.is_empty ys then List.rev acc
    else aux (List.take n ys :: acc) (List.drop n ys)
  in
  aux [] xs

let update n x xs =
    List.mapi (fun i y -> if i = n then x else y) xs

Function Types

Jim is also going to have a schedule list, but it's immutable, so it's going to be its own separate argument to my function. Also, Jim's first_use_time isn't needed for any of his workouts, so we'll set all of those to 0 when I parse them.

Our go function (common OCaml name for what's about to happen, a Seq.iterate) is going to take two arguments: Jim's schedule (a schedule list) and a frame. It's going to return a new frame, doing the following:

• Pop an index off of remaining_workouts, n.
• Obtain Jim's schedule and the other person's schedule by finding the nth element of these lists.
• Use t, the other person's schedule, and Jim's schedule to determine two things: the other person's new schedule, and the new t2 such that Jim has finished his workout and recovery time.

Let's do #3 first and break it out into its own function, as it's the most complicated step.

The do_workout Function

There are two cases:

• t is less than the other person's first_use_time, or t is inside the other person's recovery time, which means that Jim gets to work out with no waiting.
• t is inside the other person's workout time, which means that Jim needs to wait until that person's use_time is done.

In either case, we need to update the other person's schedule, since Jim's use_time might be large. So even if Jim patiently waits his turn and goes immediately after the other person is done working out, that might still delay the other person's next workout start if Jim is slow enough on that machine. We actually have a really easy way to update the other person's schedule: we just set the new first_start_time to the maximum of Jim's workout finish and the existing start of the other guy's next workout.

let do_workout t other_sched jim_sched =
  let workout_window_size = other_sched.use_time + other_sched.recovery_time in
  let other_start_time =
    other_sched.first_use_time
    + (t - other_sched.first_use_time)
      / workout_window_size * workout_window_size
  in
  let jim_start_time =
    (* Case 1 *)
    if
      t < other_sched.first_use_time
      || t >= other_start_time + other_sched.use_time
    then t
    (* Case 2 *)
      else other_start_time + other_sched.recovery_time
  in
  let new_start_time =
    List.fold_left max 0
      [
        other_sched.first_use_time;
        jim_start_time + jim_sched.use_time;
        other_start_time + workout_window_size;
      ]
  in
  ( jim_start_time + jim_sched.use_time + jim_sched.recovery_time,
    { other_sched with first_use_time = new_start_time } )

Let's run through a few test cases. Suppose that we have

other_sched = {use_time = 10; recovery_time = 10; first_use_time = 20}
jim_sched = {use_time = 12; recovery_time = 15; first_use_time = 0}

Running at t=5, Jim has the machine to himself, so he's going to take 12 + 15 seconds to do his workout (and thus the new t is 32). The other guy's workout start remains unchanged, since Jim is done with the machine at t=17.

utop # do_workout 5 jim_sched other_sched;;
- : int * schedule =
(32, {use_time = 1; recovery_time = 10; first_use_time = 20})

Running at t=15, Jim gets the machine and takes 12 + 15 seconds to do his workout (and thus the new t is 42). But the other guy's workout start has to be updated, since Jim is still working out at t=20, and isn't done until t=27. So the other guy's first_workout_time is now t=27.

utop # do_workout 15 jim_sched other_sched;;
- : int * schedule =
(42, {use_time = 1; recovery_time = 10; first_use_time = 27})

And lastly, running at t=25, the other guy is now working out, and Jim has to wait until t=30 to start working out (and thus the new t is 57). The other guy's workout start also has to be updated, since Jim is still working out at t=40. So the other guy's first_workout_time is now t=42.

utop # do_workout 25 jim_sched other_sched;;
- : int * schedule =
(57, {use_time = 10; recovery_time = 10; first_use_time = 42})

Defining The go Function

It's probably easier just to write the code. I am popping off the head of the remaining workouts, getting the schedules associated with that workout's index, and performing do_workout to get the new time and the new schedule. I then update the schedule, time, and remaining workouts.

let go jim_scheds {time=t; remaining=rs; scheds=other_scheds} =
    let r = List.hd rs in
    let (j, o) = (List.nth jim_scheds r, List.nth other_scheds r) in
    let (t2, o2) = do_workout t j o in
    {time=t2; remaining=List.tl rs; scheds=update r o2 other_scheds}

Total Time

We're going to do the following:

• Start with the initial frame.
• Execute go over and over again until we run out of workouts.
• Obtain t.
• Subtract the last recovery_time.

Thus

let total_time jim_scheds other_scheds =
    let initial = {time = 0; remaining = Seq.ints 0 |> Seq.take 10 |> Seq.cycle |> Seq.take 30 |> List.of_seq; scheds = other_scheds} in
    let final_frame = Seq.iterate (go jim_scheds) initial |> Seq.take_while (fun f -> List.is_empty f.remaining |> not) |> last in
    final_frame.time - (List.to_seq jim_scheds |> last |> fun s -> s.recovery_time)

Parsing

OCaml makes this pretty easy.

let chunk n xs =
    let rec aux acc ys = 
       if List.is_empty ys then List.rev acc else aux (List.take n ys :: acc) (List.drop n ys)
    in
    aux [] xs

let create_sched xs =
    match xs with
    | [x; y] -> {use_time = x; recovery_time = y; first_use_time = 0}
    | [x; y; z] -> {use_time = x; recovery_time = y; first_use_time = z}
    | _ -> failwith "create_sched: invalid parse"

let parse_jim line = String.split_on_char ' ' line |> List.map int_of_string |> chunk 2 |> List.map create_sched
let parse_other lines = List.map (String.split_on_char ' ' >> List.map int_of_string >> create_sched) lines

let parse_file lines =
    match lines with
    | x :: xs -> parse_jim x, parse_other xs

Main Function

I generally assume that I'm just taking from stdin and printing to stdout, which means that we turn stdin into a list of lines, run parse_file, and then run total_time on the resulting lists of schedules.

let () =
    input_lines Stdlib.stdin |> parse_file |> uncurry total_time

All Together, With Feeling

Running on the provided test case:

$ ocamlc blarg.ml -o blarg $ ./blarg <<< "5 5 3 3 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 2 1 8 3 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0" 100

Doing this in Python is left as an exercise for the reader. Personally, I would define my own Schedule and Frame classes. You can also use objects as extremely bare-bones record types.

This looks like a dynamic programming problem to me. Consider the idea of a frame containing the following things:

1. The current time t
2. A list of "counts" of remaining workouts, which starts as a big list of 3s.
3. The schedules of everyone else, since some of Jim's actions could change the schedule

And consider a function do_workout(frame, idx) that returns a new frame. We're going to

• decrement the count at that particular index in the frame
• advance t by however long it takes Jim to wait for the machine to open up, do his workout, and recover
• update the schedule if Jim's workout changes the other person's workout schedule

For the problem itself, set up a min-heap, ordered by t. We are going to

• pop the smallest element off of the heap
• check to see if all of the workouts are done. If so, return t - that's the quickest amount of time for Jim to do his workouts. You might need to check with the problem prompt to see if the very last workout's recovery time counts toward the total workout time, or if you need to discard it^([1]).
• Otherwise, perform do_workout on every non-zero index and add the resulting frames to the heap.

The natural result of this is that inefficient workouts (meaning that you've waited a long time) get put into the depths of the heap, while the most efficient scheduling (which keeps t low) gets popped off the heap more quickly.

The starting heap contains a single frame where t=0, the counts are a list of 3s, and the schedules are what is provided to you.

^[1] You can always track the recovery time as another field in the frame, and increment t by that recovery time after you've verified that Jim still has a workout to do. The initial frame will, of course, set that recovery time to 0.