850 - Crypt Kicker II

All about problems in Volume 8. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

newkid
Learning poster
Posts: 73
Joined: Fri Dec 12, 2008 3:06 am

Re: 850 - Crypt Kicker II

Post by newkid » Mon Jan 19, 2009 2:55 pm

The problem statement says..
If there is more than one possible decryption (several lines can be decoded to the key sentence), use the first line found for decoding.
But you are doing..

Code: Select all

int findkey()
{
    for(int i = lines.size() - 1; i >= 0; i--)
    {
        if(checkCandidate(lines[i]))
            return i;
    }
    return -1;
}
it should be

Code: Select all

int findkey()
{
    for(int i = 0; i < lines.size() ; i++)
    {
        if(checkCandidate(lines[i]))
            return i;
    }
    return -1;
}
Another minor thing..
your program doesnt print the last newline..

Not so critical input:

Code: Select all

4

vtz ud xnm xugm itr pyy jttk gmv xt otgm xt xnm puk ti xnm fprxq
xnm ceuob lrtzv ita hegfd tsmr xnm ypwq ktj
frtjrpgguvj otvxmdxd prm iev prmvx xnmq

the quick brown fox jumps over the lazy dog

now is the time for all good men to come to the aid of the party
xnm ceuob lrtzv ita hegfd tsmr xnm ypwq ktj
the quick brown fox jumps over the lazy dog
programming contests are fun arent they

now is the time for all good men to come to the aid of the party
the quick brown fox jumps over the lazy dog
xnm ceuob lrtzv ita hegfd tsmr xnm ypwq ktj
programming contests are fun arent they
My acc program prints..

Code: Select all

now is the time for all good men to come to the aid of the party
the quick brown fox jumps over the lazy dog
programming contests are fun arent they

the quick brown fox jumps over the lazy dog

hcz fv oju ofeu pcr xbb mccs euh oc qceu oc oju xfs cp oju axrol
the quick brown fox jumps over the lazy dog
oju yifqd krczh pct gieav cnur oju bxwl scm
arcmrxeefhm qchouvov xru pih xruho ojul

now is the time for all good men to come to the aid of the party
the quick brown fox jumps over the lazy dog
xnm ceuob lrtzv ita hegfd tsmr xnm ypwq ktj
programming contests are fun arent they
but your program prints..

Code: Select all

now is the time for all good men to come to the aid of the party
the quick brown fox jumps over the lazy dog
programming contests are fun arent they

the quick brown fox jumps over the lazy dog

now is the time for all good men to come to the aid of the party
xnm ceuob lrtzv ita hegfd tsmr xnm ypwq ktj
the quick brown fox jumps over the lazy dog
programming contests are fun arent they

hcz fv oju ofeu pcr xbb mccs euh oc qceu oc oju xfs cp oju axrol
oju yifqd krczh pct gieav cnur oju bxwl scm
the quick brown fox jumps over the lazy dog
arcmrxeefhm qchouvov xru pih xruho ojul
hmm..

alirezanoori
New poster
Posts: 26
Joined: Fri Jan 02, 2009 12:41 am

Re: 850 - Crypt Kicker II

Post by alirezanoori » Fri Jan 23, 2009 4:25 pm

Thanks in advance. Now i got AC!

aprimadi1
New poster
Posts: 1
Joined: Sun Jan 25, 2009 7:37 am

Re: 850 - Crypt Kicker II

Post by aprimadi1 » Sun Jan 25, 2009 7:43 am

Can anyone help me with this code? I don't know what is wrong.

Code: Select all

#include <iostream>
#include <sstream>
#include <cstdio>
#include <cstdlib>
#include <string>

#include <iterator>

#include <vector>
#include <map>
using namespace std;

const string KNOWN_TEXT = "the quick brown fox jumps over the lazy dog";

void readInput(vector<string> & lines) {
  string s;
  while (getline(cin, s)) {
    if (s == "") break;
    lines.push_back(s);
  }
}

bool mapText(const string & known_text, const string & text, 
             map<char, char> & mapping) {
  for (int i=0; i<known_text.length(); i++) {
    // check if ' ' is switched with 'a'-'z'
    if (!isalpha(text[i]) && text[i]!=known_text[i])
      return false;

    if (isalpha(text[i])) {
      pair< map<char, char>::iterator, bool> 
        p = mapping.insert( make_pair(text[i], known_text[i]) );
      // already mapped with different value
      if (!p.second && p.first->second != known_text[i])
        return false;
    }
  }
  return (mapping.size()==26);
}

