UVA Problem 10189 – Minesweeper Solution

UVA Problem 10189 – Minesweeper Solution:


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

Solving Technique:

Given a mine field that is a matrix / 2D array, produce an output that contains count of adjacent mines for each squares.

In a 2D array for each squares there are at most adjacent 8 squares. If the current position is i and j then,

\begin{bmatrix}  (i-1,j-1) & (i-1,j) & (i-1,j+1) \\  (i+0,j-1) &  (i,j)  & (i+0,j+1) \\  (i+1,j-1) & (i-1,j) & (i+1,j+1) \\   \end{bmatrix}

Just traverse the matrix row-column wise and check its adjacent squares for getting mine count for current position. The adjacent squares check can be implemented with 8 if conditions for each one.

Another technique is to store the co-ordinates of adjacent squares and using a for loop to check them. The illustration below shows how the 2nd code is implemented using arrays and for loops,
uva 10189 matrix adjacent squares check with saved co-ordinates and for loop
uva 10189 matrix adjacent squares check with saved co-ordinates and for loop

Here the arrow from the center shows where checking starts. The 1D arrays drow and dcol hold the row and column values the way shown above. It can be changed by modifying drow and dcol arrays.

 

Important:  Be sure to add or print a new line after each output unless otherwise specified. The outputs should match exactly because sometimes even a space character causes the answer to be marked as wrong answer. Please compile with c++ compiler as some of my codes are in c and some in c++.


More Inputs of This Problem on uDebug.


Input:

4 4
*...
....
.*..
....
3 5
**...
.....
.*...
0 0

 


Output:

Field #1:
*100
2210
1*10
1110

Field #2:
**100
33200
1*100

Code Using Multiple if Conditions:

/**
 * Author:    Asif Ahmed
 * Site:      https://quickgrid.wordpress.com
 * Problem:   UVA 10189 - Minesweeper
 * Technique: 2D Array / Matrix Boundary checking using
 *            if conditions.
 */

#include<stdio.h>
#include<string.h>


#define MAXSIZE 101


static char MineField[MAXSIZE][MAXSIZE];



int main(){

    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);


    int n, m;

    int FieldNumber = 0;

    while( scanf("%d%d", &n, &m), n ){

        getchar();

        for(int i = 0; i < n; ++i)
            scanf("%s", &MineField[i]);


        if( FieldNumber )
            printf("\n");


        for(int i = 0; i < n; ++i){
            for(int j = 0; j < m; ++j){

                if( MineField[i][j] == '*' )
                    continue;

                int temp = 0;

                if( i + 1 < n && MineField[i + 1][j] == '*' )
                    ++temp;
                if( i + 1 < n && j + 1 < m && MineField[i + 1][j + 1] == '*' )
                    ++temp;
                if( j + 1 < m && MineField[i][j + 1] == '*' )
                    ++temp;
                if( i - 1 >= 0 && j + 1 < m && MineField[i - 1][j + 1] == '*' )
                    ++temp;
                if( i - 1 >= 0 && MineField[i - 1][j] == '*' )
                    ++temp;
                if( i - 1 >= 0 && j - 1 >= 0 && MineField[i - 1][j - 1] == '*' )
                    ++temp;
                if( j - 1 >= 0 && MineField[i][j - 1] == '*' )
                    ++temp;
                if( i + 1 < n && j - 1 >= 0 && MineField[i + 1][j - 1] == '*' )
                    ++temp;


            MineField[i][j] = temp + '0';

            }
        }


        printf("Field #%d:\n", ++FieldNumber);


       for(int i = 0; i < n; ++i){
            for(int j = 0; j < m; ++j)
                putchar(MineField[i][j]);
            printf("\n");
       }

    }

    return 0;
}

Code Bound checking using Array & for Loop:

/**
 * Author:    Asif Ahmed
 * Site:      https://quickgrid.wordpress.com
 * Problem:   UVA 10189 - Minesweeper
 * Technique: 2D Array / Matrix Boundary checking using
 *            co-ordinate array and for loop.
 */

#include<stdio.h>
#include<string.h>


#define MAXSIZE 101


static char MineField[MAXSIZE][MAXSIZE];


// Co-ordinates / directions of adjacent 8 squares.
// W, SW, S, SE, E, NE, N, NW
static const int drow[] = {0, 1, 1, 1, 0, -1, -1, -1};
static const int dcol[] = {-1, -1, 0, 1, 1, 1, 0, -1};



int main(){

    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);


    int n, m;

    int FieldNumber = 0;

    while( scanf("%d%d", &n, &m), n ){

        getchar();

        for(int i = 0; i < n; ++i)
            scanf("%s", &MineField[i]);


        if( FieldNumber )
            printf("\n");


        for(int i = 0; i < n; ++i){
            for(int j = 0; j < m; ++j){

                int temp = 0;

                // If mine found do nothing.
                if( MineField[i][j] == '*' )
                    continue;


                // For each adjacent squares of the current square calculate mine count.
                // and set the count in current square.
                for(int k = 0; k < 8; ++k){

                    // Check if out of bound of the 2D array or matrix.
                    if( i + drow[k] < 0 || j + dcol[k] < 0 || i + drow[k] >= n || j + dcol[k] >= m )
                        continue;

                    // Check the appropriate co-ordinate for mine, if mine found increase count.
                    if( MineField[i + drow[k] ][j + dcol[k]] == '*' )
                        ++temp;

                }

                // All adjacent squares checked set the mine count for current squares.
                MineField[i][j] = temp + '0';

            }
        }


        printf("Field #%d:\n", ++FieldNumber);


       for(int i = 0; i < n; ++i){
            for(int j = 0; j < m; ++j)
                putchar(MineField[i][j]);
            printf("\n");
       }

    }

    return 0;
}
Advertisements

UVA Problem 11565 – Simple Equations Solution

UVA Problem 11565 – Simple Equations Solution:


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

UPDATE:

As a commenter below pointed out the solution is wrong due to the fact I made some wrong assumptions. Kindly check other sources for correct solution. This was accepted due to weak test cases. Also check udebug for different test cases.

