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

#### 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.

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,

#### 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.

// 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)

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.

// 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.
}

// 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.

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

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

return 0;
}


## UVA Problem 264 – Count on Cantor Solution

UVA Problem 264 – Count on Cantor Solution:

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.

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


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 12592 – Slogan Learning of Princess Solution KMP Algorithm Implementation and Explanation

Solving Technique:

##### Dissecting the problem statement:

The problem is straight forward. Given an input n, there will be 2n lines of input. Since each line also has accompanying next line. They are divided in first and second line. Here only first line is required for calculation. The second line is the output of the program.

Then we will be given say m lines. For each lines we are to match the first lines from previous 2n lines and output the second line.

##### Solution:

There are easier ways to solve this, but this mainly a KMP ( Knuth Morris Pratt ) algorithm tutorial.

Here the input is “jalo re jalo” which is one the inputs from the problem. The state diagrams are first drawn without following the algorithm. After that DFA table from hand tracing and code output is matched.

#### State Machine diagram without transition to initial state:

###### Explanation:

Why most states transition back to state 1 on ‘j’ input? Reaching state 1 means ‘j’ is already matched so going back to 0 will produce wrong output. Because that’d mean two j matched or “jj”. Since ‘a’ is after ‘j’ the next task is to match ‘a’ so we go back to state 1 and try to match further inputs.

Notice on state 8 on input of ‘j’ it goes to 9 instead of 1. Because that ‘j’ is also a part of the seqence and the seqence hasn’t broken yet. Finally on state 12 or on the length of the pattern string the input gets is accepted.

#### State Machine diagram with transition to initial state:

##### Calculated DFA table:

DFA table is generated with pattern being one of the input from the problem.
“jalo re jalo”

After generating the DFA table from tracing the algorithm and the DFA table state after running the algorithms both match. Also the states and transitions of the DFA table exactly match the state machine above.

#### DFA table state after running of KMP algorithm:

Input is the same string as above.

##### Step by step table fill and explanation: (CreateDFA function)

Note empty cells in the matrix contains zero. They are not shown to keep it simple here but they are there and they transition to start or beginning state which is 0.

#### Call to createDFA Function:

This is the initial state of the DFA matrix.

$\begin{tabular}{|l|l|l|l|l|l|l|l|l|l|l|l|l|} \hline & j & a & l & o & ' ' & r & e & ' ' & j & a & l & o \\ \hline & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 \\ \hline {\bf ' '} & & & & & & & & & & & & \\ \hline {\bf a} & & & & & & & & & & & & \\ \hline {\bf e} & & & & & & & & & & & & \\ \hline {\bf j} & & & & & & & & & & & & \\ \hline {\bf l} & & & & & & & & & & & & \\ \hline {\bf o} & & & & & & & & & & & & \\ \hline {\bf r} & & & & & & & & & & & & \\ \hline \end{tabular}$

#### Setting up the next state:

This is execution of line 53 in code below.

DFA[pattern[0]][0] = 1;



Here the pattern is,


pattern = "jalo re jalo";



So, pattern[0] is character ‘j’.


DFA['j'][0] = 1;



This essentially means in the j-th row and 0-th column set 1.

###### Understanding the transitions:

To understand the how the transitions work column wise lay the pattern. So if the length of pattern is m then there are m columns in the matrix. In row wise layout the set of character in the pattern. So even if there are multiple occurrence of the same character it is only represented as a row once.

By careful inspection of the DFA matrix it can be observed that state change occur when the character in that row matches the column representation of that character.

The row index is represented by the ASCII value of the set of characters in pattern. The column are represented from 0 to m where m is length of the pattern.

$\begin{tabular}{|l|l|l|l|l|l|l|l|l|l|l|l|l|} \hline & j & a & l & o & ' ' & r & e & ' ' & j & a & l & o \\ \hline & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 \\ \hline {\bf ' '} & & & & & & & & & & & & \\ \hline {\bf a} & & & & & & & & & & & & \\ \hline {\bf e} & & & & & & & & & & & & \\ \hline {\bf j} & 1 & & & & & & & & & & & \\ \hline {\bf l} & & & & & & & & & & & & \\ \hline {\bf o} & & & & & & & & & & & & \\ \hline {\bf r} & & & & & & & & & & & & \\ \hline \end{tabular}$

