Problem 662

A place to air possible concerns or difficulties in understanding ProjectEuler problems. This forum is not meant to publish solutions. This forum is NOT meant to discuss solution methods or giving hints how a problem can be solved.
Forum rules
As your posts will be visible to the general public you
are requested to be thoughtful in not posting anything
that might explicitly give away how to solve a particular problem.

This forum is NOT meant to discuss solution methods for a problem.

In particular don't post any code fragments or results.

Don't start begging others to give partial answers to problems

Don't ask for hints how to solve a problem

Don't start a new topic for a problem if there already exists one


See also the topics:
Don't post any spoilers
Comments, questions and clarifications about PE problems.
Post Reply
Sardaai
Posts: 3
Joined: Mon Mar 26, 2018 12:21 am

Problem 662

Post by Sardaai »

Not a clarification, per se, but there's an odd inconsistency in the grid near the point (4, 5).

Yes, I do feel a bit ridiculous for noticing this, much less for making a forum post about it~

User avatar
Jochen_P
Posts: 55
Joined: Mon Oct 05, 2009 10:47 am
Location: Stuttgart, Germany

Re: Problem 662

Post by Jochen_P »

Arrgh, cannot unsee this.

*Autistic screeching :mrgreen:
Image

fpbosmans
Posts: 3
Joined: Tue Feb 19, 2019 2:11 pm

Re: Problem 662

Post by fpbosmans »

I don't seem to understand the problem. How is a path defined?
According to my understanding of the problem there are 36 paths between (0,0) and (3,4).

vamsikal3
Posts: 113
Joined: Sat Oct 01, 2016 9:25 am

Re: Problem 662

Post by vamsikal3 »

1. A path is a sequence of steps from start point(0, 0) to end point(W, H).
2. A step can be made from point A(a, b) to point B(a + x, b + y) if the distance between A and B is a Fibonacci number. Take a good look at the image in the problem to understand how a step can be made.
my friend key --> 990813_OZPwQtCjkD6KlvxirOoTSZxccMFsuw1L
Image

fpbosmans
Posts: 3
Joined: Tue Feb 19, 2019 2:11 pm

Re: Problem 662

Post by fpbosmans »

Well, that is what I gathered, but still within the given constraints (x and y >= 0, so only going up and right) I don't see how you can come up with 278 paths

v6ph1
Posts: 122
Joined: Mon Aug 25, 2014 7:14 pm

Re: Problem 662

Post by v6ph1 »

For a smaller example 2x2:
Expand
You can go:
0,0 - 0,1 - 0,2 - 1,2 - 2,2
0,0 - 0,1 - 1,1 - 2,1 - 2,2
0,0 - 0,1 - 1,1 - 1,2 - 2,2
0,0 - 1,0 - 1,1 - 2,1 - 2,2
0,0 - 1,0 - 1,1 - 1,2 - 2,2
0,0 - 1,0 - 2,0 - 2,1 - 2,2
--> 6 solutions only with step = 1

AND: (Two 1-steps and one 2-step)
0,0 - 0,1 - 0,2 - 2,2
0,0 - 0,2 - 1,2 - 2,2
0,0 - 0,1 - 2,1 - 2,2
0,0 - 1,0 - 1,2 - 2,2
0,0 - 1,0 - 2,0 - 2,2
0,0 - 2,0 - 2,1 - 2,2
(Two 2-steps)
0,0 - 0,2 - 2,2
0,0 - 2,0 - 2,2
--> in Total 14

For the 3x4-Example there are the following combinations usable:
Expand
1 x (3,4)
or combinations of the following:
3x(1,0), (1,0)+(2,0), (3,0)
4x(0,1), 2x(0,1)+(0,2), (0,1)+(0,3), 2x(0,2)
Image

fpbosmans
Posts: 3
Joined: Tue Feb 19, 2019 2:11 pm

Re: Problem 662

Post by fpbosmans »

I get it, very stupid of me! tnx!

Post Reply