assignment_2.md

Άσκηση 1

Η χρήση list comprehension είναι υποχρεωτική

Ποιο είναι το άθροισμα της τετραγωνικής ρίζας όλων των αριθμών από το 1 μέχρι το 3000 που διαιρούνται με το 3 αλλά όχι με το 6;

Η τετραγωνική ρίζα υπολογίζεται ως εξής:

import math
math.sqrt(16)

Άσκηση 2

Η χρήση list comprehension είναι προτεινόμενη

Όλα τα ζευγάρια κ,λ θετικών ακεραίων που είναι μικρότεροι ή ίσοι με το 10 όπου το λ διαιρεί ακριβώς το κ είναι:

(4, 2), (6, 2), (6, 3), (8, 2), (8, 4), (9, 3), (10, 2), (10, 5)

Το άθροισμα των διαφορών αυτώ των ζευγαριών είναι:

(4 - 2) + (6 - 2) + (6 - 3) + (8 - 2) + (8 - 4) + (9 - 3) + (10 - 2) + (10 - 5) = 38

Ποιο είναι το αντίστοιχο άθροισμα διαφορών αν πάρουμε όλα τα ζευγάρια κ,λ που είναι μικρότεροι η ίσοι με το 1000;

Άσκηση 3

Φτιάξτε μία συνάρτηση με το όνομα f η οποία να επιστρέφει μία συνάρτηση η οποία να επιτρέφει μία συνάρτηση η οποία να επιστρέφει μία λίστα της οποίας το 2ο στοιχείο να είναι μία συνάρτηση η οποία να επιστρέφει το string 'mitsos'. Θα πρέπει δηλαδή να μπορώ να κάνω:

f()()()[1]()

#Αυτό πρέπει να Τυπώνει: 'Μήτσος'

Άσκηση 4

Φτιάξτε μία συνάρτηση με τον όνομα f η οποία να επιστρέφει μία λίστα με 10 στοιχεία.

Το πρώτο στοιχείο της λίστας θα είναι μία συνάρτηση η οποία θα παίρνει σαν όρισμα έναν αριθμό και θα επιστρέφει το άθροισμά του με το 1.

Το δεύτερο στοιχείο της λίστας θα είναι μία συνάρτηση η οποία θα παίρνει σαν όρισμα έναν αριθμό και θα επιστρέφει το άθροισμά του με το 2

κ.ο.κ.

Το 10ο στοιχείο της λίστας θα είναι μία συνάρτηση η οποία θα παίρνει σαν όρισμα έναν αριθμό και θα επιστρέφει το άθροισμά του με το 10.

Θα πρέπει δηλαδή να μπορώ να γράψω:

f()[5](4) --> Τυπώνει 4+6 = 10
f()[0](2) --> Τυπώνει 1+2 = 3

Άσκηση 5

Έστω το παρακάτω string:

'++-+--+-+++++++++++++-+-+++++-++--++-++++-+---++-++-+--++---++-+-++-------+-+++---+---++-+-+++-+-+++'

Φτιάξτε μια συνάρτηση που θα παίρνει μία παράμετρο ένα string. Στη συνέχεια θα επιστρέφει τη θέση στο string που βρίσκεται η μεγαλύτερη ακολουθία από συνεχόμενα '+'. Αν η μεγαλύτερη ακολουθία υπάρχει παραπάνω από μία φορά, επιστρέφει τη πιο μικρή θέση. Για παράδειγμα:

'+--+-+-----+-+--+----+--+---+++-+-+---+-----++----+-++--++++++-+-----++---+--+-+-+-+++++--++-------+' --> 56
'+-+-++--+----+-+---+-+-+---+----+-++-+-+--++++-++++-+++--++++--+----+----+-+++--+-++-+---++-+-------' --> 42

Άσκηση 6

Έστω το παρακάτω string:

'++-+--+-+++++++++++++-+-+++++-++--++-++++-+---++-++-+--++---++-+-++-------+-+++---+---++-+-+++-+-+++'

Και έστω η παρακάτω λέξη:

ZABARAKTRANEMIA

