As a computer science lecturer (though I am from cognitive science background, and even labelled as NOT from computer science, 士可杀，不可辱！), I focus on the fundamental knowledge and experience. I focus on C/C++ language on my students, because only have good fundamental knowledge and skills, then they can survive with the evolving technology once they graduated. For example, Flash was popular technology, yet now it is dying. Those who know Flash only, have to learn new technology. Without fundamental skill, how to cope with the new technologies that emerge everyday? Know the root, then you can get any leaf.
So, I gave my students an assignment. The assignment requires them to write a program that can
- Read a text file as a map, with binary information in the map, block or space. Block does not allow to move; the space allows to move.
- Find the route from upper left to the lower right (assuming that there is at least one route in the map file.)
- Show the route that goes from upper left to lower right through the space.
To write a program, the first thing is to design the data structure that can hold the input/output data. Only with the good data structure, then the algorithms will emerge automatically.
I personally spent around 3 hours to write the program using C++ language, but not object oriented and omitted the STL. No object oriented involved, but only struct. The solution involves 2D array, linked list, tree (ADT) and tree traversal, and stack with doubly linked list.
The file is read line by line, and converted into 2D array. Then using the 2D array, convert this 2D map with blocks and spaces into a tree data structure. The spaces are connected as the tree nodes, the blocks are ignored. Each node has an (x, y)-coordinate. Once the tree data structure is completed, then I wrote a depth first search (DFS) as a tree traversal, start from the upper left, and target the lower right. However, because it is a DFS, it will try all branches in the search tree. So, I have to use a stack (using doubly linked list) to store the route that straight to the destination. Finally, the route in the stack is printed.
No GUI, because inside-out is important, just like a pretty apple with rotten content is good for nothing. What I focus is the inner quality (attitude, hardworking, problem solving, etc), not the flattering or boasting. Since I am a Catholic, Chinese, cognitive science student, programmer, and INTJ personality (if you don’t know what is INTJ, please go to google it), when it is true, I say true; when it is false, I say false; when I don’t know, I say I don’t know. All the BS reserved for those BSers. Since I am a lecturer, it is my responsibility to optimise my lecturing function to guide the students in their studies. It is a shame for those academic murderers who exploit the students in order to get their own fame, get the research grant, and plagiarise the students’ work to publish their own research papers.
So, the coding I wrote also demonstrates the usage of pointer (computer science students MUST know), dynamic memory allocation, and recursive function (important in FP).
#include <cstdio>
#include <cstring>
#include <cstdlib>
struct MapNode {
MapNode *up;
MapNode *down;
MapNode *left;
MapNode *right;
int data;
int x;
int y;
int visited;
};
/**
* This is just like the OOP object constructor.
*/
MapNode* mapNodeCreate(int x, int y, int data) {
MapNode *n = new MapNode;
n->up = NULL;
n->down = NULL;
n->left = NULL;
n->right = NULL;
n->x = x;
n->y = y;
n->data = data;
n->visited = 0;
return n;
}
/**
* The following stack design is like this,
* the Stack is a container of the StackNode*.
* The StackNode contains MapNode*
* Therefore, using the Stack ADT, we can push and pop the StackNode.
* Since the StackNode is a doubly linked list, at the same time it holds the MapNode* (pointer)
*/
struct StackNode {
MapNode *mapNode;
StackNode *next;
StackNode *prev;
};
StackNode* stackNode(MapNode *mapNode) {
StackNode *n = new StackNode;
n->mapNode = mapNode;
n->next = NULL;
n->prev = NULL;
return n;
}
/**
* So, a Stack contains several StackNode*.
*/
struct Stack {
StackNode *head;
StackNode *tail;
};
Stack* stackCreate() {
Stack *s = new Stack;
s->head = NULL;
s->tail = NULL;
return s;
}
void stackPush(Stack *s, StackNode *n) {
if(!s->head) { //First item
s->head = n;
s->tail = n;
}
else { //If there is a node
s->tail->next = n;
n->prev = s->tail;
s->tail = s->tail->next;
//Make sure it is the last
s->tail->next = NULL;
}
}
int stackSize(Stack *s) {
int size = 0;
StackNode *curr = s->head;
while(curr) {
size++;
curr = curr->next;
}
return size;
}
StackNode* stackPop(Stack *s) {
StackNode *n = s->tail;
s->tail = s->tail->prev;
s->tail->next = NULL;
return n;
}
void stackPrint(Stack *s) {
StackNode *curr = s->head;
while(curr) {
printf("(%d, %d)\n", curr->mapNode->x, curr->mapNode->y);
curr = curr->next;
}
}
MapNode **list; //For storing the nodes, then delete them at the end
Stack *stack = stackCreate(); //For storing the coordinates, default will head NULL and tail NULL
/**
* In order to solve this, this is very complicated. Firstly, I used
* a variable depth to check when is the push and pop are appropriate,
* As a result, convert the depth++ to the push and depth-- to the pop
* to make sure that only correct nodes are stored, and incorrect nodes will be popped.
* So, this function is traversing all the route, and push the correct route to the stack.
*/
void mapTraverse(MapNode *node, int x, int y, bool *stop) {
if(!*stop) //Push only if still searching
stackPush(stack, stackNode(node));
if(*stop) {
return;
}
if(!node) {
stackPop(stack);
return;
}
if(node->visited) {
stackPop(stack);
return;
}
if(node->x == x && node->y == y) {
*stop = true;
printf("(%d, %d) Found!!\n", node->x, node->y);
return;
}
node->visited = 1; //mark visited
printf("(%d, %d), ", node->x, node->y);
mapTraverse(node->left, x, y, stop);
mapTraverse(node->up, x, y, stop);
mapTraverse(node->right, x, y, stop);
mapTraverse(node->down, x, y, stop);
if(!*stop) { //Do not pop if founded.
stackPop(stack);
}
}
void arrPrint(int *arr, int w, int h) {
for(int i=0;i<h;i++) {
for(int j=0;j<w;j++) {
printf("%d ", arr[i*w + j]);
}
printf("\n");
}
printf("\n");
}
/**
* The text file is the binary (1 or 0) content.
* @param w is the pointer to the width (output)
* @param h is the pointer to the height (output)
* @return a pointer of integer for the map.
*/
int* readFileToArray(const char* filename, int *w, int *h) {
FILE *fp = fopen(filename, "r");
if(!fp) {
fprintf(stderr, "Failed to open file\n");
return NULL;
}
char buffer[256];
//This method (supposed) only applicable for the text file with "\n" (Unix file),
// not the "\r\n" or "\n\r" (Windows or MacOSX)
//Get the map dimension first.
fgets(buffer, 255, fp);
int width = strlen(buffer) -1;
//Go to the end of the file
fseek(fp, 0, SEEK_END);
int height = ftell(fp) / (width+1);
printf("width: %d\theight: %d\n", width, height);
//Go back to the beginning of the file
fseek(fp, 0, SEEK_SET);
//Create an array
int *arr = new int[width * height];
int *cursor = arr;
while(fgets(buffer, 255, fp)) {
buffer[strlen(buffer) -1 ] = 0;
for(int i=0;i<strlen(buffer);i++) {
*cursor = buffer[i] - '0'; //Convert the character to the value
cursor++;
}
}
fclose(fp);
//Get the width and height
*w = width;
*h = height;
return arr;
}
MapNode* arrToMap(int *arr, int width, int height) {
//Use an array to store the map node
list = new MapNode*[width * height]; //This is the syntax that creates an array of pointer (with "*") after the data type.
for(int j=0;j<height;j++) {
for(int i=0;i<width;i++) {
//Create the node
MapNode *node = mapNodeCreate(i, j, arr[j*width +i]);
list[j*width +i] = node;
}
}
//Check the connectedness horizontally
for(int i=0;i<height;i++) {
for(int j=0;j<width -1;j++) {
if(arr[i*width+j] == 1 && arr[i*width +j+1] ==1) {
list[i*width+j]->right = list[i*width +j+1];
list[i*width+j+1]->left = list[i*width+j];
}
}
}
//Check the connectedness vertically
for(int i=0;i<height-1;i++) {
for(int j=0;j<width;j++) {
if(arr[i*width+j] == 1 && arr[(i+1)*width +j] ==1) {
list[i*width+j]->down = list[(i+1)*width +j];
list[(i+1)*width+j]->up = list[i*width+j];
}
}
}
MapNode *root = list[0];
return root; //Return the first node
}
int main(int argc, char **argv) {
if(argc < 2) {
printf("Usage: %s map.txt\n", argv[0]);
return 1;
}
int width, height;
int *arrMap;
arrMap = readFileToArray(argv[1], &width, &height);
arrPrint(arrMap, width, height);
MapNode* mapRoot = arrToMap(arrMap, width, height);
//Traverse the nodes;
bool stop = false; //use this to control so that once found, need not to perform recursive search
mapTraverse(mapRoot, width-1, height-1, &stop);
printf("Stack size %d\n", stackSize(stack));
stackPrint(stack);
delete arrMap;
//Delete all the nodes
for(int i=0;i<width * height;i++) {
delete list[i];
}
delete stack;
return 0;
}
The sample input text file,
10000000000000000000 10000000111111111100 10000000100000100000 10000000100000100000 11111111111111111110 00000100000000100000 00000100000000111110 00000100000000000000 11111100000000000000 00000111111111100000 00000100001000000000 00000100001000000000 00000000001111111100 01110000000000000110 01110000000000000011
And this is the output
width: 20 height: 15 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 1 1 1 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 (0, 0), (0, 1), (0, 2), (0, 3), (0, 4), (1, 4), (2, 4), (3, 4), (4, 4), (5, 4), (6, 4), (7, 4), (8, 4), (8, 3), (8, 2), (8, 1), (9, 1), (10, 1), (11, 1), (12, 1), (13, 1), (14, 1), (15, 1), (16, 1), (17, 1), (14, 2), (14, 3), (14, 4), (13, 4), (12, 4), (11, 4), (10, 4), (9, 4), (15, 4), (16, 4), (17, 4), (18, 4), (14, 5), (14, 6), (15, 6), (16, 6), (17, 6), (18, 6), (5, 5), (5, 6), (5, 7), (5, 8), (4, 8), (3, 8), (2, 8), (1, 8), (0, 8), (5, 9), (6, 9), (7, 9), (8, 9), (9, 9), (10, 9), (11, 9), (12, 9), (13, 9), (14, 9), (10, 10), (10, 11), (10, 12), (11, 12), (12, 12), (13, 12), (14, 12), (15, 12), (16, 12), (17, 12), (17, 13), (18, 13), (18, 14), (19, 14) Found!! Stack size 34 (0, 0) (0, 1) (0, 2) (0, 3) (0, 4) (1, 4) (2, 4) (3, 4) (4, 4) (5, 4) (5, 5) (5, 6) (5, 7) (5, 8) (5, 9) (6, 9) (7, 9) (8, 9) (9, 9) (10, 9) (10, 10) (10, 11) (10, 12) (11, 12) (12, 12) (13, 12) (14, 12) (15, 12) (16, 12) (17, 12) (17, 13) (18, 13) (18, 14) (19, 14)
Blogarious 