This is a not particularly efficient solution to a little Euler Project problem in Rust:
fn e44() -> i32 {
let ps: Vec<i32> = (2 .. 3_000).map(|n| n * (3 * n - 1) / 2).collect();
ps
.iter()
.flat_map(|&i| ps.iter().map(move |&j| (i, j)))
.filter(|&(i, j)| ps.binary_search(&(i + j)).is_ok() &&
ps.binary_search(&(j - i)).is_ok())
.map(|(i, j)| (i - j).abs())
.next()
.unwrap()
}
fn main() {
assert_eq!(e44(), 5_482_660);
}
This is a similar solution in D language:
import std.stdio: writeln;
import std.array: array;
import std.algorithm.iteration: map, filter;
import std.range: iota, assumeSorted, isRandomAccessRange;
import std.math: abs;
import std.algorithm.setops: cartesianProduct;
int e42() {
auto ps = iota(2, 3000).map!(n => n * (3 * n - 1) / 2)/*.array*/.assumeSorted;
static assert(isRandomAccessRange!(typeof(ps)));
return cartesianProduct(ps, ps)
.filter!(ij => ps.contains(ij[0] + ij[1]) &&
ps.contains(ij[1] - ij[0]))
.map!(ij => abs(ij[0] - ij[1]))
.front;
}
void main() {
assert(e42() == 5_482_660);
}
It uses assumeSorted
that returns a SortedRange
. If you call contains
on a SortedRange
, you get a binary search.
ps
is a lazy iterable (because I've commented out the .array
part that converts it to a dynamic array), but it's still a random-access range (as statically asserted by the successive line of code). The ij[0]
are there because D lacks a tuple unpacking syntax.
In Rust a binary_search_by_key
isn't enough to replace that well.
Do you like the idea of performing a binary search on a lazy iterable in Rust?