0

I have the following C++ Program:

//============================================================================
// Name        :
// Author      : Bryce Sandlund
// Version     :
// Copyright   :
// Description : Code skeleton
//============================================================================

#include <iostream>
#include <iomanip>
#include <set>
#include <vector>
#include <algorithm>
#include <cmath>
#include <complex>
#include <cstdlib>
#include <sstream>
#include <list>
#include <map>
#include <fstream>
#include <string>
#include <time.h>
#include <queue>
#include <tuple>
#include <functional>
#include <unordered_set>
#include <unordered_map>

#define INF 1000000000
#define all(c) (c).begin(),(c).end()
#define tr(c,i) for(typeof((c).begin()) i = (c).begin(); i != (c).end(); ++i)
#define EP .00001

using namespace std;

typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<bool> vb;
typedef vector<vi> vvi;
typedef vector<vb> vvb;
typedef vector<ii> vii;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef long long LL;

vvi adjList;
unordered_map<string, int> targs;

int add(string &s)
{
    if (targs.count(s))
        return targs[s];

    targs[s] = targs.size();
    adjList.push_back(vi());
    return targs.size()-1;
}

void connect(int si, int ti)
{
    if (si == ti)
        return;

    for (int i = 0; i < adjList[si].size(); ++i)
    {
        if (adjList[si][i] == ti)
            return;
    }

    adjList[si].push_back(ti);
}

vi bfs(int s)
{
    queue<ii> q;
    q.push(ii(s, -1));

    vi dist(adjList.size(), INF);

    while (!q.empty())
    {
        int top = q.front().first;
        int hops = q.front().second;
        q.pop();
        if (dist[top] != INF)
            continue;

        dist[top] = hops;
        for (int i = 0; i < adjList[top].size(); ++i)
        {
            q.push(ii(adjList[top][i], hops+1));
        }
    }

    return dist;
}

int main() {
    int caseNum = 1;
    cout << "Case " << caseNum << ":" << endl;
    string line;
    while (getline(cin, line))
    {
        stringstream ss(line);

        string command;
        ss >> command;
        if (command == "add")
        {
            string s, t;
            ss >> s;

            int si = add(s);
            if (ss >> t)
            {
                int ti = add(t);

                connect(si, ti);
                connect(ti, si);
            }
        }
        else if (command == "connections")
        {
            string s;
            ss >> s;

            if (!targs.count(s))
            {
                cout << "target does not exist" << endl;
                continue;
            }

            int st = targs[s];
            if (adjList[st].empty())
            {
                cout << "no connections" << endl;
            }
            else
            {
                vi dist = bfs(st);

                vi away(adjList.size(), 0);
                int maxd = -1;
                for (int i = 0; i < dist.size(); ++i)
                {
                    if (dist[i] == INF || dist[i] == -1)
                        continue;

                    ++away[dist[i]];
                    maxd = max(maxd, dist[i]);
                }

                for (int i = 0; i <= maxd; ++i)
                {
                    cout << i << ": " << away[i] << endl;
                }
            }
        }
        else if (command == "associated")
        {
            string s, t;
            ss >> s >> t;

            if (!targs.count(s) || !targs.count(t))
            {
                cout << "target does not exist" << endl;
                continue;
            }

            int si = targs[s], ti = targs[t];
            vi dist = bfs(si);

            if (dist[ti] == INF)
            {
                cout << "no" << endl;
            }
            else
            {
                cout << "yes " << dist[ti] << endl;
            }
        }
        else
        {
            adjList.clear();
            targs.clear();
            cout << "----------" << endl;
            cout << "Case " << ++caseNum << ":" << endl;
        }
    }

    cout << "----------" << endl;
    return 0;
}

I am using this as input:

add a b
add a c
add b d
add e b
add c f
add c g
add f h
add h i
add j k
associated a i
associated i a
associated f k
associated a h
connections a
connections i
add k g
associated a j
connections a
add h a
connections a
associated a h
add m
add n n
connections n
add a n
connections n

In Visual C++, the code produces this output (it does so on Debug or Release):

Case 1:
yes: 3
yes: 3
no
yes: 2
0: 2
1: 4
2: 1
3: 1
0: 1
1: 1
2: 1
3: 2
4: 1
5: 2
yes: 3
0: 2
1: 4
2: 2
3: 2
0: 3
1: 5
2: 1
3: 1
yes: 0
no connections
0: 1
1: 3
2: 5
3: 1
4: 1
----------

On gcc g++, it produces this output:

Case 1:
no
no
yes 0
no
0: 2
1: 2
2: 2
3: 1
0: 1
no
0: 2
1: 2
2: 2
3: 1
0: 3
1: 2
2: 2
3: 1
yes 0
----------

For reference, I am trying to solve this problem: https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&category=620&page=show_problem&problem=4574.

Any ideas why the input and output would be different on the different compilers? I don't believe I am using any undefined behavior.

Bryce Sandlund
  • 487
  • 2
  • 5
  • 17
  • 1
    You need a debugging strategy for this, e.g. add some code to dump internal state to a log file, then run the code on both compilers and compare the log files so that you can identify (or at least narrow down) where the discrepancy is coming from. Repeat until you've identified the problem. – Paul R Sep 10 '14 at 14:54
  • 1
    The concept of meaningful variable names is important. http://stackoverflow.com/questions/203618/how-to-name-variables – Yochai Timmer Sep 10 '14 at 14:55
  • The interesting part is VS us producing correct output. In an out of bounds situation, wouldn't we expect garbage? – Bryce Sandlund Sep 10 '14 at 15:17
  • My variable names are short because this is competition code, not software engineering design. I understand every variable name – Bryce Sandlund Sep 10 '14 at 15:18
  • Oops, sorry, previous comment was wrong. There's an out of range condition in line 173. – n. m. could be an AI Sep 10 '14 at 15:35

1 Answers1

1

The cause of the differences in the behavior of the code in the two platforms is the add function. You have:

int add(string &s)
{
    if (targs.count(s))
        return targs[s];

    targs[s] = targs.size();
    adjList.push_back(vi());
    return targs.size()-1;
}

In that function, the problematic line is:

    targs[s] = targs.size();

The line is tricky because depending on which side of the assignment operator gets evaluated first, you get different behavior. Please note that targs[s] involves a function call that changes the object.

You can change the function a little bit to make it consistent and predictable across platforms.

int add(string &s)
{
    if (targs.count(s))
        return targs[s];

    int size = targs.size();
    targs[s] = size;
    adjList.push_back(vi());
    return size;
}
R Sahu
  • 204,454
  • 14
  • 159
  • 270