#### Copying values from x-th column:

Execution of line 60 and 61 in code below.


for(k = 0; k < r; ++k)
DFA[k][j] = DFA[k][x];



This code basically copies values in x-th column to j-th column. Initially x = 0 and j = 1, So values from 0-th column( 0-th index ) are copied into 1-st column ( 1-st index ).

$\begin{tabular}{|l|l|l|l|l|l|l|l|l|l|l|l|l|} \hline & j & a & l & o & ' ' & r & e & ' ' & j & a & l & o \\ \hline & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 \\ \hline {\bf ' '} & & & & & & & & & & & & \\ \hline {\bf a} & & & & & & & & & & & & \\ \hline {\bf e} & & & & & & & & & & & & \\ \hline {\bf j} & 1 & 1 & & & & & & & & & & \\ \hline {\bf l} & & & & & & & & & & & & \\ \hline {\bf o} & & & & & & & & & & & & \\ \hline {\bf r} & & & & & & & & & & & & \\ \hline \end{tabular}$

#### Updating the next state and Column to to copy from:

Execution of line 66.

DFA[pattern[j]][j] = j + 1;



when, j = 1


DFA[pattern[1]][1] = 1 + 1;



since pattern[1] = ‘a’


DFA['a'][1] = 2;



This replaces the matching row and column matching character cell with value of next state which is the next column number.

Execution of line 71.


x = DFA[pattern[j]][x];



Update x the column number where to copy values from. This means if in the pattern recognition we go back in a previous state then we don’t need to recalculate. Since the transitions in that state are already calculated use those same transitions.

$\begin{tabular}{|l|l|l|l|l|l|l|l|l|l|l|l|l|} \hline & j & a & l & o & ' ' & r & e & ' ' & j & a & l & o \\ \hline & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 \\ \hline {\bf ' '} & & & & & & & & & & & & \\ \hline {\bf a} & & 2 & & & & & & & & & & \\ \hline {\bf e} & & & & & & & & & & & & \\ \hline {\bf j} & 1 & 1 & & & & & & & & & & \\ \hline {\bf l} & & & & & & & & & & & & \\ \hline {\bf o} & & & & & & & & & & & & \\ \hline {\bf r} & & & & & & & & & & & & \\ \hline \end{tabular}$

#### Skipping Some Steps:

After skipping some steps now value of j counter is 8.
So pattern[8] = j. Note here I’ve used two single quotes to represent the space character.

Here again values from 0-Th column are copied into the 8-Th column.
DFA[‘j’][8] is set to j + 1 = 9.
There was already a value there and it’ll be replaced.

Now the interesting part when updating x ( the column to copy values from )


x = DFA[pattern[j]][x]
x = DFA['j'][0]
x = 1



It already stated there which state to go for on which input.
So x becomes 1. Now in the next iteration values from 1-st column will be copied.

$\begin{tabular}{|l|l|l|l|l|l|l|l|l|l|l|l|l|} \hline & j & a & l & o & ' ' & r & e & ' ' & j & a & l & o \\ \hline & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 \\ \hline {\bf ' '} & & & & & 5 & & & 8 & & & & \\ \hline {\bf a} & & 2 & & & & & & & & & & \\ \hline {\bf e} & & & & & & & 7 & & & & & \\ \hline {\bf j} & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 9 & & & \\ \hline {\bf l} & & & 3 & & & & & & & & & \\ \hline {\bf o} & & & & 4 & & & & & & & & \\ \hline {\bf r} & & & & & & 6 & & & & & & \\ \hline \end{tabular}$

#### Final State of the DFA table or Matrix:

Similarly follwoing the procedure of copying x-th column, then updating matching character cell to next to next state or index and finally updating x to be the value at current character row and x th column we get this DFA table.
$\begin{tabular}{|l|l|l|l|l|l|l|l|l|l|l|l|l|} \hline & j & a & l & o & ' ' & r & e & ' ' & j & a & l & o \\ \hline & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 \\ \hline {\bf ' '} & & & & & 5 & & & 8 & & & & \\ \hline {\bf a} & & 2 & & & & & & & & 10 & & \\ \hline {\bf e} & & & & & & & 7 & & & & & \\ \hline {\bf j} & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 9 & 1 & 1 & 1 \\ \hline {\bf l} & & & 3 & & & & & & & & 11 & \\ \hline {\bf o} & & & & 4 & & & & & & & & 12 \\ \hline {\bf r} & & & & & & 6 & & & & & & \\ \hline \end{tabular}$

