850 - Crypt Kicker II

[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

[alirezanoori]

Thanks in advance. Now i got AC!

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

[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??

[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

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

[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.

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

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

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

[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!

[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.

[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

[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.

[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