Trouble with ProjectEuler #15 [closed]

Here’s the problem: https://projecteuler.net/problem=15

I’ve come up with a pattern which I thought would work for this and I’ve looked at what other people have done and they’ve done the same thing, such as here: http://code.jasonbhill.com/python/project-euler-problem-15/ But I always get a different answer. Here’s my code.

import java.util.*;
public class Problem15 {
    public static void main(String[] args) {
        ArrayList<Long> list = new ArrayList<Long>();
        list.add((long)1);
        int size;
        for (int x = 1;x<20;x++){
            size = list.size();
            for(int y = 1;y<size;y++){
                    long sum = list.get(y-1)+list.get(y);
                    list.set(y, sum);
            }
        list.add(list.get(size-1)*2);
        System.out.println(list);
        }
    }
}

edit: In response to Edward, I think my method is currently what you said before your edit in that this isn’t about brute force but I’m just summing the possible ways from each point in the grid. However, I don’t need a 2d array to do this because I’m only looking at possible moves from only the side. Here’s something I drew up to hopefully explain my process. My Method

So for a 1×1. Like you said, once you reach the limit of one direction, you can only travel in the limit of the other, so there’s 2 ways. This isn’t particularly helpful for a 1×1 but it is for larger ones. For a 2×2, you know that the top corner, being the limit of right, only has 1 possible path from that point. The same logic applies to the bottom corner. And, because you have a square which you have already solved for, a 1×1, you know that the middle point has 2 paths from there. Now, if you look at the sides, you see that the point for instance that has 2 beneath it and 1 to the right has the sum of the number of paths in those adjacent points so then that point must have 3 paths. Same for the other side, giving the top left corner the sum of 3 and 3, or 2 times 3.

Now if you look at my code, that’s what it’s trying to do. The element with index 0 is always 1, and for the rest of the array, it adds together the previous term and itself and replaces the current term. Lastly, to find the total number of paths, it just doubles the last number. So if the program were to try and solve for a 4×4, the array would currently look like {1, 4, 10, 20}. So the program would change it to {1, 5, 10, 20}, then {1, 5, 15, 20}, then {1, 5, 15, 35}, and finally, adds the total number of paths, {1, 5, 15, 35, 70}. I think this is what you were trying to explain to me in your answer however my answer always comes out incorrect.

Answer

Realize that it’s more about mathematical complexity than brute force searching.

You have a two dimensional array of points, where you can chose to only travel away from the origin in the x or the y direction. As such, you can represent your travel like so:

(0, 0), (1, 0), (1, 1), (2, 1), (2, 2)

some things become immediately obvious. The first one is that any path through the mess is going to require x + y steps, travelling through x + y + 1 locations. It is a feature of a Manhattan distance style path.

The second is that at any one point until you hit the maximum x or y, you can select either of the two options (x or y); but, as soon as one or the other is at it’s limit, the only option left is to chose the non-maximum value repeatedly until it also becomes a maximum.

With this you might have enough of a hint to solve the math problem. Then you won’t even need to search through the different paths to get an algorithm that can solve the problem.

— edited to give a bit more of a hint —

Each two dimensional array of paths can be broken down into smaller two dimensional arrays of paths. So the solution to f(3, 5) where the function f yields the number of paths is equal to f(2, 5) + f(3, 4). Note that f(0, 5) directly equals 1, as does f(3, 0) because you no longer have “choices” when the paths are forced to be linear.

Once you model the function, you don’t even need the array to walk the paths….

f(1, 1) = f(0, 1) + f(1, 0)
f(0, 1) = 1
f(1, 0) = 1
f(1, 1) = 1 + 1
f(1, 1) = 2

and for a set of 3 x 3 verticies (like the example cited has)

f(2, 2) = f(1, 2) + f(2, 1)
f(1, 2) = f(0, 1) + f(1, 1)

(from before)

f(1, 1) = 2
f(0, 2) = 1
f(1, 2) = 2 + 1 = 3

likewise (because it’s the mirror image)

f(2, 1) = 1 + 2 = 3

so

f(2, 2) = 3 + 3 = 6

— last edit (I hope!) —

Ok, so now you may get the idea that you have really two choices (go down) or (go right). Consider a bag containing four “commands”, 2 of “go down” and 2 of “go right”. How many different ways can you select the commands from the bag?

Such a “selection” is a permutation, but since we are selecting all of them, it is a special type of permutation called an “order” or “ordering”.

The number of binomial (one or the other) orderings is ruled by the mathematical formula

number of orderings = (A + B)!/(A! * B!)

where A is the “count” of items of type A, and B is the “count” of items of type B

3×3 vertices, 2 down choices, 2 right choices

number of orderings = (2+2)!/2!*2!

4!/1*2*1*2
1*2*3*4/1*2*1*2
(1*2)*3*4/(1*2)*1*2
3*4/2
12/2
6

You could probably do a 20*20 by hand if you needed, but the factorial formula is simple enough to do by computer (although keep an eye you don’t ruin the answer with an integer overflow).

Leave a Reply

Your email address will not be published. Required fields are marked *