uni

University stuff
git clone git://git.christosmarg.xyz/uni-assignments.git
Log | Files | Refs | README | LICENSE

assignment-5.tex (22237B)


      1 \documentclass{article}
      2 \usepackage[utf8]{inputenc}
      3 \usepackage[greek,english]{babel}
      4 \usepackage{alphabeta}
      5 \usepackage{fancyhdr}
      6 \usepackage{listings}
      7 \usepackage{mathtools}
      8 \usepackage{xcolor}
      9  
     10 % Settings
     11 
     12 \definecolor{codered}{rgb}{0,0.6,0}
     13 \definecolor{codegray}{rgb}{0.5,0.5,0.5}
     14 \definecolor{codegreen}{rgb}{0.0,0.66,0.42}
     15 \definecolor{hanblue}{rgb}{0.27,0.42,0.81}
     16 \definecolor{codeorange}{rgb}{1.0,0.55,0.0}
     17 
     18 \lstdefinestyle{mystyle}
     19 {
     20     commentstyle=\color{codegray},
     21     otherkeywords=
     22     {
     23         >,<,.,;,-,!,=,~,&,*,+,-,
     24         int8_t, % Add more types
     25         printf, scanf, exit % Add more functions
     26     },
     27     keywordstyle=\color{hanblue},
     28     numberstyle=\tiny\color{codegray},
     29     stringstyle=\color{codegreen},
     30     basicstyle=\ttfamily\small,
     31     breakatwhitespace=false,         
     32     breaklines=true,                 
     33     captionpos=b,                    
     34     keepspaces=true,                 
     35     numbers=left,                    
     36     numbersep=5pt,                  
     37     showspaces=false,                
     38     showstringspaces=false,
     39     showtabs=false,                  
     40     tabsize=4
     41 }
     42 
     43 % Colors the digits
     44 \lstset{literate=
     45    *{0}{{{\color{red!20!violet}0}}}1
     46     {1}{{{\color{red!20!violet}1}}}1
     47     {2}{{{\color{red!20!violet}2}}}1
     48     {3}{{{\color{red!20!violet}3}}}1
     49     {4}{{{\color{red!20!violet}4}}}1
     50     {5}{{{\color{red!20!violet}5}}}1
     51     {6}{{{\color{red!20!violet}6}}}1
     52     {7}{{{\color{red!20!violet}7}}}1
     53     {8}{{{\color{red!20!violet}8}}}1
     54     {9}{{{\color{red!20!violet}9}}}1
     55 }
     56 \lstset{style=mystyle}
     57 
     58 \pagestyle{fancy}
     59 \fancyhf{}
     60 
     61 % Document starts here
     62 
     63 \rhead{Εργασία 5}
     64 \lhead{Πίνακες - Δείκτες - Αρχεία}
     65 \rfoot{\thepage}
     66 
     67 \title{Εργασία 5: Πίνακες - Δείκτες - Αρχεία}
     68 \author{Χρήστος Μαργιώλης - Εργαστηριακό τμήμα 9}
     69 \date{Ιανουάριος 2020}
     70 
     71 \begin{document}
     72 
     73 \begin{titlepage}
     74     \maketitle
     75 \end{titlepage}
     76 
     77 \renewcommand{\contentsname}{Περιεχόμενα}
     78 \tableofcontents
     79 
     80 \section{Δομή προγραμμάτων και οδηγίες εκτέλεσης}
     81 
     82     \subsection{Εκτέλεση από Unix/Linux/Mac}
     83 
     84     Λόγω του ότι ορισμένες βιβλιοθήκες που έχω χρησιμοποιήσει δεν είναι συμβατές με τα Windows, τα προγράμματα,
     85     και \textit{κυρίως} ο ναρκαλιευτής, είναι περιορισμένα για συστήματα Unix.
     86 
     87 \begin{lstlisting}[language=bash]
     88 $ cd path-to-program
     89 $ make
     90 $ make run
     91 $ make run ARGS=txt/data40.txt #fcombinations MONO
     92 $ make clean
     93 \end{lstlisting}
     94     
     95     Προκειμένου να εκτελεστεί ο ναρκαλιευτής χρειάζονται τα παρακάτω dependencies:  
     96     \begin{itemize}
     97         \item cmake
     98         \item ncurses
     99         \item SDL2
    100         \item SDL2-mixer
    101     \end{itemize}
    102 
    103     \subsection{Δομή φακέλων}
    104 
    105     Το κάθε πρόγραμμα, είναι δομημένο ως εξής: Υπάρχουν πέντε \textit{βασικοί} φάκελοι, καθώς και ένα Makefile
    106     στο top directory. Στον φάκελο src βρίσκονται οι πηγαίοι κώδικες, στον include τα header
    107     files, στον οbj τα object files και στον bin το εκτελέσιμο αρχείο. Στον φάκελο txt
    108     υπάρχουν τα text files που διαβάζονται οι γράφονται από το κάθε πρόγραμμα.
    109     Το Makefile είναι υπεύθυνο για την μεταγλώττιση όλων των αρχείων μαζί, και την τοποθέτησή
    110     τους στους κατάλληλους φακέλους, την εκτέλεση των προγραμμάτων, καθώς και τον καθαρισμό των
    111     φακέλων (διαγράφει τα object files και το εκτελέσιμο με την εντολή make clean).
    112 
    113 \section{combinations - συνδυασμοί}
    114 
    115     \subsection{main.c}
    116         \lstinputlisting[language=C]{../combinations/src/main.c}
    117 
    118     \subsection{combinations.c}
    119         \lstinputlisting[language=C]{../combinations/src/combinations.c}
    120 
    121     \subsection{combinations.h}
    122         \lstinputlisting[language=C]{../combinations/include/combinations.h}
    123 
    124     \subsection{arrhandler.c}
    125         \lstinputlisting[language=C]{../combinations/src/arrhandler.c}
    126 
    127     \subsection{arrhandler.h}
    128         \lstinputlisting[language=C]{../combinations/include/arrhandler.h}
    129 
    130     \subsection{Περιγραφή υλοποιήσης}
    131 
    132     Το πρόγραμμα αυτό, όπως και τα ακόλουθα 2 προγράμματα, έχουν ως στόχο την εμφάνιση
    133     συνδυασμών, εφόσον πληρούν τις προϋποθέσεις του φύλλου εργασίας. Όσο αφορά το πρόγραμμα όμως,
    134     στο main.c αποθηκεύεται η τιμή του Ν, ο πίνακας Ν θέσεων που έχει τα στοιχεία που δίνει ο χρήστης,
    135     καθώς και τα ζευγάρια $x_{1}$, $x_{2}$, $y_{1}$ και $y_{2}$. Από την main, τέλος, καλείται και η
    136     συνάρτηση εκτύπωσης των συνδυασμών, από την οποία καλούνται επιπλέον συναρτήσεις προκειμένου να εκτελεστεί
    137     σωστά αυτή η λειτουργία.  
    138     
    139     Στο arrhandler.c γίνεται όλος ο χειρισμός του πίνακα - δηλαδή, η \textit{δυναμική} του δέσμευση,
    140     το γέμισμα του, στο όποιο εκτελούνται συναρτήσεις για τον έλεγχο του αν ένας αριθμός κατά την εισαγωγή τιμών
    141     έχει ήδη εισαχθεί, και αν τηρούνται τα όρια $[1, 49]$. Επίσης, γίνεται ταξινόμηση του πίνακα με τον αλγόριθμο
    142     quicksort, και τέλος, μία επιπλέον λειτουργία, που θα αναλυθεί στην συνέχεια.  
    143 
    144     Στο combinations.c, γίνονται όλες οι λειτουργίες που αφορούν τους συνδυασμούς, τα ζευγάρια $x$ και $y$, και τους
    145     ελέγχους για το αν τηρούνται οι εξής προϋποθέσεις προκειμένου να εμφανιστεί ένας συνδυασμός 6 αριθμών.
    146     
    147     \begin{itemize}
    148         \item Το πλήθος των αρτίων αριθμών του συνδυασμού να βρίσκεται στο διάστημα $[x_{1}, x_{2}]$
    149         \item Το άθροισμα των έξι αρθιμών του συνδυασμού να βρίσκεται στο διάστημα $[y_{1}, y_{2}]$
    150     \end{itemize}
    151 
    152     Έπειτα, μετριούνται πόσοι συνδυασμοί δεν πληρούσαν τον πρώτο όρο ή μόνο τον δεύτερο όρο, ποιοί συνδυασμοί τυπώθηκαν,
    153     καθώς και την συχνότητα εμφάνισης του κάθε στοιχείου στο σύνολο των συνδυασμών που τυπώθηκαν.
    154     Για την τελευταία λειτουργία, χρησιμοποιείται η συναρτήση findpos() που βρίσκεται στο arrhandler.c, και ελέγχει για κάθε
    155     στοιχείο του τρέχοντως συνδυασμού, ποια θέση έχει στον πίνακα Ν θέσεων, η οποία αντιστοιχίζεται με έναν τρίτο πίνακα,
    156     τον freqArr, στον οποίο αποθηκεύονται ως ακέραιες τιμές η συνχότητες εμφάνισης του κάθε στοιχείου.
    157     Ο λόγος που χρειάζεται μια συνάρτηση που βρίσκει την τοποθεσία του κάθε στοιχείου στον πίνακα Ν θέσεων είναι ώστε να αυξηθεί κατά 
    158     ένα κάθε φορά ο πίνακας των συχνοτήτων στην κατάλληλη θέση, η οποία όπως προανέφερα, αντιστοιχεί στο στοιχείο του πίνακα Ν θέσεων, 
    159     δηλαδή στο στοιχείο που έλεγχεται κάθε φορά κατα την προσπέλαση του πίνακα του τρέχοντως συνδυασμού.
    160 
    161 \section{kcombinations - συνδυασμοί με K}
    162 
    163     \subsection{main.c}
    164         \lstinputlisting[language=C]{../kcombinations/src/main.c}
    165 
    166     \subsection{kcombinations.c}
    167         \lstinputlisting[language=C]{../kcombinations/src/kcombinations.c}
    168 
    169     \subsection{kcombinations.h}
    170         \lstinputlisting[language=C]{../kcombinations/include/kcombinations.h}
    171 
    172     \subsection{arrhandler.c}
    173         \lstinputlisting[language=C]{../kcombinations/src/arrhandler.c}
    174 
    175     \subsection{arrhandler.h}
    176         \lstinputlisting[language=C]{../kcombinations/include/arrhandler.h} 
    177 
    178     \subsection{Περιγραφή υλοποιήσης}
    179 
    180     Όπως και στο προηγούμενο πρόγραμμα, το combinations, το kcombinations λειτουργεί με τον ίδιο ακριβώς τρόπο,
    181     με την διαφορά οτι η σταθερά COMBSN = 6 του προηγούμενου προγράμματος έχει αντικατασταθεί με την μεταβλητή Κ,
    182     η οποία δίνεται κάθε φορά από τον χρήστη.
    183 
    184 \section{fcombinations - συνδυασμοί από αρχείο}
    185 
    186     \subsection{main.c}
    187         \lstinputlisting[language=C]{../fcombinations/src/main.c}
    188 
    189     \subsection{fcombinations.c}
    190         \lstinputlisting[language=C]{../fcombinations/src/fcombinations.c}
    191 
    192     \subsection{fcombinations.h}
    193         \lstinputlisting[language=C]{../fcombinations/include/fcombinations.h}
    194 
    195     \subsection{arrhandler.c}
    196         \lstinputlisting[language=C]{../fcombinations/src/arrhandler.c}
    197 
    198     \subsection{arrhandler.h}
    199         \lstinputlisting[language=C]{../fcombinations/include/arrhandler.h} 
    200 
    201     \subsection{Περιγραφή υλοποιήσης}
    202 
    203     Το πρόγραμμα αυτό, επίσης όπως και τα δύο προηγούμενα προγράμματα, λειτουργεί με την ίδια λογική
    204     ακριβώς, με την διαφορά οτι όλα τα δεδομένα διαβάζονται από αρχείο, το οποίο σημαίνει ότι σε αυτό το
    205     πρόγραμμα δεν υπάρχουν όλες οι printf() - scanf() που ζητάνε από τον χρήστη να εισάγει δεδομένα, εφόσον έχουν
    206     αντικατασταθεί από την fscanf() η οποία θα διαβάσει τα δεδομένα από αρχείο. 
    207 
    208 \section{minesweeper - ναρκαλιευτής}
    209 
    210     \subsection{main.c}
    211         \lstinputlisting[language=C]{../ncurses-minesweeper/src/main.c}
    212 
    213     \subsection{minesweeper.c}
    214         \lstinputlisting[language=C]{../ncurses-minesweeper/src/minesweeper.c}
    215 
    216     \subsection{minesweeper.h}
    217         \lstinputlisting[language=C]{../ncurses-minesweeper/include/minesweeper.h}
    218 
    219     \subsection{gameplay.c}
    220         \lstinputlisting[language=C]{../ncurses-minesweeper/src/gameplay.c}
    221 
    222     \subsection{gameplay.h}
    223         \lstinputlisting[language=C]{../ncurses-minesweeper/include/gameplay.h}
    224 
    225     \subsection{navigation.c}
    226         \lstinputlisting[language=C]{../ncurses-minesweeper/src/navigation.c}
    227 
    228     \subsection{navigation.h}
    229         \lstinputlisting[language=C]{../ncurses-minesweeper/include/navigation.h}
    230 
    231     \subsection{settings.c}
    232         \lstinputlisting[language=C]{../ncurses-minesweeper/src/settings.c}
    233 
    234     \subsection{settings.h}
    235         \lstinputlisting[language=C]{../ncurses-minesweeper/include/settings.h}
    236 
    237     \subsection{outputs.c}
    238         \lstinputlisting[language=C]{../ncurses-minesweeper/src/outputs.c}
    239 
    240     \subsection{outputs.h}
    241         \lstinputlisting[language=C]{../ncurses-minesweeper/include/outputs.h}
    242 
    243     \subsection{wins.c}
    244         \lstinputlisting[language=C]{../ncurses-minesweeper/src/wins.c}
    245 
    246     \subsection{wins.h}
    247         \lstinputlisting[language=C]{../ncurses-minesweeper/include/wins.h}
    248 
    249     \subsection{audio.c}
    250         \lstinputlisting[language=C]{../ncurses-minesweeper/src/audio.c}
    251 
    252     \subsection{audio.h}
    253         \lstinputlisting[language=C]{../ncurses-minesweeper/include/audio.h}
    254 
    255     \subsection{Περιγραφή υλοποιήσης}
    256 
    257     Ο ναρκαλιευτής αυτός χρησιμοποιεί ώς βασική βιβλιοθήκη την ncurses και είναι δομημένος ως εξής:
    258     Από το main.c καλούνται αρχικά οι συναρτήσεις δημιουργίας των παραθύρων που θα εμφανιστούν
    259     στην οθόνη και στην συνέχεια καλούνται οι συναρτήσεις δημιουργίας των πινάκων $Μ \times N$,
    260     για το ναρκοπέδιο και για τον πίνακα που έχει "κρυμμένα" τα κελιά αντίστοιχα.
    261     Τέλος από την main καλείται η συνάρτηση που θα ξεκινήσει το παιχνίδι και την μουσική.  
    262 
    263     Οι συναρτήσεις για τον ορισμό στηλών, γραμμών, και αριθμό των ναρκών βρίσκονται στο settings.c.
    264     Τα όρια των διαστάσεω που μπορεί να δώσει ο χρήστης καθορίζονται από το μέγεθος της οθόνης του, το
    265     οποίο αποθηκεύεται στις μεταβλητές yMax και xMax. Στο wins.c υπάρχουν όλες οι συνάρτησεις δημιουργίας παραθύρων.  
    266 
    267     Στο minesweeper.c εκτελούνται όλες οι συναρτήσεις δημιουργίας πινάκων, τοποθέτησεις ναρκών,
    268     μέτρημα των ναρκών στα γειτονικά κελιά, καθώς και γέμισμα των κενών θέσεων τους.  
    269 
    270     Έπειτα, στο gameplay.c εκτελείται το παιχνίδι - αρχικά τυπώνεται ο πίνακας και το περίγραμμα που
    271     υπάρχει ανάμεσα σε κάθε κελί ώστε να είναι πιο εμφανίσιμο και πιο εύχρηστο το παιχνίδι. Προκειμένου
    272     τα κελιά να τοποθετηθούν στις κατάλληλες θέσεις στον πίνακα, δηλαδή να είναι ανάμεσα στα [ ],
    273     τα στοιχεία των πινάκων τοποθετούνται κάθε φορά με απόσταση δύο χαρακτήρων στον κάθετο άξονα και 
    274     τριών χαρακτήρων στον οριζόντιο, το ένα από το άλλο. Με αυτά τα δύο νούμερα προκύπτουν και τέσσερις 
    275     τύποι, οι οποίοι βοηθάνε στην σωστή προσπέλαση των στοιχείων των πινάκων κατά την διάρκεια του παιχνιδιού,
    276     και στον υπολογισμό των διαστάσεων του παραθύρου που εμφανίζεται το πεδίο. Οι τύποι είναι οι εξής
    277 
    278     \begin{equation}
    279         x_{win} = 3cols + 2
    280     \end{equation}
    281     \begin{equation}
    282         x_{board} = \frac{(x_{win}-2)}{3}
    283     \end{equation}
    284     \begin{equation}
    285         y_{win} = rows + 2
    286     \end{equation}
    287     \begin{equation}
    288         y_{board} = y_{win}-2
    289     \end{equation}
    290 
    291     Οι τύποι (2) και (4) μετατρέπουν την θέση του κέρσορα στην οθόνη σε θέσεις πίνακα.    
    292     Αφού τυπωθεί στην οθόνη ο πίνακας με κρυμμένα τα στοιχεία του, \textit{ο οποίος είναι στην ουσία ένας 
    293     $Μ \times N$ πίνακας γεμισμένος με κενά αρχικά}, ξεκινάει το βασικό loop του παιχνιδιού, στο οποίο
    294     ο χρήστης μετακινείται από κελί σε κελί, επιλέγει την κίνηση που θέλει να κάνει πάνω σε κάθε κελί,
    295     και είτε χάνει είτε νικάει. Προκειμένου να λειτουργήσει κάτι τέτοιο, μέσα στο loop γίνονται οι εξής
    296     λειτουργίες: Αρχικά ο κέρσορας μετακίνεται κάθε φορά που και ο χρήστης μετακινείται ώστε να μπορεί να δει 
    297     σε ποιο κελί βρίσκεται κάθε στιγμή, και στην συνέχεια, μπορούν να εκτελεστούν σε κάθε κελί οι εξής λειτουργίες:
    298     \begin{itemize}
    299         \item Άνοιγμα κελιού
    300         \item Flag ένα κελί
    301         \item Εξουδετέρωση νάρκης (μόνο αν το κελί είναι ήδη flagged)
    302     \end{itemize}
    303     Σε περίπτωση όμως που ο χρήστης κάνει flag ένα κελί που δεν περιέχει νάρκη, και προσπαθήσει να βγάλει την νάρκη,
    304     ή ανοίξει κελί το οποίο περιέχει νάρκη, θα χάσει. Οπότε το παιχνίδι νικιέται \textit{μόνο} όταν ο χρήστης βγάλει 
    305     όλες τις νάρκες από το πεδίο, και όχι όταν ανοίξει όλα τα κελιά που δεν έχουνε νάρκες, όπως συμβαίνει στον ναρκαλιευτή των Windows.  
    306 
    307     Συνοπτικά, τα υπόλοιπα αρχεία χειρίζονται ορισμένες λειτουργίες του παιχνιδιού, όπως την κίνηση από κελί σε κελί,
    308     τον χειρισμό των εμφανίσεων διαφόρων μηνυμάτων στην οθόνη, και τον ήχο. Συγκεκριμένα για τον ήχο χρησιμοποίησα την
    309     βιβλιοθήκη SDL2 σε συνδυασμό με την βιβλιοθήκη PThread ώστε να μπορούν να εκτελούνται \textit{"ταυτόχρονα"} και οι
    310     συναρτήσεις χειρισμού ήχου, και το υπόλοιπο παιχνίδι. 
    311 
    312 \section{Διευκρινήσεις}
    313 
    314     Αρχικά, λόγω του ότι το πρόγραμμα περιέχει πολλές μεταβλητές και συναρτήσεις θεώρησα καλύτερο να εστιάσω στην λειτουργία 
    315     του προγράμματος γενικότερα και όχι τόσο στο τι συμβολίζει η κάθε μεταβλητή/συνάρτηση, το οποίο θα μπορούσε
    316     να γίνει αρκετά κουραστικό. Τα αρχεία και οι συναρτήσεις είναι χωρισμένα έτσι ώστε να εξηγούν από το όνομα τους μόνο ακριβώς ποιες λειτουργίες
    317     εκτελούνται μέσα σε αυτά ώστε να είναι πιο εύκολη η μετέπειτα κατανόηση, συντήρηση ή βελτίωση του προγράμματος. Bέβαια, κατανοώ ότι
    318     αυτή η προσέγγιση μπορεί να θεωρηθεί πολύ συνοπτική ή και πρόχειρη.  
    319 
    320     Επίσης, η συγγραφή αυτή τη φορά έγινε στο \LaTeX, λόγω του ότι κάνει αυτόματη στοίχηση, χρωματισμό στους
    321     κώδικες, και γενικώς πολύ πιο πρακτικό τον χειρισμό μεγάλων εγγράφων, αλλά δεν κατάφερα δυστυχώς να βρω τρόπο
    322     να αλλάξω την ελληνική γραμματοσειρά σε κάποια πιο εύκολη στο διάβασμα.  
    323     
    324     Τέλος, όσο αφορά τον ναρκαλιευτή, θα ήθελα να σημειώσω οτι έχει πολύ περιθώριο για βελτιώση (και λίγο καθαρισμό στον κώδικα),
    325     και πολλές λειτουργίες, όπως ο ήχος και το multithreading, τις έβαλα περισσότερο πειραματικά, οπότε είναι αρκετά πιθανό να περιέχουν τυχόν
    326     κακές πρακτικές ή και λάθη, αλλά θεώρησα ότι ήταν μία καλή ευκαιρία για πειραματισμό. Ένα πρόβλημα το οποίο δεν κατάφερα
    327     να λύσω ήταν το να κάνουν αυτόματο resize τα παράθυρα σε περίπτωση που αλλάξει το μέγεθος του terminal. Μία λειτουργία που 
    328     θα βάλω στο μέλλον επίσης είναι να δίνεται η επιλογή στον χρήστη να ξαναπαίξει αν θέλει, πιθανώς πατώντας το κουμπί r (restart),
    329     καθώς και να βάλω χρώματα στους αριθμούς, ώστε να είναι πιο ευδιάκριτοι και να είναι πιο ξεκούραστο στο μάτι το πρόγραμμα.
    330 
    331 \section{Εργαλεία}
    332 
    333     \begin{itemize}
    334         \item Editors: Visual Studio Code, NVim
    335         \item Compiler: gcc
    336         \item Βιβλιοθήκες: SDL2, PThread, ncurses
    337         \item Shell: zsh
    338         \item OS: Arch Linux
    339         \item Συγγραφή: \LaTeX
    340     \end{itemize}
    341 
    342 \end{document}
    343