The Longest River Jump

A frog needs to cross a river that is 10 feet wide.

There are 2 stones in the water she can jump on.

A few jumps are needed, but her only concern is the longest one.

This is obviously the most problematic, so she wishes to choose a path that makes this jump as small as possible.

The length of a jump between two stones of coordinates (x1,y1) and (x2,y2) is the Euclidian distance:

sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2))

The edge of the shore where the frog initially stands is at x=0 and runs along the y-axis (it is the y-axis).

This means that the minimal distance between the shore and the first stone the frog jumps on is the x-value of the location of that stone.

The edge of the opposite shore is at x=10 and runs also along the y-axis (i.e. the 2 shores are parallel to the y-axis).

The x-coordinates of the 2 stones are given in a list x [x1, x2] and the y-coordinates are given in a list y [y1,y2].

Clearly each path will have a jump that is the longest.

The question is then how to find the path where the longest jump is the smallest possible among all possible paths and to actually compute the length of its longest jump. This is the smallest longest jump the frog needs to make. We will round it to the nearest integer (just to make testing easier)?

For example imagine the 2 stones are both located at y=5, one at x=3 and the other at x=7 (i.e. [x1=3,x2=7], [y1=5,y2=5]).

An inexperient or playful frog might hop from (x=0,y=5) to the stone at (x2=7,y2=5) (a jump of length 7), then jump to the stone at (x1=3,y1=5) (a jump of length 4) and from there jump to the shore at (x=10, y=5) (another jump of length 7).

The longest jump in this case is 7 (2 jumps of 7).

But our frog is craftier. She first jumps from (x=0, y=5) to the stone at (x1=3,y1=5) (a jump of length 3), then jumps to the stone at (x2=7,y2=5) (a jump of length 4) and from there reaches the other shore with a jump of length 3 (to x=10,y=5).

The longest jump in this case is 4. This path is indeed the smallest longest jump for the given position of the two stones. The situation is illustrated bellow

Playful frog path in black (first 1, then 2 then 3 in red).
Shortest largest jump in green (1->2->3 in blue).

Or imagine the stones are at (x1=3,x2=6) and (y1=5,y2=2). The frog will first jump from (x=0,y=5) to the stone at (x1=3,y=5) (a jump of length 3), then to the stone at (x2=6,y2=2) (a jump of length sqrt(3*3 + 3*3)= sqrt(18)= 4, when rounded) and finally from there to (x=10,y=2) a jump of length 4.

The longest jump is therefore 4.

Since there are only 2 stones, the general strategy to find the smallest largest jump is simple:

If the starting shore is denoted by S, the stones by A and B and the destination shore by E, we have the following alternatives:

S→ A→ B→ E

S → B → A → E

S → A → E

S → B→ E

(S→A→A→E is the same as S→A→E and similarly S→B→B→E is the same as S→B→E)

We compute the largest jump for each of these paths and pick the one corresponding to the smallest of these largest jumps. Note that the best path is not always one that goes through the 2 stones, i.e. it might be the case that the frog only has to jump on one stone instead of two.

For example imagine the two stones are at x=[3,3] and y=[3,5]. Then the best path would be for the frog to jump to either one of the stones first and then jump straight to the shore E, instead of jumping to the second stone and then to the shore E.

The last example also shows that there might be more than one best path. There the frog could pick either stone to jump first and both paths will come up with 7 as the longest jump.

That is because we are supposing that the frog is as close to the first as to the second stone, i.e. we neglect any jump she might have to do while on the shore  to get in front of one of the stones.

This reasoning generalizes to the case where there are 3 stones A, B and C. The possible paths would now be

S→ A→ B→C→ E
S → A → C →B → E
S→ B→ A→C→ E
S → B → C →A →E
S→ C→ A→B→ E
S → C → B →A → E
S→ A→ B→ E
S → B → A → E
S→ A→ C→ E
S → C → A → E
S→ B→ C→ E
S → C → B → E
S → A → E
S → B→ E
S → C→ E