#### DFAStringMatching Function:

Execution of line 34, 35. Here i seem to have calculated length of pattern twice. This not a problem but doing extra work.

After the DFA matrix is generated. Next apply the given query string to the matrix and see if by transition it is able reach the last state which is length of the DFA string.

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++.

Input:

3
My name is
Asif
what is kmp
string matching algorithm
jalo re jalo
agun jalo
2
jalo re jalo
what is kmp


Output:

agun jalo
string matching algorithm


### Code:

/*
* Author:   Quickgrid ( Asif Ahmed )
* Site:     https://quickgrid.wordpress.com
* Problem:  UVA 12592 Slogan Learning Princess
* Solution: Knuth Morris Pratt ( KMP ) algorithm implementation
*/

#include<cstdio>
#include<iostream>
#include<string>

using namespace std;

static string slogan[100];
static string query;

#define r 160

/**
* Space may be further minimized at the cost of running time
*/
static unsigned DFA[r][100];

unsigned DFAStringMatching(string text, string pattern){
unsigned m = pattern.length();
unsigned n = query.length();

/**
* i is incrementing by 1, meaning using text[i] whole input string can be traversed.
* text[i] is a character. DFA[text[i]][j] means text[i] character column and j th row.
* This position or cell contains the column for next transition.
*/
unsigned i, j;
for(i = 0, j = 0; i < n && j < m; ++i)
j = DFA[text[i]][j];

/**
* If j equals m then all transition completed successfully
* meaning the string are a match.
*/
if(j == m)
return 1;
else
return 0;
}

void CreateDFA(string pattern){
unsigned m = pattern.length();

/**
* Set the first state to 1
*/
DFA[pattern[0]][0] = 1;

unsigned x, j, k;
for(x = 0, j = 1; j < m; ++j){
/**
* Copy all values from x column to j column.
*/
for(k = 0; k < r; ++k)
DFA[k][j] = DFA[k][x];

/**
* Update position in table to the next transition.
*/
DFA[pattern[j]][j] = j + 1;

/**
* Update the column from which to copy values.
*/
x = DFA[pattern[j]][x];
}

/**
* Uncomment code below to see transitions to states in DFA table
* For printing transitions in DFA
* Delete this before submitting to UVA
* Empty or Zero in DFA means transition to initial state
*/

/*
int val = 0;
for(j = 0; j < m; ++j){
for(k = 0; k < r; ++k){
val = DFA[k][j];
if(val)
printf("Transition from state (%d) to state (%d) for input: %c\n", j, DFA[k][j], k);
}
printf("\n");
}
*/

}

int main()
{
static unsigned n, i, q;

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

/**
* Since each input has two lines
*/
static unsigned limit = 2 * n;

for(i = 0; i < limit; i += 2){
getline(cin, slogan[i]);
getline(cin, slogan[i+1]);
}

scanf("%u", &q);
getchar();

while(q--){
getline(cin, query);

/**
* Create the DFA table from input
*/
CreateDFA(query);

for(i = 0; i < limit; i += 2){
/**
* If the first line matches a String stored in memory
* then print the next one
*/
if(DFAStringMatching(slogan[i], query))
cout << slogan[i+1] << "\n";
}
}

return 0;
}


## UVA Problem 10696 – f91 Solution

UVA Problem 10696 – f91 Solution:

Solving Technique:

This is a simple DP problem (OR, so it looks but there’s a better way). It can be solved both iteratively and recursively with or without memoization. Still it will get accepted. But still the runtime is slow due huge input. So using a faster io may help it get accepted with a better rank.

For the matter of practice i will show all four methods i know of to solve this problem. Codes are given in this order,

1. dynamic programming solution.
2. Recursive solution without Memoization.
3. Recursive solution with Memoization.
4. Shortcut Trickery.
5. Maybe extend the shortcut Trickery with memoization or other technique by yourself ? try it !!

