Project Euler Problem 86 Statement

A spider, S, sits in one corner of a cuboid room, measuring $6$ by $5$ by $3$, and a fly, F, sits in the opposite corner. By travelling on the surfaces of the room the shortest "straight line" distance from S to F is $10$ and the path is shown on the diagram.

However, there are up to three "shortest" path candidates for any given cuboid and the shortest route doesn't always have integer length.

It can be shown that there are exactly $2060$ distinct cuboids, ignoring rotations, with integer dimensions, up to a maximum size of $M$ by $M$ by $M$, for which the shortest route has integer length when $M = 100$. This is the least value of $M$ for which the number of solutions first exceeds two thousand; the number of solutions when $M = 99$ is $1975$.

Find the least value of $M$ such that the number of solutions first exceeds one million.

Solution

1. Understanding the problem

You have a cuboid with integer side lengths \((x, y, z)\) (where \(x \le y \le z\)).

The shortest path on its surface, from one corner to the opposite corner, is the straight line on the unfolded net (or net)¹ of the cuboid. For example, if you flatten the faces, you get:

• \(\sqrt{(x + y)^2 + z^2}\)
• \(\sqrt{(x + z)^2 + y^2}\)
• \(\sqrt{(y + z)^2 + x^2}\),

depending on which faces you pick. You only need one of these to be an integer for $(x,y,z)$ to be counted as a solution.

Typically, Problem 86 focuses on the count of these solutions for all \(1 \le x \le y \le z \le M\), and you look for the first M such that the count exceeds a certain threshold.

This particular code is focusing on the case: \[ \sqrt{(x + y)^2 + z^2} \in \mathbb{Z} \] while scanning all \((x, y, z)\) with \(z \le M\). (You can symmetrically pick \((x+z)^2 + y^2\) or \((y+z)^2 + x^2\). It turns out enumerating one form is enough once you permute the variables properly.)

¹An unfolded net or net is a 2D pattern that, when folded along specific lines, creates a 3D shape. Think of it like "flattening out" a 3D shape by cutting along certain edges until it can lie flat on a surface, while keeping all faces connected.

2. Understanding the Code

2.1 Data Structures

qz = [0] * (M + 1)  # Will hold cumulative counts up to each L = 1..M
big = [set() for _ in range(M + 1)]
calc = lambda wh: L - (wh - 1)//2 if wh > L else wh//2

• qz[L]: After processing, qz[L] will contain the total number of valid \((x,y,z)\)-triplets (with the shortest path integer) for all \(z\) up to L.
• big[L]: A set of values wh associated with that L. In the context of the net of the cuboid, wh represents possible sums \(x+y\) (or analogous sides in the net).
• calc(wh): A helper function to count how many pairs \((x,y)\) satisfy \(x+y = wh\) with \(1 \le x \le y \le L\).
  If \(wh \le L\), then the number of pairs \((x,y)\) with \(x \le y\) and \(x+y = wh\) is \(\lfloor wh/2 \rfloor\).
  If \(wh > L\), we must also ensure \(y \le L\), hence \(wh - x \le L \implies x \ge wh - L\). That leads to the piecewise formula in calc(wh).

2.2 Generating the Pythagorean-like pairs (wh, L)

for m in range(2, M):
    for n in range(1, min(m, M // m + 1)):
        for wh, L in ((m*m - n*n, 2*m*n), (2*m*n, m*m - n*n)):
            if wh <= 2 * L:
                for i in range(1, M // L + 1):
                    big[L*i].add(wh*i)

This is the trickiest part. Notice it is iterating over \((m,n)\) to generate "legs" of Pythagorean triples:

A classic parameterization of primitive Pythagorean triples is \[ (m^2 - n^2,\; 2mn,\; m^2 + n^2), \quad m > n > 0. \]

The code looks at the "legs" \((m^2 - n^2)\) and \(2mn\). It calls them wh and L in each ordering:

1. \((wh, L) = (m^2 - n^2, 2mn)\)
2. \((wh, L) = (2mn, m^2 - n^2)\)

Condition: if wh <= 2 * L:
This corresponds to picking only those pairs where \( (x+y) = wh \) and \( z = L \) is a feasible dimension for a "shortest path" \(\sqrt{(x+y)^2 + z^2}\). If \((x+y) > 2z\), it no longer corresponds to that "shortest path" scenario.

Then the code scales these pairs up by i so that L*i and wh*i remain below or equal to M. In other words, for each factor i such that \(L \cdot i \le M\), it stores (wh*i) in big[L*i]. This enumerates all integer multiples of that Pythagorean pair.

When done, for each L from 1 to M, the set big[L] contains all possible sums wh such that \(\sqrt{(wh)^2 + (L)^2}\) is an integer (due to them coming from scaled Pythagorean triples).

2.3 Accumulating counts in qz

running_sum = 0
for L in range(1, M + 1):
    running_sum += sum(calc(wh) for wh in big[L])
    qz[L] = running_sum

For each L, we look at all wh in big[L]. calc(wh) gives how many valid pairs \((x,y)\) fit \(x+y = wh\) with \(1 \le x \le y \le L\).

Add them all up to get the number of \((x,y,L)\) triplets (with \(x+y=wh\)) that yield an integer shortest path. Cumulative sum: qz[L] becomes the total number of such triplets for all \(1 \le z \le L\). So qz[L] is a "running total" up to L.

2.4 Answering queries

for _ in range(int(input())):
    print(qz[int(input())])

We print "How many solutions are there up to some L ≤ M" for each query.

HackerRank version

Solves all test cases for Hackerrank Project Euler Problem 86

HackerRank Project Euler 86: Print the number of cuboids with integer dimensions up to a maximum of $M\times M\times M$, $(1\le M\le 4\times 10^5)$, such that the shortest route is an integer.