Project Euler Problem #86

May 24, 2011

Read the details of the problem here

Summary

Exploring the shortest path from one corner of a cuboid to another.

Solution

It’s been a while since I’ve posted a Project Euler solution and the ones I have posted have been catch-ups. The other day I saw a specific search on this site for a solution to Problem 86 which I hadn’t yet completed so I thought I’d give it a go…

On first reading this seemed a little unclear but it comes apart quite easily with a little prodding and poking. Taking the example that Euler gives and flattening it makes it apparent what’s going on. The shortest path (SF) is the hypotenuse of a Pythagorean triangle with sides of { 6, 8 (3+5), 10 }.

pe0086_1

The diagram below shows the case of an M x M x M cuboid to demonstrate the three variants of the shortest path in a very obvious manner.

pe0086_2

So it’s just a case of checking for Pythagorean triangles with an adjacent side of length M, and up to 2M for the opposite side. Note that, due to this abstraction from the actual cuboid, it’s not necessary to deal with the other two sides individually – the opposite side length is taken as the total of the depth and height of the cuboid. Once a suitable triangle is found the number of solutions for it, taking into account the ways in which the opposite side length may be composed for any given potential cuboids, are added onto the running total.

def ( answer, solutions ) = [ 1, 0 ]

while (true) {
  for (i in 2..(2 * answer)) {
    def hyp = Math.sqrt(answer * answer + i * i)
    if (hyp == Math.floor(hyp)) {
      solutions += (i > answer + 1) ?
          (answer + answer + 2 - i).intdiv(2) : i.intdiv(2)
    }
  }
  if (solutions > 1e6) break
  answer++
}

The solution is quite succinct and, even though it’s simply a brute force algorithm, runs in around 1.31 seconds – so well within the 15 second target. Smarter algorithms might include changing this one to a bisection search of across the solution space, or maybe pre-generating Pythagorean triangles and driving directly off of those.

Conclusion

Groovy was perfectly fast enough for solving this problem, both in terms of coding and runtime. From a performance perspective it’s advisable to use the Math.floor() function rather than a straight cast to (int) and calling intdiv() is also a must compared to a straight division.

Advertisements

2 Responses to “Project Euler Problem #86”

  1. keyzero Says:

    Hi ashishwave. Thanks for visiting my blog.

    I’ve mentioned Groovy++ before when asked about it on Question 10 – my response to that still stands. I’d love to see Groovy++ become part of the main Groovy distribution but, at the moment, I don’t think it’s going to hit the mainstream unless SpringSource pick it up. Very happy to be proved wrong though. It could happen too – SpringSource may feel they need an in-house language in much the same way that JetBrains are launching “Kotlin” and JBoss are going with “Ceylon”. Given the choice already out there I personally believe that a lot of clever people’s time is being wasted when it could be used more productively in extending common libraries & tuning the JVM platform itself.

    https://keyzero.wordpress.com/2010/01/07/project-euler-problem-10/


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 )

Twitter picture

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

Facebook photo

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

Google+ photo

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

Connecting to %s

%d bloggers like this: