Thread: Help with 2-d arrays, tough problem

Sounds like project Euler to me...write out how you would do this for a smaller grid, then extrapolate that to a larger one. If you are looking for a brute-force way, give some thought to graphs (the node/edge kind), recursive backtracking, and/or dynamic programming

I would move through the grid running through every possible path

What makes it difficult is the fact the the moves are through the lines of the grid and not the spaces, i don't know how to do that.

Yes, it's project euler which is why I'm not asking for an answer, but pseudocode or a formula.

Break down the problem. Think about the topics I mentioned above. Imaging each corner is a Node you wish to traverse through - to traverse you can go one of two directions (except for the edge Nodes and the terminal node). Then imagine how you can use recursion to traverse the next nodes until you reach the end.

Originally Posted by aesguitar

How would i do that? If i knew, I wouldn't have started this thread.

Are you familiar with data structures? Linked lists? Graphs? Recursively traversing these data structures? I'd start there. I'm not intentionally trying to be vague, but this is an advanced but extremely important topic that couldn't be done justice through this problem alone (so rather than throwing out pseudo-code for you to translate you might learn more to study the subject).

Of course, I did intentionally note this solution is brute force - the brute force solution is a good programming exercise. The alternative solution based upon a formula is...well, it IS just a formula (the derivation of which is fun, but knowing the formula itself spoils the surprise)

google 'java data structures'. You should find tons of explanations and examples. Keep in mind the many different data structures available (see List of data structures - Wikipedia, the free encyclopedia )

Originally Posted by aesguitar

...fairly complicated ...many ways to solve it...All thoughts are welcome.

Well, since you put it that way, here are my thoughts:


I will restate the problem in a way that is specific enough for me to boil it down to something that is not very complicated (to me).


You are given a 2-D array of "nodes." You want a path from the upper left node to the lower right node. Each step of the path can consist of one move to the right or one move down.

The question is: How many such paths are possible for, say, a 20x20 grid of cells bounded by the nodes.

Here's a way to look at it:

For an excursion from upper left to lower right, at each step there are two possibilities: Move to the right or move down.

Suppose we designate "Move to the right" as binary 0 and "Move down" as binary 1. (We are all computer wonks, so we really like this binary stuff, right?)


Then, for a 20x20 grid in your notation, each path will consist of exactly 40 steps. There will be a total of 20 steps to the right and 20 steps down.

A couple of simple examples:

Example 1:
Start at the upper left corner. Go straight right all of the way until you reach the upper right corner and then go straight down to the lower right corner.

A binary representation of this path is
0000000000000000000011111111111111111111 (20 zeros and 20 ones)

Example 2:
Start at the upper left corner. Go straight down all of the way until you reach the lower left corner and then go straight right to the lower right corner.

A binary representation of this path is
1111111111111111111100000000000000000000 (20 ones and 20 zeros)

Summary: All legal paths will be 40-bit numbers. Each path will have 20 ones and 20 zeros. The ones and zeros can be distributed in arbitrary ways, but the total number of each will always be the same.

Brute force way of counting the number of legal paths:
Make a loop with a long integer counter that goes from 0x00000fffffL through 0xfffff00000L. For each value, count the number of '1' bits. If the number of '1' bits is equal to 20, it's a legal path. That's a lot of counting, but it is possible.

Note that there are a couple of snazzy ways to find the number of bits set in a given integer, but the scheme is still likely to be very time-consuming. Maybe that's not so bad. (Take a break. Have a drink. Get some dinner. Have a couple more drinks. Fall in love. Start a family, ...)

Now, people who are mathematically inclined might have noticed that when we look at the paths as binary integers, the problem boils down to the following:

How many ways can 20 '1' bits be distributed in a total of 40 bits. This is the very familiar combinatorial problem: What is the number of combinations of 40 things taken 20 at a time? (We have 40 bits, how many ways can 20 '1' bits be distributed among those 40 bits?)

The conventional formula involves numbers like 40 factorial and 20 factorial, which are very large numbers. Since the result in this case is somewhere around 2 times 10 to the eleven power, it can be represented in something like 38 bits, so, if you were very (very) careful in the order in which you carried out the mathematical operations, it just might be possible to do the "counting" without overflowing 64-bit signed arithmetic and without incurring roundoff error.

However...

