UVA Problem 10008 – What’s Cryptanalysis? Solution

UVA Problem 10008 – What’s Cryptanalysis? Solution:


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

Solving Technique:

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

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

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


More Inputs of This Problem on uDebug.


Input:

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

 


Output:

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

Code:

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


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


#define N 256


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


static char s[N];


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

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

}



int main(){

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

    int n;

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

    while( n-- ){

        gets( s );

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


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

    }


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


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



    return 0;
}

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s