[Προγραμματιστικές Τεχνικές] Task 5 - Κυριακή, 11/12 11:55 μμ

[Thmmy.gr portal]

  Thmmy.gr portal
   Forum
   Downloads
   Ενεργ. Λογαριασμού
   Επικοινωνία
  
  Χρήσιμα links
   Σελίδα τμήματος
   Βιβλιοθήκη Τμήματος
   Elearning
   Φοιτητικά fora
   Πρόγραμμα Λέσχης
   Πρακτική Άσκηση
   Ηλεκτρονική Εξυπηρέτηση Φοιτητών
   Διανομή Συγγραμμάτων
   Ψηφιακό Καταθετήριο Διπλωματικών
   Πληροφορίες Καθηγητών
   Instagram @thmmy.gr
   mTHMMY
  
  Φοιτητικές Ομάδες
   ACM
   Aristurtle
   ART
   ASAT
   BEAM
   BEST Thessaloniki
   EESTEC LC Thessaloniki
   EΜΒ Auth
   IAESTE Thessaloniki
   IEEE φοιτητικό παράρτημα ΑΠΘ
   SpaceDot
   VROOM
   Panther
  

THMMY.gr Web

Helios_MultiScribbles2SMF Default ThemeSMFone_Blue

[Ανεβάζετε τα θέματα των εξετάσεων στον τομέα Downloads]

Είσαι πρωτοετής;... Καλώς ήρθες! Μπορείς να βρεις πληροφορίες εδώ. Βοήθεια για τους καινούργιους μέσω χάρτη.

Κατεβάστε εδώ το Android Application για εύκολη πρόσβαση στο forum.

Ανεβάζετε τα θέματα των εξετάσεων στον τομέα Downloads με προσοχή στα ονόματα των αρχείων!

Για ανανέωση (ή προσθήκη νέου) avatar, πρέπει η μεγαλύτερη διάσταση της εικόνας να είναι 110 pixels.

[leukosaraphs!]

Ανέβηκε η πέμπτη εργασία του μαθήματος εδώ. Happy programming

Programming Task 5

Κατάθεση εργασίας για βαθμολογία

• Κατεβάζετε τα συνοδευτικά αρχεία της Άσκησης (code.zip)
• Συμπληρώνετε τα τμήματα του κώδικα που λείπουν στο αρχείο, maze.cc.
  
• Δοκιμάζετε τον κώδικα σε περιβάλλον Linux ή cygwin τρέχοντας make clean; make
  
• Εναλλακτικά, μπορείτε να χρησιμοποιήσετε όποιο IDE - περιβάλλον επιθυμείτε για την μεταγλώττιση του προγράμματος.
• Ανεβάστε το αρχείο με τις δικές αλλαγές στο CMS
  
• Επαναλάβετε τα βήματα 2-4 μέχρι η βαθμολογία να σας είναι ικανοποιητική, ή παρέλθει ο χρόνος παράδοσης, ή βρείτε να κάνετε κάτι καλύτερο με το χρόνο σας.

Mazes!
In this assignment you will create a class to represent mazes. Mazes are a bit tricky because the most important things - the walls - sit between the cells. Let's say we have the following maze:


3 × 4 maze

The cells form a 2D grid, which we shall reference with (row, column) coordinates. Cell (0, 0) is the starting point, and cell (2, 3) is the ending point.

We can represent the maze with an array, but we also need to be able to store the walls somewhere. One approach for representing mazes is to add extra rows and columns between cells, where the walls themselves will be represented. Therefore, the above maze would be stored like this:


Representation of 3 × 4 maze

The green boxes are the cells themselves, and the yellow boxes represent the walls. The white boxes are unused in this representation, which may seem a bit wasteful, but we won't be creating giant mazes, so we'll pick a clear and slightly wasteful representation, rather than a confusing and extremely efficient one.

You can see that for a maze of size N_rows × N_cols, our representation requires a total of (2N_rows + 1)×(2N_cols + 1) elements. For our above example, with 3 rows and 4 columns, we would need (2 ⋅ 3 + 1)×(2 ⋅ 4 + 1) cells, or 7 × 9 cells.
C++ and Multidimensional Arrays

