UVA Problem 865 – Substitution Cypher Solution

UVA Problem 865 – Substitution Cypher Solution:


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

Solving Technique:

Similar problems to this problem, UVA Problem 10082 – WERTYU Solution and also UVA Problem 11278 – One Handed Typist Solution.

In this problem we are given two strings one of which is plain text and the next one is its substitution. In the plain text string there are characters that are to be mapped to its substitution characters from the substitution string.

Next comes several lines of text in which plain characters that match the required substitution characters should be replaced to its substitution character equivalent. The characters that don’t match the substitution requirement should stay the same.

The hardest part of this problem is newlines. There is a new line after number of cases, so make sure to discard that. Also an empty line marks the end of text inputs for a test case. Last thing is there is a new line between test cases, so for the last output there shouldn’t be an extra new line.

 

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

abcdefghijklmnopqrstuvwxyz
zyxwvutsrqponmlkjihgfedcba
Shar's Birthday:
The birthday is October 6th, but the party will be Saturday,
October 5.  It's my 24th birthday and the first one in some
years for which I've been employed.  Plus, I have new clothes.
So I have cause to celebrate.  More importantly, though,
we've cleaned the house!  The address is 506-D Albert Street.
Extra enticement for CS geeks:  there are several systems in
the house, and the party is conveniently scheduled for 3 hours
after the second CSC programming contest ends (not to mention,
within easy walking distance)!

 


Output:

zyxwvutsrqponmlkjihgfedcba
abcdefghijklmnopqrstuvwxyz
Sszi'h Brigswzb:
Tsv yrigswzb rh Oxglyvi 6gs, yfg gsv kzigb droo yv Szgfiwzb,
Oxglyvi 5.  Ig'h nb 24gs yrigswzb zmw gsv urihg lmv rm hlnv
bvzih uli dsrxs I'ev yvvm vnkolbvw.  Pofh, I szev mvd xolgsvh.
Sl I szev xzfhv gl xvovyizgv.  Mliv rnkligzmgob, gslfts,
dv'ev xovzmvw gsv slfhv!  Tsv zwwivhh rh 506-D Aoyvig Sgivvg.
Ecgiz vmgrxvnvmg uli CS tvvph:  gsviv ziv hvevizo hbhgvnh rm
gsv slfhv, zmw gsv kzigb rh xlmevmrvmgob hxsvwfovw uli 3 slfih
zugvi gsv hvxlmw CSC kiltiznnrmt xlmgvhg vmwh (mlg gl nvmgrlm,
drgsrm vzhb dzoprmt wrhgzmxv)!

Code:

/**
 * Author:    Quickgrid ( Asif Ahmed )
 * Site:      https://quickgrid.wordpress.com
 * Problem:   UVA 865 - Substitution Cypher
 * Technique: Character Mapping, Array Mapping
 */

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

#define N 256

static char text[N];
static char plaintext[N];
static char substitution[N];


static char newLayout[N];

static char output[N];


int main(){

    int n;

    /**
     * Input an integer.
     * discard new line character for enter.
     * discard empty line.
     */
    scanf("%d", &n);
    getchar();
    getchar();


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

        /**
         * Print spaces between test cases.
         */
        if(j)
            printf("\n");


        /**
         * Input plain text and cipher text.
         */
        gets(plaintext);
        gets(substitution);


        /**
         * Map each character to its ASCII decimal value.
         * In other words map the same character to itself.
         *
         * This is done because not all characters are changed by
         * substitution cipher so rest of the characters map to itself.
         */
        for(int i = 0; i < 256; ++i)
            newLayout[i] = i;


        /**
         * Since plain text and cipher text will equal size any of them
         * can be used to check termination condition.
         *
         * Inside the loop map plain text characters to its substitution.
         */
        for(int i = 0; plaintext[i]; ++i)
            newLayout[ plaintext[i] ] = substitution[i];


        /**
         * Print substitution string first and plain text as per requirement.
         */
        puts(substitution);
        puts(plaintext);


        /**
         * Now take input and scramble until a blank line is found.
         *
         * Here i have used string to output each line but character
         * by character output will also work.
         */
        while(gets(text) && strlen(text)){

            memset(output, 0, sizeof output);

            for( int i = 0; i < strlen( text ); ++i )
                output[i] = newLayout[ text[i] ];

            puts(output);

        }

    }

    return 0;
}