void mapLines(vector<string> & lines, map<char, char> & mapping) {
  for (int i=0; i<lines.size(); i++)
    for (int j=0; j<lines[i].length(); j++)
      if (isalpha(lines[i][j]))
        lines[i][j] = mapping[ lines[i][j] ];
}

int main() {
  int tc;

  scanf("%d\n\n", &tc);
  for (int h=0; h<tc; h++) {
    /* input */
    vector<string> lines;
    readInput(lines);

    // try mapping it
    map<char, char> mapping;
    vector<string>::iterator it;
    for (it = lines.begin(); it != lines.end(); ++it) {
      if (it->length() == KNOWN_TEXT.length() &&
          mapText(KNOWN_TEXT, *it, mapping))
        break;
    }

    if (h!=0) cout << endl;

    if (it == lines.end()) {  // mapping failed
      cout << "No solution." << endl;
    }
    else {
      mapLines(lines, mapping);
      for (vector<string>::iterator it = lines.begin(); it != lines.end(); ++it)
        cout << *it << endl;
    }
  }
  return 0;
}

gautamverma
New poster
Posts: 1
Joined: Wed Jul 02, 2008 9:57 pm

Re: 850 - Crypt Kicker II

Post by gautamverma » Wed Apr 08, 2009 6:20 am

I have checked on all inputs given and got correct answer but Still WA.

my approach is i am taking all the lines which has possibility of being the key line and
finding which letter has substituted what then building up the key line again.
if key line is being able to framed then its a correct replacement.

( header removed .)

Code: Select all

 bool crypt_check( string line, char *alphabets ) {
              
     string p_text("the quick brown fox jumps over the lazy dog");
     for( int i = 0; i<line.size(); i++ ) 
        alphabets[line[i]] = p_text[i];
     
     char c_line[line.size()];
     for( int i = 0; i<line.size(); i++ ) 
        c_line[i] = alphabets[line[i]];
    
     string check;
     for( int i = 0; i<line.size(); i++ )
        check += c_line[i];
 
     if( check == p_text )
       return true;
     else 
       return false;
     }
               
int main() {
     
    int cases;
    scanf("%d\n\n",&cases );
    int copy = cases;
    while( cases>0 ) {
        
         if( copy!=cases )
           printf("\n");
        
         vector<string> pharse;
         string str;
         while( getline( cin, str ) && str.size()!=0 )
              pharse.push_back( str );
          
         string p_text("the quick brown fox jumps over the lazy dog");
         char alphabets[128];

         bool found = false;
         int in = 0;
         while( in<pharse.size() && !found ) {
              if( pharse[in].size()==p_text.size() ) 
                 found = crypt_check( pharse[in], alphabets );
              in++;
              }
         
         if( found ) {
           // decrypt them all
           for( int i = 0; i<pharse.size(); i++ ) {
              for( int j = 0; j<pharse[i].size(); j++ ) 
                 printf("%c",alphabets[pharse[i][j]] );
              printf("\n");
              } 
           }
         else 
           printf("No solution.\n");
         cases--;
         }
    return 0;
    }
 
can anyone help me out??

rator10
New poster
Posts: 2
Joined: Wed Feb 27, 2008 9:21 am

Re: 850 - Crypt Kicker II

Post by rator10 » Sat Apr 11, 2009 5:52 am

For those of you still having trouble with this problem, one of my mistakes dealt with space being considered a letter and replaceable. A test case to see if this causes errors for yours is the following:

Code: Select all

1

_hetquicktbrowntfoxtjumpstovert_hetlazytdog
the_quick_brown_fox_jumps_over_the_lazy_dog
the answer should be:

Code: Select all

_hetquicktbrowntfoxtjumpstovert_hetlazytdog
the_quick_brown_fox_jumps_over_the_lazy_dog
note that _'s have been put in place of spaces, because the code feature seems to remove white-spaces from the beginning of the line

corns
New poster
Posts: 2
Joined: Wed Apr 22, 2009 4:25 pm

Re: 850 - Crypt Kicker II

Post by corns » Wed Apr 22, 2009 4:30 pm

My program pass all the test case post here, but still get WA ><,can anyone plx help??

thanks!

my code is as follows:

Code: Select all

#include <iostream>
#include <cstring>

using namespace std;

const char KEY[] = "the quick brown fox jumps over the lazy dog";
const int SIZEKEY = strlen(KEY);

char a[120];
char b[120];


