Problem 015

[Kelakhai]

Excel is just enough to solve the problem once the logic of the calculation is right.
But now I wonder how I'd coded a program to end with this result...
No doubt a recursive fonction would have been my favourite.

[rayfil]

@ mengtnt

If you put 20,the program run long long time. Hope some body help to optimize the program.

When I snipped your code, I should have added that optimizing such code would not be of much use anyway.

For your information, my code takes 1 microsecond on a 1.8GHz 2-year old computer. You would thus need a completely new code based on a totally different algo if you want to solve it in a reasonable time.

[denj]

Can someone snip zxyzxy12321's code? I don't think he read the red post on top...

[Otherworld]

This one is very simple. You can solve it in one line of code
However, if your language does not have that particular method, then...
It took me 12 lines in AutoIt. Probably would take less in Python (like 7-8 lines)

[Fogmeister]

OK, I've solved this problem already but I did it in Excel working out the number of routes to each individual point in the grid.

I can see now how I could use an algorithm to work this out and used a very similar algorithm to solve problem 81 in well under a second (? shortest path through the 80x80 grid question, I think that was 81).

However, I thought about a combinatoric (very new to me) solution for this (very similar to the words made out of the letters "r" and "d" that was mentioned earlier). This made me think, why do I need a program to do this at all?

Is there more to combinatorics than just figuring out the equation and typing it into a calculator?

If someone was to ask me how many ways are there of throwing 3 heads and 7 tails when tossing a coin I wouldn't use a computer algorithm to work it out.

Someone (on another thread) mentioned that there are combinatoric solutions for "almost all of the questions up to 37" and 24 in particular is shouting "combinatorics" at me but I can't see how this is possible and again why would you write a program to do it this way?

Sorry if I sound a bit stupid but I haven't quite "got" this whole combinatorics in proramming thing yet.

[Lord_Farin]

Someone (on another thread) mentioned that there are combinatoric solutions for "almost all of the questions up to 37" and 24 in particular is shouting "combinatorics" at me but I can't see how this is possible and again why would you write a program to do it this way?

Sorry if I sound a bit stupid but I haven't quite "got" this whole combinatorics in proramming thing yet.

First of all, this is not stupid. However, keep in mind that algorithms can be adapted to suit different conditions more easily (in general) than closed-form formulae for a single problem (which are often rendered invalid by changing one premise). Also, overflow problems can be a pain for closed-form solutions, for example when trying to calculate the last digit of the 10 billionth Fibonacci number.

[lemur123]

Edit: Blergh. Nevermind. I was counting gridpoints, not boxes.

[7cardcha]

If you are 1 away from the bottom right corner and move to a square that is 1 away from the bottom right corner is that backtracking.

[7cardcha]

Also if possible can somebody tell me how many in a 3x3 square

[jaap]

viewtopic.php?f=50&t=730

[rayfil]

Please remember that, for ease of searching and listing in numerical order, problem numbers less than 100 have been padded with leading 0's to make them 3-digit numbers. Your post has been transferred to, and merged with, the proper topic.

[thundre]

If you are 1 away from the bottom right corner and move to a square that is 1 away from the bottom right corner is that backtracking.

There are only 2 points which are 1 away from the bottom right corner, and you can't go from one to the other in one move. If you do it in two moves, one of those moves would be backtracking.

[gitter1226]

This one was fun. I was able to solve it using a recursive algorithm. Whole thing was 16 lines of formatted code.

[klloveall]

Is there not a PDF for this problem? I solved it using a brute-force solution that I let run overnight, but I know there's a much better solution out there and would like to know it. I've gathered there's a pattern to the number of paths, but I can't seem to figure it out. Any ideas?

Kenny

[pieppiep]

Is there not a PDF for this problem? I solved it using a brute-force solution that I let run overnight, but I know there's a much better solution out there and would like to know it. I've gathered there's a pattern to the number of paths, but I can't seem to figure it out. Any ideas?

Kenny

If you solved it and you have entered the solution, you see "Go to the thread for problem 15 in the forum." where you can click the "problem 15" to see how other people did it.
I've clicked it, there are good solutions there.

[pimspelier]

I've got a question. I use C99, and my code works correct: it gives the same answers form 1 to 5, and I know the theory behind it too. But when I ask for the answer to 20, it stops working. I think it's too big a number, but it's declared: double answer_15 and I've read that a double goes to 1.7*10³⁰⁸. So what am I doing wrong?
P.S: my solution uses combinations, which I made into a function relying on another function.

[pieppiep]

I've got a question. I use C99, and my code works correct: it gives the same answers form 1 to 5, and I know the theory behind it too. But when I ask for the answer to 20, it stops working. I think it's too big a number, but it's declared: double answer_15 and I've read that a double goes to 1.7*10³⁰⁸. So what am I doing wrong?
P.S: my solution uses combinations, which I made into a function relying on another function.

A double is a floating point number that goes to 1.7*10³⁰⁸ but not all integer numbers are possible for it.
A 64 bits integer would probably better in this problem.

[jaap]

I've got a question. I use C99, and my code works correct: it gives the same answers form 1 to 5, and I know the theory behind it too. But when I ask for the answer to 20, it stops working. I think it's too big a number, but it's declared: double answer_15 and I've read that a double goes to 1.7*10³⁰⁸. So what am I doing wrong?

The answer fits easily in a 64 bit integer. In fact, it even fits into 52 bits so a double can represent it exactly.
However, you may be constructing numbers much larger than the final answer during your calculations, numbers that are too large for a double to represent exactly. A double only remembers the first 15 decimal digits or so. So you may want to see whether you can rearrange your computation to avoid such large numbers.

[pimspelier]

It's true: one number even exceeds a long long long int (should that exist), but should I then use a long double? But that number doesn't exceed a double, so how would that help? Maybe a long long long long int?

[jaap]

It's true: one number even exceeds a long long long int (should that exist), but should I then use a long double? But that number doesn't exceed a double, so how would that help? Maybe a long long long long int?

As I said, try to rearrange your computation to avoid such large numbers. You can then do it using 64 bit integers.
Or you can try to find a different solution that does not involve larger numbers at all.