UVA Problem 11278 – One-Handed Typist Solution

UVA Problem 11278 – One-Handed Typist Solution:


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

Solving Technique:

Before starting this you can check out a similar problem UVA Problem 10082 – WERTYU Solution. That problem is very similar to this and also somewhat similar to a Caesar Cipher with right shift of 1.

The problem deals with two keyboard layouts. The author typed dovrak key layout keys in standard keyboard layout by mistake. So he was actually pressing standard keys and now his output ( input in this problem ) looks scrambled. The task is to convert all typed standard key inputs to equivalent dvorak keys.

There are a few ways to solve this problem. One ways is to painstakingly map each standard key to a dvorak key.

Another way is to map ASCII table characters from Decimal 32 to 126 as standard keys. This can be done with a loop and another array with equivalent dvorak keys. This method is easier that is eliminates one array but then creating the dvorak array becomes time consuming.

The third way which which i used here is create two arrays containing standard and dvorak keys. Then map each standard key to a dvorak key.

The code below is explained with comments.

 

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


Input:

Hg66t Mty6k!
Jhg 4ibl; pytmn 8tc 5i79urrr
t,gy jhg 6fxo kt.r

 


Output:

Hello World!
The quick brown fox jumps...
over the lazy dog.

Code Output as Characters:

/*
 * Author:     Quickgrid ( Asif Ahmed )
 * Site:       https://quickgrid.wordpress.com
 * Problem:    UVA 11278 - One Handed Typist
 * Techniques: Array mapping, Character mapping
 */

#include<stdio.h>


#define N  128
#define IO 1001


/**
 * Heart of the problem. Be careful with mapping, one typo in mapping and the verdict is wrong.
 * Here standard contains all the characters in standard keyboard including capital and small.
 * dvorak contains all the characters in dvorak keyboard including capital and small.
 */
static const char standard[N] = "`1234567890-=qwertyuiop[]\\asdfghjkl;'zxcvbnm,./~!@#$%^&*()_+QWERTYUIOP{}|ASDFGHJKL:\"ZXCVBNM<>? ";
static const char dvorak[N]   = "`123qjlmfp/[]456.orsuyb;=\\789aehtdck-0zx,inwvg'~!@#QJLMFP?{}$%^>ORSUYB:+|&*(AEHTDCK_)ZX<INWVG\" ";


/**
 * This is the mapping array. It holds mappings of dvorak to standard keyboard.
 */
static char mappingKB[N];


static char input[IO];


int main(){

    /**
     * Although mapping "mappingKB[ standard[i] ] = dvorak[i]" seems wrong and
     * mapping from "mappingKB[ dvorak[i] ] = standard[i]" seems correct.
     *
     * But its wrong remember the coach was typing dvorak in standard keyboard keys
     * instead of dvorak key mappings. Since the input was in standard keyboard and we should convert it to dvorak otherwise it looks
     * scrambled.
     *
     * So the keys of standard keyboard maps to dvorak keys.
     */
    for(int i = 0; dvorak[i]; ++i)
        mappingKB[ standard[i] ] = dvorak[i];



    while(gets(input)){

        /**
         * Convert standard keys to dvorak using pre-mapped array
         */
        for(int i = 0; input[i]; ++i)
            printf("%c", mappingKB[ input[i] ] );

        printf("\n");

    }


    return 0;
}

Code Output as String:

/*
 * Author:     Quickgrid ( Asif Ahmed )
 * Site:       https://quickgrid.wordpress.com
 * Problem:    UVA 11278 - One Handed Typist
 * Techniques: Array mapping, Character mapping
 */

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


#define N  128
#define IO 1001


