554 - Caesar Cypher

[dongyf]

Can anyone tell me why this code got WA.
Anything helpful on the problem will be appreciate.

@BEGIN_OF_SOURCE_CODE
#include <iostream>
#include <strstream>
#include <cstring>
#include <cctype>
using namespace std;

char dic[200][30];
int len;
char cipher[300], message[300];
int match, best;

void readDic()
{
char word[30];
len = 0;
cin.getline(word, sizeof(word));
while (word[0] != '#') {
strcpy(dic[len], word);
len++;

cin.getline(word, sizeof(word));
}
}

bool find(char* word)
{
for (int i = 0; i < len; i++)
if (strcmp(dic, word) == 0)
return true;

return false;
}

int toInt(char ch)
{
if (ch == ' ')
return 0;
else
return ch - 'A' + 1;
}

char toChar(int i)
{
if (i == 0)
return ' ';
else
return i - 1 + 'A';

}

void decrypt(int k)
{
for (int i = 0; i < strlen(cipher); i++) {
int x = toInt(cipher);
x = (x + k) % 27;
message = toChar(x);
}
message[strlen(cipher)] = '\0';
}

void solve()
{
best = 0;
match = 0;
for (int k = 1; k <= 26; k++) {
decrypt(k);

istrstream is(message);
char word[300];
int cnt = 0;
while (is >> word)
if (find(word))
cnt++;

if (cnt > match) {
match = cnt;
best = k;
}
}

decrypt(best);

if (strlen(message) > 60) {
int i = 60;
while (i >= 0 && isupper(message))
i--;
if (i >= 0)
message = '\0';
else
message[0] = '\0';
}

cout << message << endl;
}

void main()
{
readDic();

cin.getline(cipher, sizeof(cipher));
while (!cin.eof()) {
solve();
cin.getline(cipher, sizeof(cipher));

}
}
@END_OF_SOURCE_CODE

[donny]

firstly, i think you need to format the output
i also need some help...
i keep getting presentation error, can't seem to
get rid of it i think i have handled the word warping..
is there any trick to the output?

[dongyf]

Can you tell me what's your output for the following data
@BEGIN_OF_TEST_CASE
THANK
YOU
FOR
YOUR
HELP
#
ABCDEFGHIJ
ABCDEFGHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJ
ABCDEFGHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJ BCDEFGHIJA
@END_OF_TEST_CASE

[donny]

I get:
ABCDEFGHI

the program only takes in one line as the input.

[obayashi]

and here's my code...
why wa?

[cpp]
#include <iostream>
#include <string.h>
char dict[100][30],str[300],d[27];
int n,map[128];
void init () {
char ch;
for (ch='A';ch<='Z';ch++)
map[ch] = ch-'A'+1;
map[' '] = 0;
for (ch='A';ch<='Z';ch++)
d[ch-'A'+1] = ch;
d[0] = ' ';
}
int search (char s[]) {
for (int i=0;i<n;i++)
if (strcmp(s,dict)==0)
return 1;
return 0;
}
void decrypt () {
int i,k,l,len,maxlen,maxmatch,match;
char tmp[300],bak[300],ok[300],*p;
maxlen = maxmatch = 0;
for (k=0;k<=26;k++) {
strcpy(tmp,str);
l = strlen(tmp);
for (i=0;i<l;i++) {
tmp = d[(map[tmp]+k)%27];
}
l--;
while (tmp[l]==' ') l--;
tmp[l+1] = '\0';
strcpy(bak,tmp);
len = l+1;
match = 0;
p = strtok(tmp," \t\b\r\n");
while (p) {
if (search(p))
match++;
p = strtok(NULL," \t\b\r\n");
}
if (match>maxmatch) {
maxlen = len;
maxmatch = match;
strcpy(ok,bak);
} else if (match==maxmatch) {
if (len>maxlen) {
maxlen = len;
strcpy(ok,bak);
}
}
}
maxlen = maxlen>60?60:maxlen;
for (i=0;i<maxlen;i++)
cout<<ok;
cout<<endl;
}
int main () {
init();
while (cin>>str) {
n = 0;
while (str[0]!='#') {
strcpy(dict[n++],str);
cin>>str;
}
cin.getline(str,1);
cin.getline(str,299);
decrypt();
}
return 0;
}

[/cpp]

[arc16]

since your program crash my VC6 you can try this input by yourself and tell me the output of your program.

Code: Select all