Problem Statement Description:

Given input of A, B, C where 0 \leqslant A, B, C \leqslant 10000 and three equations,

\mathbf{ x + y + z = A }
\mathbf{ x.y.z = B }
\mathbf{ x^2 + y^2 + z^2 = C }

The task is to find values of x, y, z where x, y, z are three different integers which is ( x != y != z ). Meaning x can not be equal to y, t can not be equal to z and z can not be equal to x.

The problem asks to output the least value of x then y then z meaning the output will be in x < y < z order.


Things to notice:

One very important thing to notice is that for all three equation the values of x, y, z can be interchanged and it will still satisfy the problem.

For example,
\mathbf{ if, x = 5, y = 0, z = 9 }

then it can also be written as,
\mathbf{ x = 0, y = 5, z = 9 }
\mathbf{ x = 9, y = 5, z = 0 }

etc. all possible combinations. But the problem asks for least value of x then y then z.

So if after calculation the result is x = 9, y = 0, z = 5 which is supposed to be x = 0, y = 5, z = 9. In that case the values can be sorted which will result in x = 0, y = 5, z = 9 and this still satisfies the equations.


Solution Technique Explanation:

The simple approach to solve this problem is try all possible combinations of x, y, z and see if it produces a correct result.

The values of x, y, z being negative also satisfies this problem. Forgetting the value of negatives for the moment and focusing on the positive values. To get the naive loop count limit see x or y or z can be at least 0 and at most 100.

Same goes for the negative portion so looping for -100 to 100 for each 3 nested loops seem easy ( I haven’t given the 3 nested loop solution here. It can be found on other sites ). So from -100 to 0 to 100 there are 201 number in between. So naive solution requires 201*201*201 which is more than 8 million (8120601). This program should do 117 * 45 = 5265 iterations per test case.


This problem can be solve much faster using some algebraic substitution. Notice,

\mathbf{ x + y + z = A ........ (i) \\ }
\mathbf{ x.y.z = B ........ (ii) \\ }
\mathbf{ x^2 + y^2 + z^2 = C ........ (iii) \\ }

from equation (ii),

\mathbf{ x.y.z = B }

This can be rewritten as,

\mathbf{ z = \frac{B}{x.y} ........ (iv) }

from equation (i),

\mathbf{ x + y + z = A }

substituting value of z from (iv) to (i) gives,

\mathbf{ x + y + \frac{B}{x.y} = A }

This can be rewritten as,

\mathbf{ \frac{B}{x.y} = A - x - y ........ (v) }

similarly from (iii) and (iv),

\mathbf{ x^2 + y^2 + z^2 = C }

plugging in the value of z and solving for x and y,

\mathbf{ x^2 + y^2 + ( \frac{B}{x.y} )^2 = C ........ (vi) }

Now from (v) and (vi),
\mathbf{ x^2 + y^2 + (A - x - y)^2 = C }

Notice this equation above does not contain z. Now z can be calculated in terms of B, x, y.

This will completely remove one of the nested loops. Further improvements can be made by cutting down number of loop iterations.


Important point to notice that A, B, C can be at most 10000. Also x, y, z can differ by 1 and satisfy the equation. From above equations,

\mathbf{ x + y + z = A ........ (i) }
\mathbf{ x.y.z = B ........ (ii) }
\mathbf{ x^2 + y^2 + z^2 = C ........ (iii) }

So if x, y, z differ by 1 then,

\mathbf{ y = x + 1 }
\mathbf{ z = x + 2 }

from equation (i),

\mathbf{ x + (x + 1) + (x + 2) = A }

but A can be at most 10000.

\mathbf{ x + (x + 1) + (x + 2) = 10000 }
\mathbf{ 3x + 3 = 10000 }

So, x = 3332.3333….

But to keep it simple, notice the lower order term 3 does not make much difference. By setting x = y = z the equation can be,

\mathbf{ x + x + x = 10000 }
\mathbf{ 3x = 10000 }
\mathbf{ x = 3333.3333.... }


from equation (iii) since x is squared so it to get its iteration just calculate the square root. or, setting x = y = z and B = 10000 in equation (iii) gives,

\mathbf{ x^2 + x^2 + x^2 = 10000 }
\mathbf{ 3x^2 = 10000 }
\mathbf{ x = 57.735.... }

after rounding of,
x = 58

So the loop range for x is [-58…58].


Again from equation (ii) the iteration limit for y can be counted using x = y = z,

\mathbf{ y.y.y = 10000 }
\mathbf{ y^3 = 10000 }
\mathbf{ y = 21.544.... }

Rounded of to,
y = 22

So iteration limit for y will be from [-22…22].

Calculating using y + 1 result in rounded range [-21…21]. Although I have not tested it.


Doing further algebraic simplification will remove another loop as z can be calculated in terms of A,B,C using,

\mathbf{ (A-z)^2 - 2.\frac{B}{z} = C - z^2 }

where,

\mathbf{ xy = \frac{B}{z} }

and,

\mathbf{ x + y = A - z }

using the main equation above, the value of z can be found and by solving the other equations the values of x and y can be calculated.


Also the loops can be input dependent. If max of A, B, C is bigger than 58 than choose 58 other wise choose the max as the loop counter.

There may be more improvements possible but that’s all I can come up with now. One final improvement can be made by breaking from all loops at once once the values are found. Although goto isn’t recommended c++ doesn’t support label to break out of multiple loops unlike java.

Important:  Be sure to add or print a new line after each output unless otherwise specified. The outputs should match exactly because sometimes even a space character causes the answer to be marked as wrong answer. Please compile with c++ compiler as some of my codes are in c and some in c++.


More Inputs of This Problem on uDebug.


Input:

2
1 2 3
6 6 14

Output:

No solution.
1 2 3

Optimized Code without goto:

/**
 * Author:    Asif Ahmed
 * Site:      https://quickgrid.wordpress.com
 * Problem:   UVA 11565 - Simple Equations
 * Technique: Mathematical elimination and substitution
 */

