Header Ads Widget

Chef and Codes | codechef solution

Rajnish Tripathi 20:10

Once upon a time chef decided to learn encodings. And, obviously, he started with the easiest one (well, actually the easiest after Caesar cypher) – substitution cypher.
But very soon Chef got bored with encoding/decoding, so he started thinking how to hack this cypher. He already knows some algorithm, which is not always correct, but it’s sufficient for now. Here is its description.
Imagine we know frequency sequence of English letters (this means, that letters are sorted by their frequency of appearing in English texts, in ascending order). And let’s find frequency sequence of cyphered letters (if some of them appear equal number of times, then first in frequency sequence will be lower letter between them). Now, using this two frequency sequences we can recover plain text. Just substitute cyphered letter with origin one, if they are at same positions in sequences.

Now, Chef has frequency sequence of English letters and cypher text. And he asks you to recover plain text. Please, help him.

Input

In first line number T is given - number of test cases. Then T test cases follow. Each test case consists of two lines - frequency sequence and encrypted text.

Output

For each test case you should output decrypted with the given frequency sequence text. Please note, that the case of letters should be preserved.

Constraints

  • 1 ≤ T ≤ 1000;
  • Length of frequency sequence is always 26;
  • 1 ≤ length of the text ≤ 150000;
  • 1 ≤ sum lengths of all texts ≤ 150000.
  • Frequency sequence consists of all lowercase English letters. Text consists of any characters.

Sample 1:

Input
Output
3
qwrtyuipasdfgjkzxcvbnmheol
dummy!
bfgjklmopqrstuwxzhvnicdyea
abcd b efgd hbi!
qwrtyuipasdfgjkzxcvbnmheol
Dummy!
hello!
have a nice day!
Hello!

Code(C++):-

#include <bits/stdc++.h>
using namespace std;

int main()
{
int t;
cin >> t;
while (t--)
{
string f, c;
cin >> f;
cin.ignore();
getline(cin, c);
int a[26] = {0};
for (int i = 0; i < c.size(); i++)
{
if (c[i] >= 'a' && c[i] <= 'z')
a[c[i] - 'a']++;
else if (c[i] >= 'A' && c[i] <= 'Z')
a[c[i] - 'A']++;
}
vector<pair<int, char>> v;
for (int i = 0; i < 26; i++)
v.push_back({a[i], ('a' + i)});
sort(v.begin(), v.end());
map<char, char> m;
for (int i = 0; i < 26; i++)
if (v[i].first != 0)
m[v[i].second] = f[i];
for (int i = 0; i < c.size(); i++)
{
if (c[i] >= 'a' && c[i] <= 'z')
cout << m[c[i]];
else if (c[i] >= 'A' && c[i] <= 'Z')
cout << char('A' + (m['a' + (c[i] - 'A')] - 'a'));
else
cout << c[i];
}
cout << "\n";
}
}

Code(JAVA):-

import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class Codechef
{
    public static void main (String[] args) throws java.lang.Exception
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t =Integer.parseInt(br.readLine()),x;
        while(t-->0)
        {
         int b[]=new int[26];
         String s=br.readLine(),s1=br.readLine();
         for(int i=0;i<s1.length();i++)
         {
         x=(int)s1.charAt(i);
         if(x>96&&x<123)
         b[x-97]++;
         else if(x>64&&x<91)
         b[x-65]++;
         }
         int a[][]=new int[26][2];
         for(int i=0;i<26;i++)
         {
         a[i][0]=b[i];
         a[i][1]=i;
         }
        
         Arrays.sort(a,new Comparator<int[]>(){
         public int compare(final int[] a,final int[] b){
         if(a[0]<b[0])
         return 1;
         else if(a[0]==b[0])
         {
         if(a[1]<b[1])
         return 1;
         return -1;
         }
         return -1;
         }});
        
         for(int i=0;i<26;i++)
         b[a[i][1]]=i;
         String s2=" ";
         for(int i=0;i<s1.length();i++)
         {
         x=(int)s1.charAt(i);
         if(x>96&&x<123)
         s2+=s.charAt(25-b[x-97]);
         else if(x>64&&x<91)
         s2+=(char)(s.charAt(25-b[x-65])-32);
         else
         s2+=s1.charAt(i);
         }
         System.out.println(s2);
        }
    }
}

Recommended Post :-

HCL Coding Questions:-

Capgemini Coding Questions:-

Companies interview:-

Full C course:-    

Key points:-

Cracking the coding interview:-

 Array and string:-

Tree and graph:-

Hackerearth Problems:-

Hackerrank Problems:-

Data structure:-

 MCQs:-


 

Tags:

Post a Comment

0 Comments