HOUSE
GOOD
NOW
THING
THIS
PIGLET
MEN
TREE
BUT
WAS
AID
IN
THE
IS
IT
OTHER
BEECH
ALL
VERY
AND
FOREST
COME
OF
GRAND
ON
TRESPASSERS
FOR
PARTY
TIME
TO
MIDDLE
LIVED
THAT
THEMIDDLEOFTHEHOUSEN
HAD
#
BVTYRFMYVHRQMV MNMHRDKMTDN QMUAGERMV MFURMZVQQYRMASMNMORRPUMFDRRMN QMFURMORRPUMFDRRMINEMV MFURMZVQQYRMASMFURMSADREFMN QMBVTYRFMYVHRQMV MFURZVQQYRASFURUAGER RJFFAUVEUAGERINENBVRPRASODAXR OANDQIUVPUMUNQMFDREBNEERDEMIMA MVFM

btw, i still getting PE myself

[obayashi]

i got AC (not PE).

there's a trick.

if your output have linewraps, you should omit leading blanks in the following line.

[cpp]

eg.

bla bla XXXX...XXXXXX bla bla bla <-- then linewrap
bla bla ... <-- the following line may has leading blanks, just leave out the blanks

like this

bla bla XXXX...XXXXXX bla bla bla <-- then linewrap
bla ... <-- no leading blanks
[/cpp]

[Chok]

Hello all,
I've got WA several times for the Problem 554 - Caesar Cypher. Here is my code. Plz someone help me to find out my error.Wht i miss ????? Thanks in advance.

Code: Select all

#include<stdio.h>
#include<string.h>
#include<stdlib.h>

#define MAX 100
#define MAX_S 255

char dic[MAX][30];
int n;


int find_word(char *item)
{
	int i;
	for(i=0;i<n;i++)
		if(strcmp(dic[i],item)==0)
			return 1;
	return 0;
}


int main()
{
	char buf[MAX_S],word[MAX_S],sen[MAX_S],res[MAX_S];
	int i,len,k,pos,w,s,cnt,max;
	n=0;
//	freopen("554.in","r",stdin);
	//freopen("554.out","w",stdout);
	while(1)
	{
		gets(buf);
		if(strcmp(buf,"#")==0)
			break;
		strcpy(dic[n++],buf);
	}
	while(gets(buf))
	{
		len=strlen(buf);
		if(!len)
			continue;
		int pp;
		max=-1;
		strcpy(res,buf);
		for(k=1;k<=26;k++)
		{
			w=s=cnt=0;
			for(i=0;i<len;i++)
			{
				if(buf[i]==' ')
					pos=0;
				else
					pos=buf[i]-'A'+1;
				pos=(pos+k)%27;
				if(!pos)
				{
					word[w]='\0';
					sen[s++]=' ';
					if(find_word(word))
						cnt++;
					w=0;
					word[w]='\0';
				}
				else
				{
					word[w++]='A'+pos-1;
					sen[s++]='A'+pos-1;
				}
			}
			word[w]='\0';
			sen[s]='\0';
			if(find_word(word))
				cnt++;
			if(max<cnt)
			{
				max=cnt;
				strcpy(res,sen);
				pp=k;
			}
		}
		puts(res);
		//printf("%d\n",pp);
	}
	return 0;
}

[marthapfhui]

I am getting number of PEs. I have tried to skip the line full of spaces, removing the leading spaces, removing the trailing space, etc.

What's the trick? Any example? Thanks.

[jurajz]

Thank's to obayashi for post. I had many PEs, with this hint I have AC.

I am getting number of PEs. I have tried to skip the line full of spaces, removing the leading spaces, removing the trailing space, etc.

What's the trick? Any example? Thanks.

I don't assume leading spaces in the output, only trailing. I used this method:

- first, I deleted all trailing spaces in output_string
- if length of output_string is 60 or less than 60, write whole string
- if length of output_string is 61 or more, then i:=61 and decrement i, until output_string is not a space (I assumed, that in the this part of output_string is least 1 character, that is not a space)
- string to write is from first to (i-1)-th character, but it is needful delete all trailing spaces from this part-string
- write this part-string
- delete this part-string (included previous trailing spaces) from output_string
- if length of output_string is <=60, write it, if length of output_string is still 61 and more, process recursively method described above

[krap]

Hello there,

I've come to a solution on the Ceasar's Cypher Problem and I keep getting WAs. I took care of the litle trick you guys mentioned so now in my solution, when there are linewraps I omit the leading blanks and in each line the 61st character is being wrapped. The 60th of each line is being printed weather it is a blank or something else. I get the right output for the proposed input in the problem's page (the one that the problemset provides) so I would like to ask wheather there is a particular "tricky" input that I should try.

