Project Euler 607 - Marsh Crossing

Official link:

Thought Process

If we imagine that the person walking is a light beam, and the speed he walks is the velocity of light in that area, then this problem can be solved using Snell's Law! But first lets modify the problem to then apply Snell's law

  1. By placed A at (0,0) and rotating the graph 45 degrees such that the marsh is parallel to the y-axis point B will at (100/sqrt(2), 100/sqrt(2))

    • Knowing that the marsh is 50 units long and its center is in the middle of AB we know that 2x + 50 = 100/sqrt(2), which implies that x = (100/sqrt(2) - 50)/2, which is where the marsh begins

Then using Snell's law

All we need to do is keep track of the x, y distance we have travelled, so that once we reach the end of the marsh we find the distance from our exit point to B, then we can calculate the time taken easily.

I chose to continuously iterate the initial angle until I reached the desired precision but it is possible to backtrack the entire problem as if we follow Snell's Law till the end the final ray after exiting the marsh will interesect with B

Interactive Code

There is no interactive code for this problem, So I will include a plot I made with matplotlib of their path as well as my code