bool matchKey(char* line) {

    if(strlen(line) != SIZEKEY) 
	return false;

    for(int i='a';i<='z';i++) {
	a[i] = b[i] = -1;
    }
    a[' '] = b[' '] = ' ';

    for(int i=0;i<SIZEKEY;++i) {
	if(a[line[i]] == -1) 
	    a[line[i]] = KEY[i];
	else if(a[line[i]] != KEY[i])
	    return false;

	if( b[KEY[i]]==-1)
	    b[KEY[i]] = line[i];
	else if(b[KEY[i]] != line[i]) 
	    return false;
    }
    return true;
}


int main() {
    int cases;
    cin >> cases;
    char input[80];
    char lines[100][80];
    bool first = true;
    
    getchar(); getchar();
    for(int c=0;c<cases;++c) {
	int num;
	for(num=0;;++num) {
	    cin.getline(input, 100);
	    if(strcmp(input,"") == 0) break;
	    strcpy(lines[num], input);
	}
	
	int i;
	for(i=0;i<num;i++) {
	    if(matchKey(lines[i])) break;
	}
	if(!first) cout << endl;
	else first = false;

	if(i==num)
	    cout << "No solution." << endl;
	else {
	    for(int k=0;k<num;k++) {
		for(int j=0;j<strlen(lines[k]);j++) {
		    cout << a[lines[k][j]];
		}
		cout << endl;
	    }
	}
	
    }

    return 0;
}



Igor9669
Learning poster
Posts: 85
Joined: Sun Jun 08, 2008 12:58 pm

Re: 850 - Crypt Kicker II

Post by Igor9669 » Fri Jul 24, 2009 5:52 pm

This test help to find my bug:

Code: Select all

1

xnm ceuob lrtzv ita hegfd tsmr xnm ypwq ktj x
Ansewr should be: No solution.

abhiramn
New poster
Posts: 29
Joined: Sat May 26, 2007 7:54 pm

WA! Please help.

Post by abhiramn » Mon Sep 07, 2009 7:57 am

Hello, I am getting a WA for my code. I have tried every input on this thread. Please help me.

Code: Select all

#include<stdio.h>
#include<string.h>
int isPangram(char str[])
{
	int spaces[]={3,9,15,19,25,30,34,39},i,flags[150];

	for(i=0;i<8;++i)
		if(str[spaces[i]]!=' ')
			return 0;

	for(i=97;i<123;flags[i]=0,++i);
	for(i=0;str[i];flags[str[i]]=1,++i);
	for(i=97;i<123;++i)
		if(!flags[i])
			return 0;

	if(str[0]!=str[31]||str[1]!=str[32]||str[2]!=str[28]||str[28]!=str[33]||str[5]!=str[21]||str[11]!=str[29]||str[12]!=str[17]||str[17]!=str[26]||str[26]!=str[41])
		return 0;
	return 1;
}
int main()
{
	char str[110][90],pan[]="the quick brown fox jumps over the lazy dog",val[130];
	int i,test,len,j,t=0,k,flag;
	for(scanf("%d%*c%*c",&test);test--;)
	{
		i=-1;flag=0;
		do
		{
			++i;
			scanf("%[^\n]%*c",str[i]);
			len=strlen(str[i]);
			if(!flag&&len==43&&isPangram(str[i]))
			{
				flag=1;
				for(j=0;j<43;++j)
					val[str[i][j]]=pan[j];
			}
		}while(len);
		scanf("%*c");

		val[' ']=' ';

		if(t)
			putchar('\n');
		else
			t=1;
		if(flag)
			for(j=0;j<i;++j)
			{
				for(k=0;str[j][k];putchar(val[str[j][k]]),++k);
				putchar('\n');
			}
		else
			printf("No solution.\n");

		for(j=0;j<i;str[j][0]='\0',++j);
	}
	return 0;
}

talizmelf
New poster
Posts: 3
Joined: Thu Oct 15, 2009 5:54 am

Re: 850 - Crypt Kicker II

Post by talizmelf » Thu Nov 19, 2009 7:26 am

is about not enconding blank spaces, this is, blank spaces must match blank spaces.
for the sample above:

Code: Select all

1

_hetquicktbrowntfoxtjumpstovert_hetlazytdog
the_quick_brown_fox_jumps_over_the_lazy_dog
the output sould be

Code: Select all

No solution.
I also got WA when my code output correctly every case in this thread and I fixed it by adding this line in my matching function while iterating over the texts...

Code: Select all

if (plaintext[i] == ' ' && line[i] != ' ') return false;

buiutripa
New poster
Posts: 6
Joined: Wed Oct 21, 2009 1:44 am

Re: 850 - Crypt Kicker II

Post by buiutripa » Fri Dec 11, 2009 6:42 am

