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