#include<cstdio>
#include<algorithm>
#include<iostream>

int main(){
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int n;
    scanf("%d", &n);

    int A, B, C;

    while( n-- ){
        scanf("%d%d%d", &A, &B, &C);

        bool solutionFound = false;
        int x, y, z;

        for( x = -58; x <= 58; ++x ){
            for( y = -22; y <= 22; ++y ){

                if( x != y && ( (x * x + y * y) + (A - x - y) * (A - x - y) == C )  ){

                    int temp = x * y;

                    if( temp == 0 ) continue;

                    z = B / temp;

                    if( z != x && z != y && x + y + z == A   ){
                        if(!solutionFound){
                            int tmpArray[3] = {x, y, z};
                            std::sort(tmpArray, tmpArray + 3);
                            std::cout << tmpArray[0] << " " << tmpArray[1] << " " << tmpArray[2] << "\n";

                            solutionFound = true;
                            break;
                        }
                    }

                }
            }
        }

        if(!solutionFound) std::cout << "No solution." << "\n";

    }

    return 0;
}

Optimized Code without goto:

/**
 * Author:    Asif Ahmed
 * Site:      https://quickgrid.wordpress.com
 * Problem:   UVA 11565 - Simple Equations
 * Technique: Mathematical elimination and substitution
 */

#include<cstdio>
#include<algorithm>
#include<iostream>

int main(){
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int n;
    scanf("%d", &n);

    int A, B, C;

    while( n-- ){
        scanf("%d%d%d", &A, &B, &C);

        bool solutionFound = false;
        int x, y, z;

        for( x = -58; x <= 58; ++x ){
            for( y = -22; y <= 22; ++y ){

                if( x != y && ( (x * x + y * y) + (A - x - y) * (A - x - y) == C )  ){

                    int temp = x * y;

                    if( temp == 0 ) continue;

                    z = B / temp;

                    if( z != x && z != y && x + y + z == A   ){
                        if(!solutionFound){
                            int tmpArray[3] = {x, y, z};
                            std::sort(tmpArray, tmpArray + 3);
                            std::cout << tmpArray[0] << " " << tmpArray[1] << " " << tmpArray[2] << "\n";

                            solutionFound = true;
                            goto done;
                        }
                    }

                }
            }
        }

        if(!solutionFound) std::cout << "No solution." << "\n";
        done:;

    }

    return 0;
}

 

Digital Logic: Designing Decimal to 4 bit Gray Code Converter

Gray Code:

Difference of gray code from binary is that, for each group only one bit changes when going from one number to the next. In case of binary it can be seen from the table that multiple bit may change when going from one number to next.

How to Create Gray Code Sequence:

There are multiple shortcut technique to write gray code. This is the technique I follow,

First start with,

0
1

Next step, Add 0’s before both of them,

0 | 0
0 | 1

Next Mirror ( Write the values bottom to top instead of top to bottom ) all bits except for Left Most bit and Add 1’s in the place left most bit,

0 | 0
0 | 1
  ------> Mirror
1 | 1
1 | 0

Continuing this process again of adding 0’s before all numbers and Mirroring all bits except left most bit, then adding 1’s in place of left most bit,

0 | 0 0
0 | 0 1
0 | 1 1
0 | 1 0
  -------> Mirror
1 | 1 0
1 | 1 1
1 | 0 1
1 | 0 0

Now following same procedure for 4 bits,

0 | 0 0 0
0 | 0 0 1
0 | 0 1 1
0 | 0 1 0
0 | 1 1 0
0 | 1 1 1
0 | 1 0 1
0 | 1 0 0
  --------> Mirror
1 | 1 0 0
1 | 1 0 1
1 | 1 1 1
1 | 1 1 0
1 | 0 1 0
1 | 0 1 1
1 | 0 0 1
1 | 0 0 0

finally 4 bit gray code representing Decimal 0 to 15,

0 0 0 0
0 0 0 1
0 0 1 1
0 0 1 0
0 1 1 0
0 1 1 1
0 1 0 1
0 1 0 0
1 1 0 0
1 1 0 1
1 1 1 1
1 1 1 0
1 0 1 0
1 0 1 1
1 0 0 1
1 0 0 0

Now just start from the top with 0 and increment it by 1. That will be the decimal equivalent of the gray code.


Binary, Decimal and Gray Code Table:

Here I am representing gray code bits with A, Decimal values with D and Binary bits with B.

Binary Decimal Gray Code
B3 B2 B1 B0 D A3 A2 A1 A0
0 0 0 0 0 0 0 0 0
0 0 0 0 1 0 0 0 1
0 0 1 0 2 0 0 1 1
0 0 1 1 3 0 0 1 0
0 1 0 0 4 0 1 1 0
0 1 0 1 5 0 1 1 1
0 1 1 0  6 0 1 0 1
0 1 1 1 7 0 1 0 0
1 0 0 0 8 1 1 0 0
1 0 0 1 9 1 1 0 1
1 0 1 0 10 1 1 1 1
1 0 1 1 11 1 1 1 0
1 1 0 0 12 1 0 1 0
1 1 0 1 13 1 0 1 1
1 1 1 0 14 1 0 0 1
1 1 1 1 15 1 0 0 0

Making Decimal to Gray Converter:

Since this is Decimal to Gray Code converter, the Binary part of the table could be omitted.

A_3 = D_8 + D_9 + D_{10} + D_{11} + D_{12} + D_{13} + D_{14} + D_{15} \\  A_2 = D_4 + D_5 + D_6    + D_7    + D_8    + D_9    + D_{10} + D_{11} \\  A_1 = D_2 + D_3 + D_{4}  + D_{5}  + D_{10} + D_{11} + D_{12} + D_{13} \\  A_0 = D_1 + D_2 + D_5    + D_6    + D_9    + D_{10} + D_{13} + D_{14} \\

Let,

X_1 = D_4    + D_5 \\  X_2 = D_8    + D_9 \\  X_3 = D_{10} + D_{11} \\  X_4 = D_{12} + D_{13} \\  X_5 = X_2 + X_3 \\