Φτιάξτε μία συνάρτηση η οποία θα παίρνει δύο παραμέτρους. Ένα string μόνο με '+' και '-' και ένα άλλο string με οποιουσδίποτε χαρακτήρες. Η συνάρτησή σας θα πρέπει να αντιστοιχείσει το 2ο string στο 1ο. Με τον εξής τρόπο: Όπου υπάρχει το πρώτο '-' αντιστοιχεί το 1ο γράμμα του 2ου string. Όπου υπάρχει το δεύτερο '-' αντιστοιχεί το 2ο γράμμα του 2ου string κτλ. Αν υπάρχει '+' τότε θα πρέπει να βάζει κενό. Δεν χρειάζεται να βάζετε κενά μόλις τελειώσει το 2o string. Για παράδειγμα:

ΕΙΣΟΔΟΣ:
'++-+--+-+++++++++++++-+-+++++-++--++-++++-+---++-++-+--++---++-+-++-------+-+++---+---++-+-+++-+-+++'
'ZABARAKATRANEMIA'

ΕΞΟΔΟΣ
   Z AB A             R A     K  AT  R    A NEM  I  A

ΕΞΗΓΗΣΗ
'++-+--+-+++++++++++++-+-+++++-++--++-++++-+---++-++-+--++---++-+-++-------+-+++---+---++-+-+++-+-+++'
   Z AB A             R A     K  AT  R    A NEM  I  A

Άσκηση 7

Δίνεται η παρακάτω λίστα:

[
   'Alekos',
   'Aleksandra',
   'Aleksandros'
]

Φτιάξτε μία συνάρτηση η οποία θα παίρνει μία λίστα από strings. Θα επιστρέφει το μεγαλύτερο δυνατό υπο-string με το οποία ξεκινάν όλες οι λέξεις της λίστας. Παράδειγμα:

[
   'Alekos',
   'Aleksandra',
   'Aleksandros'
]

--> 'Alek'

[
   'Panionios',
   'Panathaikos',
   'Panaitolikos',
]

--> 'Pan'

[
	'python',
	'java',
	'assembly',

]

--> ''

Άσκηση 8

Φτιάξτε μία συνάρτηση η οποία θα παίρνει 1 παραμέτρo, ν ακέραιoς. Η συνάρτηση θα πρέπει να επιστρέφει ένα string το οποίο θα είναι το ανάπτυγμα της έκφρασης (α+β)^ν. Παραδείγματα:

n=10  Δηλαδή (α+β)^10

--> a^10 + 10a^9b + 45a^8b^2 + 120a^7b^3 + 210a^6b^4 + 252a^5b^5 + 210a^4b^6 + 120a^3b^7 + 45a^2b^8 + 10ab^9 + b^10

Χρησιμοποιείστε τη φόρμουλα που περιγράφεται εδώ: https://en.wikipedia.org/wiki/Binomial_theorem για να βρείτε τους παράγοντες του κάθε γινομένου.

Άσκηση 9

Έστω το παρακάτω string:

'aahtoootoootttuuuu-----------o'

Υπάρχει ενας τρόπος να "συμπιέσουμε" αυτό το string, γράφοντας κάθε γράμμα που επαναλαμβάνετε σκολουθούμενο με το πόσες φορές επαναλμβάνεται. Αν το υλοποιήσουμε τότε το string αυτό μπορει να γραφεί ως εξής:

'a2h1t1o3t1o3t2u4-11o1'

Φτιάξτε μία συνάρτηση με τον όνομα compress η οποία θα παίρνει ως παράμετρο ένα string s. Η συνάρτηση θα επιστρέφει ένα άλλο string το οποίο θα είναι η συμπίεση του s σύμφωνα με τον τρόπο που παρουσιάστηκε. Υποθέστε ότι το s δεν θα έχει αριθμούς μέσα.

Φτιάξτε μία συνάρτηση με τον όνομα decompress η οποία θα παίρνει ένα συμπιεσμένο string και θα επιστρέφει το αρχικό, αποσυμπιεσμένο string.

Άσκηση 10