Thanks in advance guys,

[Moha]

I followed the jurajz's hint and I got it. So according to jurajz`s instructions, we can reason this problem's judge-data is not correct. Because why we should eliminate trailing spaces? problem statement says we should divide the output into some lines which no one of them should be bigger than 60 characters. We we erase the trailing spaces it means, we are erase the output because the output has characters which deciphered into space and this elimination is ignoring them. Unfortunately we have such these problems in some of the UVa`s problems.

[krap]

I believe my code is working according what he said too. But I'll check again just in case. Thank you for your contribution!

[fryzito]

thank for their help I get AC with your help.

[jddantes]

I'm getting Runtime Error on mine:

Code: Select all

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <ctype.h>

#define SAFE printf("Safe\n");
char * shift(char * str, int k)
{
    char * decoded = (char *)malloc(251);
    int i;
    strcpy(decoded, str);

    for(i=0; decoded[i]; i++)
    {
        int num;
        if(isalpha(decoded[i]))
        {
            num = decoded[i] - 'A' + 1;
        }
        else
        {
            num = 0;
        }

        num+=k;
        if(num>26)
            num-=27;

        if(!num)
        {
            decoded[i] = ' ';
        }
        else
        {
            decoded[i]  = num + 'A' - 1;
        }


    }
    decoded[i] = 0;

    return decoded;
}

int countWords(char ** dictionary, char *str)
{
    int count = 0;
    char word[21];

    FILE * stream = fmemopen(str,strlen(str),"r");

    while(fscanf(stream, "%s",word)>0)
    {

        int i = 0;
        for(i; dictionary[i]; i++)
        {
            if(!strcmp(word,dictionary[i]))
            {
                //printf("%s matches %s in the dictionary!\n",word,dictionary[i]);
                count++;
                continue;
            }
            else
            {
                //printf("%s does not match %s in the dictionary\n",word,dictionary[i]);
            }
        }
    }
    fclose(stream);
    return count;
}

int main()
{
    char  ** dictionary = (char **)malloc(100);
    memset(dictionary,0,100);
    int i = 0;
    while(1)
    {
        char * word = (char *)malloc(22);
        //scanf("%s",word);
        fgets(word, 22, stdin);
        word[strlen(word)-1] = 0;
        if(strcmp(word,"#"))
        {
            dictionary[i] = word;
            i++;
        }
        else
        {
            break;
        }
    }

    /*

    dictionary input end

    */

    char message[252];
    fgets(message, 252, stdin);
    message[strlen(message) - 1] = 0;

    char ** decoded_strings = (char **)malloc(27);
    int k;

    int match_count[27];

    int max = 0;
    int max_words = 0;
    int index = 0;
    for(k=0; k<27; k++)
    {
        decoded_strings[k] = (char *)malloc(251);
        decoded_strings[k] = shift(message,k);
        match_count[k] = countWords(dictionary,decoded_strings[k]);

        if(match_count[k]>max)
        {
            max = match_count[k];
            max_words = 1;
            index = k;
        }
        else if(match_count[k] == max)
        {
            max_words++;
        }
    }



    if(max_words>1)
    {
        int i;
        int maxlen = 0;
        int ndex = 0;
        for(i=0; i<27; i++)
        {

            if(match_count[i] == max)
            {
                int len = strlen(decoded_strings[i]);
                if(len>maxlen)
                {
                    maxlen = len;
                    ndex = i;
                }
            }
        }

        printf("%s\n",decoded_strings[ndex]);
    }
    else if(max_words == 1)
    {
        printf("%s\n",decoded_strings[index]);
    }
    /*
    printf("Dictionary:\n");
    for(i=0; dictionary[i]; i++)
    {
        printf("%s\n",dictionary[i]);
    }

    printf("Decoded strings:\n");
    for(k=0; k<27; k++)
    {
        printf("%d %s %d\n",k,decoded_strings[k], countWords(dictionary,decoded_strings[k]));
    }*/



    //printf("Safe\n");

    /*

    end

    */


    /*
        free
    */

    // free dictionary
    for(i=0; dictionary[i]; i++)
    {
        free(dictionary[i]);
    }
    free(dictionary);
    //printf("Freed dictionary\n");
    //free decoded strings

    for(i=0; decoded_strings[i]; i++)
    {
        free(decoded_strings[i]);
    }
    //printf("Freed decoded words\n");
    //free(decoded_strings);
    return 0;
}