Pre order, In order, Post order, Level order Tree Traversal Reference Sheet

The reference sheet below shows the print traversal order for preorder, inorder, postorder and levelorder tree traversal.

Code for printing preorder, inorder, postorder and levelorder traversal is available here. Instructions for inputting a graph can be found in this tutorial.

Both recursive and iterative algorithms for tree traversal are available here.

Tree Input:
tree traversal input
tree traversal input

Tree Traversal Reference Sheet:

pre-in-post-level-order-tree-traversal
pre-in-post-level-order-tree-traversal
Advertisements

Inputting directed, undirected, weighted and unweighted graph in C, C++ Adjacency Matrix

The codes below uses 2D array adjacency matrix. For both sparse and dense graph the space requirement is always O(v2) in adjacency matrix. The codes below can be used take input and store graphs for graph algorithm related problems.

Related to this have a look at,

DIRECTED, UNDIRECTED, WEIGHTED, UNWEIGHTED GRAPH REPRESENTATION IN ADJACENCY LIST, MATRIX REFERENCE SHEET


Input for Directed Weighted Graph:

directed weighted input
directed weighted input

Code Directed Weighted Graph:

/**
 * @author  Quickgrid ( Asif Ahmed )
 * @link    https://quickgrid.wordpress.com
 * Type:    Directed Weighted Graph Input
 */

#include<stdio.h>

#define N 100

/*
 * Graph is the graph representation in adjacency matrix
 */
int Graph[N][N];

/*
 * u is the current or source vertex
 * v is the next or destination vertex
 * w is the edge weight or path cost
 */

int vertices, edges;
int u, v, w;
int i, j;

void InputGraph(){
    printf("Enter vertices and Edges:\n");
    scanf("%d%d", &vertices, &edges);

    // Reset graph
    for(i = 0; i < vertices; ++i)
        for(j = 0; j < vertices; ++j)
            Graph[i][j] = 0;

    // Input Graph
    printf("Enter (u v w):\n");
    for(i = 0; i < edges; ++i){
        scanf("%d%d%d", &u, &v, &w);
        Graph[u][v] = w;
    }
}

void PrintGraph(){
    // Print the current Graph
    printf("\n");
    printf("Graph:\n");
    for(i = 0; i < vertices; ++i){
        for(j = 0; j < vertices; ++j)
            printf("%d ", Graph[i][j]);
        printf("\n");
    }
    printf("\n");
}

int main(){

    printf("Directed Weighted Graph:\n");
    printf("============================\n\n");

    InputGraph();
    PrintGraph();

    return 0;
}

Input for Directed Unweighted Graph:

directed unweighted input
directed unweighted input

Code Directed Unweighted Graph:

/**
 * @author  Quickgrid ( Asif Ahmed )
 * @link    https://quickgrid.wordpress.com
 * Type:    Directed Unweighted Graph Input
 */

#include<stdio.h>

#define N 100

/*
 * Graph is the graph representation in adjacency matrix
 */
int Graph[N][N];

/*
 * u is the current or source vertex
 * v is the next or destination vertex
 */

int vertices, edges;
int u, v;
int i, j;

void InputGraph(){
    printf("Enter vertices and Edges:\n");
    scanf("%d%d", &vertices, &edges);

    // Reset graph
    for(i = 0; i < vertices; ++i)
        for(j = 0; j < vertices; ++j)
            Graph[i][j] = 0;

    // Input Graph
    printf("Enter (u v):\n");
    for(i = 0; i < edges; ++i){
        scanf("%d%d", &u, &v);
        // For directed graph edges (u,v) != (v,u)
        Graph[u][v] = 1;
    }
}

void PrintGraph(){
    // Print the current Graph
    printf("\n");
    printf("Graph:\n");
    for(i = 0; i < vertices; ++i){
        for(j = 0; j < vertices; ++j)
            printf("%d ", Graph[i][j]);
        printf("\n");
    }
    printf("\n");
}

int main(){

    printf("Directed Unweighted Graph:\n");
    printf("============================\n\n");

    InputGraph();
    PrintGraph();

    return 0;
}

Input for Undirected Weighted Graph:

undirected weighted input
undirected weighted input

Code Undirected Weighted Graph:

/**
 * @author  Quickgrid ( Asif Ahmed )
 * @link    https://quickgrid.wordpress.com
 * Type:    Undirected Weighted Graph Input
 */

#include<stdio.h>

#define N 100

/*
 * Graph is the graph representation in adjacency matrix
 */
int Graph[N][N];

/*
 * u is the current or source vertex
 * v is the next or destination vertex
 * w is the edge weight or path cost
 */

int vertices, edges;
int u, v, w;
int i, j;

