Page 4 of 6

Re: 850 - Crypt Kicker II

Posted: Mon Jan 19, 2009 2:55 pm
by newkid
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

Re: 850 - Crypt Kicker II

Posted: Fri Jan 23, 2009 4:25 pm
by alirezanoori
Thanks in advance. Now i got AC!

Re: 850 - Crypt Kicker II

Posted: Sun Jan 25, 2009 7:43 am
by aprimadi1
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;
}

Re: 850 - Crypt Kicker II

Posted: Wed Apr 08, 2009 6:20 am
by gautamverma
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??

Re: 850 - Crypt Kicker II

Posted: Sat Apr 11, 2009 5:52 am
by rator10
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

Re: 850 - Crypt Kicker II

Posted: Wed Apr 22, 2009 4:30 pm
by corns
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;
}



Re: 850 - Crypt Kicker II

Posted: Fri Jul 24, 2009 5:52 pm
by Igor9669
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.

WA! Please help.

Posted: Mon Sep 07, 2009 7:57 am
by abhiramn
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;
}

Re: 850 - Crypt Kicker II

Posted: Thu Nov 19, 2009 7:26 am
by talizmelf
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;

Re: 850 - Crypt Kicker II

Posted: Fri Dec 11, 2009 6:42 am
by buiutripa
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;
}

Re: 850 - Crypt Kicker II

Posted: Tue Jul 27, 2010 6:54 pm
by valkov
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!

Re: 850 - Crypt Kicker II

Posted: Sun Feb 06, 2011 8:42 am
by Ivan Goroun
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.

Re: 850 - Crypt Kicker II

Posted: Mon May 09, 2011 4:44 pm
by Shafaet_du
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

Re: 850 - Crypt Kicker II

Posted: Wed May 11, 2011 10:42 pm
by rafa4aquino
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.

Re: 850 - Crypt Kicker II

Posted: Fri Feb 17, 2012 10:29 am
by Monty
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