UVA Problem 12646 – Zero or One Solution

UVA Problem 12646 – Zero or One Solution:


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

Solving Technique:

The input is all possible combination of 3 bits. If A, B, C are thought as bits then possible binary combination are,

000 \rightarrow * \\  001 \rightarrow C \\  010 \rightarrow B \\  011 \rightarrow A \\  ---- \\  100 \rightarrow A \\  101 \rightarrow B \\  110 \rightarrow C \\  111\rightarrow * \\

This problem can be solved in multiple ways such as using string, checking equality, performing xor equality etc. My code below is exactly same as equality checking but it perform xor operation between them.

XOR Table,

\begin{tabular}{l*{6}{c}r}  X & Y & X XOR Y \\ \hline  0 & 0 & 0 \\  0 & 1 & 1 \\  1 & 0 & 1 \\  1 & 1 & 0 \\  \end{tabular}
 

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 1 0
0 0 0
1 0 0

 


Output:

C
*
A

Code:

/**
 * Author:    Asif Ahmed
 * Site:      https://quickgrid.wordpress.com
 * Problem:   UVA 12646 - zero or one
 * Technique: XOR Bits to check equality.
 */

#include<stdio.h>


int main(){

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


    int A, B, C;
    while( scanf("%d%d%d", &A, &B, &C) == 3 ){

        if( !( A ^ B ) && !( A ^ C ) )
            putchar('*');
        else{
            if( A ^ B ){
                if( B ^ C )
                    putchar('B');
                else
                    putchar('A');
            }
            else
                putchar('C');
        }
        putchar('\n');
    }


    return 0;
}
Advertisements

Converting NFA to DFA by Complete and Lazy Subset Construction

Question

Given a transition table construct the NFA and using subset construction generate the DFA.


Task:

Task is to convert the NFA N = ( Q_N, \sum, \delta_N, q_0, F_N ) to DFA D = ( Q_D, \sum, \delta_D, \{ q_0 \}, F_D ) such that L(D) = L(N) . Both DFA and the NFA will accept the same language.


Transition Table:
NFA transition table for subset construction
NFA transition table for subset construction

Transition Diagram:
 nfa from transition table
nfa from transition table

NFA Tuples:
N = ( Q_N, \sum, \delta_N, q_0, F_N ) \\  

  = ( \{ p,q,r,s \}, \{ 0,1 \}, \delta, p, \{ s \} )  

Power set of NFA states Q_N :

Since the NFA has 4 states its power set will contain 2^4 = 16 states. Omitting the empty set \emptyset there will be 2^4 - 1 = 15 states.

If Q_N is set of states of NFA the P(Q_N) which is the power set of Q_N are possible states of the DFA Q_D .

Each sets in the power sets can be named something else to make it easy to understand. Each of the sets in the power set represent a state in the DFA.

Q_N = \{ p,q,r,s \} 

P(Q_N) = \{ \{ \},\{ p \},\{ q \},\{ r \},\{ s \}, \{ p,q \}, \{ p,r \}, \{ p,s \}, \{ q,r \}, \{ q,s \}, \{ r,s \},  
        \{ p,q,r \}, \{ p,q,s \}, \{ p,r,s \}, \{ q,r,s \}, \{ p,q,r,s \} \}   

Subset Construction:

The NFA can be converted to DFA using complete subset construction or by lazy evaluation of states. I will show both methods.

F_D is all the set of N states that includes at least one accepting state. Final state of the DFA F_D is set of subset of NFA states Q_N such that S \cap F_N \ne \emptyset .

For each set S \subseteq Q_N and for each input symbol a in \sum ,

\delta_D (S,a) = \bigcup\limits_{\text{p in S}} \delta_N (p,a)

This above is the formula to fill subset table. Although when filling by hand it is clearly visible.

complete subset construction nfa to dfa
complete subset construction nfa to dfa

This will be the transition table for the DFA. Although not all the 2^N states will be there. First thing to do is where ever there is the final state of the NFA mark that with star and p will also be start state for the DFA.

