Some new obstacles appeared on the cycling path near the faculty.

Cute little creatures

We asked the Department for economy and motorized traffic at the city of Ljubljana whether this is not a bit too much, and received the following "explanation":

---

Safety of cyclists is our priority. (That is, just below the width of roads and the number of parking places.) The purpose of these obstacles is, however, not only the safety of cyclists but also of squirrels.

These cute little creatures need to cross the cycling path. They fear walking on the ground, so they jump from one obstacle to another.

• After reaching one obstacle, they run all the way to its right-hand side.
• Then they look for the next obstacle they can jump tp. Squirrels always jump to the right - never somewhere "upwards" or "downwards" from the current place or even back to the left.
• The length of their jump is at most one unit. This includes jumping between corners. Possible jumps are shown in the picture.
• To cross the path, they must reach an obstacle that either touches the right border, or ends at most one unit away (so they can jump across).

We in the Department of economy and motorized traffic at the City of Ljubljana care about tolerant coexistence of all participants in traffic, including squirrels.

 

---

Mandatory task

Obstacles are this time given in simple list of triplets (y, x0, x1).

To simplify the arguments of functions, the list will not be given as an argument, but rather as a global list ovire.

Write the following functions:

• mozen_skok(x, y, ovira) returns True if a squirrel can jump from field (x, y) to the obstacle ovira, given as a triplet (x0, x1, y). Otherwise, it returns False. (This function does not need to (and should not) use the list ovire.)

  While short, this function can be a bit nasty to write. Tests attempt to thouroughly check it, but they may overlook some mistakes that will resurface in later functions.

• mozne_ovire(x, y) gets some coordinates and returns a list of obstacles to which the squirrel can jump from there. (Tests may also use coordinates that are not on any obstacle in the list. Don't worry about that.)

• obstaja_pot(ovira) returns True if a squirrel that is currently on the given obstacle (given as triplet) can reach the other side, and False if not.

Recommendation: the last function is easier to implement as recursive function, while the first two should better be "normal".

Additional task

Squirrel often has several paths to choose between.

Write a function stevilo_poti(ovira) that returns the number of possible ways to reach the other side for a squirrel that is currently on the given obstacle. That is, the function must return number of ways to reach an obstacle that either touches the right border or is one unit away from it. If the squirrel can't cross the path from that place, the function must return zero.

There are a few cases in the picture. Note that the blue path covers four different ways although two of them end up at the same obstacle.

The brown path covers 16 different ways:

• (16, 17) can be reach in 4 ways (going straight or taking the first upper path, the second or both).
• (15, 16) can also be reached in four ways; each can be continued in two ways on the blue path, which gives a total of 8 ways.
• Finally, the squirrel can immediately join the blue path, which can then continue in 4 different ways.

This description only shows how to interpret the task. The actual function will not require any multiplication, just additions. If programmed properly, it should be quite similar to what you've done in the mandatory task.