Ένας παίκτης παίζει 100 παρτίδες πόκερ. Σε κάθε παρτίδα σημειώνει πόσα λεφτά κέρδισε ή έχασε. Τα ποσά αυτά τα σημειώνει σε μία λίστα. π.χ.:

[31, -28, 14, -12, -4, 44, 47, 2, -48, -5, -43, 32, 0, -4, 24, -46, -12, 38, -38, -27, -23, -26, 10, 42, 26, -20, -43, -50, 
2, 42, 32, 17, -33, 5, 42, 28, 2, 12, 9, -33, 22, 10, 3, 34, 12, 17, 21, 17, 24, 22, 21, -35, 33, 12, -43, 49, -17, 3, -2, 
-25, -29, -35, -26, -25, -22, -33, 10, 26, -41, 29, 6, -10, 15, -28, -23, -35, -1, -16, 24, -45, -50, -17, 20, 12, -32, 48, 
-48, 2, -41, 4, 5, 29, -36, -46, -6, -17, -18, 16, 42, 42]

Σε ποια παρτίδα ο παίκτης είχε τα περισσότερα χρήματα; Δηλαδή στη πρώτη παρτίδα ο παίκτης είχε 31. Στη δεύτερη είχε 31-28=3. Στη τρίτη είχε 31-28+14=17. κτλ. Όπως βλέπετε υπάρχουν παρτίδες που ο παίκτης έχασε χρήματα.

Φτιάξτε μία συνάρτηση η οποία θα παίρνει ως παράμετρο μία λίστα από ακέραιους. Θα επιστρέφει τη θέση στην οποία το άθροισμα όλων των αριθμών από την αρχή μέχρι εκείνη τη θέση είναι ο μεγαλύτερος. Για παράδειγμα η απάντηση στη λίστα που δόθηκε είναι 56 (ξεκινώντας από το 0).

Άσκηση 11

Θεωρήστε τον ίδιο παίκτη πόκερ. Ποιες είναι οι συνεχόμενες παρτίδες που είχε το μεγαλύτερο κέρδος; Φτιάξτε μία συνάρτηση η οποία θα παίρνει σαν παράμετρο μία λίστα με ακέραιους. Η συνάρτηση θα επιστρέφει το υποσύνολο της λίστας από συνεχόμενες τιμές που έχει το μεγαλύτερο άθροισμα. Η απάντηση στη λίστα του παραδείγματος είναι: (28,56). Δηλαδή το άθροισμα όλων των στοιχείων της λίστα απο το 28 μέχρι το 56 είναι και το μεγαλύτερο δυνατό.

Άσκηση 12

Για να γίνει ένα κέικ κάποιος μπορεί να επιλέξει μία από 6 διαφορετικές μάρκες βούτηρο. Οι τιμές τους είναι:

[82, 88, 88, 71, 79, 74]

Πρέπει επίσης να επιλέξει μία από 8 μάρκες αυγά. Οι τιμές τους είναι:

[73, 91, 82, 98, 95, 90, 70, 73]

Πρέπει επίσης να επιλέξει μία από 5 μάρκες γάλα. Οι τιμές τους είναι:

[97, 90, 89, 81, 99]

Ποιος είναι ο μέσος όρος όλων των δυνατών τιμών που μπορεί να κοστίσει ένα κέικ;

Άσκηση 13

Ας υποθέσουμε ότι έχουμε ένα γονίδιο το οποίο έχει μέγεθος 100 νουκλεοτίδια. Από το γονίδιο αυτό παίρνουμε 20 ακολουθίες. Η κάθε μία ξεκινάει και τελειώνει στις θέσεις που φαίνονται παρακάτω:

[(22, 34), (66, 75), (35, 46), (45, 59), (77, 87), (38, 58), (51, 58), (81, 90), (52, 70), (53, 65), 
(53, 72), (50, 63), (80, 100), (0, 12), (68, 81), (35, 51), (27, 34), (69, 87), (39, 47), (0, 8)]

