Joseph Mullins

Programmer | Security | Automation

joseph@ropeney.com

Trialing the new kid on the block, Rust

Back

Rust

Straight from the website a quote on the Rust language.

Rust is a systems programming language that runs blazingly fast, prevents segfaults, and guarantees thread safety.

Everyone knows C and C++ languages are very complicated, and come with almost every safety turned off. This is powerful in systems programming but also enables unknowing developers to allow memory leaks, segfaults and all those other pesty problems. From programming with Rust for a very little time and experiencing such problems with C and C++, I feel the main reason Rust can achieve what it does is with safe defaults.

The safe defaults come in the form of let variable = 1 will create an immutable variable. Immutable meaning it cannot be changed. To make this variable similar to whats found in most languages, a mutable variable you have to specify mut making the previous statement let mut variable = 1

Rust also provides "zero cost abstractions", which give us all the nice abstract features we like to use in higher level languages; with the minimum required cost at run-time. It also allows us to manually go against the compilers safety when we really know what we are doing, with the keyword unsafe and unsafe operators

A lot of the safe defaults that are achieved in Rust I wonder whether they can be achieved by a C/C++ analyser. The safe defaults do start out annoying at the start, but are achieving a good goal of secure reliable software. After a while of using it, it starts to feel natural.

Cargo

Cargo is amazing! A compiled language with its own package manager, that links libraries so easily and smoothly; as seamless as bundler in ruby. Cargo allows you to create a project with a standard directory structure and instantiates a git repository. You can then list your dependencies in Cargo.toml and it will be installed the next time you build.

Cargo has a test suite tool to run all your test code which are functions with #[test] above them. From what I can tell, when you run cargo build --release they are not put into the final release. Which brings another point, make sure when you want to ship a binary use the --release option. The Euler problem 10 below, took 4.54s to run on a standard build but 1.24s when a release build.

The compiler fight

Anyone who has used Rust will start with fighting the compiler, we are used to such automatic castings etc. that the Rust compiler seems to just not do. I found myself having to be very specific with every type I used, something simple like adding a u32 to a u64 requires explicit casting. Also, well if you had read the book it wouldn't be a surprise, but you must use a usize to index a vector; not a i32. Luckily though in all my Euler problems, I didn't have trouble with Rust's ownership system.

Lessons to Remember

Iterating over a slice of characters in a string

for n in 0..sequence.len() as u32 - length {
    for x in sequence[n as usize .. (n + length) as usize].chars() {
      ...
    }
}

Converting a character to a digit

n.to_digit(10).unwrap() // Without unwrap we get Some(n), this can't be used in maths.

std::cmp::Ordering is awesome!

  match sum.cmp(&desired_product) {
    Ordering::Less => multiplier += 1,
    Ordering::Equal =>;
    { println!("Match Found!");
      println!("a: {} b: {} c: {}", x, y, z);
      println!("product: {}", x * y * z);
      process::exit(0);
    },
    Ordering::Greater => break,
  }

Conclusion

Well the code snippets are coming below, but just in-case you came for the Rust opinion! I really like the languages philosophy, the community around it is great and I think it has a good future. Getting ontop of the language early has its concerns, as deprecating changes occur; even after 1.0 was released. Also while the claim of "no segfaults" is made, they are rare and do happen; if you look at Stackoverflow or Reddit you'll see some. The programming language though is very nice to use if you're coming from Ruby and feels very similar, except static types and faster. I really think the goals Rust is trying to achieve while enabling people to override the compiler safety nets when they need to, is where Rust should start pushing out other compiled languages.

Project Euler 8

The four adjacent digits in the 1000-digit number that have the greatest product are 9 × 9 × 8 × 9 = 5832.

73167176531330624919225119674426574742355349194934
96983520312774506326239578318016984801869478851843
85861560789112949495459501737958331952853208805511
12540698747158523863050715693290963295227443043557
66896648950445244523161731856403098711121722383113
62229893423380308135336276614282806444486645238749
30358907296290491560440772390713810515859307960866
70172427121883998797908792274921901699720888093776
65727333001053367881220235421809751254540594752243
52584907711670556013604839586446706324415722155397
53697817977846174064955149290862569321978468622482
83972241375657056057490261407972968652414535100474
82166370484403199890008895243450658541227588666881
16427171479924442928230863465674813919123162824586
17866458359124566529476545682848912883142607690042
24219022671055626321111109370544217506941658960408
07198403850962455444362981230987879927244284909188
84580156166097919133875499200524063689912560717606
05886116467109405077541002256983155200055935729725
71636269561882670428252483600823257530420752963450

Find the thirteen adjacent digits in the 1000-digit number that have the greatest product. What is the value of this product?