From the above expression,

A_3 = X_2 + X_3 + X_4 + D_{14} + D_{15} \\  .... = X_5 + X_4 + D_{14} + D_{15} \\  \\    A_2 = X_1 + D_6 + D_7 + X_2    + X_3 \\  .... = X_1 + D_6 + D_7 + X_5 \\  \\    A_1 = D_2 + D_3 + X_1  + X_3 + X_4 \\    \\  A_0 = D_1 + D_2 + D_5    + D_6    + D_9    + D_{10} + D_{13} + D_{14} \\    \\


Inputs and Outputs:

For the circuit there will be inputs each representing a decimal number. The number of outputs will be 4 from A_3 \text{ to } A_0 where, A_0 \text{ is the LSB and } A_3 \text{ is the MSB} .


How to test if its working:

Just press each buttons in the left one at a time then check to see if the values given match the value in table. The values are read bottom to top, equivalent to reading values from table left to right.


Circuit Diagram:

Download the file named 4 bit decimal to gray code converter circuit diagram from my Github.

4 bit decimal to gray code converter diagram
4 bit decimal to gray code converter diagram

UVA Problem 264 – Count on Cantor Solution

UVA Problem 264 – Count on Cantor Solution:


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

Solving Technique:

Warning this is a terrible dynamic programming and memoization solution. If you want a fast and efficient solution then, this isn’t what you are looking for.

Problem Statement:

Given an input integer that represent a rational number sequence term shown by cantor, output the rational number for that term.


Solution Types:

I have given two solution, one of which uses a 2D array to store the rational number sequence as shown by cantor and using a traversal pattern memoize the series in another array. Although the first one can be improved to only traverse 1/4 th of the array but that’s still a lot.

The next solution discards the 2D array and using the traversal pattern with some optimization memoizes the series.

The time difference as of UVA submission running time is,

0.245 ms (1st technique)
0.072 ms (2nd technique)

Removing the recursion by replacing with iterative version ( A bit harder to do ) will make it even faster. I think this one can be further improved but have no idea how.

Figuring out the algorithm:


Note everything here is assuming indexing starts from 1 instead of 0. But in my code I start with index 0 instead of 1.

 

Sequence Traversal within Matrix:
cantor sequence matrix
cantor sequence matrix

Unraveling the Sequence:
cantor sequence chain
cantor sequence chain

Traversal Pattern and Sub structure/pattern:
cantor structure and substructure pattern
cantor structure and substructure pattern

Substructure and Movement within Matrix:
cantor movement within matrix
cantor movement within matrix

Points To Notice:

1. Moves right when row number is 0 and column number is even.
2. Moves down-left when row number is 0 and column number is odd.
3. Moves down when column number is 0 and column number is odd.
4. Moves up-right when column number is 0 and column number is even.
5. Diagonal traversal gets bigger by 1 unit for each down or right movements.


Traversing the Matrix:

Traverse(r,c,index,diagonal) =     \begin{cases}      \rightarrow \text{(1 times)} & \forall : row = 0; col \in Even \\     \swarrow \text{(c - 1 times)} & \forall : row = 0; col \in Odd \\     \downarrow \ \ \text{(1 times)} & \forall : col = 0; row \in Odd \\     \nearrow \text{(r - 1 times)} & \forall : col = 0; row \in Even \\    \end{cases}

OR, In my code,

Traverse(r,c,index,diagonal) =     \begin{cases}      \rightarrow \text{(1 times)} & \forall : row = 0; col \in Even \\     \swarrow \text{(c + diagonal times)} & \forall : row = 0; col \in Odd \\     \downarrow \ \ \text{(1 times)} & \forall : col = 0; row \in Odd \\     \nearrow \text{(r + diagonal times)} & \forall : col = 0; row \in Even \\    \end{cases}

Note: Increment the index and diagonal also.


Filling the Matrix (1st code only):

CantorTable_{i,j} =     \begin{cases}      numerator = row, & \forall : Column, rows \\     denominator = column, & \forall : Column, rows \\    \end{cases}


Base case:

Note when row or the column is equal to 0 then there is a turn. If row or column becomes less than 0 then it should stop.

Also the amount values to memoize is N which is the maximum cantor sequence value for this problem. So if N values are memoized then the process should stop.

if (r < 0 || c < 0 || index > M)
    return;

Storing the fractions in 2D Struct Array:

Instead of storing the values in string it is better to store the fraction in a struct. There are 3 things in the fraction the numerator, a division sign , the denominator. There is no need to store the division sign since all elements within matrix are fraction.

struct CantorSequence{
    int numerator;
    int denominator;
};

About Space:

The first solution requires a total of O( M + \frac{N(N+1)}{2} ) space including storing the cantor sequence in another array and pre calculating the 2D cantor table and traversing.

The second solution requires a total of O( M ) space including storing the cantor sequence in another array.

Here, M is 10000000 and N is 4500. N can be adjusted but 4500 is a safe value.


Please point out if the post contains mistakes.

 

Important:  Be sure to add or print a new line after each output unless otherwise specified. The outputs should match exactly because sometimes even a space character causes the answer to be marked as wrong answer. Please compile with c++ compiler as some of my codes are in c and some in c++.


More Inputs of This Problem on uDebug.


Input:

3
14
7
10000000 

 


Output:

TERM 3 IS 2/1
TERM 14 IS 2/4
TERM 7 IS 1/4
TERM 10000000 IS 2844/1629

Code Recursive DP 2D struct Traversal and Memoize:

/***********************************************************************
 * Author:    Asif Ahmed
 * Site:      https://quickgrid.wordpress.com
 * Problem:   UVA 264 - Count on Cantor
 *
 * Technique: Zig Zag / Spiral Diagonal traversal,
 *            2D struct array,
 *            2D half diagonal fill,
 *            Recursive Dynamic Programming
 ***********************************************************************/


#include<stdio.h>
#include<string.h>

// N * N should be almost twice greater than or equal to M.
// Or, N should be such that N*(N+1)/2 is greater than M.
#define N 4500


