We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. All Contests
  2. ProjectEuler+
  3. Project Euler #86: Cuboid route
  4. Discussions

Project Euler #86: Cuboid route

Sort by

recency

|

14 Discussions

|

  • sardheeshm
     + 0 comments
    import math
from typing import List

def get_square_root(a: int) -> int:
    f = 0
    ret = 0
    for i in range(16):
        ret <<= 1
        kari_f = (f + 1) << ((15 - i) * 2)
        if a >= kari_f:
            f = f + 2
            a -= kari_f
            ret += 1
        f <<= 1
    return ret

def combinations(a: int, b_c: int) -> int:
    if 2 * a < b_c:
        return 0
    if a >= b_c:
        return b_c // 2
    return a - (b_c - 1) // 2

def gcd(a: int, b: int) -> int:
    while a != 0:
        temp = a
        a = b % a
        b = temp
    return b

def count_all(limit: int) -> List[int]:
    solutions = [0] * (limit + 1)
    for m in range(1, get_square_root(2 * limit) + 1):
        for n in range(1, m):
            if (m % 2) != (n % 2) and gcd(m, n) == 1:
                x = m * m - n * n
                y = 2 * m * n
                for k in range(1, (limit // x) + 1):
                    solutions[k * x] += combinations(k * x, k * y)
                for k in range(1, (limit // y) + 1):
                    solutions[k * y] += combinations(k * y, k * x)
    return solutions

def main():
    limit = 10**6
    solutions = count_all(limit)
    total = []
    sum_val = 0
    for i in solutions:
        sum_val += i
        total.append(sum_val)

    T = int(input())
    for _ in range(T):
        N = int(input())
        print(total[N])

if __name__ == "__main__":
    main()

  • happy_coder_
     + 0 comments

    you can find my java solution here

  • ErikTillema
     + 2 comments

    Solved this problem in F#. Insights:

    • count only really distinct cuboids, for example the cuboids (A,B,C) (3,5,6) and (6,5,3) are considered equal.
    • key insight for me was that there are only 1.5 million pythagorean triplets that correspond to a cuboid with max size 400.000
    • if you use Euclid's formula (see for example https://en.wikipedia.org/wiki/Pythagorean_triple ) to generate pythagorean triplets and you are only interested in right triangles with maximum right side length M, then you can use 1.1*sqrt(M) as an upper bound for m.

    If anybody is interested, I can write down my approach to solve this problem.

    • kitchent
       + 1 comment

      Curious to know how it works to compute million pythagorean triplets within the time limit. I've been using Euclid's formula, but that m += 1, n += 2 is supposedly killing it. It takes almost 5 seconds to generate triplets up to (with most of the time spent on finding the valid primitive triplets), let alone .

      Perhaps it is because of the upper bound you mentioned? I don't know where that 1.1*sqrt(M) comes from, the bound I used was a while-loop with condition m**2 - (m-1)**2 <= M. When I look closely, this condition is unnecessarily loose, as it does not take into account the fact that either a >= b or b >= a should be true, while and .

      EDIT: I tried using this upper bound, and got WA for Test Cases #3 through #9.

      EDIT 2: Tried with sqrt(3*M) and it works. Even sqrt(2*M) did not work, where it was missing some pairs like m=917, n=218. Maybe the difference is due to the way I handled the triples, as I append whenever a >= b_plus_c / 2 + b_plus_c % 2 or b_plus_c >= a / 2 + a % 2.

      I'm quite sure that this condition would fail again for much larger input. The naming here is quite confusing, as b_plus_c >= a / 2 + a % 2 in fact means b >= a_plus_c / 2 + a_plus_c % 2, but I just handle them all in one place.

      EDIT 3: By the way, I find it interesting that no one mentioned another key insight involved in solving this problem, that is to visualise the unfolding of the 3D box. At the beginning, I was trying to solve the equation and find the derivative of it to look for a minimum, thinking about how this problem is supposed to be 35% difficulty.

      • ErikTillema
         + 0 comments

        Yes, the upper bound is crucial in finding all the Pythagorean triplets within the time limit.

        Note that the M in my upper bound definition is not the same as the M in the problem statement. Sorry for the confusion about that. This might explain the difference in your findings about the upper bound.

        The other insight you mention is crucial as well. I didn't want to spoil too much :-)

        I hope this clears some things up.

    • micahleamer
       + 0 comments

      For me I needed to use m up to 1000 in the pythagorean triples 2mn, m^2-n^2, m^2+n^2 to generate the sides large enough to satisfy all the test cases that's sides bounded by M up to 400,000. The bound 1.1sqrt(M) is not enough. Because we need to satisfy max(2mn, m^2-n^2) < 800000 and min(2mn,m^2-n^2)<4000000. This can happen beyond the bound 1.1sqrt(M).

  • padeff
     + 0 comments

    . Would definitively advise to complete 75, and use roll distribution on the answer of 75. I dont think there is a way to solve it without generating pythagorean triplet correctly.

  • WardBeullens
     + 2 comments

    Nice question! Im am curious if anyone managed to solve it with Python 3?

    My Python 3 solution was just a bit too slow. on my personal comuter it took 15s to compute the table of solutions, which is more than the limit of 10s. However when I translated my solution to Java it finishes in just 0.2s which is much less than the limit of 4s.

    Maybe the limit is a bit too low for Python?

    • anil2381
       + 0 comments

      Solved it in python 3 in 2 seconds.

    • zeo_zagart
       + 0 comments

      python 2 in 1.8 s

Join us

Create a HackerRank account

Be part of a 26 million-strong community of developers

Already have an account?Log in