Εργασία 1

Last updated on Mar 23, 2021

Σημαντικό: διαβάστε τις οδηγίες (κοινές για όλες τις εργασίες). Περιέχουν μεταξύ άλλων και πληροφορίες για τη χρήση του git, η οποία είναι ολόιδια με τα εργαστήρια.

Στην εργασία αυτή θα χρησιμοποιήσετε έτοιμη υλοποίηση για τους περισσότερους ΑΤΔ που είδαμε στο μάθημα, η οποία παρέχεται από τη βιβλιοθήκη k08.a στο git repository της εργασίας.

Άσκηση 1 (25 μονάδες)

Υλοποιήστε ένα πρόγραμμα το οποίο διαβάζει την είσοδό του μία γραμμή τη φορά (μπορείτε να χρησιμοποιήσετε τη συνάρτηση fgets για το σκοπό αυτό). Μόλις διαβάσει την κάθε γραμμή (και πριν συνεχίσει στις επόμενες), το πρόγραμμα πρέπει να τυπώνει στην έξοδό του πόσες φορές έχει διαβάσει την ίδια γραμμή στο παρελθόν (η έξοδος πρέπει να είναι ένας ακέραιος αριθμός ακολουθούμενος από αλλαγή γραμμής \n). Για να το κάνετε αυτό μπορείτε να αποθηκεύετε όλες τις γραμμές που έχετε διαβάσει σε ένα πίνακα (η άσκηση αυτή είναι εισαγωγική και δεν απαιτεί τη χρήση της βιβλιοθήκης k08.a). Μπορείτε να υποθέσετε ότι η κάθε γραμμή είναι το πολύ 20 χαρακτήρες, και ότι η είσοδος περιλαμβάνει το πολύ 100.000 γραμμές.

Δοκιμάστε το πρόγραμμά σας με τα αρχεία εισόδου που υπάρχουν στο directory misc/words και εξετάστε τον χρόνο εκτέλεσής του σε συνάρτηση του μεγέθους της εισόδου. Μπορείτε να δώσετε ένα αρχείο file ως είσοδο στο πρόγραμμα χρησιμοποιώντας τη σύνταξη

./program < file

Επίσης μπορείτε να τυπώνετε το χρόνο εκτέλεσης του προγράμματος με την εντολή time:

time ./program

Προαιρετικά: προσπαθήστε να κάνετε το πρόγραμμά σας όσο πιο αποδοτικό μπορείτε, ώστε να χειρίζεται μεγάλα αρχεία εισόδου, χρησιμοποιώντας οποιαδήποτε τεχνική μάθατε στην εισαγωγή στον προγραμματισμό (αλλά όχι τους ΑΤΔ που παρέχονται από τη βιβλιοθήκη k08.a).

Άσκηση 2 (25 μονάδες)

Υλοποιήστε ένα πρόγραμμα που να εκτελεί ακριβώς την ίδια λειτουργία με αυτή της προηγούμενης άσκησης, αλλά χρησιμοποιώντας τον ATD Map για να αποθηκεύετε πόσες φορές έχετε δει την κάθε γραμμή εισόδου.

Στο map αντιστοιχίζετε την κάθε γραμμή με έναν αριθμό που δηλώνει πόσες φορές έχετε δει τη γραμμή αυτή (δηλαδή τα κλειδιά του map είναι συμβολοσειρές και οι τιμές ακέραιοι αριθμοί). Μόλις διαβάσετε κάθε γραμμή, ελέγχετε αν υπάρχει στο map.

  • αν όχι, είναι η πρώτη φορά που τη διαβάζετε.
  • αν ναι, η τιμή του map είναι ο αριθμός των φορών που έχετε δει τη γραμμή αυτή.

Στη συνέχεια, είτε προσθέτετε τη γραμμή στο map, είτε αυξάνετε την τιμή που περιέχει. Στην εργασία αυτή δεν υπάρχει περιορισμός για τον αριθμό γραμμών της εισόδου (αλλά κάθε γραμμή μπορείτε να θεωρήσετε ότι περιέχει το πολύ 200 χαρακτήρες).

Ελέγξτε το χρόνο εκτέλεσης του προγράμματος αυτού σαν συνάρτηση του μεγέθους της εισόδου, και συγκρίνετέ τον με αυτόν της προηγούμενης άσκησης (αναφέρετε συνοπτικά τα αποτελέσματα στο README.md).

Άσκηση 3 (25 μονάδες)

Υλοποιήστε ένα πρόγραμμα που να εκτελεί παρόμοια λειτουργία με αυτή των δύο προηγούμενων ασκήσεων, με τη διαφορά ότι, μετά από κάθε γραμμή που διαβάστηκε, το πρόγραμμα θα πρέπει να τυπώνει τη μικρότερη (με βάση τη strcmp) γραμμή από αυτές που έχουν ήδη διαβαστεί και είναι μεγαλύτερες ή ίσες από αυτή που μόλις διαβάστηκε. Αν καμία προηγούμενη γραμμή δεν είναι μεγαλύτερη ή ίση από αυτή που διαβάστηκε θα πρέπει να τυπώνει <none>. Πχ για είσοδο

And did they get you trade your heroes for ghosts?
Hot ashes for trees? Hot air for a cool breeze?
Cold comfort for change? And did you exchange
A walk on part in the war for a lead role in a cage?

το πρόγραμμα θα πρέπει να τυπώνει

<none>
<none>
Hot ashes for trees? Hot air for a cool breeze?
And did they get you trade your heroes for ghosts?

Αυτό μπορεί να γίνει αποδοτικά χρησιμοποιώντας τον ADT Set.

Άσκηση 4 (25 μονάδες)

Μια ουρά προτεραιότητας μπορεί να χρησιμοποιηθεί πολύ εύκολα για την ταξινόμηση ενός ADT (πχ ενός Vector ή List). Σκεφτείτε πώς μπορεί να γίνει αυτό, και υλοποιήστε ένα module pq_sort το οποίο να παρέχει τις παρακάτω συναρτήσεις:

// Ταξινομεί το Vector vec, με βάση τη διάταξη της συνάρτησης compare
void pq_sort_vector(Vector vec, CompareFunc compare);

// Ταξινομεί τη λίστα list, με βάση τη διάταξη της συνάρτησης compare
void pq_sort_list(List list, CompareFunc compare);

Η κεφαλίδα του module υπάρχει έτοιμη στο αρχείο include/pq_sort.h, και η βασική δομή της υλοποίησης στο αρχείο modules/pq_sort.c. Τέλος, στο αρχείο tests/pq_sort_test.c υπάρχει ένα unit test που ελέγχει την ορθότητα της μίας μόνο από τις δύο συναρτήσεις του module.

Εσείς θα πρέπει να υλοποιήσετε τις δύο συναρτήσεις, καθώς και το test που λείπει (δε χρειάζεται πρόγραμμα που να παίρνει είσοδο από το χρήστη, μόνο τα unit tests).

Άσκηση 5 (25 μονάδες)

Το “Παιχνίδι της Ζωής” (“Game of Life”) είναι ένα “κυτταρικό αυτόματο” το οποίο κατασκευάστηκε από τον μαθηματικό John Horton Conway το 1970. Κάθε κατάσταση του παιχνιδιού αυτού περιλαμβάνει έναν δισδιάστατο πίνακα απείρου μεγέθους, στον οποίο κάθε κελί έχει ακέραιες συντεταγμένες x,y. Ως συνήθως ο άξονας x είναι ο οριζόντιος, στον οποίο οι συντεταγμένες αυξάνονται προς τα δεξία, ενώ y είναι ο κατακόρυφος, στον οποίο βολεύει περισσότερο οι συντεταγμένες να αυξάνονται προς τα κάτω (αν προτιμάτε ο y να αυξάνεται προς τα πάνω κανένα πρόβλημα). Κάθε κελί μπορεί να είναι είτε “ζωντανό” είτε “νεκρό”. Το παιχνίδι ξεκινάει από κάποια δοσμένη αρχική κατάσταση, και σε κάθε χρονική στιγμή εξελίσσεται ακολουθώντας τους παρακάτω πολύ απλούς κανόνες:

  • Κάθε ζωντανό κελί με λιγότερους από 2 ή περισσότερους από 3 ζωντανούς γείτονες πεθαίνει (λόγω υπο- και υπερ-πληθυσμού αντίστοιχα).
  • Κάθε νεκρό κελί με ακριβώς 3 ζωντανούς γείτονες ζωντανεύει (λόγω αναπαραγωγής).
  • Ολα τα υπόλοιπα κελιά (ζωντανά ή νεκρά) παραμένουν ως έχουν.

Παρά τους πολύ απλούς κανόνες, στο Game of Life παρατηρούνται εξαιρετικά πολύπλοκα και ενδιαφέροντα patterns. Σκοπός της εργασίας είναι η προσωμοίωση του παιχνιδιού.

Αρχικά δημιουργήστε ένα module life το οποίο θα παρέχει τις παρακάτω λειτουργίες.

// Δημιουργεί μια κατάσταση του παιχνιδιού όπου όλα τα κελιά είναι νεκρά.
LifeState life_create();

// Δημιουργεί μία κατάσταση του παιχνιδιού με βάση τα δεδομένα του αρχείο file (RLE format)
LifeState life_create_from_rle(char* file);

// Αποθηκεύει την κατάσταση state στο αρχείο file (RLE format)
void life_save_to_rle(LifeState state, char* file);

// Επιστρέφει την τιμή του κελιού cell στην κατάσταση state (true: ζωντανό, false: νεκρό)
bool life_get_cell(LifeState state, LifeCell cell);

// Αλλάζει την τιμή του κελιού cell στην κατάσταση state
void life_set_cell(LifeState state, LifeCell cell, bool value);

// Παράγει και επιστρέφει μια νέα κατάσταση που προκύπτει από την εξέλιξη της κατάστασης state.
// Η ίδια η state δε μεταβάλλεται (ούτε καταστρέφεται).
LifeState life_evolve(LifeState state);

// Καταστρέφει την κατάσταση ελευθερώντας οποιαδήποτε μνήμη έχει δεσμευτεί
void life_destroy(LifeState state);

Ο τύπος LifeCell ορίζεται ως εξής:

typedef struct {
	int x, y;
} LifeCell;

Λόγω απλότητας, ο τύπος αυτός μπορεί να είναι ορατός στο χρήστη, χωρίς τη χρήση handle (μια μεταβλητή τύπου LifeCell περιέχει το ίδιο το struct).

Ο τύπος LifeState θα πρέπει να είναι κατάλληλα ορισμένος ώστε να αποθηκεύει με αποδοτικό τρόπο οποιαδήποτε πληροφορία χρειάζεστε για την υλοποίηση των μεθόδων αυτών, χρησιμοποιώντας οποιονδήποτε από τους ΑΤΔ που είδαμε στο μάθημα θεωρείτε σκόπιμο. Ας σημειωθεί ότι παρόλο που ο χώρος του παιχνιδιού είναι άπειρος, σε κάθε χρονική στιγμή μπορεί να υπάρχει μόνο ένας πεπερασμένος αριθμός από ζωντανά κελιά (άρα αποθηκεύοντας μόνο τα ζωντανά κελιά μπορείτε να αναπαραστήσετε πλήρως μια κατάσταση). Όμως οποιοδήποτε κελί με συντεταγμένες που περιέχονται σε μια μεταβλητή τύπου LifeCell μπορεί να είναι ζωντανό. Συνιστάται η υλοποίηση του τύπου LifeState να γίνει μέσω handle, ώστε να μην είναι ορατή στο χρήστη του module (information hiding).

Το “RLE” είναι ένα πολύ απλό text-only format για την περιγραφή ενός LifeState: με b σημειώνουμε ένα νεκρό κελί, με o ένα ζωντανό, με $ την αλλαγή γραμμής, ενώ ένας αριθμός πριν από κάποιο χαρακτήρα απλά επαναλαμβάνει τόσες φορές τη σημασία του χαρακτήρα. Ένα ! δηλώνει το τέλος του αρχείου. Πχ ένα glider αποθηκεύεται ως bo$2bo$3o!. Το pattern ξεκινάει από τις συντεταγμένες x= 0, y = 0. Αναλυτική περιγραφή του format υπάρχει εδώ, δείτε και τα παραδείγματα στο τέλος και θα κατανοήσετε τη λογική. Τις γραμμές που αρχίζουν από # καθώς και τη γραμμή x = m, y = n μπορείτε να τις αγνοήσετε.

Δημιουργήστε απλά unit tests για όλες τις λειτουργίες (δε χρειάζεται εκτελέσιμο πρόγραμμα), στα οποία θα δοκιμάζετε τις λειτουργίες πάνω σε δεδομένα για τα οποία γνωρίζετε το αναμενόμενο αποτέλεσμα.

Άσκηση 6 (25 μονάδες)

Βασιζόμενοι στην υλοποίηση της προηγούμενης άσκησης, προσθέστε τις παρακάτω λειτουργίες.