void InputGraph(){
    printf("Enter vertices and Edges:\n");
    scanf("%d%d", &vertices, &edges);

    // Reset graph
    for(i = 0; i < vertices; ++i)
        for(j = 0; j < vertices; ++j)
            Graph[i][j] = 0;

    // Input Graph
    printf("Enter (u v w):\n");
    for(i = 0; i < edges; ++i){
        scanf("%d%d%d", &u, &v, &w);
        // For undirected edge (u,v) = (v,u)
        Graph[u][v] = Graph[v][u] = w;
    }
}

void PrintGraph(){
    // Print the current Graph
    printf("\n");
    printf("Graph:\n");
    for(i = 0; i < vertices; ++i){
        for(j = 0; j < vertices; ++j)
            printf("%d ", Graph[i][j]);
        printf("\n");
    }
    printf("\n");
}

int main(){

    printf("Undirected Weighted Graph:\n");
    printf("============================\n\n");

    InputGraph();
    PrintGraph();

    return 0;
}

 

Input for Undirected Unweighted Graph:

undirected unweighted input
undirected unweighted input

Code Undirected Unweighted Graph:

/**
 * @author  Quickgrid ( Asif Ahmed )
 * @link    https://quickgrid.wordpress.com
 * Type:    Undirected Unweighted Graph Input
 */

#include<stdio.h>

#define N 100

/*
 * Graph is the graph representation in adjacency matrix
 */
int Graph[N][N];

/*
 * u is the current or source vertex
 * v is the next or destination vertex
 */

int vertices, edges;
int u, v;
int i, j;

void InputGraph(){
    printf("Enter vertices and Edges:\n");
    scanf("%d%d", &vertices, &edges);

    // Reset graph
    for(i = 0; i < vertices; ++i)
        for(j = 0; j < vertices; ++j)
            Graph[i][j] = 0;

    // Input Graph
    printf("Enter (u v):\n");
    for(i = 0; i < edges; ++i){
        scanf("%d%d", &u, &v);
        // Here value of 1 represents there is an edge (u,v)
        Graph[u][v] = Graph[v][u] = 1;
    }
}

void PrintGraph(){
    // Print the current Graph
    printf("\n");
    printf("Graph:\n");
    for(i = 0; i < vertices; ++i){
        for(j = 0; j < vertices; ++j)
            printf("%d ", Graph[i][j]);
        printf("\n");
    }
    printf("\n");
}

int main(){

    printf("Undirected Unweighted Graph:\n");
    printf("============================\n\n");

    InputGraph();
    PrintGraph();

    return 0;
}

Ternary Heap Sort Algorithm Implementation Using heap Data Structure

Ternary Heap Sort Algorithm Implementation Using heap Data Structure :


Ternary Heap Sort Algorithm Code:

#include<cstdio>
#include<cstdlib>
#include<ctime>
#include<iostream>

#define SIZE 10000
long A[SIZE], heapsize = SIZE;

void maxHeapify(long i){
    long largest;

    /**
     * Find index of first, second, third child
     */
    long l = 3 * i + 1;
    long m = 3 * i + 2;
    long r = 3 * i + 3;

    /**
     * Find largest among the parent and its child. And save that index
     */
    if(l < heapsize && A[l] > A[i])
        largest = l;
    else
        largest = i;

    if(m < heapsize && A[m] > A[largest])
        largest = m;

    if(r < heapsize && A[r] > A[largest])
        largest = r;

    /**
     * If the largest index is not of parent then there is another bigger value
     * So swap that value with parent
     */
    if(largest != i){
        std::swap(A[i], A[largest]);
        maxHeapify(largest);
    }
}

void buildMaxHeap(){
    long j;
    /**
     * Starting from the last parent to root max heapify
     */
    for(j = heapsize / 3 - 1; j >= 0; --j)
        maxHeapify(j);
}

void heapsort(){
    buildMaxHeap();

    long i;
    /**
     * Send biggest value root in the end
     * then max heapify from root again
     * this procedure sorts in ascending order because of max heap
     */
    for(i = heapsize-1; i > 0; --i){
        std::swap(A[0], A[i]);

        --heapsize;
        maxHeapify(0);
    }
}

int main(){
    clock_t begin, end;
    double time_elapsed;

    srand(time(NULL));
    register long i = 0;
    for(; i < SIZE; ++i){
        A[i] = rand() % SIZE;
        //printf("%ld ", A[i]);
    }
    //printf("\n");

    begin = clock();
    heapsort();
    end = clock();

    time_elapsed = (double)(end - begin) / CLOCKS_PER_SEC;

    for(i = 0; i < SIZE; ++i)
        printf("%ld ", A[i]);

    printf("\n\nTime elapsed: %lf\n", time_elapsed);

    return 0;
}

Binary Heap Sort Algorithm Code Using Heap Data Structure

Binary Heap Sort Algorithm Code Using Heap Data Structure:


Binary Heap Sort Code:

/**
 * @author  Quickgrid ( Asif Ahmed )
 * @link    https://quickgrid.wordpress.com
 */

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<ctime>