Ποιες θέση του γονιδίου έχουν τη μεγαλύτερη "κάλυψη". Δηλαδή η ακολουθία τους έχει διαβαστεί τις περισσότερες φορές; Φτιάξτε μία συνάρτηση η οποία θα παίρνει μία λίστα από ζευγάρια από αριθμούς. Η συνάρτηση θα επιστρέφει μία λίστα με τις θέσεις που έχουν τη μεγαλύτερη κάλυψη. Για το παράδειγμα που έχει δοθεί η απάντηση είναι:

[53, 54, 55, 56, 57]

Άσκηση 14

Έστω η λίστα με τα παρακάτω strings:

b = [
    'zabarakatranemia',
    'askardamikth',
    'mpampesika',
]

Ποια είναι τα γράμματα που υπάρχουν σε όλα τα strings της λίστας; Φτιάξτε μία συνάρτηση που θα παίρνει σαν παράμετρο μία λίστα με strings. Θα επιστρέφει μία λίστα με όλα τα γράμματα που υπάρχουν σε όλα τα strings της παραμέτρου. Για παράδειγμα για τη λίστα που δόθηκε, τα γράμματα που υπάρχουν σε όλα strings είναι: ['m', 'k', 'i', 'a']. Προσοχή η λίστα μπορεί να περιέχει και γράμματα πέρα του λατινικού αλφάβητου (ελληνικα, κινέζικα, αραβικά, ...)

Άσκηση 15

Έστω ο παρακάτω αριθμός:

a = 25629456287456291

Ποις είναι ο μεγαλύτερος αριθμός ο οποίος υπάρχει μέσα στον a και αποτελείται από ψηφία τα οποία είναι συνεχόμενα; Για παράδειγμα ο 456 είναι ο μεγαλύτερος αριθμός ο οποίος αποτελείται από συνεχόμενα ψηφία (4,5,6) ο οποίος υπάρχει μέσα στον a. Φτιάξτε μία συνάρτηση που θα παίρνει σαν παράμετρο τον a και θα επιστρέφει τον ζητούμενο αριθμό.

Άσκηση 16

Μία εταιρία φορτηγών κάνει διαδρομές μεταξύ διάφορων πόλεων. Οι πόλεις είναι κωδικοποιημένες από το 0 μέχρι το Ν-1, όπου Ν είναι το πλήθος των πόλεων. Η εταιρία έχει μία λίστα η οποία λέει αν ένα φορτηγό βρίσκεται σε μια πόλη, τότε ποια πρέπει να είναι η επόμενη. Αν υποθέσουμε ότι έχουμε μία λίστα με 10 πόλεις, η λίστα αυτή έχει την εξής μορφή:

[5, 0, 6, 6, 9, 3, 4, 0, 4, 3]

Ένα φορτηγό πάντα ξεκινάει από τη πόλη 0.

Σύμφωνα με το πίνακα η επόμενη πόλη είναι αυτή που βρίσκεται στη θέση 0, οπότε είναι η 5.

Η επόμενη πόλη είναι αυτή που βρίσκεται στη θέση 5 οπότε είναι η 3.

Η επόμενη πόλη είναι αυτή που βρίσκεται στη θέση 3 οπότε είναι η 6.

Η επόμενη πολη είναι αυτή που βρίσκεται στη θέση 6 οπότε είναι η 4.

Η επόμενη πόλη είναι αυτή που βρίσκεται στη θέση 4 οπότε είναι η 9.

Η επόμενη πόλη είναι αυτή που βρίσκεται στη θέση 9 οπότε είναι η 3.

Παρατηρούμε ότι στη 3 έχει ξαναπάει. Αν το φορτηγό πάει στη 3 τότε θα κάνει "κύκλους". Δηλαδή θα πηγαίνει 3,6,4,9,3,6,4,9,3,6,4,9,3, ....

Δηλαδή ένα φορτηγό το οποίο ξεκινάει από τη θέση 0 της λίστας θα καταλήγει να κάνει κύκλους μεταξύ 4 πόλεων (3,6,4,9).