Given a collection of integers, find a the highest product of a sequence of n length. Being the first actual program I wrote in Rust this one I fought with the compiler endlessly. Indexing the string was a complete fight for a while, but now I've finished it; it all makes sense. The best part was having the test code, that I could compare to what the Euler's result was and check my function was returning results correctly

// Project Euler problem 8
// URL: https://projecteuler.net/problem=8
//
// The four adjacent digits in the 1000-digit number that have the greatest product are
// 9 × 9 × 8 × 9 = 5832.
//
//  73167176531330624919225119674426574742355349194934
//  96983520312774506326239578318016984801869478851843
//  85861560789112949495459501737958331952853208805511
//  12540698747158523863050715693290963295227443043557
//  66896648950445244523161731856403098711121722383113
//  62229893423380308135336276614282806444486645238749
//  30358907296290491560440772390713810515859307960866
//  70172427121883998797908792274921901699720888093776
//  65727333001053367881220235421809751254540594752243
//  52584907711670556013604839586446706324415722155397
//  53697817977846174064955149290862569321978468622482
//  83972241375657056057490261407972968652414535100474
//  82166370484403199890008895243450658541227588666881
//  16427171479924442928230863465674813919123162824586
//  17866458359124566529476545682848912883142607690042
//  24219022671055626321111109370544217506941658960408
//  07198403850962455444362981230987879927244284909188
//  84580156166097919133875499200524063689912560717606
//  05886116467109405077541002256983155200055935729725
//  71636269561882670428252483600823257530420752963450
//
// Find the thirteen adjacent digits in the 1000-digit number that have the greatest product.
// What is the value of this product?

fn main() {
    let sequence = "73167176531330624919225119674426574742355349194934\
                    96983520312774506326239578318016984801869478851843\
                    85861560789112949495459501737958331952853208805511\
                    12540698747158523863050715693290963295227443043557\
                    66896648950445244523161731856403098711121722383113\
                    62229893423380308135336276614282806444486645238749\
                    30358907296290491560440772390713810515859307960866\
                    70172427121883998797908792274921901699720888093776\
                    65727333001053367881220235421809751254540594752243\
                    52584907711670556013604839586446706324415722155397\
                    53697817977846174064955149290862569321978468622482\
                    83972241375657056057490261407972968652414535100474\
                    82166370484403199890008895243450658541227588666881\
                    16427171479924442928230863465674813919123162824586\
                    17866458359124566529476545682848912883142607690042\
                    24219022671055626321111109370544217506941658960408\
                    07198403850962455444362981230987879927244284909188\
                    84580156166097919133875499200524063689912560717606\
                    05886116467109405077541002256983155200055935729725\
                    71636269561882670428252483600823257530420752963450";

    let (result, value) = find_greatest_number_length(13, sequence);
    println!("The pattern is {}", result);
    println!("The product is {}", value);
}

// Find the greatest sequence of numbers upto a certain length
// Returns (String sequence, u64 product of the sequence)
fn find_greatest_number_length(length: u32, sequence: &str) -> (&str, u64) {
    let mut current_highest: u64 = 0;
    let mut highest_position: u32 = 0;

    for n in 0..sequence.len() as u32 - length {
        let mut product: u64 = 1;

        for x in sequence[n as usize .. (n + length) as usize].chars() {
            product *= x.to_digit(10).unwrap() as u64;
        }

        if product > current_highest {
            current_highest = product;
            highest_position = n;
        }
    }

    (&sequence[highest_position as usize .. (highest_position + length) as usize], current_highest)
}

#[test]
fn works_against_euler_example() {
    let sequence = "73167176531330624919225119674426574742355349194934\
                    96983520312774506326239578318016984801869478851843\
                    85861560789112949495459501737958331952853208805511\
                    12540698747158523863050715693290963295227443043557\
                    66896648950445244523161731856403098711121722383113\
                    62229893423380308135336276614282806444486645238749\
                    30358907296290491560440772390713810515859307960866\
                    70172427121883998797908792274921901699720888093776\
                    65727333001053367881220235421809751254540594752243\
                    52584907711670556013604839586446706324415722155397\
                    53697817977846174064955149290862569321978468622482\
                    83972241375657056057490261407972968652414535100474\
                    82166370484403199890008895243450658541227588666881\
                    16427171479924442928230863465674813919123162824586\
                    17866458359124566529476545682848912883142607690042\
                    24219022671055626321111109370544217506941658960408\
                    07198403850962455444362981230987879927244284909188\
                    84580156166097919133875499200524063689912560717606\
                    05886116467109405077541002256983155200055935729725\
                    71636269561882670428252483600823257530420752963450";

    let (result, value) = find_greatest_number_length(4, sequence);
    assert_eq!(result, "9989");
    assert_eq!(value, 5832);
}

 