#define SIZE 10000
long A[SIZE];

/**
 * In the beginning the heap size is same as the array size
 */
long heapsize = SIZE;

void maxHeapify(long i){
    long largest;

    /**
     * Find right child index
     */
    long l = 2 * i + 1;

    /**
     * Compare left child against the current node
     */
    if (l < heapsize && A[l] > A[i])
        largest = l;
    else
        largest = i;

    /**
     * Find right child index
     */
    long r = 2 * i +2;

    /**
     * Compare right child against the calculated largest value node
     */
    if (r < heapsize && A[r] > A[largest])
        largest = r;

    /**
     * Swap the current value with the largest value
     */
    if (largest != i){
        /**
         * Swap the two values
         */
        std::swap(A[i], A[largest]);

        /**
         * Max heapify again rest of the heap
         */
        maxHeapify(largest);
    }
}


void buildMaxHeap(){
    register long j;
    /**
     * Start from the last parent and go to root
     */
    for (j = heapsize / 2 - 1; j >= 0; --j)
        maxHeapify(j);
}


void heapsort(){
    buildMaxHeap();
    /**
     * Start from the end of heap swap with root and decrease heap size
     * We know in max heap the biggest item is on top so swapping with the
     * last element will put the biggest value in the end. That way the
     * smallest value will be at the beginning and the biggest will be at the end
     * So by using max heap we can sort in Ascending order.
     */
    register long i;
    for (i = heapsize - 1; i > 0; --i){
        std::swap(A[0], A[i]);
        --heapsize;
        maxHeapify(0);
    }
}

int main(){
    register long i = 0;

    clock_t begin, end;
    double time_elapsed;

    srand(time(NULL));
    for (i = 0; i < SIZE; ++i)
        A[i] = rand() % SIZE;

    begin = clock();
    heapsort();
    end = clock();

    time_elapsed = (double)(end - begin) / CLOCKS_PER_SEC;

    /**
     * Comment this code if you do not want to see sorted output but just time
     */
    for(i = 0; i < SIZE; ++i)
        printf("%ld ", A[i]);

    printf("\n\nTime elapsed: %lf\n", time_elapsed);

    return 0;
}

UVA Problem 10935 – Throwing cards away I Solution

UVA Problem 10935 – Throwing cards away I Solution:


Click here to go to this problem in uva Online Judge.

Solving Technique:

It is possible possible to solve this problem in many ways. Using STL queue is one way. But I try to avoid built-in functions just so I can make my base stronger and learn new things. Here I have written my own queue implementation.

The problem says we have a deck of card which is ordered 1 to n. n is the input. Ex, if 7 is input then we have 1,2,3,4,5,6,7 cards on deck.

Next, it says discard the top card, so card after him is now topmost. Then move the topmost card of the deck to the end of the deck. Keep continuing this until two card are left of deck. The process happens like this, if n = 5 is given,

1 2 3 4 5 /* Initial array enqueued 1 through 5 */

/* First Iteration */
2 3 4 5   /* 1 is discarded and printed */
3 4 5 2   /* 2 is moved to end of queue */

/* Next Iteration */
4 5 2    /* 3 discarded and printed */
5 2 4    /* 4 moved to end of queue */

/* Next Iteration */
2 4     /* 5 discarded and printed */
4 2     /* 4 is also discarded since we want to find the last card and so we print the last card reaming on deck which is 2 */

Notice even though we discard 1 card we move the other one to the end of the deck. So the deck size is decreasing by one ( don’t get confused here ).

Since one card is thrown away and another is moved to the end i thought hey its a queue. Why? queue has a function called dequeue which discards the topmost ( or actually the element in front ). Now another card is moved to end of the deck. Queue has a similar function called enqueue which adds an element to the end of the array or queue. Also since Queue is a FIFO ( FIRST IN FIRST OUT ) data structure. So what is on the front of deck is processed first and that is what we need.

Think of it like a game where each cards are aligned horizontally and each card is a person. Now we tell the player who is in front of the line to move away so the player that was after him is in front of the line. This time we tell the player to move to the end of line. We continue this discard and adding the next one to the end  until there are only two player left. So of these two player the last player is the remaining cards and the players that were moved from line are the discarded cards.

Our input terminates with 0 ( zero ). I have explained the code below with comments.

Important:  Be sure to add or print a new line after each output. The outputs should match exactly because sometimes even a space character causes the answer to be marked as wrong answer.


Input:

7
19
10
6
0

Output:

Discarded cards: 1, 3, 5, 7, 4, 2
Remaining card: 6
Discarded cards: 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 4, 8, 12, 16, 2, 10, 18, 14
Remaining card: 6
Discarded cards: 1, 3, 5, 7, 9, 2, 6, 10, 8
Remaining card: 4
Discarded cards: 1, 3, 5, 2, 6
Remaining card: 4

Code:

/*
 * @author quickgrid ( Asif Ahmed )
 * @link   https://quickgrid.wordpress.com
 */

#include<stdio.h>
#define size 128

/*
 * unsigned since no item in our array is negative
 */
unsigned a[size], f = 0, r = 0;

void enqueue(unsigned k){
    /*
     * get a valid index in circular queue array
     */
    unsigned s = (r + 1) % (size + 1);

    /*
     * if true queue full, this check is for safety and can be deleted
     */
    if (f == s)
        return;

    /*
     * set the last element to given card
     */
    a[s] = k;
    /*
     * update the rear position marker
     */
    r = s;
}

unsigned dequeue(){
    /*
     * if true then queue empty, this check is for safety and can be deleted
     */
    if (f == r)
        return 0;

    /*
     * move the front marker one position in circular queue array
     */
    f = (f + 1) % (size + 1);
    /*
     * keep the value of last card for returning
     */
    unsigned k = a[f];
    a[f] = 0;
    return k;
}

int main(){
    register unsigned n, i;

    while (scanf("%u", &n) && n){
        /*
         * since there is one card there is no discarded card
         */
        if (n == 1){
            printf("Discarded cards:\n");
            printf("Remaining card: 1\n");
            continue;
        }

        f = 0, r = 0;
        for (i = 1; i <= n; ++i){
            /*
             * it says 1 to n cards on deck so i enqueue all cards serially
             */
            enqueue(i);
        }

        printf("Discarded cards: ");
        /*
         * stop when 2 cards on deck
         */
        while (f + 2 != r){
            printf("%u, ", dequeue());
            unsigned k = dequeue();
            enqueue(k);
        }

        /*
         * get position of last discardable card
         */
        f = (f + 1) % (size + 1);

        /*
         * print the last discardable card
         */
        printf("%u\n", a[f]);
        /*
         * now print the last remaining card on deck
         */
        printf("Remaining card: %u\n", a[r]);
    }
    return 0;
}

Tree Implementation in both custom Linked list and Array stack and Traversal In order, Pre order, Post order, Level order, Level print , Height print

Tree Implementation in both custom Linked list and Array stack and Traversal In order, Pre order, Post order, Level order, Level print , Height print:

Code Explanation:

This code is bit complex and will require knowledge on:

  1. Struct
  2. Linked list
  3. Queue
  4. Stack
  5. Binary Tree ( check this and this too  )

Input Format:

Level Order tree input style
Level Order tree input style
binary Tree Graph sample Input for the console picture shown above
binary Tree Graph sample Input for the console picture shown above

Code:

/*
 * Author: Quickgrid
 * Code: Tree creation, traversal in array & linked list ( inorder/preorder/postorder/levelorder )
 * Description:
 */

#include <stdio.h>

#define size 1000   /* used this for queue array */

struct tree{    /* binary tree structure */
    char data;
    struct tree *left;
    struct tree *right;
};
typedef struct tree node;

struct stack{   /* linear/singly linked list stack to hold tree type data */
    node *nodedata;
    struct stack *next;
};
typedef struct stack vertex;

node* q[size];  /* here our array is node data type that we defined above */
int f = 0, r = 0;
vertex *front = NULL, *rear = NULL;
node *root = NULL;

void enq(node *root){   /* circular queue array modular arithmetic */
    int s = (r+1) % (size+1); /* +1 means we don't use 1 box of the array */
    if(f == s){
        printf("Queue Full.\n");
        return;
    }
    q[s] = root; /* root is node type we put it in our node array */
    r = s;  /* s is temporary variable */
}

node *deq(){
    if(f==r){
        printf("Queue Empty.\n");
        return NULL;
    }
    f = (f+1)%(size+1);
    node *temp = q[f]; /* get the last element of the queue to return for further operations */
    q[f] = 0;
    return temp;
}

void levelOrderArray(node *root){
    enq(root);  /* here we enqueue the root or the node that we want to star from */
    while(f!=r){ /* check if our queue is not empty */
        node *v = deq(); /* dequeue one item */
        printf("%c ", v->data);
        if(v->left!=NULL){ /* check if left branch of tree exists */
           enq(v->left); /* send the left node to queue */
        }
        if(v->right!=NULL){ /* check if right branch of tree exists */
            enq(v->right); /* send the right node to queue */
        }
    }
}

void enqueue(node *root){   /* enqueue function for our stack in linked list */
    if(front == NULL){
        front = new vertex();
        front->nodedata = root;
        front->next = NULL;
        rear = front;
    }else{
        vertex *temp = new vertex();
        temp->nodedata = root;
        temp->next = NULL;
        rear->next = temp;
        rear = temp;
    }
}

vertex *dequeue(){
    if(front == NULL){
        printf("queue empty.\n");
        return front;
    }
    vertex *temp,*tmp = front;
    front = front->next;
    delete temp;
    return tmp;
}

