Έχετε βρεθεί ποτέ να περιμένετε τον ανελκυστήρα να έρθει στον όροφό σας και να παίρνει υπερβολικά πολύ χρόνο; Σε αυτήν την άσκηση θα γράψουμε ένα πρόγραμμα-οδηγό (driver) που βελτιστοποιεί τις αποφάσεις ενός ανελκυστήρα, ώστε οι επιβάτες να περπατούν όσο το δυνατόν λιγότερους ορόφους.
Μοντελοποίηση του προβλήματος. Έστω ότι ο ανελκυστήρας μας λειτουργεί σε ένα κτήριο με άπειρους ορόφους (όροφοι 1, 2, 3, …). Στο ισόγειο (όροφος 0) βρίσκονται \(numPeople\) άνθρωποι, καθένας από τους οποίους θέλει να πάει στον όροφο \(dests_i\) (\(1 \le i \le numPeople\)). Για κάποιους (τεχνικούς και άλλους λόγους—ο κατασκευαστής ήταν ελαφρώς σφιχτοχέρης) ο ανελκυστήρας θα ξεκινήσει από το ισόγειο και θα κάνει το πολύ \(numStops\) στάσεις. Κάθε επιβάτης θα βγει στον όροφο (κάποια από τις στάσεις του ανελκυστήρα) που είναι πιο κοντά στον όροφο που είναι ο προορισμός του και θα πάει από τις σκάλες στον προορισμό του. Κάθε μετάβαση επιβάτη από τις σκάλες από όροφο σε γειτονικό του όροφο (είτε ανεβαίνοντας, είτε κατεβαίνοντας) έχει κόστος 1. Ποια είναι η βέλτιστη λύση (συνολικό ελάχιστο κόστος), δηλαδή ποιες στάσεις πρέπει να κάνει ο ανελκυστήρας, ώστε οι επιβάτες του να κάνουν τις λιγότερες δυνατές μετακινήσεις με τα πόδια; Μεταξύ λύσεων με το ίδιο κόστος, προτιμώνται εκείνες που ο ανελκυστήρας σταματά σε χαμηλότερους ορόφους. Να σημειωθεί ότι δεν είναι απαραίτητο όλοι οι επιβάτες να μπουν στον ανελκυστήρα. Κάποιοι μπορεί να πάνε με τα πόδια από το ισόγειο στον προορισμό τους (επειδή αυτός θα είναι πιο κοντά στο ισόγειο απ’ ότι στην πρώτη στάση του ανελκυστήρα). Επίσης, υπάρχει ενδεχόμενο να υπάρχει λύση στο πρόβλημα με λιγότερες από \(numStops\) στάσεις, επειδή ο ανελκυστήρας θα σταματήσει σε όλους τους προορισμούς των επιβατών του και το κόστος θα ισούται με 0.
Ας δούμε λοιπόν ένα παράδειγμα. Έστω \(numPeople = 5\), \(numStops = 2\) και \(dests = [11\ 2\ 7\ 13\ 7]\). Αν ο ανελκυστήρας κάνει τις δύο στάσεις του στους ορόφους \(stops = [5\ 12]\), τότε ο πρώτος επιβάτης με προορισμό τον όροφο 11 θα βγει στον όροφο 12 (πλησιέστερη στάση στον προορισμό του) και θα κατέβει με τις σκάλες 1 όροφο (κόστος 1). Ο δεύτερος επιβάτης με προορισμό τον όροφο 2 δεν θα μπει στον ανελκυστήρα και θα ανέβει δύο ορόφους με τις σκάλες (κόστος 2). Για τον τρίτο επιβάτη, έχουμε κόστος ίσο με 2 (προορισμός ο όροφος 7 και στάση ο όροφος 5). Με όμοιο τρόπο, βρίσκουμε ότι το κόστος για τον τέταρτο επιβάτη είναι 1 και για τον πέμπτο είναι 2. Το συνολικό κόστος ισούται με \(1 + 2 + 2 + 1 + 2 = 8\). Όμως, η λύση \(stops = [7\ 11]\) έχει κόστος ίσο με 4 (γιατί;) και μπορεί να αποδειχθεί ότι είναι η βέλτιστη λύση.
Σκέψεις για την επίλυση του προβλήματος. Δεν υπάρχει περίπτωση η βέλτιστη λύση να περιέχει στάση σε όροφο μεγαλύτερο από τον υψηλότερο προορισμό των επιβατών (αν υπήρχε τέτοια στάση, θα μπορούσαμε να την μεταφέρουμε σε αυτόν τον όροφο και η νέα λύση σίγουρα θα έχει μικρότερο κόστος). Για τη συνέχεια, ας συμβολίσουμε τον υψηλότερο προορισμό των επιβατών ως \(numFloors\).
Η διαχείριση του ενδεχομένου να αρκούν λιγότερες στάσεις από \(numStops\), οπότε έχουμε λύση ελαχίστου κόστους ίσου με 0, μπορεί να γίνει με απλό τρόπο. Σκεφτείτε την περίπτωση \(numPeople = 5\), \(numStops = 3\) και \(dests = [6\ 6\ 6\ 6\ 6]\). Αρκεί ο ανελκυστήρας να κάνει μόνο μία στάση, στον όροφο 6 (κόστος 0). Την λύση αυτή θα μπορούσαμε να την αναπαραστήσουμε σαν \(stops = [0\ 0\ 6]\). Δηλαδή, θεωρούμε ότι υπάρχουν και επιπλέον, πρακτικά ανύπαρκτες, στάσεις στο ισόγειο.
Αν \(a\) και \(b\) είναι δύο διαδοχικές στάσεις του ανελκυστήρα, ας θεωρήσουμε ότι με \(fw(a, b)\) (τα αρχικά για τις λέξεις Floors Walked) συμβολίζουμε το συνολικό πλήθος των ορόφων που θα χρειαστεί να περπατήσουν όλοι οι επιβάτες που έχουν προορισμό όροφο \(d\) πιο ψηλά από τον όροφο \(a\) (\(a < d\)) και το πολύ μέχρι τον όροφο \(b\) (\(d \le b\)) για να πάνε στον όροφο \(d\) από τις σκάλες, βγαίνοντας από τον ανελκυστήρα στον όροφο \(a\) ή στον όροφο \(b\), ανάλογα με το ποιος είναι κοντινότερος στον \(d\). Το \(b\) μπορεί να ισούται με \(\infty\), στην περίπτωση που ο όροφος \(a\) είναι ο τελευταίος που θα σταματήσει ο ανελκυστήρας. Επίσης, το \(a\) μπορεί να ισούται με 0, στην περίπτωση που το \(b\) είναι η πρώτη στάση του ανελκυστήρα.
Έστω \(M_{i,j}\) το ελάχιστο κόστος για να εξυπηρετηθούν όλοι οι επιβάτες με \(i\) ακριβώς στάσεις του ανελκυστήρα, η υψηλότερη από τις οποίες είναι στον όροφο \(j\). Εκφράζεται από την ακόλουθη αναδρομική σχέση:
\[\begin{aligned} M_{0,j} &= fw(0,\infty), \quad 0 \le j \le numFloors\\ M_{i,j} &= \min_{k=0}^{j}\{M_{i-1,k} - fw(k,\infty) + fw(k,j) + fw(j,\infty)\},\\ &\quad \text{where } 1 \le i \le numStops,\ 0 \le j \le numFloors \end{aligned}\]Αν ο ανελκυστήρας δεν κινηθεί καθόλου (\(i = 0\) στάσεις), όλοι οι επιβάτες θα πάνε στους προορισμούς τους από τις σκάλες. Όταν προστεθεί μία επιπλέον στάση στον όροφο \(j\) μετά από κάποια στον όροφο \(k\), αλλάζει μόνο το κόστος των επιβατών με προορισμούς ψηλότερα από τον όροφο \(k\): από το \(M_{i-1,k}\) αφαιρούμε το κόστος τους με τις σκάλες από τον \(k\) και το αντικαθιστούμε με το κόστος όσων έχουν προορισμό μέχρι τον \(j\) (ανάμεσα σε \(k\) και \(j\)) συν το κόστος όσων έχουν προορισμό πάνω από τον \(j\). Το ελάχιστο από αυτά τα κόστη, για όλα τα πιθανά \(k\), είναι το \(M_{i,j}\). Τελικά, το ελάχιστο κόστος για το πλήρες πρόβλημα ισούται με
\[MinCost = \min_{j=0}^{numFloors}\{M_{numStops,j}\}\]και η τελευταία στάση του ανελκυστήρα είναι εκείνο το \(j\) για το οποίο έχουμε το ελάχιστο στον προηγούμενο τύπο.
Στην εργασία αυτή λοιπόν, καλείστε να υλοποιήσετε ένα πρόγραμμα σε γλώσσα C το οποίο να βρίσκει αποδοτικά την βέλτιστη από πλευράς κόστους λειτουργίας του ανελκυστήρα. Καθώς δεν γνωρίζουμε εξ αρχής ποια λύση θα έχει καλύτερη απόδοση, θέλουμε να δοκιμάσετε τέσσερις (4) εναλλακτικές μεθόδους έτσι ώστε να μπορέσουμε να συγκρίνουμε τις επιδόσεις τους (benchmarking) και να επιλέξουμε την καλύτερη για χρήση σε συστήματα παραγωγής.
progintro/hw2-<YourUsername>elevate/README.mdelevate/src/elevate.c : το αρχείο που θα περιέχει την main σας.elevate/src/recurse.c : το αρχείο με την αναδρομική υλοποίησηelevate/src/brute.c : το αρχείο με την υλοποίηση ωμής βίαςelevate/src/memoize.c : το αρχείο με την υλοποίηση που χρησιμοποιεί memoizationelevate/src/dp.c : το αρχείο με την υλοποίηση που χρησιμοποιεί δυναμικό
προγραμματισμόelevate/src/elevate.h : το αρχείο κεφαλίδας με τους ορισμούς προτύπων συναρτήσεων
όπου απαιτείται.Τα αρχεία C που θα υποβληθούν πρέπει να μεταγλωττίζονται χωρίς ειδοποιήσεις για λάθη και με κωδικό επιστροφής (exit code) που να είναι 0. Συγκεκριμένα, το πρόγραμμά σας πρέπει να μπορεί να μεταγλωττιστεί επιτυχώς με τις ακόλουθες εντολές σε ένα από τα μηχανήματα του εργαστηρίου (linuxXY.di.uoa.gr):
gcc -Os -c -Wall -Wextra -Werror -pedantic recurse.c
gcc -Os -c -Wall -Wextra -Werror -pedantic brute.c
gcc -Os -c -Wall -Wextra -Werror -pedantic memoize.c
gcc -Os -c -Wall -Wextra -Werror -pedantic dp.c
gcc -Os -c -Wall -Wextra -Werror -pedantic elevate.c
gcc -Os -o elevate recurse.o brute.o memoize.o dp.o elevate.o
--mode=MODE όπου ο χρήστης θα επιλέγει ποια
εναλλακτική υλοποίηση (MODE) επιθυμεί ανάμεσα στις ακόλουθες επιλογές: (1) recurse,
(2) brute, (3) memoize, (4) dp. Αφού ολοκληρώσετε την υλοποίησή σας, μπορείτε να
μετατρέψετε αυτό το όρισμα σε προαιρετικό έτσι ώστε να χρησιμοποιεί την βέλτιστη λύση
όταν ο χρήστης δεν το προσδιορίσει (default behavior).--mode=recurse (10%)Στο αρχείο recurse.c θέλουμε να γράψετε μια λύση στο πρόβλημα με αναδρομικό τρόπο
βασισμένη στην Σχέση που δόθηκε στην περιγραφή του προβλήματος. Η διεπαφή (interface) της
λύσης είναι πάνω σε εσάς, αλλά θέλουμε υποχρεωτικά η υλοποίησή σας στο recurse.c να
καλείται από την main που θα βρίσκεται στο elevate.c. Στο πρόγραμμά σας δεν επιτρέπεται
να ορίσετε άλλον πίνακα εκτός από αυτόν που χρειάζεται για τη φύλαξη των προορισμών των
επιβατών. Παραδείγματα εκτέλεσης ακολουθούν:
$ cat input1.txt
5 2
11 2 7 13 7
$ ./elevate input1.txt --mode=recurse
Last stop at floor: 11
The minimum cost is: 4
$ cat input2.txt
7 3
8 10 3 8 12 6 5
$ ./elevate input2.txt --mode=recurse
Last stop at floor: 10
The minimum cost is: 5
$ cat input3.txt
6 4
5 3 3 5 5 3
$ ./elevate input3.txt --mode=recurse
Last stop at floor: 5
The minimum cost is: 0
$ cat input4.txt
5 0
1 2 3 4 5
$ ./elevate input4.txt --mode=recurse
No lift stops
The minimum cost is: 15
$ cat input5.txt
20 4
8 32 14 14 6 7 25 43 12 9 1 28 27 25 33 38 42 27 14 44
$ time ./elevate input5.txt --mode=recurse
Last stop at floor: 42
The minimum cost is: 30
0.515u 0.003s 0:13.29 3.8% 0+0k 0+0io 0pf+0w
$ cat input6.txt
20 5
8 32 14 14 6 7 25 43 12 9 1 28 27 25 33 38 42 27 14 44
$ time ./elevate input6.txt --mode=recurse
Last stop at floor: 42
The minimum cost is: 20
4.318u 0.000s 0:14.74 29.2% 0+0k 0+0io 0pf+0w
$ cat input7.txt
20 6
8 32 14 14 6 7 25 43 12 9 1 28 27 25 33 38 42 27 14 44
$ time ./elevate input7.txt --mode=recurse
Last stop at floor: 43
The minimum cost is: 15
31.997u 0.000s 0:38.59 82.8% 0+0k 0+0io 0pf+0w
$ cat input8.txt
25 7
1 2 2 3 5 6 6 8 10 13 15 15 16 17 18 18 18 20 22 25 30 38 49 55 62
$ time ./elevate input8.txt --mode=recurse
Last stop at floor: 62
The minimum cost is: 35
3253.247u 0.003s 54:26.76 99.5% 0+0k 0+0io 0pf+0w
--mode=brute (30%)Παρατηρήστε ότι στις τελευταίες ενδεικτικές εκτελέσεις της αναδρομικής μεθόδου, ο χρόνος
αυξάνει δραματικά. Μία εντελώς διαφορετική μέθοδος για να προσεγγιστεί το πρόβλημα, η οποία
δεν βασίζεται στην αναδρομική σχέση που δόθηκε, είναι να κατασκευάζονται συστηματικά όλες
οι πιθανές λύσεις, δηλαδή οι δυνατοί συνδυασμοί στάσεων του ανελκυστήρα (brute force), για
κάθε μία από αυτές να υπολογίζεται το κόστος της και, τελικά, σαν λύση να δοθεί αυτή που
έχει το ελάχιστο κόστος. Αν ο μέγιστος αριθμός στάσεων είναι \(numStops\), θα πρέπει να
εξετασθούν όλες οι πιθανές λύσεις με 1 στάση, 2 στάσεις, κοκ., \(numStops\) στάσεις.
Υπενθυμίζεται ότι έχει νόημα να συζητάμε για στάσεις από 1 μέχρι \(numFloors\). Η υλοποίησή
σας πρέπει να γίνει εξ ολοκλήρου στο brute.c και να καλείται και πάλι από την main
εντός του elevate.c. Ενδεικτικές εκτελέσεις ακολουθούν:
$ ./elevate input1.txt --mode=brute
Lift stops are: 7 11
The minimum cost is: 4
$
$ ./elevate input2.txt --mode=brute
Lift stops are: 5 8 10
The minimum cost is: 5
$
$ ./elevate input3.txt --mode=brute
Lift stops are: 3 5
The minimum cost is: 0
$
$ ./elevate input4.txt --mode=brute
No lift stops
The minimum cost is: 15
$
$ time ./elevate input5.txt --mode=brute
Lift stops are: 7 14 27 42
The minimum cost is: 30
0.035u 0.003s 0:02.39 1.2% 0+0k 0+0io 0pf+0w
$
$ time ./elevate input6.txt --mode=brute
Lift stops are: 7 14 27 32 42
The minimum cost is: 20
0.240u 0.003s 0:02.87 8.3% 0+0k 0+0io 0pf+0w
$
$ time ./elevate input7.txt --mode=brute
Lift stops are: 7 14 27 32 38 43
The minimum cost is: 15
1.732u 0.003s 0:04.15 41.6% 0+0k 0+0io 0pf+0w
$
$ time ./elevate input8.txt --mode=brute
Lift stops are: 6 15 18 25 38 49 62
The minimum cost is: 35
118.186u 0.000s 2:00.45 98.1% 0+0k 0+0io 0pf+0w
--mode=memoize (20%)Παρότι με την προηγούμενη εκδοχή βελτιώθηκαν σημαντικά οι χρόνοι εκτέλεσης, όταν το μέγεθος της εισόδου μεγαλώνει αρκετά, η χρονική απόδοση του προγράμματος δεν είναι καλή, αφού ελέγχουμε εξαντλητικά όλες τις πιθανές λύσεις, το πλήθος των οποίων αυξάνει εκθετικά με το πλήθος των ορόφων στους οποίους είναι πιθανό να γίνουν στάσεις.
Οπότε, ας επιστρέψουμε στην αναδρομική μέθοδο. Γιατί όμως η αναδρομική μέθοδος έχει
ιδιαίτερα μεγάλους χρόνους εκτέλεσης για μεγάλες εισόδους; Μπορούμε να δούμε ότι
εφαρμόζοντας την αναδρομική σχέση που δόθηκε, τα περισσότερα \(M_{ij}\) υπολογίζονται
περισσότερες από μία φορά το καθένα, αρκετά από αυτά υπερβολικά μεγάλο αριθμό φορών. Πώς θα
μπορούσαμε να το διορθώσουμε; Αρκεί να χρησιμοποιήσουμε ένα δισδιάστατο πίνακα στον οποίο
να αποθηκεύεται κάθε \(M_{ij}\) την πρώτη φορά που υπολογίζεται και όταν χρειάζεται πάλι, να
μην επαναϋπολογίζεται, αλλά να λαμβάνεται η τιμή του από τον πίνακα. Η λογική της
βελτιωμένης μεθόδου εξακολουθεί να είναι αναδρομική, απλώς κάθε \(M_{ij}\) υπολογίζεται
ακριβώς μία φορά. Αυτή η τεχνική λέγεται απομνημόνευση—memoization στα αγγλικά (προσοχή
όχι memorization). Υλοποιήστε αυτήν την μέθοδο στο αρχείο memoize.c και ως συνήθως
καλέστε την από την main όταν δοθεί το κατάλληλο όρισμα από την γραμμή εντολών.
Ενδεικτικές εκτελέσεις ακολουθούν:
$ ./elevate input1.txt --mode=memoize
Last stop at floor: 11
The minimum cost is: 4
$
$ ./elevate input2.txt --mode=memoize
Last stop at floor: 10
The minimum cost is: 5
$
$ ./elevate input3.txt --mode=memoize
Last stop at floor: 5
The minimum cost is: 0
$
$ ./elevate input4.txt --mode=memoize
No lift stops
The minimum cost is: 15
$
$ time ./elevate input5.txt --mode=memoize
Last stop at floor: 42
The minimum cost is: 30
0.006u 0.000s 0:02.37 0.0% 0+0k 0+0io 0pf+0w
$
$ time ./elevate input6.txt --mode=memoize
Last stop at floor: 42
The minimum cost is: 20
0.006u 0.000s 0:01.88 0.0% 0+0k 0+0io 0pf+0w
$
$ time ./elevate input7.txt --mode=memoize
Last stop at floor: 43
The minimum cost is: 15
0.007u 0.000s 0:02.05 0.0% 0+0k 0+0io 0pf+0w
$
$ time ./elevate input8.txt --mode=memoize
Last stop at floor: 62
The minimum cost is: 35
0.007u 0.003s 0:02.32 0.0% 0+0k 0+0io 0pf+0w
--mode=dp (40%)Στην αναδρομική μέθοδο με απομνημόνευση, η λογική του υπολογισμού των \(M_{ij}\) είναι με
σειρά από-επάνω-προς-τα-κάτω (top-down), δηλαδή αρχίζουμε από τα μεγάλα \(i\), οπότε
απαιτείται ο υπολογισμός των τιμών για μικρότερα \(i\), κοκ., μέχρι να φτάσουμε στο \(i = 0\).
Μία αντίστροφη λογική είναι να συμπληρωθεί ο πίνακας των \(M_{ij}\) με σειρά
από-κάτω-προς-τα-επάνω (bottom-up): αρχίζουμε τους υπολογισμούς για \(i = 0\), συνεχίζουμε
με \(i = 1\) και τελικά καταλήγουμε στους υπολογισμούς για \(i = numStops\). Η προσέγγιση αυτή
χαρακτηρίζεται στη βιβλιογραφία ως δυναμικός προγραμματισμός (dynamic programming) και
είναι από τις πιο συχνά χρησιμοποιούμενες τεχνικές βελτιστοποίησης. Χρησιμοποιώντας δυναμικό
προγραμματισμό, υλοποιήστε στο αρχείο dp.c την εύρεση της βέλτιστης λύσης. Όταν δίνεται
το επιπλέον όρισμα --debug, θέλουμε η λύση σας να εκτυπώνει και τις τιμές \(M_{ij}\), μία
γραμμή για κάθε \(i\) (από 0 έως \(numStops\)) καθώς και όλες τις στάσεις του για την βέλτιστη
λύση! Σκεφτείτε πώς θα μπορούσε να γίνει αυτό. Αρκούν οι τιμές \(M_{ij}\); Μάλλον όχι. Μία
ιδέα, όχι όμως δεσμευτική, είναι να χρησιμοποιηθεί και ένας δεύτερος δισδιάστατος πίνακας,
στον οποίο να φυλάσσεται για κάθε \((i, j)\) η τιμή του \(k\) για την οποία στη στάση \(i - 1\)
βρέθηκε η ελάχιστη τιμή για το \(M(i, j)\), σύμφωνα με την αναδρομική σχέση που δόθηκε
αρχικά. Θα πρέπει να σκεφτείτε, βέβαια, πώς θα εκμεταλλευτείτε τα περιεχόμενα αυτού του
επιπλέον πίνακα για να βρείτε τις στάσεις του ανελκυστήρα. Ενδεικτικές εκτελέσεις
ακολουθούν (στην εκφώνηση οι μεγάλες γραμμές αναδιπλώνονται· εδώ κάθε γραμμή \(M_{i,\cdot}\)
είναι σε μία γραμμή):
$ ./elevate input1.txt --mode=dp --debug
40 40 40 40 40 40 40 40 40 40 40 40 40 40
40 35 30 27 24 20 16 12 12 12 12 12 14 16
40 35 30 26 22 18 14 10 10 8 6 4 4 4
Lift stops are: 7 11
The minimum cost is: 4
$
$ ./elevate input2.txt --mode=dp --debug
52 52 52 52 52 52 52 52 52 52 52 52 52
52 45 38 31 26 21 18 16 14 16 18 21 24
52 45 38 31 25 19 15 13 9 9 9 10 10
52 45 38 31 25 19 14 11 7 7 5 5 5
Lift stops are: 5 8 10
The minimum cost is: 5
$
$ ./elevate input3.txt --mode=dp --debug
24 24 24 24 24 24
24 18 12 6 6 6
24 18 12 6 3 0
24 18 12 6 3 0
24 18 12 6 3 0
Lift stops are: 3 5
The minimum cost is: 0
$
$ ./elevate input4.txt --mode=dp --debug
15 15 15 15 15 15
No lift stops
The minimum cost is: 15
$
$ time ./elevate input5.txt --mode=dp --debug
449 449 449 449 449 449 449 449 449 449 449 449 449 449 449 449 449 449 449 449 449 449 449 449 449 449 449 449 449 449 449 449 449 449 449 449 449 449 449 449 449 449 449 449 449
449 429 411 392 373 354 335 318 303 290 279 268 257 247 237 232 227 221 215 208 201 194 187 180 173 165 161 157 157 156 155 154 153 154 157 160 163 166 169 174 179 184 189 196 205
449 429 410 391 372 353 334 317 301 286 272 258 243 230 217 210 203 195 187 179 169 158 147 136 125 114 107 100 97 96 95 94 93 94 97 100 103 106 107 109 108 107 105 105 107
449 429 410 391 372 353 334 316 300 285 271 256 241 228 215 206 195 184 173 162 151 140 129 118 107 96 89 82 79 78 77 76 70 66 64 62 60 58 55 54 52 50 48 48 50
449 429 410 391 372 353 334 316 299 284 270 255 240 227 213 204 193 182 171 160 149 138 127 116 105 94 87 78 73 70 64 58 52 48 46 44 42 40 37 36 34 32 30 30 32
Lift stops are: 7 14 27 42
The minimum cost is: 30
0.003u 0.003s 0:02.28 0.0% 0+0k 0+0io 0pf+0w
$
$ time ./elevate input6.txt --mode=dp --debug
449 449 449 449 449 449 449 449 449 449 449 449 449 449 449 449 449 449 449 449 449 449 449 449 449 449 449 449 449 449 449 449 449 449 449 449 449 449 449 449 449 449 449 449 449
449 429 411 392 373 354 335 318 303 290 279 268 257 247 237 232 227 221 215 208 201 194 187 180 173 165 161 157 157 156 155 154 153 154 157 160 163 166 169 174 179 184 189 196 205
449 429 410 391 372 353 334 317 301 286 272 258 243 230 217 210 203 195 187 179 169 158 147 136 125 114 107 100 97 96 95 94 93 94 97 100 103 106 107 109 108 107 105 105 107
449 429 410 391 372 353 334 316 300 285 271 256 241 228 215 206 195 184 173 162 151 140 129 118 107 96 89 82 79 78 77 76 70 66 64 62 60 58 55 54 52 50 48 48 50
449 429 410 391 372 353 334 316 299 284 270 255 240 227 213 204 193 182 171 160 149 138 127 116 105 94 87 78 73 70 64 58 52 48 46 44 42 40 37 36 34 32 30 30 32
449 429 410 391 372 353 334 316 299 283 269 254 239 226 212 202 191 180 169 158 147 136 125 114 103 92 85 76 71 66 60 54 48 44 42 40 36 32 28 26 24 22 20 20 21
Lift stops are: 7 14 27 32 42
The minimum cost is: 20
0.006u 0.000s 0:02.01 0.0% 0+0k 0+0io 0pf+0w
$
$ time ./elevate input7.txt --mode=dp --debug
449 449 449 449 449 449 449 449 449 449 449 449 449 449 449 449 449 449 449 449 449 449 449 449 449 449 449 449 449 449 449 449 449 449 449 449 449 449 449 449 449 449 449 449 449
449 429 411 392 373 354 335 318 303 290 279 268 257 247 237 232 227 221 215 208 201 194 187 180 173 165 161 157 157 156 155 154 153 154 157 160 163 166 169 174 179 184 189 196 205
449 429 410 391 372 353 334 317 301 286 272 258 243 230 217 210 203 195 187 179 169 158 147 136 125 114 107 100 97 96 95 94 93 94 97 100 103 106 107 109 108 107 105 105 107
449 429 410 391 372 353 334 316 300 285 271 256 241 228 215 206 195 184 173 162 151 140 129 118 107 96 89 82 79 78 77 76 70 66 64 62 60 58 55 54 52 50 48 48 50
449 429 410 391 372 353 334 316 299 284 270 255 240 227 213 204 193 182 171 160 149 138 127 116 105 94 87 78 73 70 64 58 52 48 46 44 42 40 37 36 34 32 30 30 32
449 429 410 391 372 353 334 316 299 283 269 254 239 226 212 202 191 180 169 158 147 136 125 114 103 92 85 76 71 66 60 54 48 44 42 40 36 32 28 26 24 22 20 20 21
449 429 410 391 372 353 334 316 299 283 268 253 238 225 211 201 190 179 168 157 146 135 124 113 102 91 83 74 69 64 58 52 46 42 40 36 32 28 24 22 20 18 16 15 16
Lift stops are: 7 14 27 32 38 43
The minimum cost is: 15
0.007u 0.000s 0:02.02 0.0% 0+0k 0+0io 0pf+0w
$
$ time ./elevate input8.txt --mode=dp --debug
474 474 474 474 474 474 474 474 474 474 474 474 474 474 474 474 474 474 474 474 474 474 474 474 474 474 474 474 474 474 474 474 474 474 474 474 474 474 474 474 474 474 474 474 474 474 474 474 474 474 474 474 474 474 474 474 474 474 474 474 474 474 474
474 449 426 406 388 368 350 335 320 307 294 282 270 256 244 232 224 217 212 213 214 216 218 222 226 230 236 241 246 251 256 261 266 270 274 277 280 280 280 282 284 285 286 287 288 288 288 288 288 288 290 291 292 293 294 295 298 301 304 307 310 312 314
474 449 425 404 384 363 344 329 314 298 282 267 252 237 224 210 200 192 186 186 186 186 180 176 172 167 164 161 157 153 149 147 145 143 140 137 134 131 128 127 126 125 124 122 120 118 116 114 112 110 110 110 110 110 110 110 112 114 116 117 118 119 120
474 449 425 403 383 362 343 326 308 292 276 261 246 231 218 204 194 186 176 172 167 162 156 152 147 142 139 136 132 128 124 122 120 117 114 111 108 105 102 101 100 99 98 96 94 92 90 88 86 84 84 84 84 84 84 84 86 88 89 90 91 92 93
474 449 425 403 382 361 342 325 307 291 274 259 244 228 214 200 190 180 170 166 160 154 148 143 138 133 130 126 122 118 114 112 110 107 104 101 98 94 90 88 86 84 82 80 78 76 74 72 70 67 66 65 64 63 62 61 62 63 64 65 66 67 68
474 449 425 403 382 361 341 324 306 290 273 258 242 226 212 198 187 176 166 162 154 148 142 137 132 127 124 120 116 112 108 105 102 99 96 93 89 85 81 79 77 75 73 71 69 67 65 63 60 57 56 55 54 53 52 51 52 53 54 55 55 55 54
474 449 425 403 382 361 341 323 305 289 272 257 241 225 211 196 185 174 164 158 150 144 138 133 128 123 120 116 112 107 102 99 96 93 90 87 83 79 75 73 71 69 67 65 63 60 57 54 51 48 47 46 45 44 43 42 43 44 45 45 45 45 44
474 449 425 403 382 361 341 323 305 288 271 256 240 224 210 195 183 172 162 156 148 142 136 131 126 120 116 112 108 103 98 95 92 89 86 82 78 74 70 68 66 64 62 60 57 54 51 48 45 42 41 40 39 38 37 36 36 36 36 36 36 36 35
Lift stops are: 6 15 18 25 38 49 62
The minimum cost is: 35
0.010u 0.000s 0:02.29 0.4% 0+0k 0+0io 0pf+0w
Παρατηρήστε ότι ο χρόνος επίλυσης παραμένει μικρός! Ποια μέθοδο θα επιλέγατε για χρήση στην παραγωγή και γιατί; Δικαιολογήστε την επιλογή σας στο README και φροντίστε η επιλογή αυτή να είναι και η προεπιλεγμένη (default) αν ο χρήστης δεν επιλέξει κάποια από τα γνωστά modes.
Μέχρι στιγμής στο μάθημα είδαμε τρεις βασικούς τρόπους εισόδου για προγράμματα: (1) ορίσματα στην γραμμή εντολών, (2) πρότυπη είσοδο και (3) αρχεία. Υπάρχει κάποια καλύτερη λύση όμως αν ο χρήστης είναι ένα σύστημα τεχνητής νοημοσύνης; Τον Νοέμβριο του 2024 η εταιρεία Anthropic πρότεινε το Model Context Protocol (MCP), που θεωρείται σήμερα το standard για την υλοποίηση διεπαφών για συστήματα τεχνητής νοημοσύνης. Παρόλο που περιέχει φοβιστικούς όρους όπως “Server” και “Protocol”, στην πιο απλή μορφή του είναι απλά ένα πρόγραμμα που διαβάζει από το stdin και τυπώνει στο stdout.
Η αποστολή σας λοιπόν στα πλαίσια αυτού του bonus—εφόσον την αποδεχτείτε—θα είναι η
υλοποίηση ενός MCP server για τον elevate λύτη σας. Πιο συγκεκριμένα, θα χρειαστεί να
υλοποιήσετε μια νέα συνάρτηση main σε ένα αρχείο elevate/src/mcp.c το οποίο θα πρέπει
να μεταγλωττίζεται με αντίστοιχο τρόπο όπως παραπάνω και θα προσφέρει τις ακόλουθες
δυνατότητες:
Η συνολική διάδραση είναι: ο client στέλνει initialize (stdin) και ο server απαντά με το
αποτέλεσμα (stdout)· ο client στέλνει tools/list και ο server απαντά με τη λίστα των
εργαλείων· ο client στέλνει tools/call για το elevate με ορίσματα, ο server τρέχει
elevate(numPeople, numStops, dests, mode) και απαντά με structuredContent. Ας ξεκινήσουμε
το πρόγραμμά μας:
$ gcc -Os -c -Wall -Wextra -Werror -pedantic recurse.c
$ gcc -Os -c -Wall -Wextra -Werror -pedantic brute.c
$ gcc -Os -c -Wall -Wextra -Werror -pedantic memoize.c
$ gcc -Os -c -Wall -Wextra -Werror -pedantic dp.c
$ gcc -Os -c -Wall -Wextra -Werror -pedantic mcp.c
$ gcc -Os -o mcp recurse.o brute.o memoize.o dp.o mcp.o
$ ./mcp
Initialize. Ο server μας περιμένει είσοδο από τον χρήστη. Ας ξεκινήσουμε την χειραψία στέλνοντας το αντίστοιχο μήνυμα αρχικοποίησης:
{"jsonrpc":"2.0","id":1,"method":"initialize","params":
{"protocolVersion":"2025-11-25","capabilities":{"tools":{}},"clientInfo":
{"name":"example-mcp-client","version":"1.0.0","title":"Example MCP Client"}}}
Το παραπάνω μήνυμα είναι σε μορφή JSON, ενώ το όλο
πρωτόκολλο βασίζεται σε έναν τρόπο κωδικοποίησης που λέγεται
JSON-RPC. Για λόγους αποδοτικότητας αποφεύγουμε
τις καινούριες γραμμές (εδώ χρησιμοποιούνται μόνο για να φαίνεται το μήνυμα) καθώς και τα
κενά (για να διαβάσετε ένα JSON αρχείο με καλύτερη αναγνωσιμότητα μπορείτε να τρέξετε
python3 -m json.tool < file.json). Σε ένα τέτοιο μήνυμα αρχικοποίησης ο server μας πρέπει
να απαντήσει με το όνομά του:
{"jsonrpc":"2.0","id":1,"result":{"protocolVersion":"2025-06-18","capabilities":
{"experimental":{},"prompts":{"listChanged":false},"resources":
{"subscribe":false,"listChanged":false},"tools":{"listChanged":true}},"serverInfo":
{"name":"elevate-mcp-server","version":"0.0.1"}}}
List Tools. Τώρα ο χρήστης μπορεί να μάθει περισσότερα για τον server στέλνοντας το
μήνυμα tools/list:
{"jsonrpc":"2.0","id":3,"method":"tools/list","params":{}}
Στο οποίο ο server μας απαντάει ως εξής:
{"jsonrpc":"2.0","id":3,"result":{"tools":[{"name":"elevate","description":
"Compute the optimal elevator final stop and cost.","inputSchema":
{"properties":{"numPeople":{
"description":"Number of people that want to use the elevator.","type":"integer"},
"numStops":{"description":"Maximum number of stops the elevator can make.",
"type":"integer"},"dests":{"description":
"Destination stop of each passenger.","items":{"type":"integer"},"type":"array"},
"mode":{"default":"dp","description":
"Solving mode to be used: recurse, brute, memoize, or dp.",
"enum":["recurse","brute","memoize","dp"],"type":"string"}},"required":
["numPeople","numStops","dests"],"type":"object"},"outputSchema":
{"description":"Result of the elevator optimization.","properties":{"finalStop":
{"description":"Chosen final elevator stop (highest floor the elevator visits).",
"type":"integer"},
"minCost":{"description":"Total minimal walking cost for all passengers.",
"type":"integer"},"status":{"description":"0 on success, non-zero on error.",
"type":"integer"},"message":{"description":
"Human-readable status or error message.","type":"string"},"time":
{"description":"Elapsed time for the computation in microseconds.",
"type":"integer"}},"required":["finalStop","minCost","status","message","time"],
"type":"object"},"_meta":{"_fastmcp":{"tags":[]}}}]}}
Ο server μας τύπωσε τις δυνατότητές του (όλες τις παραμέτρους που δέχεται, περιγραφές τους καθώς και τύπους) και περιμένει εντολές από το σύστημα τεχνητής νοημοσύνης.
Tool Call Response. Ας του πούμε τι θέλουμε, κάνοντας copy-paste στο stdin:
{"jsonrpc":"2.0","id":2,"method":"tools/call","params":
{"name":"elevate","arguments":{"numPeople":5,"numStops":2,"dests":
[11,2,7,13,7],"mode":"dp"}}}
και στο stdout παρατηρούμε την απάντηση:
{"jsonrpc":"2.0","id":2,"result":{"content":
[{"type":"text","text":"{\"finalStop\":11,\"minCost\":4,\"status\":0,\"message\":
\"OK\",\"time\":15}"}],"structuredContent":
{"finalStop":11,"minCost":4,"status":0,"message":"OK","time":15},"isError":false}}
Αυτό ήταν! Ο server μας πλέον είναι συμβατός με οποιοδήποτε σύστημα τεχνητής νοημοσύνης
υποστηρίζει MCP, όπως το Claude Code, VS Code, Cursor, κοκ. Η εκφώνηση δείχνει μια
ενδεικτική διάδραση όπου ο server προστίθεται με claude mcp add --transport stdio elevate
-- ./mcp και το μοντέλο τον καλεί για το παράδειγμα με dests = [11,2,7,13,7] και για
benchmarking όλων των modes. Αν κάποιο παιδί καταφέρει να κάνει live demo (όχι βίντεο,
πραγματική διάδραση) της MCP σύνδεσης με κάποιο πραγματικό μοντέλο κατά την προφορική
εξέταση, η βαθμολογία για το bonus κομμάτι διπλασιάζεται.
Πριν την υποβολή της εργασίας, μην ξεχάσετε το elevate/README.md, μέσα στο οποίο πρέπει
να συμπεριλάβετε τις όποιες παρατηρήσεις σας κατά την διεκπεραίωση της άσκησης! Ο κώδικας
απαιτείται να είναι καλά τεκμηριωμένος με σχόλια καθώς αυτό θα είναι μέρος της
βαθμολόγησης.
Ξεκίνα από μια συνάρτηση fw(a, b) που χειρίζεται σωστά το \(b = \infty\) και έλεγξέ την με
το χέρι στο πρώτο παράδειγμα (π.χ. \(M_{0,j} = 40\)). Για το brute σκέψου πώς
απαριθμούνται όλοι οι αύξοντες συνδυασμοί στάσεων (με αναδρομή ή με έναν «μετρητή» σαν
οδόμετρο). Τα memoize και dp χρειάζονται πίνακα \((numStops+1) \times (numFloors+1)\) που
δεσμεύεται δυναμικά, με μια ειδική τιμή για «δεν υπολογίστηκε ακόμα»· για να ανακατασκευάσεις
τις στάσεις κράτα σε δεύτερο πίνακα ποιο \(k\) έδωσε το ελάχιστο και ακολούθησέ το προς τα πίσω.
Πρόσεξε τις ισοπαλίες (προτιμώνται χαμηλότεροι όροφοι) και την περίπτωση \(numStops = 0\).
Αριθμός στον οδηγό: Α25.4
(στο κεφάλαιο) ·
Μόνιμο αναγνωριστικό: hw-2025-hw2-elevate ·
Σύνδεσμος: https://progintro.github.io/study/questions/homework/hw-2025-hw2-elevate.html ·
Markdown (GitHub)