With Java's BigInteger class, you can do the large-factorial calculations and other arithmetic in a short time and without a lot of hassle with order of calculations. I can calculate 40 factorial and 20 factorial and perform all required arithmetic in something like a few milliseconds on my old, creaky, Linux workstation.



Cheers!

Z

Originally Posted by aesguitar

Alright, I like thinking in formulas as they can generally be applied in other ways. How would one derive the conventional formula?

IF you have never heard of "the number of combinations of N things taken K at a time, you might start here: Combinations-Wikipedia

The number of combinations of N things taken K at a time is given by

N! / (K! * (N-K)!)   (Where the "!" means "factorial," not "glad to see you.")

So for the 20x20 case of your example, the way that I am looking at it we need the number of combinations of 40 things taken 20 at a time or

40!/((20!)*(20!))

I indicated how I did it in Java. (Wrote a factorial function using the BigInteger class.)

You can check your answer by comparing it with the output of the following two lines of Python 2.6

>>> from math import factorial
>>> print factorial(40)/(factorial(20)*factorial(20))
137846528820

Cheers!


Z

Thank you for that, I already had a factorial method written that is pretty fast. Now, I'll have a method for combinations of N taken R at a time.

I got the solution in 1ms.

Originally Posted by Zaphod_b

...
And that's all I have to say about that...

I meant that I won't go into the combinatorial "solution" any more. (Well not after these few words.)
What I like about the combinatorial solution is that I can arrive at a closed formula without using a computer!. (Of course I need some kind of computer or calculator that can handle "the number of combinations of 40 things taken 20 at a time," but the derivation itself is mental, not computery.)

Now, I like to be able to come at things from more than one direction, so here's a way that actually counts the paths without going into trees, recursive traversal of graphs (with or without memoization), etc., etc., etc. I mean, all of those topics are, perhaps, important, but I don't necessarily see any of them as a solution looking for this problem.

Anyhow...

Now, I could, maybe, do the counting mentally, but for this one I'll write a simple program to do the counting. (In addition to being better at counting, the computer program makes it easy to change the number of nodes without me having to reset my internal mental counter.)

I'll present it kind of like pseudo-code, but the actual Java (or C++ or whatever...) implementation can follow this precisely. (And I say that, because that is exactly what I did. Results are below.)

Suppose we have a 2-D array of cells: for example 20x20
Then there is an array of 21x21 "nodes," where each cell is bounded by the four
nodes at its corner coordinates.
 
Suppose we designate the location of the upper left node as (0,0) and the
lower right node as (20,20).  We define a path to be an excursion from the
upper left node to the lower right node as being a sequence of steps for
which each step can go exactly one node to the right or one node down from
the current location.
 
The question is: How many such paths are there from the node at (0,0)
to the node at (20,20)?
 
In array notation, the locations would be nodes[0][0] and nodes[20][20],
respectively.
 
Here's the drill:
 
        // Prompt the user to enter the number of cells and read it in.
        // In Java, it could go like this:
        Scanner keyboard = new Scanner(System.in);
        System.out.print("Enter the number of cells: ");
        int numCells = keyboard.nextInt();
 
        // For convenience, define the number of nodes here:
        int numNodes = numCells + 1;
        long [][] nodes = new long[numNodes][numNodes];
 
        // Initialize the grid distances.
        // The value for node[i][j] is equal to the number
        // of ways to get there from node[0][0]
        //
        // The first ones are easy:
        //
        // No traveling necessary, but this value is needed for
        // some of the other calculations.
        nodes[0][0] = 0;
 
        // Now take care of the outside nodes
        //
        for (int i = 0; i < numNodes; i++)
        {
            // Go down the left-most column
            // There is only one way to get to location [0][i]:
            // Straight down from the starting point.
            // That is: all nodes in the left-most column are
            // on the same path.
 
            // So---set nodes[0][i] to 1
 
            // Go right on the top-most row
            // There is only one way to get to location [i][0]:
            // Straight right from the starting point.
            // That is: all nodes on the top row are on the
            // same path.
 
            // So---set nodes[i][0] to 1
        }
 
        // Now, the more interesting paths.  For an interior
        // node at location [i][j] on any path, there are exactly
        // two immediately preceding nodes from which we could
        // have arrived there:
        //    The node to its immediate left: nodes[i-1][j]
        // and
        //    The node just above it: nodes[i][j-1]
        //
        for (int i = 1; i < numNodes; i++)
        {
            for (int j = 1; j < numNodes; j++)
            {
                // Add the values from the two immediately preceding
                // nodes to get the number of ways to get here:
                // nodes[i][j] = value at nodes[i-1][j] plus value at nodes[i][j-1]
            }
        }
        // Taa-daa! The grand finale:  How many ways are there to get to
        // the lower right node? Well just show the value that
        // was the very last value calculated by the nested loops:
        System.out.printf("Number of paths from the node at (0,0) to the node at (%d,%d) = %d\n",
                numNodes-1, numNodes-1, nodes[numNodes-1][numNodes-1]);
    }