Φτιάξτε μία συνάρτηση η οποία θα παίρνει σαν παράμετρο μία λίστα από ακέραιους. Η συνάρτηση θα επιστρέφει το μέγεθος του κύκλου (δηλαδή το πλήθος των πόλεων) που θα κάνει ένα φορτηγό, αν ξεκινήσει από τη θέση 0. Θεωρούμε ότι πάντα υπάρχει κύκλος. Επίσης θα πρέπει η υλοποίησή σας να δουλεύει για αυθαίρετα μεγάλες λίστες.

Μερικά επιπλέον παραδείγματα:

[6, 2, 9, 5, 9, 2, 0, 0, 0, 3] --> 2
[0, 3, 3, 5, 5, 5, 1, 1, 8, 6] --> 1

Άσκηση 17

Ένα ρομποτάκι κινείται σε έναν διδιάστατο χώρο ξεκινώντας από το σημείο 0,0. Το ρομποτάκι δέχεται σαν είσοδο ένα string το οποιο περιγράφει τα βήματά του. Το string αυτό έχει τα παρακάτω γράμματα:

• ">": πήγαινε δεξιά (π.χ. από το 1,3 --> 2,3)
• "<": πήγαινε αριστερά (π.χ. από το 1,3 --> 0,3)
• "v": πήγαινε κάτω (π.χ. από το 1,3 --> 1,2)
• "^": πήγαινε πάνω (π.χ. από το 1,3 --> 1,4)

Για παράδειγμα μία ακολουθία μπορεί να είναι:

^>v<

Δηλαδή πήγαινε πάνω, μετά δεξιά, μετά κάτω μετά αριστερά.

Φτιάξτε μία συνάρτηση η οποία θα δέχεται ένα string το οποίο θα έχει μόνο τους χαρακτήρες: "<", ">", "^", "v". Θα επιστρέφει το πλήθος από τις θέσεις τις οποίες το ρομποτάκι έχει επισκεφθεί μία και μόνο φορά. Θεωρείστε ότι το 0,0 είναι η θέση που ξεκινάει οπότε πριν ακόμα αρχίσει να κινείται, έχει επισκεφθεί αυτή τη θέση 1 φορά (μπορεί όμως στο μέλλον να τη ξαναεπισκεφθεί).

Παραδείγματα:

'v>v<vvv<<vv^v<v>vv>v<<<^^^^^<<^<vv>^>v^>^>^>^>^><vvvv<^>^<<^><<<^vvvv>^>^><^v^><^<>^^>^vvv^<vv>>^>^^<>><>^>vvv>>^vv>^<><>^<v^>^>^><vv^vv^>><<^><<v>><>^<^>>vvv>v>>>v<<^<>'
--> 6

'<^<v<>v>^^v^^^<^v^^>>><^>^>v<>^<>>^>^^v^><v<v>>><>v<v^v>^v<>>^><v>^<>v^>^<>^v^^^v^^>>vv<<^^><^<vvv>^>^^<^>>^^^^^v^<v>vv<>>v^v<^v^^<><^<^vv^><>><><>v>vvv^vv^^<<><<vvv><<^v^>'
--> 2

Άσκηση 18

Θεωρείστε το ίδιο ρομποτάκι με τη προηγούμενη άσκηση. Αλλάξτε τη συνάρτηση έτσι ώστε να επιστρέφει το πλήθος από θέσεις που ΔΕΝ έχει επισκεφτεί. Για να το κάνετε αυτό υπολογίστε το εξής:

• Ποια είναι η πιο δεξιά θέση που έχει επισκεφθεί; Έστω η 4
• Ποια είναι η πιο αριστερή θέση που έχει επισκεφθεί; Έστω η -3
• Ποια είναι η πιο πάνω θέση που έχει επισκεφθεί; Έστω η 2
• Ποια είναι η πιο κάτω θέση που έχει επισκεφθεί; Έστω η -1

Πάρτα όλα τις θέσεις που υπάρχουν στο παραλληλόγραμμο που ορίζονται από αυτές τις "ακραίες" θέσεις. Για παράδειγμα.