This is my code. I tested all inputs of this topic and all ok, but still WA
What is wrong with it?


#include <iostream>
#include <map>
#include <iterator>
#include <cstdlib>
using namespace std;

int padrao[43] = {1,2,3,4,5,6,7,8,9,4,10,11,12,13,14,4,15,12,16,4,17,6,18,19,20,4,12,21,3,11,4,1,2,3,4,22,23,24,25,4,26,12,27};
string frase = "the quick brown fox jumps over the lazy dog";
map<char, char> dicionario;
int n;
string linha, linhas[300];
bool achou;

bool montaMapa(string s) {
map<char, int> mapa;
int id = 1;

if (s.size() != 43) {
return false;
}

for (int i = 0; i < 43; i++) {
if (mapa[s] == 0) {
mapa[s] = id;
id++;
}
if (mapa[s] != padrao) {
return false;
}
}

for (int i = 0; i < 43; i++) {
dicionario[s] = frase;
}

return true;
// copy(linhaNum, linhaNum + s.size(), ostream_iterator<int>(cout, ","));
// cout << endl << s.size() << endl;
}

void traduz(int k) {
for (int i = 0; i < linhas[k].size(); i++) {
linhas[k] = dicionario[linhas[k]];
}
}

bool primeiro;

int main() {
primeiro = true;

getline(cin, linha);
n = atoi(linha.c_str());

getline(cin, linha);

while (n--) {
achou = false;
int i;
for (i = 0; true; i++) {
if (!getline(cin, linha) || (linha == "") ) break;

// cout << linha << endl;

bool branco = true;
for (int k = 0; k < linha.size(); k++) {
if (!isspace(linha[k])) {
branco = false;
break;
}
}

if (branco) {
break;
}

linhas = linha;
if (!achou && montaMapa(linha)) {
achou = true;
}
}

if (primeiro) primeiro = false;
else cout << endl;

if (!achou) {
cout << "No solution." << endl;
continue;
}

for (int j = 0; j < i; j++) {
traduz(j);
cout << linhas[j] << endl;
}

dicionario.clear();
}

return 0;
}

valkov
New poster
Posts: 20
Joined: Tue Jul 20, 2010 3:11 pm

Re: 850 - Crypt Kicker II

Post by valkov » Tue Jul 27, 2010 6:54 pm

Just got AC on this problem.
Some hints:

Watch for cases such as

Code: Select all

1
xxxxx yyyy sdakj ddd
You should print

Code: Select all

No solution.
Putting every char of the line in a set and checking if the size is equal to 27 might help you while checking if a particular line is "The One" :)

Good luck!

Ivan Goroun
New poster
Posts: 10
Joined: Sun Dec 20, 2009 12:01 am

Re: 850 - Crypt Kicker II

Post by Ivan Goroun » Sun Feb 06, 2011 8:42 am

Yeah, it's the spaces. Also, a line with as many spaces as letters should also be no solution.

Code: Select all

the_quick_brown_fox_jumps_over_the_lazy_dog

xxx xxxxx xxxxx xxx xxxxx xxxx xxx xxxx xxx
Output no solution.

Shafaet_du
Experienced poster
Posts: 147
Joined: Mon Jun 07, 2010 11:43 am
Location: University Of Dhaka,Bangladesh
Contact:

Re: 850 - Crypt Kicker II

Post by Shafaet_du » Mon May 09, 2011 4:44 pm

I line can be coverted to S= "the quick brown fox jumps over the lazy dog" if it satisfies following condition:

1. line.size()==S.size()
2. length of all words in line == length of all words in S(individually)
3. All 26 letters must be present and they all map to different characters.

Hope it will help

rafa4aquino
New poster
Posts: 1
Joined: Wed May 11, 2011 10:40 pm

Re: 850 - Crypt Kicker II

Post by rafa4aquino » Wed May 11, 2011 10:42 pm

I got WA anyone here can help me?

Code: Select all

Solved
input:

Code: Select all

1

vtz ud xnm xugm itr pyy jttk gmv xt otgm xt xnm puk ti xnm fprxq
xnm ceuob lrtzv ita hegfd tsmr xnm ypwqktj
frtjrpgguvj otvxmdxd prm iev prmvx xnmq
output:

Code: Select all

No solution.

Monty
New poster
Posts: 7
Joined: Fri Feb 17, 2012 10:24 am

Re: 850 - Crypt Kicker II

Post by Monty » Fri Feb 17, 2012 10:29 am

I am having a problem with this also. I tried every test case in this thread and I check out on all of them, however I am still getting WA. I can't think of any test cases where mine would produce a wrong output. Here is my code,

