Project Euler Forum

Hi!
I have a question about Problem 144 (View Problem).
I wasn't sure where to put this question (there is another topic related with Problem 144: viewtopic.php?f=3&t=1915&p=20291&hilit=144#p20291). I opened a new topic.

My program is finished, I think everything is OK.
When I start the program (done with Mathematica) with the following input (0, 10.1, 1.4, -9.6) (the info of problem 144), the program runs until the 33rd reflection of the beam, Then the laser gets stuck in the values x=+-5, in the next reflection y = -96.07 and an error happens.

I managed to run the program without this error, but then the program does an endless loop with x=5 or x=-5 and y around +- 0.003 and that is impossible.

My questions are: Does the 2nd reflection happen at (3.9, -6.0)? Does the 9th reflection happen at (3.3, 7.5)? (I know there are more digits, but I don't want to give too much info. I want only to know if these values are correct )

Coordinates to the nearest hundredth are as follows:
second: (-3.99, -6.02)
ninth: (3.29, 7.53)
thirty-third: (-4.10, -5.74)

I had problems with this also, for a long time. Make absolutely sure you have the right formulae, because that is actually quite hard. As a test, you could plot the ellipse, and your reflections. It is then easy to see if you're correct.

Could someone please post the first five reflections?

EDIT: My program gets the same results for the 2nd, 9th and 33rd, but my answer isn't correct!!!

(0.006 -10.000)

This is the last point I get, rounded. This point is the 160th-170th point I get, hopefully I'm not giving too much away here. Am I anywhere close?

EDIT*: Just realised the problem, pretty much as soon as I edited this point. Embarrassing! :\

EDIT**: Solved

Could someone clarify me on this? I wonder if I have precision problem or something ...
I end somewhere between 570 and 580th reflection, on point (0.0071073, 9.9999899) (rounded). No luck.
Here are some of my reflections - are these correct?
300 - (0.0946, 9.9982)
400 - (-0.1308, -9.9966)
500 - (0.1670, 9.9942)

The first one is incorrect, so I would say, the others are bad too (I haven't tested). This won't be your problem probably, but look for the counterm to calculate reflections correctly (+/-1 are common mistake, at least for me).

MaJJ wrote:Could someone clarify me on this? I wonder if I have precision problem or something ...
I end somewhere between 570 and 580th reflection, on point (0.0071073, 9.9999899) (rounded). No luck.
Here are some of my reflections - are these correct?
300 - (0.0946, 9.9982)
400 - (-0.1308, -9.9966)
500 - (0.1670, 9.9942)

TheEvil wrote:The first one is incorrect, so I would say, the others are bad too (I haven't tested). This won't be your problem probably, but look for the counterm to calculate reflections correctly (+/-1 are common mistake, at least for me).

Off-by-one errors, yeah ... The thing is, I have tried to submit my answer +- 1, +- 2 and nothing succeeds. So the answer probably lies elsewhere and it's not off-by-one?

Could you please tell me if reflection 300 is one of these? (reflections 299,300,301 in my program)
(0.9444, -9.8200)
(0.0946, 9.9982)
(-2.1689, -9.0102)

EDIT: nevermind, rewrote it in Haskell and voilá

Holy crap! I think I'll be earning that Fibonacci Fever award with this one. I felt kind of stupid for quite a while for not being able to figure out a simple formula for the slope of the trajectory of the reflection given the slopes of the incoming trajectory and the tangent slope at the point of reflection. I think I have found a method of calculating it though. And the formula I got using the outgoing trajectory to find the next point of reflection is ugly as sin.

I don't think it will be giving too much away to say that it appears the coordinates of each reflection point appear that they should be rational. My first stab at this is to try to store exact values as fractions to eliminate any rounding errors, but I'm starting to get the feeling 64 bit integers are going to prove inadequate real fast.

My hat's off to anyone who's already completed this problem. Hoping to join your ranks soon.

Update: It appears that the numerator and denominator overflowed with the very next point of reflection (which I may or may not have been able to prevent with better implementation of division of fractions). Either that or there's a problem with my formula. I'll rewrite the program without fractions and see if I get the answer I should get. If I do, it should be off to the races from there. I hope.

Maybe I'm not giving away too much, but you should try to find some formulae. Some coordinate geometry is very useful, and do not forget that it is a seriously easier problem than it looks like. And one more thing: I spent 6 hours trying to find the bug in my code, and I forgot to add the first reflection, it can be a common problem.

I solved in excel using decimals. I was just trying to run a few iterations to test my formulae but found that what I was doing was good enough to generate the final answer. No need for fractions and, yes, make sure you count accurately. I was one out to start with too.

Doesn't the laser beam get reflected off the top before it ever makes it into the ellipse?

grump wrote:Doesn't the laser beam get reflected off the top before it ever makes it into the ellipse?

The light beam enters through the gap at x ~ 0.0071 (-0.01 <= 0.0071 <= 0.01).

Oops... so it does... Not quite sure how I screwed up that calculation.

Can someone help me confirm what's wrong with my formula? I used wolframalpha to calculate it, but it's giving the x coordinate of the first intersection as ~1.46 instead of 1.4.

Message me, and I'll send you the links.

seestrahseestrah wrote:Can someone help me confirm what's wrong with my formula? I used wolframalpha to calculate it, but it's giving the x coordinate of the first intersection as ~1.46 instead of 1.4.

Message me, and I'll send you the links.

The point (1.4, -9.6) given in the problem is an input for the program. Together with the starting point (0, 10.1) it defines the initial direction of the lightbeam. WIthout that information, the light could have entered the hole under almost any angle. As such, I don't see how you can be calculating it.
The first point you need to calculate is the second reflection, shown in the left picture in the problem statement, which obviously has x<0.

jaap wrote:

seestrahseestrah wrote:Can someone help me confirm what's wrong with my formula? I used wolframalpha to calculate it, but it's giving the x coordinate of the first intersection as ~1.46 instead of 1.4.

Message me, and I'll send you the links.

The point (1.4, -9.6) given in the problem is an input for the program. Together with the starting point (0, 10.1) it defines the initial direction of the lightbeam. WIthout that information, the light could have entered the hole under almost any angle. As such, I don't see how you can be calculating it.
The first point you need to calculate is the second reflection, shown in the left picture in the problem statement, which obviously has x<0.

Annd.... I'm an idiot. I was so confused about what I was doing wrong for the longest time, but it turns out it was a simple sign mistake.

thedoctar wrote:Could someone please post the first five reflections?

EDIT: My program gets the same results for the 2nd, 9th and 33rd, but my answer isn't correct!!!

(0.006 -10.000)

This is the last point I get, rounded. This point is the 160th-170th point I get, hopefully I'm not giving too much away here. Am I anywhere close?

EDIT*: Just realised the problem, pretty much as soon as I edited this point. Embarrassing! :\

EDIT**: Solved

Same result as you were, but haven't find the bug!

EDIT: I also find the correct answer now, after reading the text again.

thedoctar wrote:Could someone please post the first five reflections?

EDIT: My program gets the same results for the 2nd, 9th and 33rd, but my answer isn't correct!!!

(0.006 -10.000)

This is the last point I get, rounded. This point is the 160th-170th point I get, hopefully I'm not giving too much away here. Am I anywhere close?

EDIT*: Just realised the problem, pretty much as soon as I edited this point. Embarrassing! :\

EDIT**: Solved

haha, thank you for this

I had the same results as you, and was pulling my hair out because I kept going over my code and couldn't find any error and was lost because I wasn't even sure what direction to head next. Then I read your post and was like "I've got to be close, what could be embarrassing that he fixed that fast and now it works? "

oooooooh, duh! lol!!

mpiotte wrote:

grump wrote:Doesn't the laser beam get reflected off the top before it ever makes it into the ellipse?

The light beam enters through the gap at x ~ 0.0071 (-0.01 <= 0.0071 <= 0.01).

Wouldn't it be great if just once there was a trick question as alluded to here with the answer equal to 0?

c0wt00n wrote: Tue May 19, 2015 2:05 am

thedoctar wrote:Could someone please post the first five reflections?

EDIT: My program gets the same results for the 2nd, 9th and 33rd, but my answer isn't correct!!!

(0.006 -10.000)

This is the last point I get, rounded. This point is the 160th-170th point I get, hopefully I'm not giving too much away here. Am I anywhere close?

EDIT*: Just realised the problem, pretty much as soon as I edited this point. Embarrassing! :\

EDIT**: Solved

haha, thank you for this

I had the same results as you, and was pulling my hair out because I kept going over my code and couldn't find any error and was lost because I wasn't even sure what direction to head next. Then I read your post and was like "I've got to be close, what could be embarrassing that he fixed that fast and now it works? "

oooooooh, duh! lol!!

I too ran into this problem, lol.