static const char standard[N] = "`1234567890-=qwertyuiop[]\\asdfghjkl;'zxcvbnm,./~!@#$%^&*()_+QWERTYUIOP{}|ASDFGHJKL:\"ZXCVBNM<>? ";
static const char dvorak[N]   = "`123qjlmfp/[]456.orsuyb;=\\789aehtdck-0zx,inwvg'~!@#QJLMFP?{}$%^>ORSUYB:+|&*(AEHTDCK_)ZX<INWVG\" ";

static char mappingKB[N];

static char input[IO];
static char output[IO];


int main(){

    for(int i = 0; dvorak[i]; ++i)
        mappingKB[ standard[i] ] = dvorak[i];


    while(gets(input)){

        // Reset memory otherwise character form previous input will be shown along with new
        memset(output, 0, sizeof output);

        for(int i = 0; input[i]; ++i)
            output[i] = mappingKB[ input[i] ];

        puts(output);

    }


    return 0;
}

UVA Problem 10082 – WERTYU Solution

UVA Problem 10082 – WERTYU Solution:


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

Solving Technique:

Read the first paragraph and input section carefully. This is a simple mapping problem.

The problem is that the keyboard is broken and every key that was pressed its immediate right character was printed. So we have to reverse that procedure by mapping every input character to the character to its left based on the given keyboard.

Generating the keyboard layout is easy. We can use an array and lay them sequentially so when we find a character we print the character that is to its left.

If we only use array to layout keyboard then for every input we will need to search the whole array. We can fix this by mapping the layout array to another array beforehand only once. Then just access that index and print.

Here the first code below is mapping from predefined lookup table. The second one does brute force to find its match. Here I have used stringstream but c++ string or c char array can also be used.

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:

O S, GOMR YPFSU/

Output:

I AM FINE TODAY.

Code (Mapping from predefined Lookup table):

/**
 * @author  Quickgrid ( Asif Ahmed )
 * @link    https://quickgrid.wordpress.com
 * Problem: UVA 10082 WERTYU ( using c++ string stream )
 */

#include<cstdio>
#include<sstream>
#include<iostream>

#define N 256

/**
 * Predefined keyboard layout
 */
static const char kb[64] = "`1234567890-=QWERTYUIOP[]\ASDFGHJKL;'ZXCVBNM,./";
static char s[N], A[N];

void createTable(){
    /**
     * space character does not change
     */
    A[' '] = ' ';

    /**
     * Create keyboard layout from broken keyboard
     */
    register int i = 0;
    for(; kb[i]; ++i)
        A[kb[i+1]] = kb[i];
}

int main(){
    std::ios_base::sync_with_stdio(NULL);
    std::cin.tie(0);
    register int i, j;

    /**
     * Create the keyboard layout beforehand
     */
    createTable();

	while(gets(s)){
        /**
         * Create a string stream from table to print all together
         * We can also use string and add each character then print
         */
        std::stringstream ss;

        /**
         * Lookup characters from predefined table
         */
        for(i = 0; s[i]; ++i)
            ss << A[s[i]];

        std::cout << ss.str() << "\n";
	}
	return 0;
}

Code (Using Lookup Table):

/**
 * @author  Quickgrid ( Asif Ahmed )
 * @link    https://quickgrid.wordpress.com
 * Problem: UVA 10082 WERTYU ( using c++ string stream )
 */

#include<cstdio>
#include<sstream>
#include<iostream>

static const char kb[64] = "`1234567890-=QWERTYUIOP[]\ASDFGHJKL;'ZXCVBNM,./";
static char s[256];

int main(){
    std::ios_base::sync_with_stdio(NULL);
    std::cin.tie(0);
    register int i, j;

	while(gets(s)){
        std::stringstream ss;

        for(i = 0; s[i]; ++i){
            if(s[i] == ' ')
                ss << ' ';
            else{
                /**
                 * Each character maps to a character in its left as defined
                 */
                for(j = 0; kb[j]; ++j){
                    if(s[i] == kb[j])
                        ss << kb[j - 1];
                }
            }
        }
        std::cout << ss.str() << "\n";
	}
	return 0;
}

UVA Problem 1368 – DNA Consensus String Solution

UVA Problem 1368 – DNA Consensus String Solution:


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