void levelorder (node *root){
    enqueue(root);
    while ( front != NULL ){
        vertex *v = dequeue();  /* we dequeue one vertex type data from our vertex stack */
        if(v!=NULL){
            printf("%c",v->nodedata->data);

            if (v->nodedata->left != NULL){ /* nodedata is our data part which holds node type data */
                enqueue(v->nodedata->left);
            }
            if (v->nodedata->right != NULL){
                enqueue(v->nodedata->right);
            }
        }
    }
}

int treeHeight(node *root){
    if(root == NULL){
        return 0;
    }
    int leftHeight = treeHeight(root->left);
    int rightHeight = treeHeight(root->right);

    if(leftHeight > rightHeight){
        return leftHeight+1;
    }else{
        return rightHeight+1;
    }
}

void printGivenLevel(node *root, int level){
    if(root == NULL){
        return;
    }
    if(level == 1){
        printf("%c ", root->data);
    }else if(level > 1){
        printGivenLevel(root->left, level-1);
        printGivenLevel(root->right, level-1);
    }
}

void createBinaryTree (node *root)
{
    char ans;

    fflush(stdout);
    printf("%c has any left child: ", root->data);
    fflush(stdin);
    ans = getchar();

    if (ans == 'y') /* create left side of a tree node */
    {
        root->left = new node ();
        root->left->left = NULL;
        root->left->right = NULL;
        fflush(stdout);
        printf("Enter left data of %c: ", root->data);
        fflush(stdin);
        scanf("%c",&root->left->data);
        createBinaryTree (root->left);  /* recursive call with created node as root to check if it has left and right */
    }

    fflush(stdout);
    printf("%c has any right child: ", root->data);
    fflush(stdin);
    ans = getchar();

    if (ans == 'y') /* create right side of a tree node */
    {
        root->right = new node ();
        root->right->left = NULL;
        root->right->right = NULL;
        fflush(stdout);
        printf("Enter right data of %c: ", root->data);
        fflush(stdin);
        scanf("%c",&root->right->data);
        createBinaryTree (root->right);
    }
}

void postOrder(node *root){
    if(root->left!=NULL){
        postOrder(root->left);
    }
    if(root->right!=NULL){
        postOrder(root->right);
    }
    printf("%c ", root->data);
}

void preOrder(node *root){
    printf("%c ", root->data);
    if(root->left!=NULL){   /* check if left side of that node exist */
        preOrder(root->left);   /* recursive call of preorder using this node as the root */
    }
    if(root->right!=NULL){
        preOrder(root->right);
    }
}

void inOrder(node *root){
    if(root->left!=NULL){
        inOrder(root->left);
    }
    printf("%c ", root->data);
    if(root->right!=NULL){
        inOrder(root->right);
    }
}

int main ()
{
    char ans;
    fflush(stdout);
    printf("Do u want to create a tree: ");
    fflush(stdin);
    ans = getchar();

    root = new node ();
    fflush(stdout);
    printf("Enter root of tree: ");
    fflush(stdin);
    scanf("%c",&root->data);
    createBinaryTree(root);

    int height = treeHeight(root);
    printf("\nTree Height: %d", height);

    printf("\nLevel order Linked List: ");
    levelorder(root);   /* Instead of sending root we can send another node to level order from that node */
    printf("\nLevel order Array: ");
    levelOrderArray(root);
    printf("\nPre order : ");
    preOrder(root);
    printf("\nIn order : ");
    inOrder(root);
    printf("\nPost order : ");
    postOrder(root);

    printf("\nEnter level to print:");
    int level;
    scanf("%d", &level);
    if(level >= height || level < 1){
        printf("\nGiven level doesn't exist.");
    }else{
        printf("Level %d: ", level);
        printGivenLevel(root, level);
        printf("\n");
    }
    return 0;
}

UVA Problem 591 ( Box of Bricks ) Solution

UVA Problem 591 ( Box of Bricks ) Solution:


Click here to go to this problem in uva Online Judge.

Solving Technique:

If we read this problem carefully then there are a some very important clues,

  1. make all stacks the same height (line 2)
  2. he sets out to rearrange the bricks, one by one (line 3)
  3. The total number of bricks will be divisible by the number of stacks (line 7)

From the above points and problems description it is clear that Little Bob can only move the blocks one by one. Also the first line of input will be less or equal to 50 and the block heights will be less than or equal to 100. So we can use integer ( also unsigned integer ) for them.

Another thing it is said that dividing sum of stack heights with stack count is always possible. Meaning that gives us the height of the wall ( total stacks height sum, h[i] / stack count, n ).

The technique is there can be three types of box stack. That is equal to, less than or greater than height of the wall( total stacks height sum, h[i] / stack count, n ).

Since Bob can move boxes one by one it doesn’t matter which stack to start from. We can find the number of blocks to move from by only subtracting those stack that are greater in height than the max wall height. No need to perform this action on stacks that are equal or less high than max wall height.

