My algorithm only finds the longest path in 2d array

Question

I'm having an assignment for school and my method needs to find every possible path starting from a given node. Now the problem is, my method only finds the longests paths and then stops creating new paths and I can't seem to figure out why it is doing this (maybe too inexperienced in Java). I'm using a char[3][3] array the method needs to iterate through. The basic idea is working out, but just not all paths.

The method I wrote:

private void computeAllPaths(Point current, ArrayList<Point> currentFullPath) {

    if (currentFullPath.isEmpty()) {
        currentFullPath.add(current);
    }

    for (Point coord : neighbouringCoords.get(current)) {
        if (!(currentFullPath.contains(coord))) {
            currentFullPath.add(coord);
            if (!(paths.contains(currentFullPath))) {
                paths.add(currentFullPath);
                //start over again with same coord
                computeAllPaths(currentFullPath.get(0), new ArrayList<Point>()); 
            } else {
                //try to add another coord
                computeAllPaths(coord, currentFullPath); 
            }
        }
    }
}

The method call:

computeAllPaths(new Point(0, 0), new ArrayList<Point>());

The declaration:

private List<ArrayList<Point>> paths = new LinkedList<ArrayList<Point>>();

Some output for the 3x3 array:

    Current paths size: 8

(0.0,0.0)(1.0,0.0)(0.0,1.0)(0.0,2.0)(1.0,2.0)(2.0,2.0)(2.0,1.0)(2.0,0.0)(1.0,1.0)
(0.0,0.0)(1.0,0.0)(2.0,0.0)(2.0,1.0)(2.0,2.0)(1.0,2.0)(0.0,2.0)(0.0,1.0)(1.0,1.0)
(0.0,0.0)(1.0,0.0)(2.0,0.0)(2.0,1.0)(1.0,1.0)(2.0,2.0)(1.0,2.0)(0.0,2.0)(0.0,1.0)
(0.0,0.0)(1.0,0.0)(2.0,0.0)(2.0,1.0)(2.0,2.0)(1.0,2.0)(0.0,2.0)(0.0,1.0)(1.0,1.0)
(0.0,0.0)(1.0,0.0)(2.0,0.0)(2.0,1.0)(2.0,2.0)(1.0,2.0)(1.0,1.0)(0.0,2.0)(0.0,1.0)
(0.0,0.0)(1.0,0.0)(2.0,0.0)(2.0,1.0)(2.0,2.0)(1.0,2.0)(0.0,2.0)(0.0,1.0)(1.0,1.0)
(0.0,0.0)(1.0,0.0)(2.0,0.0)(2.0,1.0)(2.0,2.0)(1.0,2.0)(0.0,2.0)(0.0,1.0)(1.0,1.0)
(0.0,0.0)(1.0,0.0)(2.0,0.0)(2.0,1.0)(2.0,2.0)(1.0,2.0)(0.0,2.0)(0.0,1.0)(1.0,1.0)

I have tried many types of lists and sets, but noone seems to be working and I have no clue why, can someone help me figure this out?

Example of a board:

N | N | A
R | E | T
N | T | O

Allowed movements: Let's say we start at R (1,0) then allowed moves would be:

N(0,0)
N(0,1)
E(1,1)
T(2,1)
N(2,0) So basically it's direct neighboors.

I don't understand your question. Can you give some more information about the underlying data and the allowed movement rules? — mikyra, Mar 02 '13 at 12:02

Piotr Jaszkowski · Accepted Answer · 2013-03-02T13:01:47.403

So I'm not Java coder myself, but you're doing few things badly.

with currentFullPath you're adding a pointer to it to paths and you should add a pointer to it's copy, so guess what happens. After you add it to paths you are further changing it later. Basically to debug this, just print out paths every pass of the inside loop. Also you should create copies of currentFullPath for each coord in neighbouringCoords if you don't do this, you will eventually add all neighbours to the same path.

Remember Java is always passing pointer to the object.

Edit: I see that there still a lot of nonsense flying around. Try this:

private void computeAllPaths(Point current, ArrayList<Point> currentFullPath) {

    if (currentFullPath.isEmpty()) {
        currentFullPath.add(current);
    }

    for (Point coord : neighbouringCoords.get(current)) {
        if (!(currentFullPath.contains(coord))) {
            ArrayList<Point> newList = new ArrayList<Point>(currentFullPath);
            newList.add(coord);
            if (!(paths.contains(newList))) {
                paths.add(newList);
                //start over again with same coord
                computeAllPaths(currentFullPath.get(0), new ArrayList<Point>()); 
            } else {
                //try to add another coord
                computeAllPaths(coord, newList); 
            }
        }
    }
}

Show results.

Edit 2: This will be a lot faster.

private void computeAllPaths(Point current, ArrayList<Point> currentFullPath) {

    if (currentFullPath.isEmpty()) {
        currentFullPath.add(current);
    }

    for (Point coord : neighbouringCoords.get(current)) {
        if (!(currentFullPath.contains(coord))) {
            ArrayList<Point> newList = new ArrayList<Point>(currentFullPath);
            newList.add(coord);
            paths.add(newList);                           
            computeAllPaths(coord, new ArrayList<Point>(newList));            
        }
    }
}

Current paths size: 10296 And it found 39 valid words on a 3x3 Array! Thank you very much! I was close to your solution but kept adding the coordinates to currentFullPath which didn't lead to any good results. — , Mar 02 '13 at 12:29
Although it works perfect for a 3x3 array, it goes stack overflow when I try it on a 4x4 array. I'm using a HashSet to store the paths — , Mar 02 '13 at 12:40
I dont' event want to try and calculate amount of paths for 4x4 array, because it will be probably smth like 10^5 times more than for 3x3 array. If you want to find all valid words then don't store all paths! Just remember your path and limit length for it. Also store valid words. — Piotr Jaszkowski, Mar 02 '13 at 12:56
After applying your new fix, it shows 1012519 different paths starting from just one coordinate ... I believe this is kind of an overkill for my machine when trying to calculate all the paths? — , Mar 02 '13 at 13:09
No 1012519 starting from one point in a 4x4 Array. I started from 0,0 and got 1012519 different paths. These are my results: Time needed: 6.279 seconds Current paths size: 1012519 — , Mar 02 '13 at 13:30

My algorithm only finds the longest path in 2d array

1 Answers1