Problem 015

[Bernardo]

In the following order I have found an answer for 20 but I think the format of my answer is off.
Any hint on exponential notation; or should I use full notation (which hasn't worked for me)?

Code: Select all

n --> #
2 --> 6
3 --> 20
4 --> 70
5 --> 252

[stijn263]

Hm, you should enter the entire number as your answer. Perhaps you have an overflow problem? You can pm me your answer if you want and I'll help you further

[keyzplayer]

In this case backtracking means start at the right bottom of the grid. Then take a look at the adjacent points in the grid (there are three) and ask yourself: In how many ways can I move from that point to the point at the right bottom. Next step is to do the same for each of these three points and for the points anjecent to those and so on until you see the pattern.

Solved this in 1 minute work with a spreadsheet.

[juvan]

Hello all

I am quite new to the projecteuler, but I have to say, I'm loving it. This is the first time I'm posting on this forum, for it is the first time, that I truly want to know...
How the heck do you work out the algorithm for this problem, because what I got so far, is that I've translated this problem to be something like this : "We have a 40 letter "word", comprising of two letters, let's say 'r' and 'd', why r and d? I'll tell you later. And we have to use both letters equally, 20 times each, so 20 r's and 20 d's, so there is our 40 letter "word". The question is, how many different "words" can can be created?

And now I'm trying to solve this problem, but my question is, how the heck do you do this one (I know that you could do it, with some highly optimized clever mathematical algorithm, but I think that's a bit much, for these are still only the starting problems), without approaching it this way, I've had a couple of ideas that all failed in the end, and this is the first one that I think that if I work out, will be sufficient.

thank you all

have a nice day

[harryh]

Your interpretation of the problem seems correct

Now, see if you can verify the results given in previous posts for smaller "words";
e.g. how many 10-letter words are there using 5 r's and 5 d's ?
Does your result agree with that posted previously by stijn263 for a 5x5 board?
If so, you are on the right track !
The next step would be to attempt longer and longer "words" watching how much time your program needs and how you can speed it up in order to make 40-letter words in reasonable time.

PS I can tell you that it does not require "some highly optimized clever mathematical algorithm"...
... and welcome to PE juvan

[juvan]

I got the solution to my little "translated" problem (with r's and d's ), and I found it while looking at something called the Pascal's triangle, it gave me the mathematical formula to solve it, and it was very neat and short and sweet (though I couldn't in my life time have came up with it on my own), but this way, using the formula, it was all combinatorics, it wasn't really an algorithm doing some sweet computations (for i.e. making a "map" of the grid and then going about it). And making an algorithm for this problem, I think would need, what I said previously, "some highly optimized clever mathematical algorithm"... Because the sheer amount of possible routs is incredibly huge. So I think that this problem, is basically just the discovery of a mathematical formula, or am I mistaking??

Thanks for the warm welcome it's a sweet site, and I sure am happy to have found it.

Cheers.

[ddrm]

So I think that this problem, is basically just the discovery of a mathematical formula, or am I mistaking??

It doesn't have to be. Often with these problems the key is to work out a way of not doing things repeatedly.

In this case, try thinking of how the problem develops as you move away from the END point. If you can "remember" how many solutions there are to a smaller problem (say, getting from TL to BR of a 5 x 5 square, or even a 1 x 1 square)), you don't need to recalculate it each time you get to that situation - you can just add that number on.

Using that approach I got an answer in "0 msec", whereas trying to use your "RD string" method recursively was going to take all day...

Hope that is helpful. Enjoy the problems - I am struggling to stay at 50% done...



D

[zcxvbn]

I got the solution to my little "translated" problem (with r's and d's ), and I found it while looking at something called the Pascal's triangle, it gave me the mathematical formula to solve it, and it was very neat and short and sweet (though I couldn't in my life time have came up with it on my own), but this way, using the formula, it was all combinatorics, it wasn't really an algorithm doing some sweet computations (for i.e. making a "map" of the grid and then going about it). And making an algorithm for this problem, I think would need, what I said previously, "some highly optimized clever mathematical algorithm"... Because the sheer amount of possible routs is incredibly huge. So I think that this problem, is basically just the discovery of a mathematical formula, or am I mistaking??

Thanks for the warm welcome it's a sweet site, and I sure am happy to have found it.

Cheers.

It's perfectly fine if you don't come up with solutions completely on your own - part of the value of these problems is to learn from other sources too but you should at least try to understand why a certain solution works. It's usually more satisfying that way too.

Also, I think you'll find that a lot of problems later on will require some clever algorithm design, i.e. they won't admit a 'closed-form' solution like for this problem, so you won't be disappointed ;P

[weird_dave]

I've spotted a sequence to the problem but I can't remember what the sequence is called so I can research it!
The sequence is:
0
1 1
1 2 1
1 3 3 1
1 4 6 4 1
I'm sure someone know's what it's called

[stijn263]

Pascal's Triangle?

[weird_dave]

That's the one
I was hoping there might be a way to make a simple formulae to get the number I want but it doesn't look that simple...
Still, generating the triangle should be a quick method....

[jetrii]

I was able to solve this problem using a very simple 5 line recursive function. However, it just brute forces all the possibilities and it can take quite a while to find the solution when the grid is larger than 16x16. I'm still trying to find a faster solution myself before I look at what others have done. How long did it take you guys to find the solution to 20x20 on your machines?

[TripleM]

Less than a millisecond.

[jetrii]

Less than a millisecond.

Wow, I really need to fix my implementation then. It's very short and clean but it takes minutes on large grids.

EDIT: Yea, I was completely overthinking this. Much easier than I initially thought.

[mina.fouad]

I think we can solve this problem without coding, we can do by techniques of counting. any one agrees with me?

[stijn263]

Sure, Problem 15 (View Problem) can be solved without coding. I would use a calculator though

[zxyzxy12321]

oooo, i calculate the first 9 answers of the problem
code start run at: 1296628395.187000s

• 1 2
• 2 6
• 3 20
• 4 70
• 5 252
• 6 924
• 7 3432
• 8 12870
• 9 48620

code finish run at: 1296628396.843000s
escaped: 1.656000s
it's so slow. i just enumerates all binary number that below 1 << grid-size * 2
that i mean: 1: right, 0: down, that could only this two ways to get to the end
and, if 1 is as same many as 0 as grid-size, then that is a valid way.
e.g.:
grid-size:2

1 1 0 0
1 0 1 0
1 0 0 1
0 0 1 1
0 1 1 0
0 1 0 1

then, that was 6 diff. ways to the end.
so, travel all number below 1 << (2 * 2), that's 10000₂
okay, that must be a available algorithmic, but very inefficient.

python 3 code

Code: Select all

snip

does someone have better idea?

[stijn263]

How many routes are there through a grid of 2*5?
And how many through a grid of 3*4?
So how many routes are there through a grid of 3*5?

Good luck!

[Scuzlebut]

I spent a day wondering why my answer was wrong until I realised I was missing a digit

[mengtnt]

I analyse the problem.Find the restrict condition is that you only move right and down. So establish the math model.I describe the problem as planar coordinate system . Every step ,you only add x for a unit or y for a unit.Use 2 binary tree solve the problem.My code as follow.But I find that the program can get the result below 14.If you put 20,the program run long long time.Hope some body help to optimize the program.
[code]
snip
[/code]
validate result:
snip
(long time 3 minute)