Programiranje 1

Naloga vsebuje teste. Naloga je rešena samo, če prestane vse teste. Poglej navodila za poganjanje testov.

Obvezna naloga

1. Napiši funkcijo podatek(kljuc, podatki), ki dobi neko vrednost kljuc in nek seznam parov. Med njimi mora poiskati tisti, par, pri katerem je prva vrednost enaka podanemu ključu; funkcija mora vrniti drugo vrednost.

   • Klic podatek("Berta", [("Ana", 156), ("Berta", 167), ("Cilka", 160)]) vrne 167.
   • Klic podatek(42, [(42, "6 * 8"), (33, "11 * 3")]) vrne "6 * 8".
   • Klic podatek("Koper", [('Piran', (0, 0)), ('Koper', (8, 2)), ('Žiri', (39, 60))]) vrne (8, 2).
   • Klic podatek("Žiri", [("Piran", 23), ("Koper", 4), ("Žiri", 481)]) vrne 481.

Če ključa ne najde, (npr. v klicu podatek("Žiri", [("Piran", 23), ("Koper", 4)])) mora vrniti None.

2. Napiši funkcijo razdalja(t1, t2), ki prejme dve terki, ki predstavljata koordinati točk na ravnini. Vrniti mora evklidsko razdaljo med točkama. Klic razdalja((0, 0), (3, 4)) mora vrniti 5.

3. Napiši funkcijo oddaljenost(kraj1, kraj2, koordinate), ki prejme imeni dveh krajev in seznam, ki vsebuje koordinate krajev v takšni obliki, kot ga vidiš v tretjem primeru pri prvi funkciji. Funkcija mora vrniti evklidsko razdaljo med krajema. (Dober nasvet: funkcija naj kliče prejšnji funkciji.) Predpostaviti smeš, da se koordinate obeh krajev nahajo v seznamu.

4. Napiši funkcijo visina(kraj1, kraj2, visine), ki prejme imeni dveh krajev in višine krajev v seznamu, kot ga vidiš v četrtem primeru pri prvi funkciji. Funkcija naj vrne višinsko razliko (vzpon) od prvega kraja do drugega; če je prvi višji, funkcija vrne negativno vrednost. Spet smeš predpostaviti, da sta višini obeh krajev znani.

5. Napiši funkcijo cas(s, h), ki vrne čas, ki ga porabi nek kolesar, da prevozi pot dolžine s (v kilometrih), ki se dvigne za h (v metrih; h je lahko tudi negativen, če gre za spust). Čas izračunamo tako:

   • kolesar v osnovi porabi 2,4 minute za kilometer razdalje.
   • Če gre za dvig, se čas poveča še za 1 / 12 minute za vsak meter višine;
   • če gre za spust, pa se čas zmanjša za 1 / 250 minute za vsak meter spusta.

   Primera:

   • Klic cas(2, 300) vrne 29,8: za 2 km porabi 2 * 2,4 = 4,8 minut, poleg tega pa porabi 1 / 12 * 300 = 25 minut zaradi 300 m dviga.
   • Klic cas(10, -100) vrne 23,6: za 10 km porabi 10 * 2,4 = 24 minut, vendar se to zmanjša za 100 / 250 = 0.4 minute zaradi spuščanja.

(Posebej drugi primer kaže, da vsaka podobnost te formule z resničnimi dogodki ni zgolj naključna temveč tudi ne prav zelo verjetna.)

6. Napiši funkcijo cas_med(kraj1, kraj2, koordinate, visine), ki vrne čas, ki ga bo kolesar potreboval za vožnjo od prvega do drugega kraja. Pomen argumentov in formule so takšne kot v prejšnjih nalogah. (Uporabljaj funkcije, ki jih že imaš!)

7. Napiši funkcijo skupni_cas(kraji, koordinate, visine), ki prejme seznam krajev, skozi katere bo šel kolesar, in vrne skupni čas, ki ga bo porabil za to pot.

Dodatna naloga

Kolesar bi rad čimbolj skrajšal čas potovanja. Izpustiti sme en kraj - lahko prvega, lahko zadnjega, lahko kateregakoli vmes.

Napiši funkcijo skrajsaj(kraji, koordinate, visine), ki vrne seznam brez tega kraja. Klic skrajsaj(["Piran", "Ljubljana", "Koper"], koordinate, visine) vrne ["Piran", "Koper"]. Enak rezultat vrneta tudi klica skrajsaj(["Ljubljana", "Piran", "Koper"], koordinate, visine) in skrajsaj(["Piran", "Koper", "Ljubljana"], koordinate, visine).