The following code solves the 2 stone case.
Note that all paths with the same smallest largest jump are shown.
In particular notice the last case. The two stones are located at the same x coordinate. The frog has three options all leading to a smallest largest jump of 7:
It can jump on any one stone, then jump to the far shore.
Or it can jump to one stone, then to the other, then from there to the shore.
Of course this last case involves three jumps instead of just two but since our problem does not require the number of jumps to be a minimum this is ok even if not fully optimal.
Notice also the first case. The smallest longest path of length 4 involves going from the shore to (3, 5) then to (7, 5) then to the far shore. The reverse (7, 5) then to (3, 5) does not lead to a best path because the longest jump is 7 instead of 4.

And the following code solves the case for the 3 stone case.
The code is a generalization of the 2 stone case.
To enumerate all possible paths we first consider all paths involving one stone only (one for loop), then those involving two stones (two for loops) and finally those using all the 3 stones (three for loops).

We might ask whether there is a more elegant way to solve the problem for any number of stones without keeping nesting for loops.
If we use regular python, instead of skulpt, we can use the itertools module and its method permutations to solve the n=3 case with a variation of the following code

def longestJump(x, y):
    best_jump = 10 # infinity
    best_path = ()
   
    for i, j, k in itertools.permutations(range(3)):           
        jump0 = x[i]                                      # shore to i
        jump1 = sqrt((x[i]-x[j])**2 + (y[i]-y[j])**2)     # i to j
        jump2 = sqrt((x[j]-x[k])**2 + (y[i]-y[j])**2)     # j to k
        jump3 = 10 - x[k]                                 # k to far shore
        longest = max(jump0, jump1, jump2, jump3)
        if longest < best_jump:
            best_jump = longest
            best_path = (i, j, k)
    return best_jump, best_path

This code still assumes n=3 and in particular forces us to explicitly enumerate all the jumps (to be clear, for 3 stones we also need to generate the permutations of 2 stones and consider also the 1 stone case, just like we did when we used several for loops above). It can be easily adapted to n=2,4,5 but we will have to change it for each of those cases.

General search code to handle any number of stones can be written if we think of the problem as searching for the best paths in a graph. Each stone is a vertex in this graph. The initial and the final shores are also added as vertices to the graph. Lets say we number the initial shore as vertex 0, the n stones as vertices 1 through n and the end shore as vertex n+1 (so the graph has n+2 vertices). Noticing that the frog never jumps back once it reaches the end shore and it never jumps from a stone to the initial shore nor can it jump from one shore to the other (i.e. it has to jump to at least one stone), we can generate the graph for the problem with the following code

  def GenerateGraph(self,num_stones):       
       # each stone plus the initial starting and ending points is
       # a vertex. The starting point is index 0 and the 
       # ending point is at index num_stones +1
       n = self.num_stones + 1
       for i in range(0, n+1):
           self.graph[i]=list()
       
       for i in range(1, n):
           # from the initial starting point we can
           # reach every stone
           self.graph[0].append(i)
           for j in range(1, n):
               if i == j:
                  continue
               # we can go from any stone to any other stone 
               self.graph[i].append(j)
           # we can go from any stone to the far shore     
           self.graph[i].append(j+1)

This generates the graph as a dictionary of adjacency lists (lists with the vertices that can be reached from each vertex that is a key of the dictionary). For example for 3 stones it is:
{0: [1, 2, 3], 1: [2, 3, 4], 2: [1, 3, 4], 3: [1, 2, 4], 4: []}
This graph is independent of the position of the stones, so for a given number of stones it can be generated just once.
With the graph on hand, we can find all possible paths from one shore (vertex 0) to the other (vertex n+1) using breadth first search. Paths from the shore to any one stone are added to a queue and popped one by one. Each time we pop one of these paths we look at all the vertices connected to the last vertex on the path. If it is not the terminal vertex (n+1) we added it to the path and then added it to the queue. If it is the terminal vertex we added it to a list of all the paths from 0 to n+1.