Solving Technique:

Rank 174, Run time 12 ms ( 0.012 s ).

First input is number of test cases. Next of two inputs one is number of strings to input and another is the size of string. Our strings will only contain A, C, G, T characters.

For solving this problem we first need to find consensus string. That is of all strings we check each column of all strings and count the maximum occurring character in that column. This character is our consensus string character for that column.

Consensus string size is same as the input string size. Since each of its characters are maximum occurring characters in the input string. Example,

TATGATAC
TAAGCTAC
AAAGATCC
TGAGATAC
TAAGATGT
========
TAAGATAC    /* Consensus String, check each column for max character count */

Now that we have found the consensus string we just need to find consensus error. I will only explain the logic here, I have commented my code below.

TATGATAC
TAAGCTAC
AAAGATCC
TGAGATAC
TAAGATGT
========
TAAGATAC    /* Consensus String */
========
11101021    /* Consensus Error, 1+1+1+0+1+0+2+1 = 7, count every character of a column that don't match that consensus string character */

Now if you understood my explanation time to go write a better solution :).

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:

3 
5 8 
TATGATAC 
TAAGCTAC 
AAAGATCC 
TGAGATAC 
TAAGATGT 
4 10 
ACGTACGTAC 
CCGTACGTAG 
GCGTACGTAT 
TCGTACGTAA 
6 10 
ATGTTACCAT 
AAGTTACGAT 
AACAAAGCAA 
AAGTTACCTT 
AAGTTACCAA 
TACTTACCAA

Output:

TAAGATAC 
7 
ACGTACGTAA 
6 
AAGTTACCAA 
12

Code:

/*
 * Author: Quickgrid ( Asif Ahmed )
 * Site: https://quickgrid.wordpress.com
 * Problem: UVA 1368 ( DNA Consensus String )
 */

#include<stdio.h>

int main(){
    register unsigned n, a, b, i, j, k, error;
    scanf("%u", &n);

    while(n--){
        scanf("%u%u", &a, &b);

        /**
         * Create the string array
         */
        char **s = new char*[a+1];
        for(i = 0; i < a; ++i){
            /**
             * Allocate space for each string
             */
            s[i] = new char[b+1];
            /**
             * Input a string in i th position
             */
            scanf("%s", s[i]);
        }

        /**
         * Consensus string declaration
         */
        char *conseq = new char[b+1];
        /**
         * K is used below
         */
        for(k = i = 0; i < b; ++i){
            /**
             * Reset A,C,G,T count array
             */
            unsigned int seq[4] = {0};
            for(j = 0; j < a; ++j){
                switch(s[j][i]){
                case 65:    /* 65, 'A' here seq[0] is A */
                    ++seq[0];
                    break;
                case 67:    /* 'C' */
                    ++seq[1];
                    break;
                case 71:    /* 'G' */
                    ++seq[2];
                    break;
                case 84:    /* 'T' */
                    ++seq[3];
                }
            }

            unsigned max = seq[0], maxIndex = 0;
            for(j = 1; j < 4; ++j){
                if(seq[j] > max){
                    /**
                     * Find the max count of A,C,G,T in a column, in all strings
                     */
                    max = seq[j];
                    /**
                     * Remember the maxIndex for creating consensus string
                     */
                    maxIndex = j;
                }
            }

            /**
             * We keep adding to our consensus string the most count of A,C,G,T
             */
            switch(maxIndex){
            case 0:
                conseq[k++] = 65;
                break;
            case 1:
                conseq[k++] = 67;
                break;
            case 2:
                conseq[k++] = 71;
                break;
            case 3:
                conseq[k++] = 84;
            }
        }

        for(error = i = 0; i < b; ++i){
            for(j = 0; j < a; ++j){
                /**
                 * Calculate the error count by moving column by column of all strings, then comparing against the consensus string character in that column
                 */
                if(s[j][i] != conseq[i])
                    ++error;
            }
        }

        /**
         * Print the consensus string and error count EACH ON A NEW LINE
         */
        printf("%s\n%u\n", conseq, error);
    }
    return 0;
}