#define M 10000000


/**
 * Table to construct the sequence
 */
struct CantorTable{
    int numerator;
    int denominator;
} CT[N][N];


// Holds cantor values from 1 to M by index
CantorTable OrderedCantor[M];


/**
 * Fill in the cantor table.
 */
void CantorFill(){

    for(int row = 0; row < N; ++row){

        int cutoff = N - row;

        for(int col = 0; col < cutoff; ++col){
            CT[row][col].numerator   = row + 1;
            CT[row][col].denominator = col + 1;
        }

    }

}


void RecursiveCantor(int r, int c, int index, int diagonal){

    // base case
    if( r < 0 || c < 0 || index > M ){
        return;
    }


    OrderedCantor[index].numerator = CT[r][c].numerator;
    OrderedCantor[index].denominator = CT[r][c].denominator;



    // Amount of times to travel in diagonal
    ++diagonal;



    if(r == 0){

        // when odd move down left
        if(c % 2){
            for(int i = 0; i < c + diagonal; ++i){
                ++index;
                r = r + 1;
                c = c - 1;
                RecursiveCantor( r, c, index, diagonal );
            }
        }

        // when even Move right
        else{
            ++index;
            c = c + 1;
            RecursiveCantor( r, c, index, diagonal );
        }
    }

    if(c == 0){

        // when odd move down
        if(r % 2){
            ++index;
            r = r + 1;
            RecursiveCantor( r, c, index, diagonal );
        }

        // when even Move up right
        else{
            for(int i = 0; i < r + diagonal; ++i){
                ++index;
                r = r - 1;
                c = c + 1;
                RecursiveCantor( r, c, index, diagonal );
            }
        }

    }

}



int main() {


    // Initialize Cantor table
    CantorFill();


    // Pass in row, column, index, diagonal traversal size
    RecursiveCantor(0, 0, 1, 0);


    int n;


    while( scanf("%d", &n) == 1 ){
        printf("TERM %d IS %d/%d\n", n, OrderedCantor[n].numerator, OrderedCantor[n].denominator );
    }

    return 0;
}


Code Recursive DP Sequence Memoize:

/***********************************************************************
 * Author:    Asif Ahmed
 * Site:      https://quickgrid.wordpress.com
 * Problem:   UVA 264 - Count on Cantor
 *
 * Technique: Zig Zag / Spiral Diagonal traversal,
 *            Recursive Dynamic Programming
 ***********************************************************************/


#include<stdio.h>
#include<string.h>


#define M 10000000


/**
 * Table to construct the sequence
 */
struct CantorTable{
    int numerator;
    int denominator;
};


// Holds cantor values from 1 to M by index
CantorTable OrderedCantor[M];




void RecursiveCantor(int r, int c, int index, int diagonal){

    // base case
    if( r < 0 || c < 0 || index > M ){
        return;
    }


    // change from table traversed DP
    OrderedCantor[index].numerator = r + 1;
    OrderedCantor[index].denominator = c + 1;


    // Amount of times to travel in diagonal
    ++diagonal;



    if(r == 0){

        // when odd move down left
        if(c % 2){
            for(int i = 0; i < c + diagonal; ++i){
                ++index;
                r = r + 1;
                c = c - 1;
                RecursiveCantor( r, c, index, diagonal );
            }
        }

        // when even Move right
        else{
            ++index;
            c = c + 1;
            RecursiveCantor( r, c, index, diagonal );
        }
    }

    else if(c == 0){

        // when odd move down
        if(r % 2){
            ++index;
            r = r + 1;
            RecursiveCantor( r, c, index, diagonal );
        }

        // when even Move up right
        else{
            for(int i = 0; i < r + diagonal; ++i){
                ++index;
                r = r - 1;
                c = c + 1;
                RecursiveCantor( r, c, index, diagonal );
            }
        }

    }

}



int main() {

    // Pass in row, column, index, diagonal traversal size
    RecursiveCantor(0, 0, 1, 0);


    int n;


    while( scanf("%d", &n) == 1 ){
        printf("TERM %d IS %d/%d\n", n, OrderedCantor[n].numerator, OrderedCantor[n].denominator );
    }

    return 0;
}

UVA Problem 10921 – Find the Telephone Solution

UVA Problem 10921 – Find the Telephone Solution:


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

Solving Technique:

Given a string of alphabets (A-Z), 1, 0, and Hyphens( – ) task for this problem is to find numbers represented by a character from the given table.

1, 0, Hyphen should not be changed since they aren’t in table. Just change a character with its integer representation from table. Easiest way to do this is create a mapping array with pattern from the table. Then map the pattern to each character and print result.

 

Important:  Be sure to add or print a new line after each output unless otherwise specified. The outputs should match exactly because sometimes even a space character causes the answer to be marked as wrong answer. Please compile with c++ compiler as some of my codes are in c and some in c++.


More Inputs of This Problem on uDebug.


Input:

1-HOME-SWEET-HOME
MY-MISERABLE-JOB

 


Output:

1-4663-79338-4663
69-647372253-562

Code:

/**
 * Author:    Asif Ahmed
 * Site:      https://quickgrid.wordpress.com
 * Problem:   UVA 10921 - Find The Telephone
 * Technique: Mapping character from an array to another.
 */

#include<stdio.h>
#include<string.h>


#define N 128


static char mappingArray[N] = "22233344455566677778889999";


static char table[N];
static char input[N];


int main(){

    /**
     * The code below fill 'A' to 'O' with appropriate values.
     * Not necessary when using mapping array.
     */
    /*
    for(int i = 0; i <= 15; ++i ){
        table[64 + i] = k;
        if(i % 3 == 0) ++k;
    }
    */


    int k = 0;

    /**
     * Map each character index to integer value from mapping array.
     */
    for(int i = 'A'; i <= 'Z'; ++i)
        table[i] = mappingArray[k++];


    /**
     * These characters don't change.
     */
    table['-'] = '-';
    table['0'] = '0';
    table['1'] = '1';


    /**
     * Take input, then iterate through each character
     * and print the character indexed value from table.
     */
    while( gets(input) ){
        for(int i = 0; input[i]; ++i)
            printf("%c", table[ input[i] ]);
        printf("\n");
    }

    return 0;
}

