What caused a difference in output?

Question

I was solving this problem on CodinGame.com and I managed to write a code that passed the system test for the last test case (a very large test case). But compiling on my laptop I get an output of 0 instead of 57330892800 which the code gave me from their machine. I compiled with both Visual Studio 2012 Express and Dev C++ 4.9.9.2.

I used a recursive function so if I had ran out of stack memory, I'd expected a stack overflow error but there was no error, nothing, just an output of 0. Why is this happening on my system while it worked just fine on the site's machine? What could have caused this, cos I doubt it is stack overflow?

#include<iostream>
#include<algorithm>
#include<stack>
#include<string>
#include<map>
#include<set>
#include<vector>

using namespace std;
typedef long long LONG;


string X[]={".-","-...","-.-.","-..",
            ".","..-.","--.","....",
            "..",".---","-.-",".-..",
            "--","-.","---",".--.",
            "--.-",".-.","...","-",
            "..-","...-",".--","-..-",
            "-.--","--.."};
map<string, int> dict;

string morse(const string ret){
        string s;
        for(char c : ret) s+=X[c-'A'];
        return s;
}

LONG decode(int start, string &word, vector<LONG> &mem){
        if(start == word.size()) return 1;
        else if(mem[start] != -1) return mem[start];

        LONG res = 0;
        string s;
        for(int i=0; i<19*4 && start+i<word.size(); i++){
                s+=word[start+i];
                auto curr = dict.find(s);
                if(curr!=dict.end()) res+=curr->second*decode(start+i+1, word, mem);
        }
        mem[start]=res;
        return res;
}

int main(){
        string word;
        cin>>word;
        int n; cin>>n;
        for(int i=0; i<n; i++){
                string s;
                cin>>s;
                dict[morse(s)]++;
        }
        vector<LONG> mem(word.size(), -1);
        cout<<decode(0, word, mem)<<endl;
}

Answer 1

I think that I have managed to strip your code down to a minimal program:

#include<iostream>
#include<string>

using namespace std;

int main(){
        string word;
        cin>>word; // or getline(cin, word);
        cout << word.size() << endl;
}

Results with your test-case input file:

• On Codingame (with test=4), it prints 9884 (as expected).
• On my personal computer, after compiling the source file into a binary named "prog", from a terminal command-line (console):
  1. If I run ./prog then copy-paste the text from the file into the console, it prints 4095 (bad).
  2. If I run ./prog < Test_4_input.txt instead, then it prints 9884 (good).

I assume that you did the equivalent of 1. (launch the program from your IDE and paste the text into its "Console" tab) whereas Codingame "works like" 2. and thus you got the problem described here: Linux terminal input: reading user input from terminal truncating lines at 4095 character limit (the read buffer seems to have a size limit of 4096 bytes (and uses the last one for a newline character, hence the truncation at 4095)).

---

Edit: As for how I found it out:

Like you, I had begun with running the program in an IDE (Eclipse) and copy-pasting the file contents into the embedded input console, and I was also getting 0 as a result. So I started tweaking the code and debugging it in the IDE.

I first added a global counter (initialized to 0) incremented on the first line of decode and printed at the end of main, to see how many times the function was called. Its final value was 1254 on Codingame but only 541 in my IDE.
So I set a conditional breakpoint in decode just after the increment (condition: counter == 541), launched the debugger and stepped in the code, and saw that the loop was terminating early. I then watched the local variables, and I noticed that word had a size of 4095. I found it "funny" because it's 4096 minus 1 and 4096 is a power of two; you know, like when you see 255.
So I opened a text editor and copy-pasted only the first line of the input file, and saw that its length wasn't 4095 but 9884. Now I was starting to sense the issue. So I stripped the code down to the minimal test case shown above, then switched to a command-line terminal to check (having seen that Codingame shows a Bash test script using solution < in$test.txt), and searched the web a bit to find some references to similar problems (like the linked question above). "Puzzle solved."

Hopefully that will help you to solve your future problems by yourself :)

Answer 2

I think in your case, start ==0 and mem[start] == 0 and so decode is returning 0 the first time it is called.

Put the following two lines at the beginning of decode function to check if that is the case:

cout << start;
if(mem[start] != -1) return mem[start];