For example for the 3 stones case, starting at one shore, we add vertex 0 to a queue. Then we go through all the vertices that can be reached from 0 (1,2,3) and add the paths 0--> 1, 0-->2, 0-->3 to the queue as lists.
We then pop path 0-->1 from the queue, go through all the vertices that can be reached from 1 and add the resulting paths to the queue: 0-->1-->2, 0-->1-->3. Paths that go from 0 to 4 (shore to shore) like 0-->1-->4 are added to a list with all possible paths 0 to 4 paths. Next we would pop path 0-->2 and repeat the process. The paths 0-->2-->1, 0-->2-->3 would be added to the queue and 0-->2-->4 would be added to the list of all paths fro 0 to 4. And so on. We end up with the following paths from 0 to 4:

[

# one stone paths

[0, 1, 4], [0, 2, 4], [0, 3, 4], 

# 2 stone paths

[0, 1, 2, 4], [0, 1, 3, 4], [0, 2, 1, 4], [0, 2, 3, 4], [0, 3, 1, 4], [0, 3, 2, 4], 

# 3 stone paths

[0, 1, 2, 3, 4], [0, 1, 3, 2, 4], [0, 2, 1, 3, 4], [0, 2, 3, 1, 4], [0, 3, 1, 2, 4], [0, 3, 2, 1, 4]

]

Again notice how these paths are independent of the position of the 3 stones and therefore can be generated just once for a given number of stones.

The final step is to search through all these paths to get all those where the longest jump is the smallest. The easiest way is to loop through all the paths and for each compute the longest jump length. Store the paths in a dictionary where the key is the longest jump. Then the best paths are the ones with the lowest key.

The complete code (including a python implementation of a Queue) is below. Tests for 2,3,4, and 5 stones are given. You can try other cases (what is the highest number of stones the code can handle, i.e. before the browser becomes unresponsive?). 

Intersection of two line segments in the plane

We are given two line segments (in the plane) through their two end point (x,y) coordinates. To simplify the problem lets assume the two segments are either horizontal or vertical and their endpoint coordinates are integers.

The two segments might not intersect at all, they might intersect at a single point or they might have a whole segment in common. The following figure shows those three possibilities. The last pair of segments (red and cyan) overlap in a segment, the pair before the red-cyan pair intersects at a single point and the first three pairs of segments do not intersect. Notice that the overlap segment will either be horizontal or vertical since the two segments are both horizontal or both vertical when a segment overlap occurs.

How would we write a simple python program that returns a string 'NO INTERSECTION', 'POINT INTERSECTION' or 'SEGMENT INTERSECTION' for each of the three possible cases outlined above and returns the intersection segment?

 Lets suppose the endpoint coordinates of the first segment are given as a python list s1:[x1 y1 x2 y2] and similarly for the second segment s2:[x1 y1 x2 y2].

 It is tempting to use a few if statements to check for the different configurations of the two line segments but boundary cases make such an approach hard to get right: Imagine one of the line segments is just a single point in the other segment. In this case we want to return "POINT INTERSECTION" not "SEGMENT INTERSECTION". Yet another case is if the two line segments are both points.

 An easier and better solution is to write code that naturally handles all possible cases. We can first easily determine the overlapping region of the two line segments, and then see if it is a point, a segment, or if there is no overlap.

The x coordinate of the leftmost endpoint of the intersection segment will be

  left = max(min(s1.x1,s1.x2),min(s2.x1,s2.x2)).

That is we search among the endpoints of s1 and s2 for the the one with the largest left coordinate  (the min gets the endpoint in each segment that is the leftmost).

Similarly the x coordinate of the rightmost endpoint of the intersection segment will be

right = min(max(s1.x1,s1.x2),max(s2.x1,s2.x2)).

That is we search among the endpoints of s1 and s2 for the one with the smallest right coordinate (the max gets the endpoint in each segment that is the rightmost).

We can extend this logic to find the y coordinates of the endpoints of the intersection segment:

bottom = max(min(s1.y1,s1.y2),min(s2.y1,s2.y2))

top = min(max(s1.y1,s1.y2),max(s2.y1,s2.y2))

With the coordinates of the segment endpoints we can promptly find out if there is intersection or not. For example if left > right or bottom>top there is no intersection whatsoever. If left=right and bottom=top the 2 segments meet at a single point. Otherwise they overlap in a segment.


Here it is this solution (you can change the code and try different approaches: it will be executed roughly every minute, and you can change this interval by editing the value 60000 to the value most convenient to you)

And a more concise way of coding it up is