Strange program behavior

Question

So I wanted to write code which solves this problem: "Collecting Beepers" And I did:

int rec(int current, int beers)
{
    if(beers == (1 << (numOfBeers + 1)) - 1) return cost(beerX[0], beerY[0], beerX[current], beerY[current]);
    int optimal = 100000;
    for(int i = 1; i <= numOfBeers; ++i)
    {
        if(((1 << i) & beers) == 0)
        {
            int newBeersSet = (1 << i) | beers;
            int c = cost(beerX[current], beerY[current], beerX[i], beerY[i]);
            int current = c + rec(i, newBeersSet);
            optimal = min(optimal, current);
        }
    }
    return optimal;
}

The strange thing is, that when I replace the part

int c = cost(beerX[current], beerY[current], beerX[i], beerY[i]);
int current = c + rec(i, newBeersSet);

with

int current = cost(beerX[current], beerY[current], beerX[i], beerY[i]) + rec(i, newBeersSet);

the logic is absolutely the same and yet my program crashes on the same (the one given in the problem desciption) input and the online judge gives wrong answer as a result from the program execution while with the original code it gives Accepted. Any ideas what could possibly be wrong?

Have you verified that cost is still being called before rec? — Scott Hunter
– Scott Hunter, Commented Dec 29, 2014 at 23:15

Ole Dittmann · Accepted Answer · 2014-12-29 23:30:07Z

2

That is propably because your variable "current" is overriden. Try:

int current2 = cost(beerX[current], beerY[current], beerX[i], beerY[i]) + rec(i, newBeersSet);
optimal = min(optimal, current2);

edited Dec 29, 2014 at 23:30

answered Dec 29, 2014 at 23:22

Ole Dittmann

1,7841 gold badge14 silver badges22 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

M.M · Accepted Answer · 2014-12-29 23:28:35Z

2

In this line you are using an uninitialized variable:

int current = cost(beerX[current],  // ...

This declares a new variable current and then, before the variable has had a value assigned, uses it as index to beerX.

You probably meant:

int new_current = cost(beerX[current],  // ...

which uses the existing current variable which was declared in the parameter list for the rec function.

answered Dec 29, 2014 at 23:28

M.M

143k26 gold badges223 silver badges400 bronze badges

Collectives™ on Stack Overflow

Strange program behavior

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related