UVA Problem 10935 – Throwing cards away I Solution

Posted on by quickgrid
See More

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;
}

BFS Sequence for Unirected Graph in C++

Posted on by quickgrid

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)

Posted on by quickgrid

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;
}