Home > Optimization, Programming, Uncategorized > Project Euler 607

Project Euler 607


If you like solving Project Euler problems you should try Problem number 607. It’s not very hard, as it can be reduced to a small optimization problem. The idea is to find a path which minimizes time, knowing that certain regions correspond to different speeds. A precise statement of the result can be found on the official page. Here’s an image of the path which realizes the shortest time:

euler607

 

Advertisements
  1. Harshit
    June 16, 2017 at 8:46 pm

    Hello

    Could you please give me a hint or any kind of advise on how to approach this?

    Would have been easy if there were only two type of regions, but 6 different regions give 6
    variables and i don’t think solving those giant partial differential equations is the way to go.

    Thanks

    • June 16, 2017 at 11:52 pm

      There is no giant PDE involved. There are indeed six variables and you can find the partial derivatives of the time needed to go from A to B with respect to any of them. This is called the gradient of the function. Then you use any gradient descent algorithm to find the path which gives minimal time.

  2. Srini
    December 30, 2017 at 5:43 pm

    Hi Ben,

    Pls can you help me understand how to find the gradient of the function using the gradient descent method GDM for PE Problem 607?

    I solved the problem in Python using Snell’s Law but I am lost on the GDM and would really like to understanf. I read this article* to understand GDM. Though I understood the concept of GDM and could do it if I had a (x,y) dataset, I could not understand which function to differentiate for Problem 607?

    Would it be: Minimize Time in days = Sigma ( y / cos(Θ) ) / Speed_on_Terrain ?

    Thanks

    (*article: https://storage.googleapis.com/supplemental_media/udacityu/315142919/Gradient%20Descent.pdf)

    • December 30, 2017 at 9:05 pm

      Hello,

      The functional to be minimized is the total time. The time spent in one of the regions is the distance divided by the speed. Since the speed is known for each region and is constant, when computing the gradient, only the distance needs to be differentiated.

      You need to find how many variables are needed in the problem. Since in each of the constant speed sections, the optimal paths are straight segments, you just need to keep track of several points which move along lines. In order to make this easy, I considered an orientation of the figure which makes all the lines horizontal, so only x coordinates are needed in the parametrization.

      Once you have all the coordinates of the points, the distance is computed using the usual formula: square root of sum of squares of differences between coordinates (Pythagoras).

      If the multiple regions problems poses difficulties, try a version with two regions first.

  3. Srini
    January 1, 2018 at 3:35 pm

    Thank you for the comments and guidance. I solved PE 607 with 6 variables using scipy as in http://rextester.com/LTCZI89522.

    This is not perhaps what you had suggested using partial derivatives of time. I would love to know how to solve 607 without using a solver should you have time. You are a great teacher and give lucid clarifications!

    • January 1, 2018 at 10:15 pm

      Good job! Solving the problem without an optimization toolbox would mean constructing the gradient descent algorithm yourself. As I see from your code, you did not code explicitly the gradient, but you optimized the objective directly.

      It is possible to construct a function which computes the value and the derivatives with respect to each variable as outputs. Then you could code a gradient descent algorithm “by hand”. Start from an admissible point x0 and compute the value and the gradient. Pick a step size eps>0. Compute x = x0-eps*gradient. Check if the value at x is lower than that at x0. If it is the case then change x0 to x and repeat. In order to accelerate the convergence you could also vary the size of the step: if you have a successful descent eps becomes 1.1*eps. If not eps=0.9*eps. You stop when the descent tolerance is lower than the desired precision.

      This is a very basic algorithm. Maybe it should be more finely tuned to arrive at the desired precision. If I ever implement it I’ll post it on the blog.

  4. January 11, 2018 at 4:02 pm

    Hi Beni,

    I think I have done it now with the Gradient Descent Method as you suggested though on http://rextester.com/BBMB88593 I’m not able to decrease delta range to 1e-10 in line 72 which gives a more accurate result (it times out).

    The code is also very slow and takes about 10secs on my Mac with 1e10 on line 72. I would love your thoughts when you have time.

    Thanks!

  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

w

Connecting to %s

%d bloggers like this: