Implementation of daily programming challenge 348 Hard. Reimplementation of existing algorithm, but in Rust.

348h.rs

use std::env;

#[derive(Debug, Clone, Copy)]
struct Pair(u32, u32);

impl Pair {
    fn contains(&self, item: u32) -> bool {
        self.0 == item || self.1 == item
    }
    // Get the item that isn't the one passed in
    fn other(&self, item: u32) -> u32 {
        if self.0 == item {
            self.1
        } else {
            self.0
        }
    }
}

fn square_sum(first: u32, second: u32) -> bool {
    let num = first + second;
    let root = (num as f64).sqrt() as u32;
    root.pow(2) == num
}

fn build(tail: u32, available: &[Pair], reached: u32, highest: u32) -> Option<Vec<u32>> {
    if reached == highest {
        return Some(vec![tail]);
    }

    let (current, nextavail): (Vec<Pair>, Vec<_>) = available.iter().partition(|pair| 
        pair.contains(tail)
    );
    if current.is_empty() {
        return None;
    }

    // New numbers to test
    let newtails: Vec<_> = current.iter().map(|pair| pair.other(tail)).collect();

    for newtail in newtails {
        if let Some(mut seq) = build(newtail, &nextavail, reached + 1, highest) {
            seq.insert(0, tail);
            return Some(seq);
        }
    }
    None
}

fn main() {
    let highest = env::args().skip(1).next().unwrap().parse().unwrap();
    let upper = highest + 1;

    let pairs: Vec<Pair> = (1..upper).flat_map(|first|
        ((first + 1)..upper).filter_map(move |second|
            if square_sum(first, second) {
                Some(Pair(first, second))
            } else {
                None
            }
        )
    ).collect();

    let mut frequencies: Vec<_> = (1..upper).map(|num| {
        (pairs.iter().filter(|pair| pair.contains(num)).count(), num)
    }).collect();

    frequencies.sort();

    for (_, start) in frequencies {
        match build(start, &pairs, 1, highest) {
            Some(list) => {
                println!("{:?}", list);
                return;
            },
            None => (),
        };
    }
    println!("Not possible");
}