Now a direct implementation of this stuff gives me the following output:

Enter the number of cells: 20
Size of the array of cells is 20x20
There are 21x21 nodes.
Number of paths from the node at (0,0) to the node at (20,20) = 137846528820

Anyhow...

Since this is the same value that I got from the combinatorial solution, I can't think of anything else to say except that maybe the problem statement is either misleading or incomplete.

Note that I originally ran it using a BigInteger array for the nodes even though I "knew" that it shouldn't overflow a Java long variable (signed 64-bit integer). Results are the same.



Cheers!

Z

Well...

I just registered at projecteuler.net and submitted the answer to problem #15 that I have posted here several times: 137846528820
It was accepted.

I am apparently the 55434th person (or other being) to submit a correct solution.


Cheers!

Z

Originally Posted by aesguitar

I'm getting 1378465288200 instead of 137846528820

And you didn't notice that it was different from the answer(s) that I posted? I always try to come up with an independent way to check my work, and I even showed the answer obtained from an alternative program.

Originally Posted by aesguitar

...something in my factorial() method is adding a zero to the end of the number...

So: didn't you test it before plugging it into a program that uses it? I mean you don't have to go all the way to 40 factorial or even 20 factorial, but you should do some testing.

import java.util.Scanner;
import java.math.BigInteger;
 
public class TestFactorial
{
    public static void main(String [] args)
    {
        Scanner keyboard = new Scanner(System.in);
        String xstr;
        System.out.print("Enter a positive integer: ");
        xstr = keyboard.nextLine();
        while (xstr.length() > 0)
        {
            BigInteger x = new BigInteger(xstr);
            System.out.println("Calling factorial (" + x + ")");
            BigInteger xfact = factorial(x);
            System.out.println("factorial(" + x + ") = " + xfact);
            System.out.println();
            System.out.print("Enter another positive integer: ");
            xstr = keyboard.nextLine();
        }
    }
 
    public static BigInteger factorial(BigInteger n)
{
// Implementation of the factorial function goes here.
}

A run with your factorial function:

Enter a positive integer: 1
Calling factorial (1)
factorial(1) = 1
 
Enter another positive integer: 2
Calling factorial (2)
factorial(2) = 1
 
Enter another positive integer: 3
Calling factorial (3)
factorial(3) = 2
 
Enter another positive integer: 4
Calling factorial (4)
factorial(4) = 6
 
Enter another positive integer: 5
Calling factorial (5)
factorial(5) = 24
 
Enter another positive integer: 6
Calling factorial (6)
factorial(6) = 120
 
Enter another positive integer: 7
Calling factorial (7)
factorial(7) = 720
 
Enter another positive integer: 8
Calling factorial (8)
factorial(8) = 5040
 
Enter another positive integer: 9
Calling factorial (9)
factorial(9) = 40320
.
.
.

See? There's a pattern here:
Other than factorial(1), they all act like the argument is off by 1: Didn't go through the multiplication loop enough times, right?

A couple of notes:
I can't see any earthly reason to make the argument a BigInteger. Why not just use an int? I mean, you aren't going to be calculating factorial values for numbers greater than 2147483747 are you? I don't think so.

Anyhow...

Now, it's OK to use BigInteger argument and loop counter if you really want to, but no matter how you implement it, the loop control should not terminate the loop until after it has multiplied by a term equal to value of n, right? When your loop counter reaches n, it terminates the loop before multiplying by that last value. Or so it seems to me...

Bottom line: Your factorial function is not "adding an extra zero to the end." It is operating incorrectly so that instead of calculating

factorial(40)/(factorial(20)*factorial(20)) = 137846528820

as it was supposed to, your program is, apparently, getting

factorial(39)/(factorial(19)*factorial(19) = 1378465288200

See how it goes? Test the lower level functionality first, and the higher-level stuff will take care of itself. Don't jump to conclusions about what the program is doing. Make it tell you!


Cheers!

Z