So the result is the sum of subtraction of each stacks that are greater than from ( all stack sum / stack count ). Also since blocks are moved one by one this is the final result.

Important:   We normally print a new line after each output line but for this problem asks us to Output a blank line after each set. Meaning with our normal line break we need to add another line break. Be sure to add or print a new line after each output. The outputs should match exactly because sometimes even a space character causes the answer to be marked as wrong answer.


Code Explanation:

  1. First I take the stack count and loop that many times. [ also reset moves, and c ( count ) variable each time ]
  2. Now for each loop I take the height of stack in an array and sum it.
  3. Next I find the wall height by dividing the sum with stack count.
  4. Now I use another loop to loop through the array. In it subtract elements greater than stack height and also sum up this value to moves ( number of box movement needed ).
  5. Lastly I print in the exact format the problem asked.
  6. One more thing I printed an extra newline because the problem asked for a blank line after each set.

Input:

6
5 2 4 1 7 5
0

Output:

Set #1
The minimum number of moves is 5.

Code:

/*
 * @author  Quickgrid ( Asif Ahmed )
 * @link    https://quickgrid.wordpress.com
 */

#include<stdio.h>

static int a[128];

int main(){
    register int i, c = 1;
    int n, sum, maxHeight, moves, temp;

    while (scanf("%d", &n) && n){
        moves = sum = 0;

        for (i = 0; i < n; ++i){
            scanf("%d", &a[i]);
            sum += a[i];
        }

        maxHeight = sum / n;

        for (i = 0; i < n; ++i){
            if(a[i] > maxHeight)
                moves += a[i] - maxHeight;
        }

        printf("Set #%d\nThe minimum number of moves is %d.\n\n", c++, moves);
    }
    return 0;
}

UVA Problem 11192 ( Group Reverse ) Solution

UVA Problem 11192 ( Group Reverse ) Solution:


Click here to go to this problem in uva Online Judge.

Solving Technique:

This one is a bit tricky. Also it seems to be closely related to this ( 483 word scramble ) uva problem. Basically for this problem we are to take an integer ( which is the number of groups ) and a string until we are given a 0. Now our input is given like this,

3 ABCEHSHSH

5 FA0ETASINAHGRI0NATWON0QA0NARI0

0

So, the first problem for beginner is taking input for this. From the input we can easily see that there are two parts and the first part is an integer and second part is a string. Also we need to keep taking input until we find 0. What if we divide our scanf or input taking into two parts. First take the integer and check if its 0 or not then if it’s not zero then take the string and continue like this.

Our first input is an integer which is group number or number of parts the string can be divided to. So, from the given problem statement,

TOBENUMBERONEWEMEETAGAINANDAGAINUNDERBLUEICPCSKY

This string has length 48. We have divided into 8 groups of equal length and so the length of each group is 6. Meaning each group or each part of sentence will consist of 6 characters.

UNEBOTNOREBMEEMEWENIAGATAGADNAEDNUNIIEULBRYKSCPC

Our task is to reverse print/output each and every group. We can easily find how many members are in each group by dividing the length of the string with input ( number of groups ) we are given.

Important:  Be sure to add or print a new line after each output. The outputs should match exactly because sometimes even a space character causes the answer to be marked as wrong answer.


Code Explanation:

Here I have used stack data structure ( see this and this ) to solve this problem. First I find the length of the string then find how many characters in each group by dividing string length with group number. I also keep a counter ” x “ and keep pushing each character of the string in stack until I reach the last character or until our counter is not equal to the group member count. Also increment the counter each time i push into the stack. Also I keep a condition to check if  I have reach the last character or until our counter is equal to the group member count then pop until our loop counter has reached zero. Since stack is a LIFO data structures the last character i pushed into the stack are the first one to come out ( meaning they are outputted in reverse order ). This process keeps running until we reach the end of the sentence.


Input:

3 ABCEHSHSH
5 FA0ETASINAHGRI0NATWON0QA0NARI0
0

Output:

CBASHEHSH
ATE0AFGHANISTAN0IRAQ0NOW0IRAN0

Commented Code ( See the next Code for easier understanding of stack ):

/**
 * @author Quickgrid ( Asif Ahmed )
 * @url https://quickgrid.wordpress.com
 */

#include<stdio.h>

/**
 * Input string buffer
 */
static char s[128];

/**
 * Global index for accessing input array, may be declared inside main
 */
int top = -1;