C++ doesn't have very good support for dynamically allocated multidimensional arrays; languages like Java are much better at this kind of thing. In C++, we typically allocate a 1-dimensional array with enough space for the total number of elements, and then map our 2D (or 3D, or whatever) coordinates into our 1D array. For example, given a 2D array with N_rows rows and N_cols columns:

• The program can allocate a 1D array with N_rows × N_cols elements
• An element at 2D position (row, col) can be mapped to row × N_cols + col

This mapping should make sense: for each row we are going to skip, we must move past N_cols cells to get to the next row. Of course, this is not the only way we can map 2D coordinates into the 1D array, but this is the typical approach for C and C++. It is called a row-major order. (A few other languages, like MATLAB and Fortran, use a column-major order for how they represent multidimensional arrays.)
Accessing Maze Cells and Walls

In order to provide a simple abstraction for people to use, we will implement a Maze class that uses cell coordinates to reference various aspects of the maze, but internally we will map cell coordinates into the "expanded representation" we use internally. We will call the coordinates in the expanded representation expanded coordinates.

You should be able to see how to map cell coordinates into expanded coordinates very easily. Given a maze with N_{cell − rows}× N_{cell − cols} cells, we can map the cell coordinates (r_cell, c_cell) into expanded coordinates (r_exp, c_exp) as follows:

• r_exp = 2r_cell + 1
• c_exp = 2c_cell + 1

Given a particular cell, we will want to know if there is a wall on a particular side of the cell; we will use the cardinal directions "North", "East", "South" or "West" of the cell. Then, we can ask questions like:

• Is there a wall to the west (left) of cell (1, 2) in the original maze? Yes.
• Is there a wall to the north of cell (2, 3) in the maze? No.

Accessing the walls between cells is similarly straightforward:

• To access the wall north of a given cell, compute the cell's expanded coordinates and subtract 1 from the row value.
• To access the wall south of a given cell, compute the cell's expanded coordinates and add 1 to the row value.
• To access the wall east of a given cell, compute the cell's expanded coordinates and add 1 to the column value.
• To access the wall west of a given cell, compute the cell's expanded coordinates and subtract 1 from the column value.

Your Tasks

You will need to complete the implementation of the Maze class. There are quite a few member functions to implement, but you should not worry about this since the vast majority of them will end up being only a few lines long, at most. Only a few of these functions will actually require careful thought.

To help you know what you need to do, we are providing you with an initial version of maze.hh. This file contains the following:

• A declaration of the Maze class, which includes all operations you must support. Feel free to add member functions if you wish (in particular, private helper functions), but don't change the public interface that the class specifies!
• A MazeCell enumeration that specifies all the values that cells in the expanded representation of the maze can take on. You should not need to change this.
• A Direction enumeration that specifies the cardinal directions that are used by the maze code. You should not need to change this.
• A Location class that can be used to represent (row, column) locations. You shouldn't need to make any changes to this class.

The reason for the Location class is that C++ functions cannot return more than one value, but it is very helpful to be able to return a (row, col) value from various functions. Thus, we can package the row and column value into a Location object, and return that object from a function.

The required operations in the maze class are explained in the comments in the maze.hh header file. Feel free to ask for any clarifications.
Suggested Approach

You will need to dynamically allocate an array for the expanded representation of the maze using the heap. Since you are dynamically allocating memory, you will need to write a destructor to free the memory, and a copy-constructor and an assignment operator to handle copying and assignment correctly. (That is, you will need to perform a deep copy, not a shallow copy.) This is the Rule of Three - if you implement a copy-constructor, assignment operator, or destructor for your class, you really should implement all three.

If you create simple abstractions for your class, you will find that your implementation goes much easier. For example, you need to implement these private helper functions in maze.cc:

 

Code:

 // Take 2D expanded coordinates and compute the corresponding 1D array index
  int getArrayIndex(const Location &loc) const;

  // Returns the expanded coordinates of the specified cell coordinates
  Location getCellArrayCoord(int cellRow, int cellCol) const;
  
  // Returns the expanded coordinates of the wall on a specific side of
  // a cell given in cell coordinates
  Location getWallArrayCoord(int cellRow, int cellCol,
                             Direction direction) const;