The table can be filled using shortcut by first copying the NFA table for the first four states since they are same as the NFA. Next for each element in the set for an copy from its corresponding row and union all the sets.

The same thing is done in the formula above. To get the transition from a state ( each of the sets in the power set ) for an input symbol which replaces a it produces the output. Right side of the formula takes each element from the set and for the input symbol it produces an item and unions them.

For example,

\delta_D ( \{ p,s \}, 0) = \delta_N (p,0) \cup \delta_N (s,0)  
         = \{ p,q \} \cup \{ s \}  
         = \{ p,q,s \}  

Another example,

\delta_D ( \{ p,q,r,s \}, 1) = \delta_D ( \{ p,q,r \} ,1) \cup \delta_N (s,1)  
            = \{ p,r \} \cup \{ s \}  
            = \{ p,r,s \}  

Here, I just used the pre-computed value in the subset table. Since {p,q,r} is computed beforehand so I get the value from the table.

Each sets can be renamed to something else. Here I name sets from 1 to 15. Although it becomes a little bit confusing with the input symbol but it will take a lot of work to change things.

After renaming the states in the subset table,

subset construction renamed dfa states
subset construction renamed dfa states

Reachable States:

Only reachable states of power set of Q_N or the reachable states of the DFA Q_D .

subset construction reachable states of dfa
subset construction reachable states of dfa

Constructed DFA:
complete subset construction dfa
complete subset construction dfa
Lazy Evaluation / Subset Construction:

The above method is very slow and time consuming. Since all 2^N are not reachable for every DFA so this method will speed up the process by avoiding extra work.

Lazy evaluation to construct dfa from subset
Lazy evaluation to construct dfa from subset

Start with the start state and only construct the states the are reachable from starting state and similarly follow those states.


After Renaming:
Lazy evaluation to construct dfa from subset renamed table
Lazy evaluation to construct dfa from subset renamed table

Generated DFA using Lazy Subset Construction:
lazy subset construction dfa
lazy subset construction dfa

As it is visible both DFA are same.

Translating C Code to MIPS Code to Machine Language with Machine Instruction in Binary and Hex Format

The code won’t be exactly translated to MIPS code but similar code is written so the output is same as the c code.

C Code:

#include<stdio.h>

int main(){

    int a = 2;

    // Prints 20 in Hexadecimal which is equivalent to 32 in Decimal
    printf("%x\n", a << 4);

    return 0;
}

Let, $t0 represent a and $t1 represent the output value in Hex.

MIPS Code:

# This is Comment.
# $0 register is always 0.

ori $t0, $0, 2
sll $t1, $t0, 4

The first line of of MIPS code is or immediate. It can be used to load the value 2 into register $t0. Any value or’ed with another value is the same value. Remember $t0 in represents a in the C Code above.

The sll command shifts contents register $t0 by 4 bits. It is equivalent to, $t1 = $t1 << 4. 2 Shifted by 4 bits in decimal is 32 and in Hexadecimal is 20.


Code Execution in MARS:

No lines executed:
mips shifting register values no line executed
mips shifting register values no line executed
First Line executed:
mips shifting register values one line executed
mips shifting register values one line executed
Second Line executed:
mips shifting register values two lines executed
mips shifting register values two lines executed

Machine Language:

Here the first line of MIPS code ori is I-Format and the second line of code sll is R-type / Format instruction.

For the first line,
ori $t0, $0, 2
Machine Instruction in Binary:

Since ori is an I type instruction it will have 4 fields. It has opcode, rs, rt and immediate. $t0 is numbered 8, $0 register is 0. Opcode for ori is 13.

001101 00000 01000 0000000000000010
opcode rs rt immediate
6 bits 5 bits 5 bits 16 bits

In order to convert the binary to Hex format instruction make group in 4 bits.

Machine Instruction Bits in Group of four:
0011 0100 0000 1000 0000 0000 0000 0010
which in Hexadecimal is,
0x34080002

It matches the instruction in the pictures above. Look at the codes column.


Similarly for the 2nd line,
sll $t1, $t0, 4
Machine Instruction in Binary:

Since ori is an I type instruction it will have 6 fields. It has opcode, rs, rt, rd, shamt (shift amount) and funct. Here rs is not used so set to 0. $t0 to $t7 registers are numbered from 8 to 15. So $t0 is numbered 8, $t1 is 9. The Opcode for sll ( Shift Left Logical ) is 0 and funct ( function ) is also 0.

000000 00000 01000 01001 00100 000000
opcode rs rt rd shamt funct
6 bits 5 bits 5 bits 5 bits 5 bits 6 bits

In order to convert the binary to Hex format instruction again make group in 4 bits.

Machine Instruction Bits in Group of four:
0000 0000 0000 1000 0100 1001 0000 0000
which in Hexadecimal is,
0x00084900

Which again matches the instruction in the code column shown above.

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

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

 

NFA Extended Transition Function Input Processing

Question:

\sum = \{ 0,1 \} \\   \\  L = \{ w|w \text{ over} \sum^* \text{ where w has 1 before the ending symbol} \}

Equivalent regular expression: (0 + 1)^* 1 (0 + 1)


The NFA:

NFA accepting w 1 alphabet
NFA accepting w 1 alphabet

Here,
N = (Q, \sum, \delta, q_0, F) = ( \{q_0,q_1,q_2 \} , \{ 0,1 \} , \delta , q_0 , \{ q_2 \} )


Transition Table:

NFA transition table
NFA transition table

Transition Function:

\delta (q_0, 0 ) = \{ q_0 \} \\  \\  \delta (q_0, 1 ) = \{ q_0, q_1 \} \\  \\  \delta (q_1, 0 ) = \{ q_2 \} \\  \\  \delta (q_1, 1 ) = \{ q_2 \} \\  \\  \delta (q_2, 0 ) = \emptyset \\  \\  \delta (q_2, 1 ) = \emptyset \\


Input Processing Shown with Arrows:

For input string, w = 011
nfa input tracing 011
nfa input tracing 011

For input string, w = 01010
nfa 01010
nfa 01010

Extended transition Function Input Processing:

For input, w = 011

\hat{\delta} (q_0, \epsilon ) = \{ q_0 \} \\     \\  \\    \hat{\delta} (q_0, 0 ) = \{ q_0 \} \\    \\  \\    \hat{\delta} (q_0, 01 ) = \delta ( \hat{\delta} (q_0, 0 ), 1 ) \\  ............. = \delta ( q_0, 1 ) \\   ............. = \{ q_0, q_1 \} \\     \\  \\    \hat{\delta} (q_0, 011 ) = \delta ( \hat{\delta} (q_0, 01 ), 1 ) \\  .............. = \delta ( \{ q_0, q_1 \}, 1 ) \\  .............. = \delta ( q_0, 1 ) \cup \delta ( q_1, 1 ) \\  .............. = \{ q_0, q_1 \} \cup \{ q_2 \} \\   .............. = \{ q_0, q_1, q_2 \} \\


For input, w = 01010. Since sub-string 01 is already calculated I will reuse it.

\hat{\delta} (q_0, 010 ) = \delta ( \hat{\delta} (q_0, 01 ), 0 ) \\  .............. = \delta ( \{ q_0, q_1 \}, 0 ) \\  .............. = \delta ( q_0, 0 ) \cup \delta ( q_1, 0 ) \\  .............. = \{ q_0 \} \cup \{ q_2 \} \\   .............. = \{ q_0, q_2 \} \\     \\  \\    \hat{\delta} (q_0, 0101 ) = \delta ( \hat{\delta} (q_0, 010 ), 1 ) \\  ................. = \delta ( \{ q_0, q_2 \}, 1 ) \\  ................. = \delta ( q_0, 1 ) \cup \delta ( q_2, 1 ) \\  ................. = \{ q_0, q_1 \} \cup \emptyset \\   ................. = \{ q_0, q_1 \} \\     \\  \\    \hat{\delta} (q_0, 01010 ) = \delta ( \hat{\delta} (q_0, 0101 ), 0 ) \\  .................. = \delta ( \{ q_0, q_1 \}, 0 ) \\  .................. = \delta ( q_0, 0 ) \cup \delta ( q_1, 0 ) \\  .................. = \{ q_0 \} \cup \{ q_2 \} \\   .................. = \{ q_0, q_2 \} \\

