Rust - gregorymorrison/euler1 GitHub Wiki
Rust is a systems-programming language, introduced in 2010 and sponsored by Mozilla. It prides itself on performance and safety (of both type- and concurrency-). It competes in the same space as languages such as Go and D. Let's try kicking the tires on Rust. Here is a simple iterative version of Euler1:
// Euler1 in Rust
fn euler1(n: i32) -> i32 {
let mut retval: i32 = 0;
for i in 1..=n {
if i % 3 == 0 || i % 5 == 0 {
retval += i;
}
}
retval
}
fn main() {
println!("Euler1 = {}", euler1(999));
}Here is one using the canonical functional functions, map/filter/fold. It took me like five minutes to write this, having no experience with Rust before:
// Euler1 in Rust
fn is_euler1(n: i32) -> bool {
n%3 == 0 || n%5 == 0
}
fn euler1(n: i32) -> i32 {
(1..n)
.map(|n| n)
.filter(|&n| is_euler1(n))
.fold(0, |sum, x| sum + x)
}
fn main() {
println!("Euler1 = {}", euler1(1000));
}Here we can see that the return statement is implied - it returns the last value calculated.
Here's a functional version that uses tail recursion with an accumulator. One of the main points here is that the function euler1(n, acc) is deterministic - it will always return the same output for a given input. This is accomplished in part by the absence of any variable manipulation - there are instead only functions which return values. The other main point is that this recursion uses tail call optimization - it's written in such a way that an intelligent compiler can optimize its stack usage to be O(n) instead of O(n!). In English, this means that your program will probably not crash even for hugely recursive calls.
// Euler1 in Rust
fn is_euler1(n: i32) -> bool {
n%3 == 0 || n%5 == 0
}
fn euler1(n: i32, acc: i32) -> i32 {
if n == 1 {
acc
} else if is_euler1(n) {
euler1(n-1, acc+n)
} else {
euler1(n-1, acc)
}
}
fn main() {
println!("Euler1 = {}", euler1(999, 0));
}Rust has pattern matching and guards:
// Euler1 in Rust
fn is_euler1(n: i32) -> bool {
n%3 == 0 || n%5 == 0
}
fn euler1(n: i32, acc: i32) -> i32 {
let x = n;
match x {
x if x == 1 => acc,
x if is_euler1(x) => euler1(n-1, acc+n),
_ => euler1(n-1, acc)
}
}
fn main() {
println!("Euler1 = {}", euler1(1000));
}Here's a version where we generate three ranges - multiples of 3, 5, and 15, and we subtract the multiples of 15 since they're going to be the duplicate values found in the other two sequences:
// Euler1 in Rust
fn my_ints(i: i32, step: usize, n: i32) -> i32 {
(i..n).step_by(step)
.fold(0, |sum, x| sum + x)
}
fn euler1(n: i32) -> i32 {
my_ints(0,3,n) + my_ints(0,5,n) - my_ints(0,15,n)
}
fn main() {
println!("Euler1 = {}", euler1(1000));
}Here's a different version - I simply generate three arrays of ints up to 999, one step 3, one step 15 starting at 5, and one step 15 starting at 10. This covers all the ints divisible by 3 or 5 with no overlaps, and we simply sum them all up. Cool!
// Euler1 in Rust
fn my_ints(i: i32, step: usize, n: i32) -> i32 {
(i..n).step_by(step)
.fold(0, |sum, x| sum + x)
}
fn euler1(n: i32) -> i32 {
my_ints(0,3,n) + my_ints(5,15,n) + my_ints(10,15,n)
}
fn main() {
println!("Euler1 = {}", euler1(1000));
}Rust here is strict - it requires step to be an unsigned int, while it requires n to be a signed int; I don't know why, either...
Rust isn't object-oriented, but it does have C-style data structures. They're immutable by default. They can even have behaviors. It's not quite OOP, though - it's missing inheritance and polymorphism. Let's try this out. Here is a somewhat contrived example where we create a structure that holds size and result, and has a solve behavior.
// Euler1 in Rust
struct Euler1 {
size: i32,
result: i32,
}
impl Euler1 {
fn solve(&mut self) {
for i in 1..=self.size {
if i % 3 == 0 || i % 5 == 0 {
self.result += i;
}
}
}
}
fn euler1(n: i32) -> i32 {
let mut euler = Euler1 {size : n, result : 0};
euler.solve();
euler.result
}
fn main() {
println!("Euler1 = {}", euler1(999));
}Here's another version using a Quicksort-based algorithm. Here we recursively break the list up in half and then reassemble it. Instead of sorting each half, though, we’ll filter the pivot value, converting it to 0 if it’s not divisible. Here, euler() returns euler() calculated on the half of the list before the pivot element, euler() calculated on the half of the list after the pivot element, and the pivot element or 0, all added together.
// Euler1 in Rust
// calculate a value for the pivot element
fn my_val(n: i32) -> i32 {
if n % 3 == 0 || n % 5 == 0 {
return n;
}
return 0;
}
fn euler(ints: Vec<i32>) -> i32 {
// if the list is empty, return 0
if ints.len() == 0 {
return 0;
} else {
let pivot = ints.len() / 2;
// recursively process the half of the list below the middle element
let mut pre = 0;
if 0 < pivot {
pre = euler ( (ints[0..(pivot)]).to_vec() );
}
// recursively process the half of the list above the middle element
let mut post = 0;
if pivot+1 <= ints.len()-1 {
post = euler ( (ints[(pivot+1)..(ints.len())]).to_vec() );
}
// return thisVal + the results from the first and last halves
return pre + my_val( ints[pivot] ) + post;
}
}
fn euler1(size: i32) -> i32 {
let ints: Vec<i32> = (1..size).collect();
return euler (ints);
}
fn main() {
println!("Euler1 = {}", euler1(1000));
}You can see here that I use the built-in range functionality to generate a collection of ints, and then pass it as a vector to euler(). The strong typing took a little getting used to - Rust seems to have a rich collection of types that I had to sort through. The compiler seems a little slow and quite nitpicky about all sort of things, but its error messages are actually quite good. Immutability is by default; you have to declare any variables that are going to be mutated (changed) using the keyword mut.
One more example - I just found this elegant algorithm based on an observation by little Carl Friedrich Gauss. It operates in O(1) constant time. Don't sweat it if this seems inscrutable; click the blog link above for an explanation. Here is my version:
// Euler1 in Rust
fn my_sum(n: i32, size: i32) -> i32 {
(((size/n) * (size/n)) + (size/n)) * n / 2
}
fn euler1(size: i32) -> i32 {
my_sum(3, size) + my_sum(5, size) - my_sum(15, size)
}
fn main() {
println!("Euler1 = {}", euler1(999));
}Interestingly, the compiler even has built-in documentation. When attempting to compile, the compiler would sometimes put out helpful messages like For more information about this error, try 'rustc --explain E0594'., which when entered in would return manpage-like help documentation. Cool!
You can install Rust on Ubuntu using apt install rustc. I chose to install Rust using these directions:
curl --proto '=https' --tlsv1.2 -sSf https://sh.rustup.rs | sh
export PATH=~/.cargo/bin:$PATHThere are a couple of sandboxes that you can also try Rust online with no installation. Here is the output from http://www.compileonline.com/compile_rust_online.php:
$ rustc euler1.rs
$ ./euler1
Euler1 = 233168
$And here is the output from https://play.rust-lang.org/:
Standard Error
Compiling playground v0.0.1 (file:///playground)
Finished dev [unoptimized + debuginfo] target(s) in 0.60 secs
Running `target/debug/playground`
Standard Output
Euler1 = 233168