int main(){
    register unsigned j,u,n,i,x;

    /**
     * Input group count and Check if count is Not Zero
     */
    while (scanf("%u", &n) && n) {
        scanf("%s", s);

        /**
         * Find out input string size
         */
        for (j = 0; s[j]; ++j);

        /**
         * Find out length of each group
         */
        n = j / n;

        /**
         * Group Reverse loop
         */
        for (x = i = 0; i < j; ++i) {
            /**
             * For checking is the item after is NUL terminator
             */
            u = s[i + 1];

            /**
             * @var u
             * If the character after current is NUL then NOT u, is True
             *
             * @var n
             * Check to see if characters in group count is NOT full, then push more to stack
             */
            if ( !u || x != n ) {
                /**
                 * Push current character on top of stack
                 */
                s[++top] = s[i];
                /**
                 * Keep a count of characters pushed on stack
                 */
                ++x;
            }

            /**
             * If character limit per group is reached then Condition is True
             */
            if ( !u || x == n ) {
                /**
                 * Empty the the stack for every pushed character
                 */
                while (x--){
                    /**
                     * Output character by character in reversed form
                     */
                    printf("%c", s[top]);
                    --top;
                }
                x = 0;
            }

        }
        printf("\n");
    }
    return 0;
}

Code:

/*
 * Author: Quickgrid ( Asif Ahmed )
 * Site: https://quickgrid.wordpress.com
 */

#include<stdio.h>

char s[101];
int top = -1;

void push(char c){
    if(top + 1 >= 101)
        return;

    s[++top] = c;
}

void pop(){
    if (top == -1)
        return;

    printf("%c", s[top]);
    s[top--] = '\0';
}

int main(){
	int n,j,i,x;
	while (scanf("%d", &n) == 1 && n != 0){
        x = 0;
        scanf("%s", &s);
        for (i = 0; s[i]; ++i);
        n = i / n;

        for (i = 0; s[i]; ++i){
            if (s[i+1] == '\0' || x != n){
                push(s[i]);
                ++x;
            }

            if (s[i+1] == '\0' || x == n){
                while (x--)
                    pop();

                x = 0;
            }
        }

        printf("\n");
	}
	return 0;
}

BFS Sequence for Unirected Graph in C++

Code Explanation:

Coming soon maybe…… Until then please look at the commented code.

Example Graph:

Example Undirected Graph for applying BFS
Example Undirected Graph for applying BFS

Code:

/**
 * @author  Quickgrid ( Asif Ahmed )
 * @link    https://quickgrid.wordpress.com
 */

#include<stdio.h>

#define size 100

/**
 * Here nodes are represented with characters
 */
char vertex[size], visited_sequence[size], q[size];

/**
 * The graph which is a 2D matrix
 */
int graph[size][size];

/**
 * Counters for visited sequence, queue etc
 */
int count_visited_seq = 0, f = 0, r = 0, n;


/**
 * Update the visited sequence array
 */
void visit(char v)
{
    visited_sequence[count_visited_seq++] = v;
}


/**
 * Check the visited sequence array against a node
 * to see if it is already visited
 */
int isVisited(char v)
{
    for(int i = 0; i != count_visited_seq; ++i)
    {
        if(visited_sequence[i] == v)
        {
            return 1; // means already visited
        }
    }
    return 0; // not visited
}


/**
 * Display the BFS visited sequence
 */
void displayVisitedSequence()
{
    for(int i = 0; i < count_visited_seq; ++i)
    {
        printf("%c ", visited_sequence[i]);
    }
    printf("\n");
}


void enqueue(char v)
{
    int s = (r + 1) % (size + 1);
    if(s == f)
    {
        return;
    }
    q[s] = v;
    r = s;
}


char dequeue()
{
    if(f == r)
    {
        return '\0';
    }
    f = (f + 1) % (size + 1);
    char v = q[f];
    q[f] = '\0';
    return v;
}


/**
 * Check the adjacent nodes of given node to see if there is an edge
 * Also check if it is not already visited then enter it to queue
 */
void checkAdjecency(char v)
{
    for(int i = 0; i != n; ++i)
    {
        if(vertex[i] == v)
        {
            for(int j = 0; j != n; ++j)
            {
                if(graph[i][j] == 1 && !isVisited(vertex[j]))
                {
                    enqueue(vertex[j]);
                }
            }
        }
    }
}


/**
 * Create undirected graph, map characters as nodes identifiers
 * Reset the graph meaning set 0, to point out no edge exist
 */
void createGraph()
{
    int i, j;
    for(i = 0; i < 26; ++i)
    {
        vertex[i] = i + 'A';
    }

    printf("How many vertex:\n");
    scanf("%d", &n);
    for(i = 0; i != n; ++i)
    {
        for(j = 0; j != n; ++j)
        {
            graph[i][j] = 0;
        }
    }

    for(i = 0; i != n; ++i)
    {
        for(j = i + 1; j != n; ++j)
        {
            printf("%c-%c exist:\n", vertex[i], vertex[j]);
            scanf("%d", &graph[i][j]);
            if(graph[i][j] == 1)
            {
                graph[j][i] = graph[i][j];
            }
        }
    }
}


/**
 * Start processing the queue
 */
