Valid 1D Paths

type path = int * (bool * int) list

A path represents a sequence of integers from a given starting point, where each element is a direction (true for right, false for left) together with a distance. For example, the path (0, [(false, 1);(true, 2);(true, 3);(false, 1)]) represents the sequence

\[ 0 \longrightarrow (-1) \longrightarrow 1 \longrightarrow 4 \longrightarrow 3 \]

It's possible for the length-part of a path to be 0 or negative, i.e., (false, 0) stays in place and (false, -1) moves right by 1.

We think of a path as being traced out by a point mass on \(\mathbb R\) where, by time step \(i + 1\), the point mass travels the distance and direction given by the path at index \(i\). In between each time step, the point mass travels at a constant velocity. Note that this means the point mass will travel different velocities between each time step, depending on how far it has to travel.

Two paths are valid if their point masses never "phasing through each other" during the tracing of each path. For example, the paths

\[ 0 \longrightarrow 3 \longrightarrow -2 \]

and

\[ 5 \longrightarrow 2 \longrightarrow -5 \]

are not valid because their point masses need to phase through each other to get to the correct positions after 1 time step, whereas the paths

\[ 0 \longrightarrow 6 \longrightarrow -6 \]

and

\[ 5 \longrightarrow 7 \longrightarrow -5 \]

are valid because, even though they cover a lot of the same parts of \(\mathbb{R}\), the point masses never occupy the same position at the same time. If one path is longer than the other, the point mass of the shorter path is treated as being stationary until the other path finishes. For example,

\[ 0 \longrightarrow 6 \]

and

\[ 5 \longrightarrow 7 \longrightarrow -5 \]

are not valid because in order to get from 7 to -5, the second point mass has to travel through 6, where the first point mass remains stationary.

Implement the function

val is_valid : path -> path -> bool

so that is_valid p1 p2 is true if and only if p1 and p2 are valid.

Hint: Think about the plots of the point mass positions against time. What does the constant velocity mean about those plots? What do the plots look like when the point masses "phase through" each other?

Challenge worth nothing: Implement this function so that it takes a list of paths instead of just two paths.

let _ = assert (is_valid (0, []) (10, []))

let p1 = (0, [(true, 3); (false, 5)])
let p2 = (5, [(false, 3); (false, 7)])
let _ = assert (not (is_valid p1 p2))

let p3 = (0, [(true, 6); (false, 12)])
let p4 = (5, [(true, 2); (false, 12)])
let _ = assert (is_valid p3 p4)

let p5 = (0, [(true, 6)])
let _ = assert (not (is_valid p5 p4))