UVA Problem 10008 – What’s Cryptanalysis? Solution

UVA Problem 10008 – What’s Cryptanalysis? Solution:


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

Solving Technique:

Task for this problem is to find occurrence of each alphabetical character. Uppercase and lowercase are treated as same characters. No other characters except for upper and lower case characters must be counted.

After counting their occurrence print them in most to least order. If multiple characters have same character count then print the characters alphabetically. Ex: If E occurred 2 times, A occurred 2 times then, print A first then E.
 

Important:  Be sure to add or print a new line after each output unless otherwise specified. The outputs should match exactly because sometimes even a space character causes the answer to be marked as wrong answer. Please compile with c++ compiler as some of my codes are in c and some in c++.


More Inputs of This Problem on uDebug.


Input:

3
This is a test.
Count me 1 2 3 4 5.
Wow!!!! Is this question easy?

 


Output:

S 7
T 6
I 5
E 4
O 3
A 2
H 2
N 2
U 2
W 2
C 1
M 1
Q 1
Y 1

Code:

/**
 * Author:    Asif Ahmed
 * Site:      https://quickgrid.wordpress.com
 * Problem:   UVA 10008 - What's Cryptanalysis
 * Technique: Counting character occurrence in string,
 *            Lexicographical / alphabetically sort characters,
 */


#include<stdio.h>
#include<string.h>
#include<algorithm>


#define N 256


// Holds each character and its occurrence in string.
struct collection{
    char character;
    int occurence;
} node[26];


static char s[N];


// Sorts based on occurrence, if occurrence count is same
// then sort using lexicographical / alphabetically first character.
int cmp(collection a, collection b){

    if(a.occurence < b.occurence)
        return 0;
    else if(a.occurence > b.occurence)
        return 1;
    else
        return (a.character <= b.character) ? 1 : 0;

}



int main(){

    // O(1)
    // Represent character by its ASCII value index.
    for(int i = 'A'; i <= 'Z'; ++i)
        node[i].character = i;

    int n;

    scanf("%d", &n);
    getchar();

    while( n-- ){

        gets( s );

        // Convert string to uppercase O(n)
        for(int i = 0; s[i]; ++i){
            if( s[i] >= 'a' && s[i] <= 'z')
                s[i] = s[i] - 32;
        }


        // O(n)
        // Counting using character index
        for(int i = 0; s[i]; ++i){
            if( s[i] >= 'A' && s[i] <= 'Z' )
                ++node[ s[i] ].occurence;
        }

    }


    // Sorts occurrence most to least and in lexicographic order.
    std::sort(node + 'A', node + 'Z', cmp);


    // O(1)
    // Prints sorted occurrence most to least.
    // Also prints characters in lexicographic
    // order if two occurrence are same.
    for(int i = 'A'; i <= 'Z'; ++i){
        if(node[i].occurence)
            printf("%c %d\n", node[i].character, node[i].occurence);
    }



    return 0;
}

UVA Problem 11713 – Abstract Names Solution

UVA Problem 11713 – Abstract Names Solution:


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

Solving Technique:

For input of n there will be 2*n lines. Task is to match a pair of lines. The vowels a, e, i, o, u in the strings doesn’t matter. Except these the rest of both strings should match.

That means each character in a index from both strings should match. Their order needs to be same. Except vowels if the match then output is yes. Otherwise the output is no.

 

Important:  Be sure to add or print a new line after each output unless otherwise specified. The outputs should match exactly because sometimes even a space character causes the answer to be marked as wrong answer. Please compile with c++ compiler as some of my codes are in c and some in c++.


More Inputs of This Problem on uDebug.


Input:

5
pele
polo
pele
pola
ronaldo
ronaldino
pele
pelet
pele
bele

 


Output:

Yes
Yes
No
No
No

Code:

/**
 * Author:    Asif Ahmed
 * Site:      https://quickgrid.wordpress.com
 * Problem:   UVA 11713 - Abstract Names
 * Technique: Removing specific characters from string
 *            by copying into another string.
 */

#include<stdio.h>
#include<string.h>

#define N 36


static char s[N];
static char t[N];

static char tmpS[N];
static char tmpT[N];


int main(){

    int n;

    scanf("%d", &n);
    getchar();

    while( n-- ){


        gets(s);
        gets(t);


        // If their length is not the same then output is no.
        if( strlen(s) != strlen(t) ){
            printf("No\n");
            continue;
        }


        // Reset memory.
        int j = 0, k = 0;
        memset(tmpS, 0, sizeof tmpS);
        memset(tmpT, 0, sizeof tmpT);


        // Remove vowels from the first string.
        for(int i = 0; s[i]; ++i){
            if(s[i] == 'a' || s[i] == 'e' || s[i] == 'i' || s[i] == 'o' || s[i] == 'u')
                continue;
            else
                tmpS[j++] = s[i];
        }


        // Remove vowels from the second the string.
        for(int i = 0; t[i]; ++i){
            if(t[i] == 'a' || t[i] == 'e' || t[i] == 'i' || t[i] == 'o' || t[i] == 'u')
                continue;
            else
                tmpT[k++] = t[i];
        }


        // After removing the vowels the strings should match.
        if( strcmp(tmpS, tmpT) == 0 )
            printf("Yes\n");
        else
            printf("No\n");

    }

    return 0;
}

UVA Problem 424 – Integer Inquiry Solution

UVA Problem 424 – Integer Inquiry Solution:


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

Solving Technique:

This problem requires adding integers. The integers are very long, meaning they won’t fit even in long long. So the addition needs to be done using arrays.

It can be solved using integers arrays but my solution uses character array. Code is explained in the comments.

Similar to this problem UVA 10035 Primary Arithmetic and UVA 713 – Adding Reversed Numbers.

 

