BBM203-Assignment 1 Multi-dimensional array, matrix Solved

In this experiment, you are expected to implement an application which is the logic core simulator of a simple hidden treasure game. Main focus point of this experiment is to get you familiar with arrays, matrices, dynamic memory allocation and read-write files. Implementing the program without using the benefits of dynamic memory allocation will be penalized.

1           Background Information
1.1          C++ language
C++ was developed by Bjarne Stroustrup, as an extension to the C language. It gives programmers a high level of control over system resources and memory.

C++ is one of the world’s most popular programming languages. It can be found in today’s operating systems, Graphical User Interfaces, and embedded systems. It is an object-oriented programming language which gives a clear structure to programs and allows code to be reused, lowering development costs.

1.2          Arrays
An array is a series of elements of the same type placed in contiguous memory locations that can be individually referenced by adding an index to a unique identifier. It can be used to store the collection of primitive data types such as int, float, double, char, etc of any particular type. To add to it, an array in C++ can store derived data types such as structures, pointers etc.

C++ allows programmers to create statically or dynamically allocated arrays. A statically allocated array variable is a constant pointer that points to a fixed size array in automatic storage (i.e. the call stack). In contrast, pointer variables can be used to point to arrays allocated in dynamic memory (known as the heap or free store) that can be assigned different addresses (of other arrays in dynamic memory).

 

One more important point that you need to remember when we have allocated the memory in heap and after some time during the execution of the program if that memory is no more required then we must delete the memory. If we don’t delete the unused memory then it causes a memory leak problem.

1.3             Multi-dimensional arrays
A multi-dimensional array can be termed as an array of arrays that stores homogeneous data in tabular form (row× column) which is also known as matrix. We can create arrays with any number of dimensions. However, the complexity also increases as the number of dimensions increases. The most used multidimensional array is the Two-Dimensional Array.

1.4          Dynamic memory allocation
The task of fulfilling an allocation request consists of locating a block of unused memory of sufficient size. Memory requests are satisfied by allocating portions from a large pool of memory called the heap or free store. At any given time, some parts of the heap are in use, while some are ”free” (unused) and thus available for future allocations. There may be cases where the memory needs of a program can only be determined during runtime. For example, when the memory needed depends on user input. On these cases, programs need to dynamically allocate memory, for which the C++ language integrates the operators new and delete.

1.5          Online resources
•    C++ Tutorial

•    C++ Wikipedia

2           Experiment
In this experiment, it is aimed to find the hidden treasure within a treasure map designed as a matrix. For this purpose, the map and key data must be read from the file. Afterwards, the key must be moved on the map depending on the rules. The result of the multiplication of the map matrix and the key matrix will give an idea of the place of the treasure.

 

You should use matrix structure to implement all these operations in the C++ programming language. To store the matrices, you must use dynamic memory allocation.

 

Figure 1: An Example for Treasure Map Matrix

The treasure map is designed as a matrix as shown in Figure 1. The size of the map matrix is not fixed but must be determined according to the input file that will be given at runtime. Each element of the map matrix is a number. Map matrix may include negative or more than one digit numbers. The elements of the matrix placed in the edges are zeros. That show you the boundary of the map.

 

Figure 2: An Example for Key Matrix

As shown in Figure 2, the key is designed as a square matrix with degree n that is an odd value (e.g. 3,5,7). n is a variable that will be determined at runtime. By using the key matrix, the hidden treasure can be found in the map.

In order to find treasure, we slide the key matrix on the map. The part of the map matrix that is covered by the key specify a sub-matrix on the map. By multiplying the key matrix by the obtained sub-matrix, we find the direction of the next sliding. The direction is computed by taking mod five of multiplication result (result % 5). The result of the mod operation is interpreted as follows:

(Result%5)
0
1
2
3
4
Action
Found treasure
Go up
Go down
Go right
Go left
The search operation must be started from the top left corner of the map matrix. The details of the first step are shown in Figure 3. In order to get a full score from this assignment, you have to design search function recursively.

 

Figure 3: Start search

A: Sub-matrix

B: Key Matrix

C: Multiplication of matrices A and B (Dot product) (Summation of all product of each corresponding entries).

D: Remaining part of the mod (5,C)

E: Estimated direction

F: Final direction

G: Output: write center cell address of sub-matrix (with the order Row, Column) and C P.S. If the C is negative, then add 5 in negative cases.

In case of key matrix is placed on the boundary of map (e.g. most right or most left) where there is no way to slide through the determined direction, you must move in the opposite direction as shown in Figure 4. Actually, the estimated direction may be changed by the mentioned exception.

 

Figure 4: Handling the exception for the estimated direction

 

Figure 5: Treasure Found!

If the mod result is zero, the treasure is found as shown in Figure 5. The place of the treasure is the midpoint of the sub-matrix. Your program must print out the midpoints of the sub-matrix in each step.

P.S. There will not be a map exception with no treasure.

2.1          Execution
The name of the compiled executable program should be “findtreasure”. Your program should read input/output file names from the command line, so it will be executed as follows:

findtreasure [size of map matrix] [size of key matrix] [input file name] [output file name] e.g. ./findtreasure 18x18 3 mapmatrix.txt keymatrix.txt output.txt

You can see sample input and output in piazza page. The program must run on DEV (dev.cs.hacettepe.edu.tr) UNIX machines. So make sure that it compiles and runs on dev server. If we are unable to compile or run, the project risks getting zero point. It is recommended that you test the program using the same mechanism on the sample files (provided) and your own inputs. You must compare your own output and sample output. If your output is different from the sample, the project risks getting zero point, too.

2.2          Input/Output file format
In the map matrix file, the numbers are separated by spaces and newlines. You do not need to check the input for errors. An example map matrix file can be given as follows:

 

Figure 6: Sample map matrix file

Your program should write outputs to the output file, so that each line in the output file will contain the midpoint of the sub-matrix and also the result of multiplication. If the above input file is given, the output file should be as below:

 

Figure 7: Sample output file