(-3, 2)  (-2, 2)  (-1, 2)  (0, 2)  (1, 2)  (2, 2)  (3, 2)  (4, 2)
(-3, 1)  (-2, 1)  (-1, 1)  (0, 1)  (1, 1)  (2, 1)  (3, 1)  (4, 1)
(-3, 0)  (-2, 0)  (-1, 0)  (0, 0)  (1, 0)  (2, 0)  (3, 0)  (4, 0)
(-3, -1) (-2, -1) (-1, -1) (0, -1) (1, -1) (2, -1) (3, -1) (4, -1)

Υπολογίστε το πλήθος από αυτές τις θέσεις που το ρομποτάκι ΔΕΝ έχει επισκεφτεί. Για παράδειγμα:

a = 'v>v<vvv<<vv^v<v>vv>v<<<^^^^^<<^<vv>^>v^>^>^>^>^><vvvv<^>^<<^><<<^vvvv>^>^><^v^><^<>^^>^vvv^<vv>>^>^^<>><>^>vvv>>^vv>^<><>^<v^>^>^><vv^vv^>><<^><<v>><>^<^>>vvv>v>>>v<<^<>'
--> 168

'<^<v<>v>^^v^^^<^v^^>>><^>^>v<>^<>>^>^^v^><v<v>>><>v<v^v>^v<>>^><v>^<>v^>^<>^v^^^v^^>>vv<<^^><^<vvv>^>^^<^>>^^^^^v^<v>vv<>>v^v<^v^^<><^<^vv^><>><><>v>vvv^vv^^<<><<vvv><<^v^>'
--> 257

Άσκηση 19

Έστω ότι έχουμε τις παραπάνω θέσεις σε ένα διδιάστατο χώρο

[(-34, 7),
 (-66, -36),
 (-50, 33),
 (95, 0),
 (-86, 48),
 (46, -27),
 (-39, -46),
 (53, -87),
 (-26, 37),
 (13, -37)]

Έχουμε δηλαδή 10 σημεία. Ο πρώτος αριθμός είναι η συντεταγμένη του στο x και ο δεύτερος στο y. Δηλαδή ο πρώτος αριθμός είναι στο -34,7 του διδιάστατου χώρου. Ορίζεται η ευκλίδεια απόσταση μεταξώ δύο σημείων a,b:

import math
def euclidean(a,b):
	return math.sqrt((a[0]-b[0])**2 + (a[1]-b[1])**2)

Ορίζουμε επίσης τη μέση θέση δύο σημείων ως το μέσο της ευθείας που τα συνδέει:

def mesh_thesh(a,b):
	# This function returns 2 numbers! 
	return (a[0]+b[0])/2, (a[1]+b[1])/2

Στη συνέχεια εφαρμόζουμε τον παρακάτω αλγόριθμο: Βρίσκουμε τα δύο σημεία τα οποία είναι πιο κοντά με βάση την ευκλίδεια απόσταση. Αφού τα βρούμε, διαγράφουμε το ένα από τη λίστα και το άλλο το αντικαθιστούμε με τη μέση θέση των δύο σημείων αυτών. Άρα στο τέλος θα μείνουμε με μία λίστα με 9 σημεία. Επαναλαμβάνουμε αυτή τη διαδικασία μέχρι να μείνει ένα σημείο στη λίστα. Στη συνέχεια βρίσκουμε ποιο σημείο από την αρχική λίστα είναι πιο κοντά στο ένα στοιχείο που έμεινε. Φτιάχτε μία συνάρτηση που θα δέχεται σαν όρισμα μία λίστα με σημεία στον διδιάστατο χώρο και να επιστρέφει το σημείο της λίστας το οποίο είναι πιο κοντά στο ένα σημείο που υπολογίστηκε όπως περιγράφηκε παραπάνω.

Παράδειγμα

[(-34, 7),
 (-66, -36),
 (-50, 33),
 (95, 0),
 (-86, 48),
 (46, -27),
 (-39, -46),
 (53, -87),
 (-26, 37),
 (13, -37)]

--> 9

[(58, -50),
 (-67, 34),
 (-77, 40),
 (-19, -23),
 (-53, -66),
 (39, 15),
 (-85, -14),
 (42, 81),
 (-4, -59),
 (71, 15)]

--> 3