Important:  Be sure to add or print a new line after each output unless otherwise specified. The outputs should match exactly because sometimes even a space character causes the answer to be marked as wrong answer. Please compile with c++ compiler as some of my codes are in c and some in c++.


More Inputs of This Problem on uDebug.


Input:

123456789012345678901234567890
123456789012345678901234567890
123456789012345678901234567890
0

 


Output:

370370367037037036703703703670

Code:

/**
 * Author:    Asif Ahmed
 * Site:      https://quickgrid.wordpress.com
 * Problem:   UVA 424 - Integer Inquiry
 * Technique: Adding Multi String Integer characters column wise
 */


#include<stdio.h>
#include<string.h>

#define N 160


static char s[N][N];
static char output[N];



int main(){

    int i = 0;

    int maxlen = 0;


    // Finish taking all the inputs.
    while( gets(s[i]) ){

        // Exit for input of 0.
        if( s[i][0] == '0' && ! s[i][1] )
            break;

        int len = strlen( s[i] );

        // Get the max length to create padding.
        if( len > maxlen )
            maxlen = len;

        ++i;
    }

    // Save rows
    int rows = i;


    // Create padding for each of the strings.
    for(int j = 0; j < i; ++j){

        int temp = strlen( s[j] );

        if( temp != maxlen ){

            // Shift by this many spaces to create 0's in front.
            int padding = maxlen - temp;

            // shift by padding columns.
            for(int k = temp - 1; k >= 0; --k)
                s[j][k + padding] = s[j][k];

            // Add 0's as paddings.
            for(int k = 0; k < padding; ++k)
                s[j][k] = '0';
        }
    }


    int carry = 0, z = 0;

    for(int j = maxlen - 1; j >= 0; --j){

        int sum = 0;

        // Add values column wise.
        for(int i = 0; i < rows; ++i)
            sum += s[i][j] - '0';

        // Add if any previous  carry
        sum = sum + carry;

        // Add value to output
        output[z++] = sum % 10 + '0';

        // get the carry for adding to next column
        carry = sum / 10;

    }

    // Print if any carry first
    if(carry)
        printf("%d", carry);


    // Then print what ever character is left
    for(int i = z - 1; i >= 0; --i){
        if(output[i] >= '0' && output[i] <= '9')
            printf("%c", output[i]);
    }
    printf("\n");

    return 0;
}

UVA Problem 10035 – Primary Arithmetic Solution

UVA Problem 10035 – Primary Arithmetic Solution:


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

Solving Technique:

For this problem two integers less than 10 digits are given. The task is to find how many carry operations occur when adding.

This problem may be solved using strings since input integer is less than 10 digits. It can be solved with out using array. My implementation is using character array to add and count carry operations.

Similar to this UVA 713 – Adding Reversed Numbers Solution and UVA PROBLEM 1225 – DIGIT COUNTING

 

Important:  Be sure to add or print a new line after each output unless otherwise specified. The outputs should match exactly because sometimes even a space character causes the answer to be marked as wrong answer. Please compile with c++ compiler as some of my codes are in c and some in c++.


More Inputs of This Problem on uDebug.


Input:

123 456
555 555
123 594
0 0

 


Output:

No carry operation.
3 carry operations.
1 carry operation.

Code:

/**
 * Author:    Asif Ahmed
 * Site:      https://quickgrid.wordpress.com
 * Problem:   UVA 10035 - Primary Arithmetic
 * Technique: Adding leading 0's integer string,
 *            Making two strings of same length,
 *            Adding String Integers.
 */

#include<stdio.h>
#include<string.h>

#define N 128

static char s[N];
static char t[N];

static char output[N];


int main(){

    while( scanf("%s", s) && scanf("%s", t) ){

        // Although a major flaw input beginning with 0 and
        // two strings matching. But for this problem it doesn't matter.
        if( strcmp(s,t) == 0 && s[0] == '0' )
            break;


        int lens = strlen(s);
        int lent = strlen(t);


        // Add leading 0's to smaller string (May not be necessary).
        // Shift each characters in string right by padding length.
        if( lens > lent ){

            int padding = lens - lent;

            for(int i = lent - 1; i >= 0; --i)
                t[i + padding] = t[i];

            for(int i = 0; i < padding; ++i)
                t[i] = '0';
        }

        else if( lens < lent ){

            int padding = lent - lens;

            for(int i = lens - 1; i >= 0; --i)
                s[i + padding] = s[i];

            for(int i = 0; i < padding; ++i)
                s[i] = '0';
        }



        int maxlen;
        if(lens > lent)
            maxlen = lens;
        else maxlen = lent;


        int carry = 0;
        int c = 0;
        int sum = 0;


        // Add two Strings, if a carry operation occurs
        // then add that to the count.
        for(int i = maxlen - 1; i >= 0; --i){

            sum += s[i] - '0' + t[i] - '0';

            sum = sum + carry;

            carry = sum / 10;

            if(carry)
                ++c;

            sum = 0;

        }


        if(!c)
            printf("No carry operation.\n");
        else if( c > 1 )
            printf("%d carry operations.\n", c);
        else
            printf("%d carry operation.\n", c);

    }

    return 0;
}

UVA Problem 713 – Adding Reversed Numbers Solution

UVA Problem 713 – Adding Reversed Numbers Solution:


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

Solving Technique:

The biggest problem in this problem is that there is no built in data type to hold 200 digit numbers. Although this problem is good in sense that it says that the number can be 200 characters long.

To handle this large number array is needed. while others may have solved using integer array and their methods may be faster. But mine addition is using character array.

The problem can be solved in a few ways. One which is reversing two string. Then added leading 0’s to the smaller string then adding and printing the result.

Another method is to add trailing 0’s to smaller string if their length differ. Then add them and print the result if starting from left most column. Other wise print result in reverse if calculating from right most column.


For example using first method,

when input is 24 and 1, their reversal is,

42
01
==
43

Since i am using right most column as 0 th index. So the result will be 34.

Again for input 4358 and 754,

8534
0457
====
8991

Result will be 1998. This is because i am starting calculation from rightmost column and moving carry to left.


Another method is adding as is then print result from left,
4358
7540
====
1998