Grade School High Precision Floating Point Number Adder Implementation in C++

Warning: This program has not been thoroughly tested. So it may produce incorrect results.

How the Code Works:

Note this problem calculates the integer and fractional portion separately in array as opposed to techniques learned in numerical analysis. To test if outputs are correct check against other high precision calculator such as this calculator.

Similar to this problem or same techniques used in uva problem 424 integer inquiry solution, uva problem 10035 primary arithmetic solution, uva problem 713 adding reversed numbers solution. The technique from this problem can also be applied to the mentioned problems.


Solution Steps:
Example Input:
25.401
534.2914
710.84
9.7808
980.7223

Note here are two separate arrays with one for decimal part and other for fraction. The dot is not stored anywhere, it is just shown to make it easy to understand. First the numbers are aligned with padding functions to create this,

025 . 4010
534 . 2914
710 . 8400
009 . 7808
980 . 7223

Although not used in this problem below, this pic that shows how I calculated sum column-row (column major) wise which is not cache friendly.

uva 424 integer inquiry order of operation
uva 424 integer inquiry order of operation

As shown in the pic above the technique is almost same but this time row and columns are interchanged and kept in a separate array which looks like this,

New Decimal Array:
05709 
23108 
54090 
New Fraction Array:
42877
09482
11002
04083

Next the operation is carried out as shown below,

row wise addition of high precision floating point numbers
row wise addition of high precision floating point numbers

Sample Test Input:

3.6692156156
65652.6459156456415616561
33.54615616
1.1
9854949494968498.49684984444444444444444443213615312613216512331918565

Output:

Output: 9854949495034189.45813726568600610054444443213615312613216512331918565

Code:

/********************************************************************************************
 * Author:    Asif Ahmed
 * Site:      https://quickgrid.wordpress.com
 * Problem:   Naive High Precision Floating Point Number Adder
 *
 * Warning:   This Code is mostly useless and hard to read. It is not represented in
 *            usual sign, exponent sign, exponent magnitude, mantissa magnitude format.
 *            The Program should produce correct output till given FRACTION_LIMIT after
 *            decimal point for unsigned numbers (Negative numbers not supported).
 *
 *            Also it may not necessary produce correct result as it is not throughly
 *            tested. Use it with caution.
 *
 *            Please follow input format. I have not handled any exception for incorrect
 *            input formats.
 *
 *******************************************************************************************/



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



// Increase the TEST_NUMBERS to calculate more float numbers.
#define TEST_NUMBERS  5

#define DECIMAL_SIZE  100
#define FRACTION_SIZE 100




// Function Prototypes
void sumDecimal(char **, int, int);
void sumFractions(char **, int);


// Array for holding decimal and fractional portion
static char decimal[TEST_NUMBERS][DECIMAL_SIZE];
static char fraction[TEST_NUMBERS][FRACTION_SIZE];


// Pointers reversed decimal and fractional result array.
char *resDec, *resFrac;
int resDecLen, resFracLen;



