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

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 674 – Coin Change Solution

UVA Problem 674 – Coin Change Solution:


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

Solving Technique:

Given 5 types of coins: 50-cent, 25-cent, 10-cent, 5-cent, and 1-cent. We are to calculate the number of ways the input amount can be distributed with this coins.

This problem is a bit harder. It can be solved with dynamic programming or using greedy technique. Use bottom up technique instead of top down to speed it up.

We can also replace this,

 for(i = 5; i < N; ++i)
        a[i] = a[i - 1];

with this since we know no matter what the input it is always possible to give 1 cents,

for(j = 0; j < N; ++j)
        a[j] = 1;

It is hard to visualize without drawing the recursion tree or the array. The first 20 indexes of the array looks like this,

Index: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
Coins: 1 1 1 1 1 2 2 2 2 2 4  4  4  4  4  6  6  6  6  6  9

Explanation:

/* TO DO */

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:

11
26
5
4

Output:

4
13
2
1

Code Bottom Up:

/**
 * @author  Quickgrid ( Asif Ahmed )
 * @link    https://quickgrid.wordpress.com
 * Problem: UVA 674 Coin Change
 */

#include <stdio.h>
#define N 8000

static int a[N] = {1, 1, 1, 1, 1};
static const int coins[4] = {5, 10, 25, 50};

int main()
{
    register int i, j;

    for(i = 5; i < N; ++i)
        a[i] = a[i - 1];

    for(i = 0; i < 4; ++i){
        for(j = coins[i]; j < N; ++j)
            a[j] += a[ j - coins[i] ];
    }

    int n;
    while(scanf("%d", &n) == 1)
        printf("%d\n", a[n]);

    return 0;
}

Loop Fission Variant:

/**
 * @author  Quickgrid ( Asif Ahmed )
 * @link    https://quickgrid.wordpress.com
 * Problem: UVA 674 Coin Change
 */

#include <stdio.h>

#define N 8000
#define M 5

static int a[N] = {1, 1, 1, 1, 1};

int main()
{
    register int i, j;

    for(j = M; j < N; ++j)
        a[j] += a[j - 1];

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

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

    for(j = 25; j < N; ++j)
        a[j] += a[j - 25];

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

    int n;
    while(scanf("%d", &n) == 1)
        printf("%d\n", a[n]);

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