554 - Caesar Cypher

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

Moderator: Board moderators

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 554 - Caesar Cypher

Post by brianfry713 » Tue Mar 11, 2014 10:19 pm

Try running your code on the sample input.
Check input and AC output for thousands of problems on uDebug!

jddantes
Learning poster
Posts: 73
Joined: Sat Mar 08, 2014 8:55 am

Re: 554 - Caesar Cypher

Post by jddantes » Wed Mar 12, 2014 2:01 pm

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

Code: Select all

HOUSE
GOOD
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.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 554 - Caesar Cypher

Post by brianfry713 » Wed Mar 12, 2014 8:43 pm

http://ideone.com/uuL69C
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!

jddantes
Learning poster
Posts: 73
Joined: Sat Mar 08, 2014 8:55 am

Re: 554 - Caesar Cypher

Post by jddantes » Thu Mar 13, 2014 5:38 pm

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.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 554 - Caesar Cypher

Post by brianfry713 » Thu Mar 13, 2014 8:34 pm

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!

jddantes
Learning poster
Posts: 73
Joined: Sat Mar 08, 2014 8:55 am

Re: 554 - Caesar Cypher

Post by jddantes » Thu Mar 13, 2014 10:05 pm

Alright, thanks again.

jddantes
Learning poster
Posts: 73
Joined: Sat Mar 08, 2014 8:55 am

Re: 554 - Caesar Cypher

Post by jddantes » Tue Apr 08, 2014 12:52 pm

I still have no clue why it results to a Runtime Error though.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 554 - Caesar Cypher

Post by brianfry713 » Tue Apr 08, 2014 9:02 pm

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.
Check input and AC output for thousands of problems on uDebug!

jddantes
Learning poster
Posts: 73
Joined: Sat Mar 08, 2014 8:55 am

Re: 554 - Caesar Cypher

Post by jddantes » Sun Aug 24, 2014 5:56 am

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

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 554 - Caesar Cypher

Post by brianfry713 » Thu Aug 28, 2014 12:39 am

Try this input from this thread:

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
AC output:

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!

jddantes
Learning poster
Posts: 73
Joined: Sat Mar 08, 2014 8:55 am

Re: 554 - Caesar Cypher

Post by jddantes » Tue Sep 30, 2014 12:14 am

Okay thanks. Turns out I misunderstood the problem; I thought the whole decrypted text should not exceed 60 characters. :)

metaphysis
Experienced poster
Posts: 139
Joined: Wed May 18, 2011 3:04 pm

Re: 554 - Caesar Cypher

Post by metaphysis » Tue Feb 21, 2017 3:42 pm

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.

metaphysis
Experienced poster
Posts: 139
Joined: Wed May 18, 2011 3:04 pm

Re: 554 - Caesar Cypher

Post by metaphysis » Wed Feb 22, 2017 5:20 am

There are so many ads, please administrator clear it all!

Post Reply

Return to “Volume 5 (500-599)”