void BFS()
{
    char v;
    int exit = 0;
    while(1)
    {
        fflush(stdout);
        printf("Enter a node to Enqueue:\n");
        fflush(stdin);
        scanf("%c", &v);
        for(int i = 0; i != n; ++i)
        {
            if(vertex[i] == v)
            {
                enqueue(vertex[i]);
                exit = 1;
            }
        }
        if(exit)
        {
            break;
        }
    }

    while(f != r)
    {
        char v = dequeue();
        if(!isVisited(v))
        {
            visit(v);
        }
        checkAdjecency(v);
    }
}


int main()
{
    createGraph();
    BFS();
    displayVisitedSequence();
    return 0;
}

Stack Queue Array Hybrid (Data Structure)

Description: Here i combined my knowledge of stack and queue array into a single code. Firstly we are working with Queue. We can enqueue items in a queue. But when we dequeue the dequeued item is pushed to the stack ( We push the dequeued item in stack ) . The items pushed in stack are in the same order as they were in queue  since Queue is FIFO ( First In First Out ) data structure. We can also pop items from that stack. Now when we pop them they are enqueued back to the queue. The interesting thing is when they are popped they fill up the queue in reverse order since Stack is LIFO ( Last In First Out ) data structure.


input system
stack queue data structure 1
input system
stack queue data structure 2

Stack Functions: pop(), push(), displayStack(), searchStack()

Queue Functions: enqueue(), dequeue(), displayQueue(), searchQueue()


Code:

/**
 * @author  Quickgrid ( Asif Ahmed )
 * @link    https://quickgrid.wordpress.com
 */

#include<stdio.h>

#define size 100

int q[size+1], f = 0, r = 0;
int s[size], top = -1;

void showMenu()
{
    printf("1.Enqueue\n");
    printf("2.Dequeue\n");
    printf("3.Show Queue\n");
    printf("4.Search Queue\n");
    printf("5.Show Stack\n");
    printf("6.Search Stack\n");
    printf("7.Pop stack\n");
    printf("8.Exit\n");
}

void push(int item)
{
    if(top+1 >= size)
    {
        printf("stack Overflow.\n");
        return;
    }
    s[++top] = item;
}

void displayQueue()
{
    int i = (f+1) % (size+1);
    for(int j=i; j!=r+1; ++j)
    {
        if(j>size)
        {
            j = 0;
        }
        if(f != r)
        {
            printf("%d ", q[j]);
        }
    }
    printf("\n");
}

void enqueue(int num)
{
    int s = (r+1) % (size+1);
    if(s == f)
    {
        printf("Queue Full.\n");
        return;
    }
    q[s] = num;
    r = s;
}

void dequeue()
{
    if(f == r)
    {
        printf("Queue empty.\n");
        return;
    }
    f = (f+1) % (size+1);
    printf("%d\n", q[f]);
    push(q[f]);
    q[f] = 0;
}

void searchQueue(int item)
{
    int i = (f+1) % (size+1);
    for(int j=i; j!=r+1; ++j)
    {
        if(j > size)
        {
            j = 0;
        }
        if(f!=r)
        {
            if(q[j] == item)
            {
                printf("%d found in queue\n", item);
            }
        }
    }
}

void searchStack(int item)
{
    for(int i=0; i<=top; ++i)
    {
        if(s[i] == item)
        {
            printf("%d found at index: %d\n", item, i);
        }
    }
}

void displayStack()
{
    for(int i=0; i<=top; ++i)
    {
        printf("%d ", s[i]);
    }
    printf("\n");
}

void pop()
{
    if(top == -1)
    {
        printf("Stack Underflow.\n");
        return;
    }
    printf("%d\n", s[top]);
    enqueue(s[top]);
    s[top--] = 0;
}

int main()
{
    int choice, exitcode = 1, item;

    do
    {
        showMenu();
        printf("Enter choice:\n");
        scanf("%d", &choice);
        switch(choice)
        {
        case 1:
            printf("Enter item to enqueue:\n");
            scanf("%d", &item);
            enqueue(item);
            printf("Stack: ");
            displayStack();
            printf("Queue: ");
            displayQueue();
            break;
        case 2:
            dequeue();
            printf("Stack: ");
            displayStack();
            printf("Queue: ");
            displayQueue();
            break;
        case 3:
            displayQueue();
            break;
        case 4:
            printf("Enter item to search:\n");
            scanf("%d", &item);
            searchQueue(item);
            printf("Stack: ");
            displayStack();
            printf("Queue: ");
            displayQueue();
            break;
        case 5:
            displayStack();
            break;
        case 6:
            printf("Enter item to search:\n");
            scanf("%d", &item);
            searchStack(item);
            printf("Stack: ");
            displayStack();
            printf("Queue: ");
            displayQueue();
            break;
        case 7:
            pop();
            printf("Stack: ");
            displayStack();
            printf("Queue: ");
            displayQueue();
            break;
        case 8:
            exitcode = 0;
            break;
        }
    }
    while(exitcode == 1);

    return 0;
}