Planning a Ride

The city of Ljubljana published a video about cycling in Ljubljana. In short: they expose typical habits of cyclists in Ljubljana, which are, in their view, wild descents down the staircases, slaloms between pedestrians and so forth. Your professor's basic mode of transport is cycling, and he rides an unfortunate third of his annual distance in Ljubljana. He therefore asks you to solve this task in order to help him planning his trips.

The map shows 21 crossroads in Ljubljana (following the opinion of the city's experts for GDPR, names have been replaced with letters to protect their privacy). Connections require different skills: for instance, going from B to C requires slalom between heaps of Bolt scooters and between flower pots.

The entire list of skills in this task is as follows (give in Slovenian, because functions work with these exact texts).

stopnice: Descent down a staircase
pešci: Wild ride between pedestrians
lonci: Slalom between flower pots
bolt: Slalom between scooters
robnik: Jumping onto the curb
gravel: Riding on loose gravel
trava: Plowing through park lawns
avtocesta: Driving on the highway
crepinje: Riding on shattered glass
rodeo: Riding on the bike path through Črnuče

The map on figure uses one-letter acronyms, while the task defines the map as follows:

A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, R, S, T, U, V = "ABCDEFGHIJKLMNOPRSTUV"

zemljevid = {
    (A, B): "gravel trava",
    (A, V): "pešci lonci",
    (B, C): "bolt lonci",
    (B, V): "",
    (C, R): "stopnice pešci lonci",
    (D, F): "stopnice pešci",
    (D, R): "pešci",
    (E, I): "trava lonci",
    (F, G): "trava črepinje",
    (G, H): "črepinje pešci",
    (G, I): "avtocesta",
    (H, J): "robnik bolt",
    (I, M): "avtocesta",
    (I, P): "gravel",
    (I, R): "stopnice robnik",
    (J, K): "",
    (J, L): "gravel bolt",
    (K, M): "stopnice bolt",
    (L, M): "robnik pešci",
    (M, N): "rodeo",
    (N, P): "gravel",
    (O, P): "gravel",
    (P, S): "",
    (R, U): "trava pešci",
    (R, V): "pešci lonci",
    (S, T): "robnik trava",
    (T, U): "gravel trava",
    (U, V): "robnik lonci trava"
}

Keys are pairs of connected crossroads, and the corresponding values are strings containing skills, separated by spaces. We see that the value for key (B, C) equals "bolt lonci", which is short for Slalom med odvrženimi skiroji in Slalom med cvetličnimi lonci.

All connections go in both directions (MOL believes that cyclist don't care about which way they ride and on which side of the road). If there's a connection between B and C, there's also a connection between C and B, and it requires the same skills.

Mandatory task

Write the following functions.

Function dvosmerni_zemljevid(zemljevi) gets a map (a dictionary like the one above) and returns a new map, this differs from the given in that
- all connections also appear in the opposite order (if the original map contains a key (B, C), the resulting map also includes (C, B));
- dictionary values are no longer strings but sets of skills. Call
```
dvosmerni_zemljevid({(A, B): "robnik bolt",
                     (A, C): "bolt rodeo pešci",
                     (C, D): ""}
```
returns
```
{('A', 'B'): {'robnik', 'bolt'},
 ('B', 'A'): {'robnik', 'bolt'},
 ('A', 'C'): {'bolt', 'rodeo', 'pešci'},
 ('C', 'A'): {'bolt', 'rodeo', 'pešci'},
 ('C', 'D'): set(),
 ('D', 'C'): set()}
```
I highly recommend using this function in some of the functions that follow.
mozna_pot(pot, zemljevid) gets a path (pot) formed as string of letters that designate crossroads, and a map as dictionary. It returns True, if such path is possible (that is: there are connections between all pairs of consecutive crossroads), and False if not.

Call mozna_pot("ABCRVRIEIPNM", zemljevid) returns True, while call mozna_pot("ABCRVREPNM", zemljevid) return False, because there is no connection between R and E.
potrebne_vescine(pot, zemljevid) get the same arguments, but the path will always be possible. The function must return the required set of skills to ride the given path.

Call potrebne_vescine("RIPSTUT", zemljevid) returns {'robnik', 'stopnice', 'makadam', 'trava'} because this are the skills needed to ride across RIPSTUT (in the map, they are marked as sr, g, rt and gt).
nepotrebne_vescine(pot, zemljevid, vescine) gets the same arguments and a list of particular cyclist's skills. The function must return a subset of skills that are unnecessary for this path.

Call nepotrebne_vescine("IPNMNPO", zemljevid, {'stopnice', 'makadam', 'bolt', 'rodeo'}) returns {'stopnice', 'bolt'}, because these two skills are not needed to ride "IPNMNPO".
Function tocke_vescine(zemljevid, vescina) returns a string containing the locations for which there exist at least one connection that requires the given skill vescina. Each letter must appear only once. Letters must be sorted alphabetically.

Call tocke_vescin(zemljevid, "avtocesta") returns "GIM", because avtocesta appears on connections leading from/to points G, I and M.

Call tocke_vescine(zemljevid, "rodeo") returns "MN", because rodeo cycling path (the one and the only original) is in Črnuče.

Extra task

This week's extra is not much more difficult than the mandatory task.

Write a function koncna_tocka(pot, zemljevid, vescine), which gets the same arguments as nepotrebne_vescine. It must return two things: the point at which the cyclist will get stuck because (s)he lacks some skill(s), and a set of lacking skills to continue (at that point - do not look further!)

If he manages the whole trip, the function naturally returns the last point and an empty set.

Call koncna_tocka("ABCRVB", zemljevid, {"makadam", "trava"} returns ("B", {'lonci', 'bolt'}). A cyclist attempting to ride "ABCRVB" and having the listed skills would get stuck at B because he can't slalom between flower pots and between scooters. The planned path would later require some additional skills, but the function must stop here.

Course Activities

Recent Courses

Planning a Ride

Mandatory task

Extra task