Code: Select all

import java.io.IOException;
import java.util.ArrayList;
import java.util.StringTokenizer;


public class Main
{
	public int anyout=0;
	static String ReadLn(int maxLength)
    {                            
     byte line[] = new byte [maxLength];
     int length = 0;
     int input = -1;
     try{
         while (length < maxLength){
             input = System.in.read();
             if ((input < 0) || (input == '\n')) break;
             line [length++] += input;
         }

         if ((input < 0) && (length == 0)) return null;
         return new String(line, 0, length);
     }catch (IOException e){
         return null;
     }
    }

    public static void main(String args[])  // entry point from OS
    {
     
     String in;
     Main w = new Main();
     int time=0;
     int numDa=0;
     ArrayList<String> words=new ArrayList<String>();
     while((in=Main.ReadLn(255))!=null)
     {
         StringTokenizer st = new StringTokenizer(in);
         if(time==0)
         {
         	numDa=Integer.parseInt(in.trim());
         }
         else if(time>1)
         {
        	 if(st.countTokens()==0)
        	 {
        		 if(words.size()>0)
        		 {
        			 w.doWork(words);
        			 numDa--;
        			 words.clear();
        		 }
        		 if(numDa==0)
        		 {
        			 System.exit(1);
        		 }
        	 }
        	 words.add(in.trim());
         }
         time++;
      }
    }
    public void doWork(ArrayList<String> words)
    {
    	boolean solution=false;
    	int[] fullLetterMapping=new int[26];
    	String sent="the quick brown fox jumps over the lazy dog";
    	for(int a=0;a<words.size();a++)//Track it down
    	{
    		if(words.get(a).length()==43)
    		{
    			//Do manual checks
    			
    			//Check for spacing consistency
    			if(words.get(a).charAt(3)==' '
	    		 &&words.get(a).charAt(9)==' '
	    		 &&words.get(a).charAt(15)==' '
	    		 &&words.get(a).charAt(19)==' '
	    		 &&words.get(a).charAt(25)==' '
	    		 &&words.get(a).charAt(30)==' '
	    		 &&words.get(a).charAt(34)==' '
	    		 &&words.get(a).charAt(39)==' ')
    			{
    				
    				char e=words.get(a).charAt(2);
    				
    				if(words.get(a).split(e+"").length==4&&words.get(a).charAt(28)==e
    		    	&&words.get(a).charAt(33)==e)
    		    	{
    					char o=words.get(a).charAt(12);
    					if(words.get(a).split(o+"").length==5&&words.get(a).charAt(17)==o
    			    	 &&words.get(a).charAt(26)==o
    			    	 &&words.get(a).charAt(41)==o)
    					{
    						char r=words.get(a).charAt(11);
        					if(words.get(a).split(r+"").length==3&&words.get(a).charAt(29)==r)
        					{
        						//Convinced it is the right one. Create full mapping.
        						for(int b=0;b<words.get(a).length();b++)
        						{
        							if(sent.charAt(b)!=' ')
        								fullLetterMapping[(int)words.get(a).charAt(b)-97]=(int)sent.charAt(b);
        						}
        						
        						//Double check if it really is
    							StringBuilder word=new StringBuilder(words.get(a));
   
    							for(int c=0;c<word.length();c++)
    				    		{
    				    			if(word.charAt(c)!=' ')
    				    				word.setCharAt(c,(char)fullLetterMapping[(int)word.charAt(c)-97]);
    				    		}
    				    		if(word.toString().equals(sent))//Checks out
    				    		{
    				    			solution=true;
    				    			break;
    				    		}
        					}
    					}
    		    	}
    			}
    		}
    	}
    	if(solution)
    	{
	    	for(int a=0;a<words.size();a++)
	    	{
	    		StringBuilder word=new StringBuilder(words.get(a));
	    		
	    		for(int b=0;b<word.length();b++)
	    		{
	    			if(word.charAt(b)!=' ')
	    				word.setCharAt(b,(char)fullLetterMapping[(int)word.charAt(b)-97]);
	    		}
	    		String w=word.toString();
	    		System.out.print(w);
	    	    if(a!=words.size()-1)
	    			System.out.println();
	    	    anyout=1;
	    	}
    	}
    	else
    	{
    		if(anyout==0)
    			System.out.print("No solution.");
    		else
    			System.out.print("\nNo solution.");
    		anyout=1;
    	}
    	System.out.println();
    }
}

Thanks

Post Reply

Return to “Volume 8 (800-899)”