Programiranje 1

This task is graded so you mustn't ma naloga se ocenjuje, zato je ne smete izpustiti. You must solve, at minimum tasks for grade 6. To get a certain grade, you must also solve tasks for lower grades. As usual, submit your work in a single file.

---

Department for economy and motorized traffic at the City of Ljubljana decided to popularize cycling through a system of award points for use of various skills. Riding on grass is worth three points, riding among pedestrians is four points, riding a highway gives you ten points and so forth. A cyclist who collects a certain number of points gets a category C driver license (+ permission for parking on sidewalks).

Points (in Slovenian, because that's what you have in tests):

• črepinje: 1,
• robnik: 1,
• lonci: 1,
• gravel: 2,
• bolt: 2,
• rodeo: 2,
• trava: 3,
• pešci: 4,
• stopnice: 6,
• avtocesta: 10.

A few changes with respect to task Načrtovanje poti:

• Skills are the same as the last time, but we only use shorter forms.
• Dictionary keys are the same, but include both directions, so you don't neet to call dvosmerni_zemljevid.
• Dictionary values are sets of short names for skills, for instance {"pešci", "avtocesta"}. (The possibility of having to cycle between pedestrians on a highway may sound ridiculous, but half a year ago the city decided the sidewalks can also serve as parking space, so redirecting traffic to sidewalks would not be a big surprise at some point in the future.)

While solving the task, you are going to be grateful for the following picture.

Grade 6

• Write a function vrednost_povezave(povezava, zemljevid) that returns the number of award points that a cyclist gets for riding the given connection. Connection is a pair of crossroad names, like ("A", "B"), that is, the same form as used for dictionary keys. The number of award points is the sum of points for required skills. If needed skills are {"pešci", "avtocesta", "bolt"}, the function must return 16 (that is, 4 + 10 + 2).

• Write a function najboljsa_povezava(zemljevid) the returns the most rewarding connection in the map, that is, the one that gives us most points. If there are more connections with the same number of points, return any of them. (In fact, there will always be two, because all connections are bi-directional.)

• Write a function vrednost_poti(pot, zemljevid) that returns the number of award points that a cyclist gets for taking a certain path. The function must return the sum of points for all connections in the path. If the same skill is needed on multiple connections, it is counted each time. The path is given in the same form as usual. You can assume that the path is possible, i.e. that all connections exist.

Grade 7

• Write a function najbolj_uporabna(pot, zemljevid) that returns the skill that appears on most connections on the given path. In case there are multiple such connections, return any. In case the path requires no skills, return None.

Grade 8

• Write a function mozna_pot(pot, zemljevid, vescine) that returns True if the given set of skills is sufficient to pass the given path, where each skill may be used at most once. If, for instance, the path requires two rides on staircases, the cyclist stops at their second occurence. (Assuming she has that skill at all. If not, she stops at the first.) It may also happen that some required connections do not exist at all. In the case that cyclist can't ride this path due to missing skills, duplicated skills on path, or missing connections, return False.

• The above function is of course pointless: why wouldn't a cyclist use the same skill twice? Write a function koncna_tocka(pot, zemljevid, vescine) that returns the point at which she stops, or the end point if she can pass the entire path. For this function, skills are given as a set of pairs: the first element is a name of the skill, and the second is the number of times she can use that skill. If skills are {("pešci", 3), ("trava", 1), ("črepinje", 2)} the cyclist can ride among pedestrians for three times, across the grass once, and over broken glass twice. If she encounters a certain path of broken glass, she stops. Also take into account that some connections may not exist at all.

• The above function is still pointless: why limiting the number of uses of a certain skill at all? One never gets tired of puncturing tires on broken glass, does she? Write a function do_nagrade(pot, zemljevid, meja) that returns the point that the cyclist reaches before the total number of award points exceeds the threshold (meja) at which the city mayor would award him the abovementioned drivers license.

  If the path cannot be ridden due to a missing connection, the function returns the point at which the cyclist is forced to stop.

  If the cyclist rides the entire path without exceeding the threshold, return the last point.

Grade 9

• Rewrite functions for grade 6 using a single list/dict/set comprehension. Functions can only have a return statement. (If you used a dictionary within vrednost_povezave move it outside the function.)

• Write a function naslednje_tocke(tocke, zemljevid, vescine) that gets a set of points, a map and a list of skills. It must return a set of points that include the given points and all points that are directly reachable from (i.e. directly connected to) these points, with connections that do not require any skills that the cyclist does not possess.

  Call naslednje_tocke({V, F}, zemljevid, {"pešci", "stopnice", "lonci", "rodeo"}) returns {V, A, B, R, F, D}, because a cyclist with the given skill can move (in a single step) (from V) to A, B, R and (from F) to D. She can't go from V to, say U, because she doesn't handle "robniki" and "trava".

  This function should also be written in a single line naslednje_tocke because there's no reason for it to be any longer.

Grade 10

• Write a function dosegljive(tocka, zemljevid, vescine) that returns a set of points reachable - in any number of steps - from the single given point tocka (e.g. "V") with a given set of skills.

Hint: Use the function from grade 9.

This is not difficult at all. A solution without any generators and fancy stuff takes some five lines of code.

Extra challenges

Grade 11

Write a function dosegljive_n(tocka, zemljevid, meja) that returns a set of points reachable from tocka without exceeding the given threshold.

(Učilnica will show that you received a grade of 11, but this is only for kudos. At actual grading it will count as 10.)

Grade 12

Cyclist is at a given point and doesn't have any skills. If a golden fish grants him three wishes, which skills must he choose to cover as many points as possible?

Write a function naj_vescine(tocka, zemljevid, zelje) that gets a starting point, a map and a number of wishes (not necessarily three). The function must return a pair: the optimal skill set and the number of points that can be visited by such set. In case there are multiple such sets, return any.

Call naj_vescine("A", zemljevid, 2) returns ({"pešci", "lonci"}, 5) because these two skills allow us to reach five points (A, V, B, R, D) from A. No set of two skills allows us to cover more.

Consider that a set of skills may be very very large. Don't just check all combinations of three skills.

Help: if you need to use a set as a dictionary key, or construct a set of sets, use frozenset. It's list set, but immutable. If a and b are sets, you can also write frozenset(a | b), which gives you a frozen set that can be used as for keys or stored in a set.