554 - Caesar Cypher
Moderator: Board moderators
-
- Guru
- Posts: 5947
- Joined: Thu Sep 01, 2011 9:09 am
- Location: San Jose, CA, USA
Re: 554 - Caesar Cypher
Try running your code on the sample input.
Check input and AC output for thousands of problems on uDebug!
Re: 554 - Caesar Cypher
Yes, I've tried it.
I've noticed though, that if I use fgets with redirection (e.g. ./a.out <554.txt) strlen would give a result with an extra two letters.
For example
Here, HOUSE would have a length of 7. Is this because fgets appends another newline aside from the one it reads from the file?
When I don't use redirection (i.e. I type the words manually) I get a length of 6.
I've noticed though, that if I use fgets with redirection (e.g. ./a.out <554.txt) strlen would give a result with an extra two letters.
For example
Code: Select all
HOUSE
GOOD
When I don't use redirection (i.e. I type the words manually) I get a length of 6.
-
- Guru
- Posts: 5947
- Joined: Thu Sep 01, 2011 9:09 am
- Location: San Jose, CA, USA
Re: 554 - Caesar Cypher
http://ideone.com/uuL69C
fgets includes the newline chars. Maybe you are using DOS newlines "\r\n" instead of UNIX newlines "\n".
fgets includes the newline chars. Maybe you are using DOS newlines "\r\n" instead of UNIX newlines "\n".
Check input and AC output for thousands of problems on uDebug!
Re: 554 - Caesar Cypher
Oh okay thanks. Could this be from copypasting from the forums? If not, by any chance will it be the file format (.txt or no extension at all)? I'm developing on a Windows PC.
-
- Guru
- Posts: 5947
- Joined: Thu Sep 01, 2011 9:09 am
- Location: San Jose, CA, USA
Re: 554 - Caesar Cypher
If you're on a Windows PC your newlines will probably be "\r\n" once it's saved in a text file. It should be straightforward to write a program to convert to UNIX "\n" newlines if you want. In UNIX you can use the built-in dos2unix and unix2dos commands. If you're typing it in manually then it probably depends on your IDE. If you're using fgets you could try writing your code to handle both types of newlines.
Check input and AC output for thousands of problems on uDebug!
Re: 554 - Caesar Cypher
Alright, thanks again.
Re: 554 - Caesar Cypher
I still have no clue why it results to a Runtime Error though.
-
- Guru
- Posts: 5947
- Joined: Thu Sep 01, 2011 9:09 am
- Location: San Jose, CA, USA
Re: 554 - Caesar Cypher
Run your code on the sample input. Insert debug print statements that check if you're only calling free on the same memory addresses that have been returned from malloc.
If you can't figure it out post your updated code that works on the sample input.
You could use static memory allocation instead of dynamic since the lengths of the strings are in the problem statement.
If you can't figure it out post your updated code that works on the sample input.
You could use static memory allocation instead of dynamic since the lengths of the strings are in the problem statement.
Check input and AC output for thousands of problems on uDebug!
Re: 554 - Caesar Cypher
I used STL containers, got WA this time. Any sample input? Or is this really about spaces/length of the string, as discussed before?
Code: Select all
#include <cstdio>
#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <utility>
using namespace std;
int main(){
char buff[2000];
set<string> dictionary;
map<int, set<string> > mymap; // Num known, string
while(fgets(buff, 2000, stdin)!=NULL){
if(buff[0] == '#'){
break;
}
string word = buff;
word.pop_back();
dictionary.insert(word);
}
fgets(buff, 2000, stdin);
string encrypted = buff;
//printf("%s", buff);
encrypted.pop_back();
// cout<<"Encrypted text:"<<encrypted<<endl;
for(int k = 0; k<27; k++){
string decrypted = encrypted;
for(int x = 0; x<encrypted.size(); x++){
int index;
if(encrypted[x] == ' '){
index = 0;
} else {
index = encrypted[x] -'A' + 1;
}
int newIndex = (index+k)%27;
if(!newIndex){
decrypted[x] = ' ';
} else {
decrypted[x] = 'A' + newIndex - 1;
}
//printf("%d %d : ", index, newIndex);
//printf("%c->%c\n", encrypted[x], decrypted[x]);
}
// cout << k << ":" << decrypted << endl;
// Count number of registered words
int cnt = 0;
istringstream iss(decrypted);
string word;
string trimmedString;
//cout << "Decrypted: "<< decrypted<<endl;
int e = 0;
while(iss>>word){
//cout <<"Got word:"<< word << endl;
e++;
if(e>1){
trimmedString.append(" "+word);
//printf("Appending: ");
// cout << word << endl;
} else {
trimmedString.append(word);
//cout<< "Stariting: " << word << endl;
}
if(dictionary.count(word)){
//cout << "[+] "<< word << endl;
cnt++;
}
if(iss.eof()){
break;
}
}
// int len = trimmedString.size();
// cout <<"Trimmed:"<< trimmedString << endl << endl;
mymap[cnt].insert(trimmedString);
}
/* for(map<int, set<string> >::reverse_iterator itr = mymap.rbegin(); itr!=mymap.rend(); itr++){
int numRecog = itr->first;
set<string> strings = itr->second;
cout << numRecog << endl;
for(set<string>::iterator it = strings.begin(); it!=strings.end(); it++ ){
printf("(%d) ", (*it).size());
cout << *it << endl;
}
}*/
int maxCnt = mymap.rbegin() -> first;
//printf("Max number of recognized words: %d\n", maxCnt);
string finalAns;
if(mymap[maxCnt].size() ){ // Get maxlen
string ans;
set<string> myset = mymap[maxCnt];
int maxlen = 0;
for(set<string>::iterator itr = myset.begin(); itr!=myset.end(); itr++){
int len = (*itr).size();
if(len>maxlen && len < 61){
maxlen = len;
ans = *itr;
}
}
finalAns = ans;
}
if(finalAns.size() == 0){
finalAns = encrypted;
}
cout << finalAns << endl;
return 0;
}
-
- Guru
- Posts: 5947
- Joined: Thu Sep 01, 2011 9:09 am
- Location: San Jose, CA, USA
Re: 554 - Caesar Cypher
Try this input from this thread:AC output:
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
Code: Select all
PIGLET LIVED IN A VERY GRAND HOUSE IN THE MIDDLE OF A BEECH
TREE AND THE BEECH TREE WAS IN THE MIDDLE OF THE FOREST AND
PIGLET LIVED IN
THEMIDDLEOFTHEHOUSENEXTTOHISHOUSEWASAPIECEOFBROKENBOARDWHICH
HAD TRESPASSERS W ON IT
Check input and AC output for thousands of problems on uDebug!
Re: 554 - Caesar Cypher
Okay thanks. Turns out I misunderstood the problem; I thought the whole decrypted text should not exceed 60 characters. ![:)](./images/smilies/icon_smile.gif)
![:)](./images/smilies/icon_smile.gif)
-
- Experienced poster
- Posts: 139
- Joined: Wed May 18, 2011 3:04 pm
Re: 554 - Caesar Cypher
The output specification is not so clear.
You should print a '\n' at end of EVERY line of output even the last line.
I didn't print a '\n' at last line that brings to me many WAs.
You should print a '\n' at end of EVERY line of output even the last line.
I didn't print a '\n' at last line that brings to me many WAs.
metaphysis: http://uhunt.onlinejudge.org/id/95895
My solutions for UVa problems: https://github.com/metaphysis/Code.
My solutions for UVa problems: https://github.com/metaphysis/Code.
-
- Experienced poster
- Posts: 139
- Joined: Wed May 18, 2011 3:04 pm
Re: 554 - Caesar Cypher
There are so many ads, please administrator clear it all!
metaphysis: http://uhunt.onlinejudge.org/id/95895
My solutions for UVa problems: https://github.com/metaphysis/Code.
My solutions for UVa problems: https://github.com/metaphysis/Code.