Oh man wow 😮 Problem 9 was quite hard 😱 I had to build two new functions in the Mu stdlib for computing combinations and permutations, but then the combinations of range(1000) for triples such as a + b == c is enormous! So i had to write iterator versions of these to do lazy evaluation. Anyway solution follows:
#!/usr/bin/env mu
// Special Pythagorean Triplet
import "iter"
fn usage() {
print("Usage:", args()[0], "<n>")
}
fn sqr(x) { x * x }
fn main() {
if len(args()) < 2 {
usage()
exit(1)
}
n := must(int(args()[1]))
print("n:", n)
// For a < b < c and a + b + c == n, both a and b are strictly less
// than n/2. Generate only (a,b) combinations and derive c directly. This
// keeps the search lazy and reduces n=1000 from C(999,3) = 165,668,499
// candidate triples to C(499,2) = 124,251 candidate pairs.
pairs := iter.combinations(iter.range(1, n / 2), 2)
triples := iter.map(pairs, fn(xs) {
a := xs[0]
b := xs[1]
return [a, b, n - a - b]
})
// Enforce b < c; a < b is already guaranteed by combinations over an
// increasing range, and a + b + c == n holds by construction.
triples = iter.filter(triples, fn(xs) {
return xs[1] < xs[2]
})
// Euler 9 has one answer for n=1000. find() stops the entire upstream
// iterator chain as soon as the first Pythagorean triple is found.
answer := iter.find(triples, fn(xs) {
return sqr(xs[0]) + sqr(xs[1]) == sqr(xs[2])
})
print(answer)
if answer != nil {
print(answer[0] * answer[1] * answer[2])
}
}
main()
Timeline Sandbox 
