For speed challenge (single thread)

my-step-tsp-speed.rs

#[macro_use]
extern crate log;
extern crate csv;
extern crate env_logger;
extern crate ordered_float;
extern crate rustc_serialize;

use std::collections::HashSet;
use ordered_float::OrderedFloat;

fn main() {
    env_logger::init().unwrap();
    let args = std::env::args().collect::<Vec<String>>();
    assert!(args.len() > 1);
    let mut reader = csv::Reader::from_file(&args[1]).unwrap();
    let cities = reader.decode().map(|r| r.unwrap()).collect::<Vec<City>>();
    let tsp = TSP::new(cities);
    let answer = tsp.solve();
    info!("Distance: {}", tsp.route_dist(&answer));
    println!("index");
    for i in &answer {
        println!("{}", i);
    }
}

#[derive(RustcDecodable)]
struct City {
    x: f64,
    y: f64,
}

struct TSP {
    n: usize,
    dist: Vec<Vec<f64>>,
}

type Route = Vec<usize>;

const GOAL: f64 = 47_000.0;

impl TSP {

    fn new(cities: Vec<City>) -> TSP {
        let n = cities.len();
        let mut dist = vec![vec![0.0; n]; n];
        for i in 0..n {
            for j in 0..i {
                dist[i][j] = (cities[i].x - cities[j].x).hypot(cities[i].y - cities[j].y);
                dist[j][i] = dist[i][j];
            }
        }
        TSP {
            n: n,
            dist: dist,
        }
    }

    fn greedy(&self) -> Route {
        let mut unvisited = (1..self.n).collect::<HashSet<usize>>();
        let mut current = 0;
        let mut route = vec![current];
        while let Some(&i) = unvisited.iter().min_by_key(|&&i| OrderedFloat(self.dist[current][i])) {
            route.push(i);
            unvisited.remove(&i);
            current = i;
        }
        route
    }

    fn route_dist(&self, route: &Route) -> f64 {
        route.iter().fold(0.0, |acc, &i| acc + self.dist[route[i]][route[(i + 1) % self.n]])
    }

    fn solve(&self) -> Route {
        let mut route = self.greedy();
        let n = self.n;
        let mut dist = self.route_dist(&route);
        'outer: loop {
            for i in 0..n {
                for j in (i + 2)..n {
                    let i2 = if i == 0 { n - 1 } else { i - 1 };
                    let j2 = j - 1;
                    let dist_add = self.dist[route[i2]][route[j2]] + self.dist[route[i]][route[j]];
                    let dist_sub = self.dist[route[i2]][route[i]] + self.dist[route[j2]][route[j]];
                    let dist_diff = dist_add - dist_sub;
                    if dist_diff < 0.0 {
                        route[i..j].reverse();
                        dist += dist_diff;
                        if dist < GOAL {
                            break 'outer;
                        }
                        continue 'outer;
                    }
                }
            }
            break;
        }
        route
    }
}