Αρχικά, μια συνάρτηση η οποία πραγματοποιεί διαδοχικές εξελίξεις του παιχνιδιού και τις επιστρέφει σε μία λίστα. Η συνάρτηση αυτή θα πρέπει να ελέγχει και αν κατά τις εξελίξεις αυτές το παιχνίδι πέφτει σε ατέρμονη επανάληψη, το οποίο συμβαίνει αν παράγουμε κάποια κατάσταση που έχουμε ήδη παράξει στο παρελθόν.

// Επιστρέφει μία λίστα από το πολύ steps εξελίξεις, ξεκινώνας από την κατάσταση
// state. Αν βρεθεί επανάληψη τότε στο *loop αποθηκεύεται ο κόμβος της λίστας στον
// οποίο συνεχίζεται η εξέλιξη μετά τον τελευταίο κόμβο, διαφορετικά NULL.
List life_evolve_many(LifeState state, int steps, ListNode* loop);

Με άλλα λόγια, σε κάθε εξέλιξη ελέγχουμε αν το νέο state έχει ξαναεμφανιστεί. Αν ναι, δεν προστίθεται στη λίστα, αποθηκεύουμε στο *loop τον κόμβο στον οποίο έχει εμφανιστεί το state, και διακόπτουμε τις εξελίξεις (δεν υπάρχει λόγους να συνεχίσουμε, περαιτέρω εξελίξεις θα παράγουν ήδη γνωστά states). Αν μετά από steps εξελίξεις δεν έχει βρεθεί επανάληψη σταματάμε θέτωντας *loop = NULL (και η λίστα θα περιέχει steps+1 states). Πχ:

  • Έστω ότι ξεκινώντας από state = Α, η πλήρης ακουθία εξελίξεων είναι A,B,C,B,C,B,....
  • Η κλήση life_evolve_many(state, 2, loop) επιστρέφει A,B,C και θέτει *loop = NULL.
  • Η κλήση life_evolve_many(state, 3, loop) επιστρέφει επίσης A,B,C αλλά θέτει *loop = Β.

Ο έλεγχος ατέρμονης επανάληψης μπορεί να γίνει αποδοτικά με τρόπο παρόμοιο με την Άσκηση 2, αρκεί να ορίσετε μια κατάλληλη διάταξη (συνάρτηση compare) του τύπου LifeState (αλλά και μη αποδοτικές υλοποιήσεις θα γίνουν δεκτές).

Στη συνέχεια, υλοποιήστε ένα πρόγραμα life_gif το οποίο να δημιουργεί ένα GIF animation του οποίου κάθε εικόνα (frame) απεικονίζει τμήμα μιας κατάστασης του παιχνιδιού, δείχνοντας την εξέλιξή του από μια αρχική κατάσταση. Το πρόγραμμα θα καλείται ως εξής:

life_gif <state> <top> <left> <bottom> <right> <frames> <zoom> <speed> <delay> <gif>

Οι παράμετροι περιγράφονται παρακάτω:

  • state (string): η αρχική κατάσταση (αρχείο RLE).

  • top, left, bottom, right (int): το gif θα περιλαμβάνει μόνο τα κελιά που ανήκουν στο παραλληλόγραμμο που ορίζεται από τις συντεταγμένες αυτές. Δηλαδή ένα κελί x,y εμφανίζεται στο gif αν left <= x <= right και top <= y <= bottom (υπεθύμιση: οι y συντεταγμένες αυξάνονται προς τα κάτω).

  • frames (int >= 1): ο αριθμός των εικόνων του gif animation.

  • zoom (float > 0): πόσα pixels του GIF αντιστοιχούν σε ένα cell

    • αν zoom >= 1 τότε για κάθε cell (μέσα στα όρια που δίνονται) θα παράγονται round(zoom) x round(zoom) pixels στο GIF, τα οποία θα είναι όλα μαύρα αν το κελί είναι ζωντανό, αλλιώς άσπρα.
    • αν zoom < 1 τότε για κάθε round(1/zoom) x round(1/zoom) κελιά (μέσα στα όρια που δίνονται) θα παράγεται ένα pixel στο GIF, το οποίο θα είναι μαύρο αν η πλειοψηφία των αντίστοιχων κελιών είναι ζωντανά, αλλιώς άσπρο.

    Σημείωση: το zoom δεν επηρρεάζει ποια κελιά εμφανίζονται στο gif, αλλά το μέγεθός τους.

  • speed (int >= 1): κάθε frame του gif (μετά το πρώτο) απεικονίζει την κατάσταση που προκύπτει μετά από speed εξελίξεις από το προηγούμενο frame. Αν δηλαδή speed = 2 τότε κάθε 2 εξελίξεις παράγεται ένα frame.

  • delay (int): ο χρόνος που διαρκεί κάθε frame (msecs).

  • gif (string): το αρχείο προς δημιουργία.