Dodatni izziv

Recimo, da bi v vseh krajih v seznamu koordinate zabili visok jambor in nato okrog Slovenije napeli zelo dolgo elastiko. Ta bi se dotikala le nekaterih jamborjev - tistih, "na robu". Ljubljane gotovo ne, saj je preveč v sredini, gotovo pa bi se dotikala Murske Sobote, ki štrli ven.

Napiši funkcijo, ki prejme seznam koordinat in vrne seznam krajev (po vrsti, začenši od poljubnega kraja), ki bi se jih elastika dotikala.

This task includes tests. Your solution will be accepted as correct only if it passes them. See instructions for running tests.

Mandatory Task

1. Implement a function podatek(kljuc, podatki), which receives a certain value key and a list of pairs (podatki). The function must find a pair in which the first value equals the key, and it must return the second value of the pair.

   • Call podatek("Berta", [("Ana", 156), ("Berta", 167), ("Cilka", 160)]) returns 167.
   • Call podatek(42, [(42, "6 * 8"), (33, "11 * 3")]) returns "6 * 8".
   • Call podatek("Koper", [('Piran', (0, 0)), ('Koper', (8, 2)), ('Žiri', (39, 60))]) returns (8, 2).
   • Call podatek("Žiri", [("Piran", 23), ("Koper", 4), ("Žiri", 481)]) return 481.

If the key is not found (as in podatek("Žiri", [("Piran", 23), ("Koper", 4)])) the function must return None.

2. Implement a function razdalja(t1, t2), which gets two tuples that represent coordinates of two points in a plain. It must return the Euclidean distance between them. The call razdalja((0, 0), (3, 4)) must return 5.

3. Implement a function oddaljenost(kraj1, kraj2, koordinate), which gets names of two places and a list with names and coordinates in the same form as in the third example for the first function. The function must return the Euclidean distance between the two places. (A good advice: the function should call the first two functions.)

   You may assume that the list includes both places.

4. Implement a function visina(kraj1, kraj2, visine), which gets names of two places and list of heights above sea level as in the fourth example for the first function. The function must return the ascent from the first place to the second; the ascent is of course negative if the second place is lower than the first. You may again assume that both places appear in the list.

5. Implement a function cas(s, h), which returns time needed by a cylist for a path of length s kilometers with h meters of ascent (h can also be negative). The time is computed using the following formulae:

   • the cyclist needs, basically, 2.4 minutes per kilometer.
   • In case of ascent, the time is increased by 1 / 12 minutes per meter of ascent;
   • in case of descent, the basic time is reduced by 1 / 250 minute per meter of descent.

   Examples:

   • Call cas(2, 300) returns 29.8: for 2 km she needs 2 * 2.4 = 4.8 minutes, which is increased by 1 / 12 * 300 = 25 minutes because of 300 m ascent.
   • Call cas(10, -100) returns 23.6: for 10 km she needs 10 * 2.4 = 24 minutes, which is decreased by 100 / 250 = 0,4 minutes because of descent.

(The second example clearly shows that any similarity of this formulae with real times is purely coincidental and not very probable.)

6. Implement a function cas_med(kraj1, kraj2, koordinate, visine), that return time that the cyclist will need from the first to the second place. The meaning of arguments and the formulae are the same as before. (And so is the advice: use the functions that you already have.)

7. Implement a function skupni_cas(kraji, koordinate, visine), which gets a list of places that the cyclist will traverse, and returns the total time needed for the trip.

Extra tasks

The cyclist would like to decrease the time needed for the trip. He may skip one single place -- the first, the last or any in between.

Implement a function skrajsaj(kraji, koordinate, visine), which returns a list without that place. The order of other places must stay the same. Call skrajsaj(["Piran", "Ljubljana", "Koper"], koordinate, visine) returns ["Piran", "Koper"] (Piran and Koper are nearby towns on the seaside, and Ljubljana is 100 km away). The same result is returned by skrajsaj(["Ljubljana", "Piran", "Koper"], koordinate, visine) and skrajsaj(["Piran", "Koper", "Ljubljana"], koordinate, visine).

Extra challenge

(Solve this for your amusement; it does not affect the grade.)

Assume a large mast is set at each place in the list koordinate. Then we stretch an elastic rope around Slovenia. This rope surely does not touch Ljubljana, which is a rather central town, but it touches Murska Sobota, which is in the corner, not far from Austria and Hungary.

Write a function that gets a list of coordinates and returns a list of towns (in order, but starting from any) that the rope will touch.