why is my algorithm returning stackoverflow exception?

Question

I have to do an algorithm that fills a bi-dimensional array with random (between 0 and 2) numbers, the only condition is that I can have the same number 3 or more times horizontally and vertically. For example

[0,0,1,2,1
 0,1,2,1,2
 1,2,0,1,0]

is ok

[0,0,0,2,1
 0,1,2,1,2
 1,2,0,1,0]

or

[0,0,1,2,1
 0,1,1,1,2
 1,2,1,1,0]

is wrong.

So here is my algorithm:

public class CandyHelper {

    private final int minimumChainLength = 3;
    private final int searchChainSize    = 3;

    public Candy[][] randomInit(int rowCount, int columnCount) {
        Candy[][] map = new Candy[rowCount][columnCount];
        for (int row = 0; row < rowCount; ++row) {
            for (int column = 0; column < columnCount; ++column) {
                // Fill square with random candy.
                Random rand = new Random();
                int value = rand.nextInt(3);
                Candy candy = new Candy();
                candy.setType(value);
                map[row][column] = candy;
            }
        }

        if (findHint(map)) {
            //System.out.println("Winning conditions");
            map = null;
            map = randomInit(rowCount, columnCount);          
        } else {
            System.out.println("no wining");
        }

        return map;
    }

    // Function which searches for match of at least `MinimumChainLength`.
    private boolean findHint(Candy[][] map) {
        int rowCount = map.length;
        int columnCount = map.length;

        List<Candy> hintMove = new ArrayList<Candy>();

        // Search rows.
        for (int row = 0; row < rowCount; ++row) {
            // Search for chain.
            for (int chainStart = 0; chainStart < columnCount - searchChainSize; ++chainStart) {
                // Add initial cell in chain.
                hintMove.clear();
                hintMove.add(map[row][chainStart]);
                for (int nextInChain = chainStart + 1; nextInChain < columnCount; ++nextInChain) {
                    if (map[row][nextInChain].getType() == hintMove.get(0).getType()) {
                        hintMove.add(map[row][nextInChain]);
                    } else {
                        break;
                    }
                }           
                // Was a chain found?
                if (hintMove.size() >= minimumChainLength)
                    return true;
            }
        }

        // Search columns.
        for (int column = 0; column < columnCount; ++column) {
            // Search for chain.
            for (int chainStart = 0; chainStart < rowCount - searchChainSize; ++chainStart) {
                // Add initial cell in chain.
                hintMove.clear();
                hintMove.add(map[chainStart][column]);
                for (int nextInChain = chainStart + 1; nextInChain < rowCount; ++nextInChain) {
                    if (map[nextInChain][column].getType() == hintMove.get(0).getType()) {
                        hintMove.add(map[nextInChain][column]);
                    } else {
                        break;
                    }
                }
                // Was a chain found?
                if (hintMove.size() >= minimumChainLength)
                    return true;
            }
        }

        // No chain was found, so clear hint.
        hintMove.clear();
        return false;     
    }

}

and my pojo:

public class Candy {
   private int type;

    public int getType() {
        return type;
    }

    public void setType(int type) {
        this.type = type;
    }

    @Override
    public String toString() {
        return "Candy{" + "type=" + type + '}';
    }

}

When I start from an array of 10x10 I start getting the stack overflow errors. What should I do to correct them?

Thanks in advance.

Stack overflow would make me look for a method that called itself again and again, adding more frames to the stack until it was exhausted. Look for that. (PS - "Candy"? Is this meaningful for your context?) — duffymo
– duffymo, Commented Dec 20, 2016 at 22:00
Not the problem, but you don't want to be creating a new Random for each number you generate. — John3136
– John3136, Commented Dec 20, 2016 at 22:00
"the only condition is that I can have the same number 3 or more times horizontally and vertically." - that doesn't sound like a condition. — Klitos Kyriacou
– Klitos Kyriacou, Commented Dec 20, 2016 at 22:01
Firslty I presume you mean can not have same number 3 or more times horizontally and vertically, in that case your second matrix should not be ok since it has three zeros horizontally in the first line. — Sash Sinha
– Sash Sinha, Commented Dec 20, 2016 at 22:06

d80tb7 · Accepted Answer · 2016-12-20 22:29:16Z

1

your problem is this line:

map = randomInit(rowCount, columnCount);

essentially every time findHint returns true you're going to recursively invoke randomInit. This means that the bigger the probability of FindHint returning true the higher the chance of a stackoverflow. In your case the bigger you make your grid the higher the probability FindHint is going to return true and I guess at size 10 it's almost certain to end up in a stackoverflow.

I all honesty I'm not sure why you call randomInit again here rather than just returning the map?

answered Dec 20, 2016 at 22:29

d80tb7

9433 gold badges9 silver badges21 bronze badges

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

1 Comment

linker85 Over a year ago

I do that call to avoid having repeated columns and rows with 3 elements

Paul Brinkley · Accepted Answer · 2016-12-20 22:33:16Z

Without having run your code, I would guess that it has to do with randomInit() calling itself if findHint() is true. I can find nothing wrong with your code for findHint() (aside from a few performance tweaks - e.g. there's no need for you to construct a list of matches just to count how many there are), but the fact that you presumably only run into this problem on 10x10 grids is telling. Any 10x10 grid of objects with only three types is very likely to have three in a row - likely enough that it will cause your randomInit() to call itself enough times to get you your stack overflow.

I'm not 100% sure what you want randomInit() to do. If you want it to keep generating a random grid until there are no sets of N, I would suggest putting the grid generation code in a separate method (call it generate()) and then have randomInit() call it in a while loop:

boolean setFound;
do {
    map = generate(rowCount, columnCount);
    setFound = findHint(map);
} while (setFound);

Collectives™ on Stack Overflow

why is my algorithm returning stackoverflow exception?

2 Answers 2

1 Comment

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Related