Then, your other functions can use these helpers to perform their tasks. By taking this approach, you minimize the number of places where you will have to write the tricky array-indexing operations that are so easy to get wrong. If you have bugs, you will only have to fix them in one place.

Use assertions liberally! Here are some ideas; if you see other places to use assertions, put them there too!

• Check every set of incoming coordinates to be sure they are in the proper range.
• Check row coordinates and column coordinates in separate assertions.
• As indicated in the comments for getNeighborCell(), trip an assertion if someone tries to get a neighbor cell that is invalid.

Probably the hardest function to write will be the print() function. You can use the << stream-output operator on the ostream object, just as if it were cout. You may want to follow a structure like the following:

  

Code:

Output the number of cell-rows and cell-columns
  
  For each row r from 0 to numRows - 1:
      Output the walls above row r
      Output the cells in row r, along with the walls in between those cells
      
  Finally, output the walls below the last row

Testing

You can download the tester to exercise your maze code. It performs a pretty exhaustive battery of tests, so by the time your program passes all the tests, you should have a pretty high confidence that it works. You can compile and run the test program like this:

Code:

  make clean; make

All Done?

When you have finished your maze program, you should submit your completed maze.cc files on the CMS.

Edit: Μεγάλωσα το μέγεθος των εικόνων.
Edit2: Ανέβασα το διορθωμένο code.zip.

[MrRobot]

Για όσους αρχίσουν την άσκηση προσέξτε στο maze.cc στην τελευταία συνάρτηση (print) κανονικά πρέπει να γράφει

Code:

void Maze::print(ostream &os) const

Βέβαια πρέπει να έχει ανέβει καινουργιο code.zip στο elearning που το έχει διορθωμένο αυτό το σημείο.

[kongr45gpen]

Version 2 -- 28/11/2016 10:25

• Διορθώθηκε το void Maze::print(ostream &os) const

[TheoProt]

Στην getArrayIndex(...) πρέπει να επιστρέφουμε τις τιμές των δύο συντεταγμένων ;

[MrRobot]

Όταν φτιάχνεις τον πίνακα cells στην ουσία αναπαριστας έναν διδιάστατο πίνακα με τη βοήθεια ενός μονοδιάστατο. Ή getArrayIndex() πρέπει να μετατρέπει τις διδιαστατες συντεταγμένες σε μονοδιάστατης . Για παράδειγμα αν έχεις έναν πίνακα με 3 γραμμές και 4 στήλες τότε για να πάρεις τη μονοδιάστατη συντεταγμένη του κελιού που βρίσκεται στη δεύτερη γραμμή στην πρώτη στήλη θα πεις 2*μηκος_γραμμης +1. Το μονο που πρέπει να προσέχεις είναι ότι οι συντεταγμένες ξεκινάνε από το 0.

[TheoProt]

Όταν φτιάχνεις τον πίνακα cells στην ουσία αναπαριστας έναν διδιάστατο πίνακα με τη βοήθεια ενός μονοδιάστατο. Ή getArrayIndex() πρέπει να μετατρέπει τις διδιαστατες συντεταγμένες σε μονοδιάστατης . Για παράδειγμα αν έχεις έναν πίνακα με 3 γραμμές και 4 στήλες τότε για να πάρεις τη μονοδιάστατη συντεταγμένη του κελιού που βρίσκεται στη δεύτερη γραμμή στην πρώτη στήλη θα πεις 2*μηκος_γραμμης +1. Το μονο που πρέπει να προσέχεις είναι ότι οι συντεταγμένες ξεκινάνε από το 0.

Μήκος γραμμής εννοείς πόσα cells υπάρχουν στον διδιάστατο μέχρι να φτάσουμε στο κελί που θέλουμε ;

[konsalex]

Παιδια πως κάνουμε test απο Codeblocks πχ ή απο καθε ενα IDE?

Για παραδειγμα θελω να δω αν λειτουργει σωστα η πρωτη function int Maze::getArrayIndex(const Location loc) const