#### Solution explanation:

Here the formula is given, we just need rearrange it and get the recurrence relation,

If N ≤ 100, then f91(N) = f91(f91(N+11));
If N ≥ 101, then f91(N) = N-10.

So from the given statement generating recurrence relation will be,

f(n) = { f(f(n+11)), if n <= 100
{ n - 10,     if n >= 101


Here base case is for any n greater than or equal to 101 is return n – 10. No more recursive call on that.
This can be simplified but i won’t go into that. The codes below will give a better idea.

Now, just create a function named f and use if else or ternary to implement the given relation and it’ll work.

#### Memoization:

Since we’ve found out the recurrence relation it won’t be hard to memoize the code. We can use a memo array to store the already calculated results. We need not change much from the previous recursive solution to memoize it.

Add an if condition in the beginning if the value is already calculated and stored in memo array just return. Other wise when returning just store the return values in memo.

That’s it.

#### Dynamic Programming ( bottom up method ):

Our recurrence relation will never change. Since there is no other function needed we just calculate and store values in memo array. I started from 1,000,000 because the problem statement said an integer may be at most 1,000,000. Just loop through that many times and store results in memo array.

##### Last Solution Trick:

It come to me when i was testing my own inputs. Anything less or equal 100 result in 91. Any greater value results in that value minus 10. Take a look at the code below to get the idea.

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++.

Input:

500
91
1
5
190
100
101
0

Output:

490
91
91
91
180
91
91

### Code Bottom Up (Iterative) Dynamic Programming:

/**
* @author  Quickgrid ( Asif Ahmed )
* Problem: UVA 10696 - f91
* Type:    Bottom Up (Iterative) Dynamic Programming
*/

#include<cstdio>
#include<sstream>

using namespace std;

#define N 1000000

static int F[N];

int main(){
int n, i;

for(i = N; i >= 0; --i){
if(i >= 101)
F[i] = i - 10;
else
F[i] = F[F[i + 11]];
}

while(scanf("%d", &n) && n)
printf("f91(%d) = %d\n", n, F[n]);

return 0;
}


### Code Top Down (Recursive) Without Memoization:

/**
* @author  Quickgrid ( Asif Ahmed )
* Problem: UVA 10696 - f91
* Type:    Top Down (Recursive) without Memoization
*/

#include<stdio.h>

int f(int n){
return (n >= 101) ? n - 10 : f(f(n + 11));
}

int main(){
int n;

while(scanf("%d",&n) && n)
printf("f91(%d) = %d\n", n, f(n));

return 0;
}


### Code Top Down (Recursive) with Memoization:

/**
* @author  Quickgrid ( Asif Ahmed )
* Problem: UVA 10696 - f91
* Type:    Top Down (Recursive) with Memoization
*/

#include<stdio.h>

static unsigned F[1000000];

unsigned f(unsigned n){
if(F[n])
return F[n];

if(n >= 101)
return F[n] = n - 10;
else
return F[n] = f(f(n+11));
}

int main(){
unsigned n;

while(scanf("%u",&n) && n)
printf("f91(%u) = %u\n", n, f(n));

return 0;
}


### Shortcut Technique:

/**
* @author  Quickgrid ( Asif Ahmed )
* Problem: UVA 10696 - f91
* Type:    shortcut technique
*/

#include<stdio.h>

int main(){
unsigned n;

while(scanf("%u", &n) && n){
if(n <= 100)
printf("f91(%d) = 91\n", n);
else
printf("f91(%d) = %d\n", n, n - 10);
}

return 0;
}


## Ternary Heap Sort Code in C++ using Heap Data structure

##### Introduction:

This code is implementation of ternary heap sort. The code requires no input. Data inputs (integers) are generated randomly then sorted using heap sort.

Only change the define SIZE value to for sorting large or small amount of numbers.

Code for Binary Heap Sort here.

#### Ternary Heap Sort Code Cpp:

/**
* @author  Quickgrid ( Asif Ahmed )
* Problem: Ternary Heap Sort
*/

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

#define SIZE 10
int A[SIZE], heapsize = SIZE;

void maxHeapify(int i){
int largest;

/**
* Find right child index
*/
int l = 3 * i + 1;

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

/**
* find mid child index
*/
int m = 3 * i + 2;

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

/**
* Find right child index
*/
int r = 3 * i + 3;

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

/*
* If child nodes have larger value then current node
*/
if(largest != i){
/**
* Swap the two values
*/
std::swap(A[i], A[largest]);

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

void buildMaxHeap(){
int j;
/**
* operate on third of array
*/
for(j = heapsize / 3 - 1; j >= 0; --j)
maxHeapify(j);
}

void heapsort(){
buildMaxHeap();

int i;
for(i = heapsize - 1; i > 0; --i){
std::swap(A[0], A[i]);

/**
* Decrease the heap size as right of heap is already sorted
*/
--heapsize;

/**
* Again max heapify the rest of the heap
*/
maxHeapify(0);
}
}

int main(){
int i;

clock_t begin, end;
double time_elapsed;

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

printf("Sorting Now....\n");
begin = clock();
heapsort();
end = clock();

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

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

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

return 0;
}


## UVA Problem 10684 – The jackpot Solution

UVA Problem 10684 – The jackpot Solution:

Solving Technique:

This is an maximum sub array sum problem. Here we need find maximum subarray sum in 1D array. It can be solved easily with Kadane’s algorithm in O(n) time.

One thing to keep in mind the sample input isn’t properly aligned. So input format may be a bit confusing.

##### Explanation:

If the sum of array elements become 0 then we should set the sum to zero. Meaning we didn’t take any previous elements. Otherwise if we keep sum negative then we’ll never have the correct answer. Since we could get a bigger sum by discarding negative sum subset.

###### For example,

5
12  -4  -10  4  9

Here from first element to -10 we have a sum of -2. If we then add 4, 9 to the current sum -2 the max value is 11. But we could get a better result by discarding all previous sum since 12, -4, -10 produces a negative sum. There is no meaning taking a negative value. So discarding all previous sums till -10 then adding 4, 9 we get a max value of 13.

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.

Input:

5
12  -4  -10  4  9
3
-2 -1 -2
0

Output:

The maximum winning streak is 13.
Losing streak.

### Code:

/**
* @author  Quickgrid ( Asif Ahmed )
* Problem: UVA 10684 - The jackpot
*/

#include<stdio.h>

static int subset[10002];

int main(){
static unsigned n, i;
static int sum, max;

while(scanf("%u", &n) && n){

sum = max = i = 0;

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

if(sum < 0)
sum = 0;

if(sum > max)
max = sum;
}

if(max > 0)
printf("The maximum winning streak is %d.\n", max);
else
printf("Losing streak.\n");
}
return 0;
}


## UVA Problem 147 – Dollars Solution

UVA Problem 147 – Dollars Solution:

Solving Technique:

This problem is very very very very similar to uva 674 ( Coin Change ) and uva 357 ( Let me count the ways ). These problems can be used as hint or template for this problem. So if you want to solve on your own don’t look down.

1. The amount doesn’t exceed $300.00 2. Exit / terminate program for the input of 0.00 3. Amount can be / is a floating point number 4. There are different values that can be used make up the decimal and the fractional portion 5. Output should be justified with width 6 before printing input amount and width 17 afterwards then the number of ways the amount is made up of. #### Solution Technique: Instead of calculating the decimal and the fractional portion separately we can use one method to calculate the count. Since a Dollar can be made up of coins that is,$1 = 100 cents. So we can just calculate how many ways the coins can be made and that will be the answer.

###### For example,
• $4.70 = 470 cents •$2.00      =      200 cents
• $6.75 = 675 cents •$300.00  =  30000 cents

So we can put all the ways the coins can be divided to an array. Then use that calculate the count. Now whenever we can divide the amount with a specific coin we increase the count. We need calculate for all the specific coins.

Here I have given two codes, they are essentially the same. Only difference is in the second code instead of using an array to calculate the count, I have split the loop to show the calculations.

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. Compile with C++ to be safe from compile errors although some codes do work with C compiler.

Input:

0.20
2.00
4.90
6.70
8.45
0.00

Output:

  0.20                4
2.00              293
4.90             5698
6.70            19187
8.45            49007

## Code:

/**
* @author  Quickgrid ( Asif Ahmed )
* Problem: UVA 147 - Dollars
*/

#include<stdio.h>

#define N 30002

static long long c[N];
static const unsigned coins[] = {5, 10, 20, 50, 100, 200, 500, 1000, 2000, 5000, 10000};

int main(){
unsigned i, j;
float n;

c[0] = 1;
for(i = 0; i < 11; ++i){
for(j = coins[i]; j < N; ++j)
c[j] += c[j - coins[i]];
}

while(scanf("%f", &n) == 1 && n){
// Rounding error fix
unsigned coin = (unsigned)((n + 0.001) * 100);

// 6 width justified including the input amount and 17 width afterwards including count
printf("%6.2f%17lld\n", n, c[coin]);
}
return 0;
}


## Code (Loop Split):

/**
* @author  Quickgrid ( Asif Ahmed )
* Problem: UVA 147 - Dollars ( Loop Split )
*/

#include<stdio.h>

#define N 30002

static long long c[N];

int main(){
unsigned i, j;
float n;

c[0] = 1;

/*
* Loop Split
*/

for(j = 5; j < N; ++j)
c[j] += c[j - 5];

for(j = 10; j < N; ++j)
c[j] += c[j - 10];

for(j = 20; j < N; ++j)
c[j] += c[j - 20];

for(j = 50; j < N; ++j)
c[j] += c[j - 50];

for(j = 100; j < N; ++j)
c[j] += c[j - 100];

for(j = 200; j < N; ++j)
c[j] += c[j - 200];

for(j = 500; j < N; ++j)
c[j] += c[j - 500];

for(j = 1000; j < N; ++j)
c[j] += c[j - 1000];

for(j = 2000; j < N; ++j)
c[j] += c[j - 2000];

for(j = 5000; j < N; ++j)
c[j] += c[j - 5000];

for(j = 10000; j < N; ++j)
c[j] += c[j - 10000];

while(scanf("%f", &n) == 1 && n){
// Rounding error fix
unsigned coin = (unsigned)((n + 0.001) * 100);

// 6 width justified including the input amount and 17 width afterwards including count
printf("%6.2f%17lld\n", n, c[coin]);
}
return 0;
}


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

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

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

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

## 0-1 Knapsack:

This problem can be solved be dynamic programming. Given some weight of items and their benefits / values / amount, we are to maximize the amount / benefit for given weight limit.

##### Background:

Suppose we are thief trying to steal. We got a knapsack with a weight carry limit. We go to a house there are a few items. The items have weights and also resale value. Now with our limited weight in the knapsack and many valuable items to take, we need to maximize our gain. We can do so by trying all items and filling the weight limit.

We will be given a few things as input. Such as number of items, each of their weights, each of their monetary value / cost ( if it represents cost ) and a weight limit. We are to find that by trying all items and the weight limit what is the maximum possible benefit.

If it is unclear the Wikipedia article on 0-1 knapsack may be helpful. I will show the table fill and items taken in the knapsack in another post.

##### Recurrence Relation:

The recurrence relation for this problem follows,

cost[ i, w ] = cost[ i – 1, w ] if, Wi > w
cost[ i, w ] = max( cost[ i – 1, w ], cost[ i – 1, w – W] ) if, Wi <= w

##### Question:
items | weight | benefit
========================
1     | 6      | 10
2     | 1      | 5
3     | 2      | 7
4     | 5      | 12
5     | 4      | 8
6     | 3      | 6


For weight of 10 what is the maximum possible benefit by trying all item?

For this problem max benefit is 26.

The answer is always found in cost[ item_count, total_weight ]
Our item_count was 6 and total_weight was 10.
Here the answer is in cost[ 6, 10 ] which is 26.

## Code:

#### Iterative:

/**
* @author  Quickgrid ( Asif Ahmed )
* Problem: Zero one knapsack iterative
*/

#include<stdio.h>

#define N 128

int CostTable[N][N];
int Weight[N];
int Benefit[N];

int total_weight = 10;
int item_count = 6;

inline int max(int a, int b){
return a > b ? a : b;
}

void dynamicKnapsack(){
int i = 0;

/*
* Set each column in first(zeroth) row to zero
*/
for(; i <= total_weight; ++i)
CostTable[0][i] = 0;

/*
* Set each row in first(zeroth) column to zero
*/
for(int i = 0; i <= item_count; ++i){
CostTable[i][0] = 0;

/*
* calculate till required weight
*/
for(int w = 1; w <= total_weight; ++w){
/*
* Get value from row above
* or,
* the value from a left column (w - Weight[i]) in the row above with added benefit
*/
if(Weight[i] <= w)
CostTable[i][w] = max(Benefit[i] + CostTable[i-1][w - Weight[i]], CostTable[i-1][w]);
else
CostTable[i][w] = CostTable[i-1][w];
}
}
}

void printCostTable(){
for(int i = 0; i <= item_count; ++i){
printf("%d:  ", i);
for(int w = 0; w <= total_weight; ++w)
printf("%d ", CostTable[i][w]);
printf("\n");
}
}

int main(){

Weight[1] = 6;
Weight[2] = 1;
Weight[3] = 2;
Weight[4] = 5;
Weight[5] = 4;
Weight[6] = 3;

Benefit[1] = 10;
Benefit[2] = 5;
Benefit[3] = 7;
Benefit[4] = 12;
Benefit[5] = 8;
Benefit[6] = 6;

dynamicKnapsack();

printf("Max Benefit: %d\n\n", CostTable[item_count][total_weight]);

printCostTable();

return 0;
}


#### Recursive:

/**
* @author  Quickgrid ( Asif Ahmed )
* Problem: Zero one knapsack recursive
*/

#include<stdio.h>

#define N 128

int CostTable[N][N];
int Weight[N];
int Benefit[N];

int total_weight = 10;
int item_count = 6;

inline int max(int a, int b){
return a > b ? a : b;
}

int RecursiveKnapsack(int i, int w){
if(i == 0 || w == 0)
return 0;

if(Weight[i] > w)
return RecursiveKnapsack(i - 1, w);
else
return max(RecursiveKnapsack(i - 1, w), RecursiveKnapsack(i - 1, w - Weight[i]) + Benefit[i]);
}

int main(){

Weight[1] = 6;
Weight[2] = 1;
Weight[3] = 2;
Weight[4] = 5;
Weight[5] = 4;
Weight[6] = 3;

Benefit[1] = 10;
Benefit[2] = 5;
Benefit[3] = 7;
Benefit[4] = 12;
Benefit[5] = 8;
Benefit[6] = 6;

printf("Max Benefit: %d\n", RecursiveKnapsack(item_count, total_weight));

return 0;
}


#### Recursive Memoized:

/**
* @author  Quickgrid ( Asif Ahmed )
* Problem: Zero one knapsack recursive memoization
*/

#include<stdio.h>

#define N 128

int CostTable[N][N];
int Weight[N];
int Benefit[N];

int total_weight = 10;
int item_count = 6;

inline int max(int a, int b){
return a > b ? a : b;
}

int RecursiveKnapsack(int i, int w){
if(CostTable[i][w] != -1)
return CostTable[i][w];

if(Weight[i] > w)
CostTable[i][w] = RecursiveKnapsack(i - 1, w);
else
CostTable[i][w] = max(RecursiveKnapsack(i - 1, w), RecursiveKnapsack(i - 1, w - Weight[i]) + Benefit[i]);
}

int main(){

Weight[1] = 6;
Weight[2] = 1;
Weight[3] = 2;
Weight[4] = 5;
Weight[5] = 4;
Weight[6] = 3;

Benefit[1] = 10;
Benefit[2] = 5;
Benefit[3] = 7;
Benefit[4] = 12;
Benefit[5] = 8;
Benefit[6] = 6;

/*
* Set all values of 2D matrix CostTable to Minus 1
*/
for(int i = 0; i <= item_count; ++i)
for(int w = 0; w <= total_weight; ++w)
CostTable[i][w] = -1;

printf("Max Benefit: %d\n", RecursiveKnapsack(item_count, total_weight));

return 0;
}


## LCS Algorithm Practice Sheet With Solution Steps

LCS Algorithm blank sheet made with a sample input from uva 10405 longest common subsequence. See this and this tutorial to have a better understanding.