I’ve implemented the first method only. The code is explained in comments.

 

Important:  Be sure to add or print a new line after each output unless otherwise specified. The outputs should match exactly because sometimes even a space character causes the answer to be marked as wrong answer. Please compile with c++ compiler as some of my codes are in c and some in c++.


More Inputs of This Problem on uDebug.


Input:

3
24 1
4358 754
305 794

 


Output:

34
1998
1

Code:

/***********************************************************************
 * Author:    Asif Ahmed
 * Site:      https://quickgrid.wordpress.com
 * Problem:   UVA 1225 - Digit Counting
 * Technique: Reverse string or character array,
 *            Add padding or add leading 0's to given string,
 *            Discard leading or trailing 0's in string,
 *            Shift characters in string by given number of spaces,
 *            add two character array or strings,
 *            Adding very large numbers.
 ***********************************************************************/


#include<stdio.h>
#include<string.h>


#define N 512


static char* firstNumber;
static char* secondNumber;


static char input[N];


/*********************************************************************
 * Pass a string and a Integer length greater than the String length.
 * The function will add leading 0's to the string. The length of the
 * new string will be equal to the passes integer.
 *********************************************************************/
char* fixLength(char* number, int maxlen){


    /**
     * Calculate padding or the amount positions to shift digits to the right.
     * If length of string is 5 and maxlen is 8 then each digit starting from
     * the end will be shifted 3 places to the right.
     *
     * Ex: Original String = "25634", Modified String = "00025634"
     */
    int numLength = strlen(number);
    int padding = maxlen - numLength;


    /**
     * Starting from the end of given string shift each character to the right
     * by calculated padding.
     *
     * Character are shifted from rear otherwise beginning from 0 index will
     * replace existing character in the string and output string will be garbage.
     */
    for(int i = numLength - 1; i >= 0; --i)
        number[i + padding] = number[i];


    /**
     * Add leading 0's to empty places in the string.
     */
    for(int i = 0; i < padding; ++i)
        number[i] = '0';


    /**
     * Mark end of String
     */
    number[maxlen] = '\0';


    return number;
}



/*********************************************************************
 * Given a string and its length this function reverses the string.
 * It first discards any leading 0's in the input string then reverses
 * the input string.
 *********************************************************************/
char* reverseString( char* number, int len ){

    /**
     * Initialize a new char array to keep the string after discarding
     * and leading zeros.
     */
    char* tempNumber = new char[N];
    int k = 0, i;


    /**
     * Only discards leading zeros and not any other internal zeros.
     */
    for(i = 0; i < len; ++i)
        if(number[i] - '0') break;
    for(; i < len; ++i)
        tempNumber[k++] = number[i];
    tempNumber[k] = '\0';


    /**
     * Reverse the new string without leading zeros.
     */
    int tmp = k / 2;
    for(int i = 0, j = k - 1; i < tmp; ++i, --j){
        int swap = tempNumber[i];
        tempNumber[i] = tempNumber[j];
        tempNumber[j] = swap;
    }


    return tempNumber;
}



/**********************************************************************************
 * Starting from the last column add two integers. Then add any carry to the left
 * column. This way calculate the addition. In the end if any carry left add it
 * to the output char array. For safety assume last carry can be bigger than one
 * digit.
 **********************************************************************************/
void add( char* firstNumber, char* secondNumber, int lengthFirst, int lengthSecond){

    /**
     * Initialize a new array to keep sum of two number strings.
     */
    char* tempNumber = new char[N];
    int k = 0;
    int sum = 0;
    int carry = 0;


    /**
     * Starting from last column move left to 0th index. Add the numbers and if there
     * is carry add it to left column.
     */
    for(int j = lengthFirst - 1; j >= 0; --j){

        // Add two number
        sum = firstNumber[j] - '0' + secondNumber[j] - '0';

        // Add if any previous carry
        sum = sum + carry;

        // place the part of output number
        tempNumber[k++] = (sum % 10) + '0';

        // calculate the the carry
        carry = sum / 10;
    }

    /**
     * Assuming last carry can be more than one digit. Add carry digits to output array.
     */
    while(carry){
        tempNumber[k++] = (carry % 10) + '0';
        carry /= 10;
    }
    tempNumber[k] = '\0';


    /**
     * Discard any leading 0's before printing. Only discards leading 0's and nothing else.
     */
    int p = 0;
    for(; p < k; ++p)
        if(tempNumber[p] - '0') break;

    for(; p < k; ++p)
        printf("%c", tempNumber[p]);
    printf("\n");

}


int main() {

    /**
     * Important allocate memory for the numbers.
     */
    firstNumber = new char[N];
    secondNumber = new char[N];


    int n;

    scanf("%d", &n);
    getchar();


    while(n--){

        int j = 0, k = 0;

        /**
         * Take input of two numbers as strings.
         */
        scanf("%s%s", firstNumber, secondNumber);


        /**
         * Get each of their length.
         */
        int firstNumberLength = strlen(firstNumber);
        int secondNumberLength = strlen(secondNumber);


        /**
         * Initial guess the first number string is bigger.
         */
        int maxlen = firstNumberLength;


        /**
         * Reverse both of the number string.
         */
        firstNumber = reverseString(firstNumber, firstNumberLength);
        secondNumber = reverseString(secondNumber, secondNumberLength);


        /**
         * Add padding to the strings calling fixlength function.
         * Pass in the smaller number string and bigger number string size.
         *
         * If initial guess of first number is bigger is wrong then update
         * the max length with second number length.
         */
        if( firstNumberLength < secondNumberLength ){
            firstNumber = fixLength(firstNumber, secondNumberLength);
            maxlen = secondNumberLength;
        }
        else
            secondNumber = fixLength(secondNumber, firstNumberLength);


        /**
         * Now pass in the two numbers and max length to add them and print answer.
         * Notice here i pass the same argument twice this need to be fixed and also
         * there are many more improvements needed in other functions.
         */
        add(firstNumber, secondNumber, maxlen, maxlen);

    }

	return 0;
}