[MrRobot]

Μήκος γραμμής εννοείς πόσα cells υπάρχουν στον διδιάστατο μέχρι να φτάσουμε στο κελί που θέλουμε ;

Μήκος γραμμής είναι το μήκος των γραμμών του διδιαστατου πίνακα, δηλαδή στην περιπτωση μας 2*numCols+1 που είναι το συνολικό μήκος μιας γραμμής του expanded λαβυρίνθου.

[MrRobot]

Tips για την λύση της άσκησης

Αφού φορτωσετε τα αρχεία σε όποιο περιβάλλον κάνετε την εργασία (Linux, codeblocks, visual studio, κτλ)υπάρχει το πρόβλημα ότι δεν μπορεί να γίνει built το project (στα liux δεν ξέρω αν υπάρχει πρόβλημα) γιατί οι συναρτήσεις στο maze.cc δεν επιστρέφουν κάτι ενώ είναι τύπου int , Location κτλ. Αρα μπορείτε να βαλετε να επιστρέφουν κάποια "dummy values" , πχ return 0 στις int και αντίστοιχα στους άλλους τύπους τύπους. Επίσης εμένα με βοήθησε να δω το test-maze.cc και να φτιάχνω τις συναρτήσεις του maze.cc με τις σειρά που τις ελέγχει το πρώτο. Μόλις κάνετε σωστά τις συναρτήσεις που ελέγχει το κάθε τεστ θα σας βγάζει OK εκτελώντας το project

Happy Coding 

[kongr45gpen]

CMS Programming Task 5
by Φλωρος Δημητριος - Saturday, 3 December 2016, 7:38 PM
 

Για την επιτυχή υποβολή του αρχείου, πρέπει να αλλάξετε την πρώτη γραμμή του αρχείου maze.cc σε

#include "ps5.h"

Αλλιώς θα σας βγάλει compile error. Για να δοκιμάζετε τον κώδικα τοπικά, χρησιμοποιείτε κανονικά

#include "maze.hh"

Version 3 -- 04/12/2016 13:22

• Προστέθηκε διευκρίνιση για το παραπάνω (προσοχή, το ps5.h θέλει μόνο ένα h στο τέλος!).

[JasonV97]

Παιδιά να ρωτήσω, στη getNeighborCell, όταν δοθεί κάποιο από τα τετράγωνα που δεν έχει γειτονικό, τι υποτίθεται πρέπει να κάνουμε?

[kongr45gpen]

Παιδιά να ρωτήσω, στη getNeighborCell, όταν δοθεί κάποιο από τα τετράγωνα που δεν έχει γειτονικό, τι υποτίθεται πρέπει να κάνουμε?

Δεν χρειάζεται να κάνεις κάτι, αν θες όμως μπορείς να βάλεις μερικές assert στον κώδικά σου (π.χ. στην Maze::getArrayIndex() για να ελέγχονται όλες οι προσπελάσεις), ώστε να βγάζει error το πρόγραμμα και να μην κρασάρει.

[Egkelados]

Στη συνάρτηση

Code:

MazeCell getCell(int cellRow, int cellCol) const;

και γενικά σε όλες όσες έχουν ορίσματα τα cellRow και cellCol, αυτά δίνονται σε cell-coordinates ή σε expanded cell-coordinates?

[kongr45gpen]

Στη συνάρτηση

Code:

MazeCell getCell(int cellRow, int cellCol) const;

και γενικά σε όλες όσες έχουν ορίσματα τα cellRow και cellCol, αυτά δίνονται σε cell-coordinates ή σε expanded cell-coordinates?

Δίνονται σε καθαρά cell coordinates (εξ' άλλου, υποτίθεται πως τα expanded coordinates είναι θέμα της υλοποίησης της Maze, και ο κώδικας έξω από αυτήν δεν γνωρίζει για την εσωτερική αναπαράσταση των κελιών και των τοίχων, οπότε όλες οι public συναρτήσεις καλούνται με τις απλές συντεταγμένες του κελιού).

[Egkelados]

Ευχαριστώ πολύ για τη διευκρίνηση!