euler71.rs

use std::cmp::{PartialOrd, Ord, Ordering};
use std::collections::HashSet;

// Calculates the highest common factor with Euclid's algorithm
// Probably the hottest code. Is there a faster way to calculate the HCF?
fn hcf(mut a: i64, mut b: i64) -> i64 {
	while b != 0 {
		let temp = (b, a - b*(a/b));
		a = temp.0;
		b = temp.1;
	}
	a
}

// My Fraction type. Pretty simple implementation since Rust automagically generates
// the hashing and equality code.
#[derive(Debug, Hash, PartialEq, Eq)]
struct Fraction {
	numer: i64,
	denom: i64,
}

impl Fraction {
	// This function creates a fully reduced fraction.
	fn new(numer: i64, denom: i64) -> Fraction {
		let x = hcf(numer, denom);
		Fraction {
			numer: numer/x,
			denom: denom/x,
		}
	}
}

// This is boilerplate I need for sorting to work
impl PartialOrd for Fraction {
	fn partial_cmp(&self, other: &Fraction) -> Option<Ordering> {
		Some(self.cmp(&other))
	}
}

// Real comparison code. Basically make floats out of the fractions and compare the floats
impl Ord for Fraction {
	fn cmp(&self, other: &Fraction) -> Ordering {
		(self.numer as f64 / self.denom as f64).partial_cmp(
			&(other.numer as f64 / other.denom as f64)
		).unwrap()
	}
}

fn main() {
	// We use a HashSet to store our generated fraction. 
	// This wway we don't have to check for dupes manually.
	let mut fracs = HashSet::with_capacity(1_000_000);
	println!("Generating fractions...");
	for d in 4..=1_000_000 {
		let x = d/7;
		let lower = 3*x-1;
		let upper = 3*(x+1);
		for n in lower..upper {
			if n > 0 {
				fracs.insert(Fraction::new(n, d));
			}
		}
	}
	println!("Sorting fracs...");
	let mut list: Vec<_> = fracs.iter().collect();
	// We don't care about having the sort keep identical fractions in the same order 
	// since there aren't any duplicates. Therefore we can use an unstable sort
	// for speed and memory's sake.
	list.sort_unstable();
	let three_sevenths = Fraction::new(3, 7);
	for (i, f) in list.iter().enumerate() {
		if **f == three_sevenths {
			println!("{:?}", list[i-1].numer);
		}
	}
}