// Align decimal portion of the numbers and zeros.
void fixPaddingDecimal(int carry){

    // Holds calculated length of all strings.
    static int memo[TEST_NUMBERS];


    // Find out the max length of largest decimal.
    int maxlength = memo[0] = strlen(decimal[0]);


    // Get the max length for padding or aligning.
    for(int i = 1; i < TEST_NUMBERS; ++i){
        int len = memo[i] = strlen(decimal[i]);
        if( len > maxlength )
            maxlength = len;
    }



    // Shift elements by appropriate positions or, create padding.
    // Look at my other linked pages from the post to understand this part.
    for(int i = 0; i < TEST_NUMBERS; ++i){
        int len = memo[i];

        if( len != maxlength ){
            int padding = maxlength - len;

            for(int j = len - 1; j >= 0; --j)
                decimal[i][padding + j] = decimal[i][j];

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



    // Create a new 2D array that will hold values in the new changed order.
    char **cacheFrindlyFloatOrganization = new char*[maxlength + 1];
    for(int i = 0; i < maxlength; ++i)
        cacheFrindlyFloatOrganization[i] = new char[TEST_NUMBERS + 1];


    // Copy decimal portion to the mew changed order array.
    for(int j = 0; j < maxlength; ++j){
        for(int i = 0; i < TEST_NUMBERS; ++i){
            cacheFrindlyFloatOrganization[j][i] = decimal[i][j];
        }
    }


    // Debug
    /*
    for(int i = 0; i < maxlength; ++i){
        for(int j = 0; j < TEST_NUMBERS; ++j){
            printf("%c ", cacheFrindlyFloatOrganization[i][j]);
        }
        printf("\n");
    }
    */


    // After fixing alignment add the decimal portion.
    sumDecimal( cacheFrindlyFloatOrganization, maxlength, carry);

}



// Add all the decimal numbers.
void sumDecimal(char **cacheFrindlyFloatOrganization, int maxlength, int carry){

    // Holds the output decimal part in reversed order.
    char *resultDecimal = new char[maxlength + 1];

    int z = 0;


    // Again look at the pages linked from this post.
    // I have explained this in uva 424, 10035, 713 etc.
    for( int i = maxlength - 1; i >= 0; --i ){

        int sum = 0;

        for(int j = 0; j < TEST_NUMBERS; ++j)
            sum = sum +  cacheFrindlyFloatOrganization[i][j] - '0';

        sum = sum + carry;
        resultDecimal[z++] = sum % 10 + '0';
        carry = sum / 10;
    }

    // Stored in reversed order
    if(carry)
        resultDecimal[z++] = carry + '0';
    resultDecimal[z] = '\0';


    // Store the address and length of resultDecimal
    resDec = resultDecimal;
    resDecLen = z;


}



// As explained above this ALMOST does the same thing as function decimal code.
void fixPaddingFraction(){

    // Holds calculated length of all strings
    static int memo[TEST_NUMBERS];


    // Find out the max length of largest fraction
    int maxlength = memo[0] = strlen(fraction[0]);

    for(int i = 1; i < TEST_NUMBERS; ++i){
        int len = memo[i] = strlen(fraction[i]);
        if( len > maxlength )
            maxlength = len;
    }


    // Add zeros to empty positions.
    for(int i = 0; i < TEST_NUMBERS; ++i){
        int len = memo[i];

        if( len != maxlength ){
            for(int j = len ; j < maxlength; ++j)
                fraction[i][j] = '0';
            fraction[i][maxlength] = '\0';
        }
    }


    // Explained above.
    char **cacheFrindlyFloatOrganization = new char*[maxlength + 1];
    for(int i = 0; i < maxlength; ++i)
        cacheFrindlyFloatOrganization[i] = new char[TEST_NUMBERS + 1];


    // Interchanging row and columns
    for(int j = 0; j < maxlength; ++j){
        for(int i = 0; i < TEST_NUMBERS; ++i){
            cacheFrindlyFloatOrganization[j][i] = fraction[i][j];
        }
    }


    // Debug
    /*
    for(int i = 0; i < maxlength; ++i){
        for(int j = 0; j < TEST_NUMBERS; ++j){
            printf("%c ", cacheFrindlyFloatOrganization[i][j]);
        }
        printf("\n");
    }
    */

    // Sum the fractional array part.
    sumFractions(cacheFrindlyFloatOrganization, maxlength);
}




// Does ALMOST the same thing for decimal function code.
void sumFractions(char **cacheFrindlyFloatOrganization, int maxlength){

    char *resultFraction = new char[maxlength + 1];

    int z = 0, carry = 0;

    for( int i = maxlength - 1; i >= 0; --i ){

        int sum = 0;

        for(int j = 0; j < TEST_NUMBERS; ++j)
            sum = sum +  cacheFrindlyFloatOrganization[i][j] - '0';

        sum = sum + carry;
        resultFraction[z++] = sum % 10 + '0';
        carry = sum / 10;
    }


    // Stored in reversed order
    resultFraction[z] = '\0';


    // Hold the address and length resultFraction array.
    resFrac = resultFraction;
    resFracLen = z;


    // Call the padding function for by sending the carry from fraction part.
    fixPaddingDecimal(carry);
}



// The output decimal and fraction array are in reversed order.
// They need to be reversed before outputting.
void reverseString(char *tmpString, int tmpStringLen){

    for(int i = 0, j = tmpStringLen - 1; i < j; ++i, --j ){
        int temp = tmpString[i];
        tmpString[i] = tmpString[j];
        tmpString[j] = temp;
    }
}



int main(){


    // Comment freopen lines below to input and output from console.
    // In order to use freopen create a file named input_file.txt
    // in same directory as your cpp file. The output of the program
    // will be in output_file.txt file.

    /*
    freopen("input_file.txt", "r", stdin);
    freopen("output_file.txt", "w", stdout);
    */



    for(int i = 0; i < TEST_NUMBERS; ++i){
        //printf("Enter float:\n");
        scanf("%[0-9].%[0-9]", &decimal[i], &fraction[i]);
        getchar();
    }


    // This is where it all starts.
    fixPaddingFraction();



    reverseString(resDec, resDecLen);
    reverseString(resFrac, resFracLen);


    // Debug
    printf("Output: %s.%s\n", resDec, resFrac );



    return 0;
}

Digital Logic: Binary to Gray Code Converter

Before starting with this read Digital Logic: Designing Decimal to 4 bit Gray Code Converter if you are unfamiliar.


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
Binary to Gray Code Converter:

This same technique can be applied to make gray to binary converter. There will be 4 input bits, which represent binary and 4 output bits which represent equivalent gray code.

Since we are creating binary to gray code converter so, we need to find expressions for each gray code output in terms of input binary bits.

So, there will be four output bits A_3, A_2, A_1, A_0 . For these output bits the input will be different combinations of B_3, B_2, B_1, B_0 based on minimized expression.


Karnaugh Maps:

A3:

4 bit binary to gray code A3 expression
4 bit binary to gray code A3 expression

Minimized expression from the above k map,
A_3 = B_3


A2:

4 bit binary to gray code A2 k map
4 bit binary to gray code A2 k map

Minimized expression from the above k map,
A_2 = B_3 \overline{B_2} + B_2 \overline{B_3}

But, the expression of XOR Gate is (Let, A and B be the inputs),
A.\overline{B} + B.\overline{A} = A \oplus B
[Note: This is not related to this problem but, only showing how XOR can be made from And, Or, Not gates]

Similarly,it can be shown that,
B_3 \overline{B_2} + B_2 \overline{B_3} = B_2 \oplus B_3

If XOR gate is not available then the former expression can be used with and, or and not gates to design the gray code converter.


A1:

4 bit binary to gray code A1 k map
4 bit binary to gray code A1 k map

Minimized expression from the above k map,
A_1 = B_1 \overline{B_2} + B_2 \overline{B_1}

Similarly,it can be shown that,
B_1 \overline{B_2} + B_2 \overline{B_1} = B_1 \oplus B_2


A0:

4 bit binary to gray code A0 k map
4 bit binary to gray code A0 k map

Minimized expression from the above k map,
A_0 = B_0 \overline{B_1} + B_1 \overline{B_0}

Similarly,it can be shown that,
B_0 \overline{B_1} + B_1 \overline{B_0} = B_0 \oplus B_1


Circuit Diagram using XOR gates:

Download the logisim circ file from github.

4 bit binary to Gray Code Converter using XOR gates
4 bit binary to Gray Code Converter using XOR gates

Circuit Diagram without using XOR gates:

Download the logisim circ file from github.

4 bit binary to Gray Code Converter without using XOR gates
4 bit binary to Gray Code Converter without using XOR gates

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