Problem 9

A Pythagorean triplet is a set of three natural numbers, a < b < c, for which,
a2 + b2 = c2

For example, 32 + 42 = 9 + 16 = 25 = 52.

There exists exactly one Pythagorean triplet for which a + b + c = 1000.
Find the product abc.

A big thanks to the folks maintaining the page at wikipedia for the algorithm Formulas for generating Pythagorean triples. This was a fun problem to solve and took a bit of research to work out the best way to implement. Definitely a way to get more comfortable with the Rust compiler.

// Project Euler problem 9
// URL: https://projecteuler.net/problem=9
//
// A Pythagorean triplet is a set of three natural numbers, a < b < c, for which,
//                    a2 + b2 = c2
//
// For example, 3^2 + 4^2 = 9 + 16 = 25 = 5^2.
//
// There exists exactly one Pythagorean triplet for which a + b + c = 1000.
// Find the product abc.

use std::cmp::Ordering;
use std::process;

fn main() {
    let desired_product = 1000;

    let mut m: u32 = 2;
    let mut n: u32 = 1;

    loop {
        let (a, b, c) = generate_base_pythagoren_triangle(m, n);

        let mut multiplier: u32 = 1;
        loop {
            let (x,y,z) = multiply_base_pythagoren_triangle(a, b, c, multiplier);
            let sum = sum_of_pythagoren_triangle(x,y,z);

            match sum.cmp(&desired_product) {
                Ordering::Less => multiplier += 1,
                Ordering::Equal => {
                    println!("Match Found!");
                    println!("a: {} b: {} c: {}", x, y, z);
                    println!("product: {}", x * y * z);
                    process::exit(0);
                },
                Ordering::Greater => break,
            }
        }

        let sum = sum_of_pythagoren_triangle(a,b,c);
        if sum < desired_product {
            if n < m {
                m += 1;
            } else {
                m += 1;
                n = 1;
            }
        } else {
            panic!("Not found");
        }
    }

}

fn generate_base_pythagoren_triangle(m: u32, n: u32) -> (u32, u32, u32)
{
    let a = (m * m) - (n * n);
    let b = 2 * m * n;
    let c = (m * m) + (n * n);

    (a, b, c)
}

#[test]
fn test_generate_base_pythagoren_triangle() {
    assert_eq!((3,4,5), generate_base_pythagoren_triangle(2,1));
    assert_eq!((5,12,13), generate_base_pythagoren_triangle(3,2));
    assert_eq!((7,24,25), generate_base_pythagoren_triangle(4,3));
}


fn multiply_base_pythagoren_triangle(a: u32, b: u32, c: u32, multiplier: u32) -> (u32, u32, u32)
{
    (a * multiplier, b * multiplier, c * multiplier)
}

#[test]
fn test_multiply_base_pythagoren_triangle() {
    assert_eq!((6,8,10), multiply_base_pythagoren_triangle(3,4,5,2));
    assert_eq!((9,12,15), multiply_base_pythagoren_triangle(3,4,5,3));
}

fn sum_of_pythagoren_triangle(a: u32, b: u32, c: u32) -> u32
{
    (a + b + c)
}

#[test]
fn test_sum_of_pythagoren_triangle() {
    assert_eq!(12, sum_of_pythagoren_triangle(3,4,5));
    assert_eq!(30, sum_of_pythagoren_triangle(5,12,13));
}

 

Problem 10

The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.

Find the sum of all the primes below two million.

Fairly simple problem, try running with and without --release and observe dramatic speed differences

// Project Euler problem 10
//  URL: https://projecteuler.net/problem=10
//
// The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.
// Find the sum of all the primes below two million.

fn main() {

  println!("{}", calculate_sum_of_primes(2000000));
}

fn check_prime(number: u64) -> bool
{
  if number % 2 == 0 {
    return false
  }

  let max: u64 = (number as f64).sqrt() as u64;
  for n in 2..max + 2 {
    if number % n == 0 {
      return false
    }
  }
  true
}

#[test]
fn test_check_prime() {
  assert_eq!(check_prime(3), true);
  assert_eq!(check_prime(1523), true);
  assert_eq!(check_prime(6), false);
  assert_eq!(check_prime(4), false);
  assert_eq!(check_prime(242), false);
}

fn calculate_sum_of_primes(amount: u64) -> u64 {
  let mut sum: u64 = 1;

  for n in 1 .. amount + 1 {
    if check_prime(n) {
      sum += n;
    }
  }
  sum
}

#[test]
fn test_calculate_sum_of_primes() {
  assert_eq!(17, calculate_sum_of_primes(10));
}

Comments