Αν η υλοποίηση κάποιας συγκεκριμένης παραμέτρου, πχ του zoom, σας δυσκολεύει ιδιαίτερα, απλά αγνοήστε την.

Στο παρακάτω site θα βρείτε έναν τεράστιο αριθμό από ενδιαφέροντα patterns για να δοκιμάσετε. Μπορείτε να χρησιμοποιήσετε και το πρόγραμμα Golly για να δοκιμάσετε τα patterns.

Για τη δημιουργια GIFs μπορείτε να χρησιμοποιήσετε τη βιβλιοθήκη bitmap, η οποία περιέχεται στο git repository της εργασίας, μαζί με ένα παράδειγμα της χρήσης της (gif_example). Documentation θα βρείτε στα αντίστοιχα modules (bmp.h, gif.h).

Speed Competition

Τα προγράμματα life_gif που λειτουργούν σωστά και δεν περιέχουν memory leaks (η ορθότητα προέχει!) συμμετέχουν σε διαγωνισμό ταχύτητας, σε ένα σύνολο από διαφορετικές εκτελέσεις (που δεν ανακοινώνονται). Τα 2 γρηγορότερα κερδίζουν bonus 100% και 50% στο βαθμό ολόκληρης της εργασίας.

Artistic Competition

Ο διαγωνισμός αυτός είναι ομαδικός, σε ομάδες οποιουδήποτε αριθμού ατόμων, χωρίς κανένα περιορισμό (μπορούν να συμμετέχουν και άτομα άπο άλλα τμήματα / έτη / σχολές / κλπ). Σκοπός είναι η δημιουργία ενός video, του οποίου η εικόνα θα προέρχεται από animations (ένα ή περισσότερα) που έχουν δημιουργηθεί με το πρόγραμμα life_gif κάποιου μέλους της ομάδας (ο μόνος περιορισμός). Το video μπορεί να περιέχει ήχο/μουσική και κείμενο με τη μορφή υπότιτλων.

Στο directory misc/video_sample του repository της εργασίας υπάρχει ένα Makefile που δείχνει πώς μπορούμε να δημιουργήσουμε ένα video με το πρόγραμμα ffmpeg χρησιμοποιώντας ως είσοδο αρχεία .gif, ένα αρχείο .mp3 για τον ήχο, και ένα αρχείο .srt για τους υπότιτλους. Μπορείτε να χρησιμοποιήσετε το Makefile αυτό και να το τροποποιήσετε με οποιοδήποτε τρόπο θέλετε, ο μόνος περιρισμός είναι ότι η εικόνα πρέπει να προέρχεται αποκλειστικά από τα GIF animations που παράγει το life_gif. Επίσης μπορείτε να προσθέσετε επιπλέον δυνατότητες στο life_gif αν το θεωρείτε σκόπιμο.

Ημερομηνία λήξης είναι η ημερομηνία παράδοσης της δεύτερης εργασίας του μαθήματος (έχετε δηλαδή αρκετό χρόνο μετά το τέλος της πρώτης εργασίας). Η παράδοση γίνεται δημιουργώντας ένα Markdown αρχείο στο repository του μέλους που δημιούργησε το life_gif με περιεχόμενα:

  • Ονομα ομάδας και λίστα μελών (αν θέλετε μπορείτε να συμμετέχετε και ανώνυμα, πρέπει να γνωρίζω τουλάχιστον το μέλος της ομάδας που δημιούργησε το video, αλλά δεν είναι απαραίτητο να το ανακοινώσω)
  • Youtube URL με το video
  • Πληροφορίες για το πώς μπορεί κάποιος να παράγει το video (θα πρέπει να περέχεται σχετικό Makefile, το οποίο να εκτελεί το life_gif με κατάλληλες παραμέτρους, και στη συνέχεια να παράγει το video από τα GIF που δημιουργήθηκαν).

Οι συμμετοχές θα κριθούν αποκλειστικά με αισθητικά κριτήρια κατόπιν ψηφοφορίας (ίσως γίνει προ-επιλογή σε περίπτωση μεγάλου αριθμού συμμετοχών). Τα μέλη των 2 νικητριών ομάδων θα μοιραστούν 200% και 100% bonus στην άσκηση (με μέγιστο 100% ανά άτομο).

Για έμπνευση: https://www.youtube.com/watch?v=C2vgICfQawE