[(44, 29),
 (31, 1),
 (-14, 79),
 (98, -78),
 (-2, 34),
 (-80, -27),
 (98, -21),
 (25, -23),
 (33, 45),
 (-85, -40),
 (53, 81),
 (50, -53),
 (42, 56),
 (-30, 100),
 (74, 20),
 (-78, -80),
 (-39, 42),
 (87, 19),
 (15, 98),
 (85, -27)]
 
 --> 7

Άσκηση 20 (Εξαιρετικά δύσκολη)

Δίνεται η παρακάτω λίστα:

[[673, 517, 674, 834, 991, 458, 558, 538, 990],
 [758, 469, 850, 940, 889, 937, 978, 703],
 [925, 838, 595, 880, 767, 685, 659],
 [589, 455, 858, 808, 748, 837],
 [586, 994, 875, 779, 945],
 [979, 685, 661, 817],
 [498, 814, 940],
 [597, 687],
 [844]]

Η λίστα αυτή περιέχει τις αποστάσεις μεταξύ 10 πόλεων. Η 1η πόλη απέχει από τη 2η 673.

Η 1η πόλη απέχει από τη 3η 517.

Η 1η πόλη απέχει από τη 4η 674.

Η 1η πόλη απέχει από τη 10η 990.

Η 2η πόλη απέχει από τη 3η 758.

Η 2η πόλη απέχει από τη 4η 469.

Η 2η πόλη απέχει από τη 10η 703.

Η 8η πόλη απέχει από τη 9η 597.

Η 8η πόλη απέχει από τη 10η 687.

Η 9η πόλη απέχει απο τη 10η πόλη 844.

Εννοείται επίσης ότι η απόσταση μεταξύ της πόλης Α και Β είναι ίδια με την απόσταση της Β με την Α..

Ένα φορτηγό θέλει να ξεκινήσει από τη 1η πόλη και να καταλήξει πάλι στη 1η πόλη έχοντας επισκεφτεί όλες τις υπόλοιπες πόλεις ακριβώς 1 φορά τη κάθε μία. Με ποια σειρά πρέπει να τις επισκεφτεί ώστε να κάνει τη μικρότερη δυνατή απόσταση;

Φτιάξτε μία συνάρτηση η οποία θα παίρνει ως παράμετρο μία λίστα σαν αυτή του παραδείγματος. Η συνάρτηση θα επιτρέφει μία λίστα με τη σειρά των πόλεων που ελαχιστοποιούν την απόσταση. Για παράδειγμα:

Για το παράδειγμα που δόθηκε: --> [0, 6, 7, 8, 2, 9, 1, 3, 5, 4, 0]

# Ένα άλλο παράδειγμα

[[518, 711, 908, 526, 431, 731, 898, 661, 487],
 [586, 634, 850, 668, 441, 624, 699, 728],
 [910, 895, 928, 536, 875, 747, 477],
 [679, 909, 572, 543, 728, 734],
 [871, 599, 615, 836, 715],
 [739, 874, 994, 544],
 [859, 624, 742],
 [886, 528],
 [740]]

--> [0, 5, 9, 2, 1, 6, 4, 7, 3, 8, 0]

Στις λύσεις που έχω βάλει εδώ, 0 είναι η 1η πόλη .... 9 είναι η 10η πόλη.

Αυτό το πρόβλημα είναι γνωστό σαν Travelling Salesman Problem. Το πρόβλημα ανοίκει σε μία ιδιαίτερη κατηγορία προβλημάτων: Αυτή που δεν υπάρχει καλύτερη λύση (ή μάλλον δεν έχει βρεθεί ακόμα..) πέρα της εξαντλητικής. Δηλαδή το να πάρεις όλες τις πιθανές διαδρομές και να βρεις τη πιο σύντομη, είναι αυτή τη στιγμή ο καλύτερος αλγόριθμος που υπάρχει!

Μην σας ανησυχεί όμως αυτό. Για τα μεγέθη που βάζουμε σε αυτή την άσκηση, ο υπολογιστής σας μπορεί να βρει τη λύση σε μερικά δευτερόλεπτα!