use std::env;
use std::io::BufReader;
use std::io::BufRead;
use std::fs::File;
use std::process;
use std::collections::{HashMap, HashSet};
use std::io::{stdin, stdout, Write};

type Track = char;

#[derive(Copy)]
struct Cart {
  dir: (i32, i32),
  next_rot: i32,
  id: u32
}

impl Clone for Cart {
    fn clone(&self) -> Cart { *self }
}

type Tracks = HashMap<(usize, usize), Track>;
type Carts = HashMap<(usize, usize), Cart>;

impl Cart {
  fn char(&self) -> char {
    match self.dir {
      (1, 0) => '>',
      (-1, 0) => '<',
      (0, 1) => 'v',
      (0, -1) => '^',
      _ => panic!("Invalid dir")
    }
  }
}

fn is_track(ch: char) -> bool {
  ch == '/' || ch == '\\' || ch == '+'
}

fn track_at(tracks: &Tracks, x: usize, y: usize) -> bool {
  tracks.contains_key(&(x, y))
}

fn is_cart(ch: char) -> bool {
  ch == '<' || ch == '>' || ch == '^' || ch == 'v'
}

fn cart_at(carts: &Carts, x: usize, y: usize) -> bool {
  carts.contains_key(&(x, y))
}

fn cart_dir(ch: char) -> (i32, i32) {
  match ch {
    '>' => (1, 0),
    '<' => (-1, 0),
    '^' => (0, -1),
    'v' => (0, 1),
    _ => panic!("Not a cart")
  }
}

fn rot_cart(cart: &Cart, curve: char) -> (i32, i32) {
  let dir = cart.dir;
  if curve == '/' {
    match dir {
      (1, 0) => (0, -1),
      (-1, 0) => (0, 1),
      (0, -1) => (1, 0),
      (0, 1) => (-1, 0),
      _ => panic!("Not a correct direction")
    }
  }
  else if curve == '\\' {
    match dir {
      (1, 0) => (0, 1),
      (-1, 0) => (0, -1),
      (0, -1) => (-1, 0),
      (0, 1) => (1, 0),
      _ => panic!("Not a correct direction")
    }
  }
  else if curve == '+' {
    match cart.next_rot {
      -1 => match dir {
        (1, 0) => (0, -1),
        (0, 1) => (1, 0),
        (-1, 0) => (0, 1),
        (0, -1) => (-1, 0),
        _ => panic!("Not a correct direction")
      },
      0 => dir,
      1 => match dir {
        (1, 0) => (0, 1),
        (0, 1) => (-1, 0),
        (-1, 0) => (0, -1),
        (0, -1) => (1, 0),
        _ => panic!("Not a correct direction")
      },
      _ => panic!("Not a correct next_rot")
    }
  } else {
    panic!("Not a valid curve");
  }
}

fn visualize(tracks: &Tracks, carts: &Carts, my: usize, mx: usize) {
  for y in 0..my {
    for x in 0..mx {
      if cart_at(carts, x, y) {
        print!("{}", carts[&(x, y)].char());
      }
      else if track_at(&tracks, x, y) {
        print!("{}", tracks[&(x, y)]);
      }
      else {
        print!(" ");
      }
    }
    print!("\n");
  }

  let mut s = String::new();
  let _ = stdout().flush();
  stdin().read_line(&mut s).expect("Did not enter a correct string");

}

fn main() {
  let args: Vec<String> = env::args().collect();
  if args.len() != 2 {
    println!("Wrong number of arguments. Provide a file name and worker count.");
    process::exit(1);
  }
  let filename = &args[1];

  println!("Using file {} as input.", filename);
  let f = match File::open(filename) {
    Ok(file) => file,
    Err(e) => {
      println!("Failed to open file {}. {:?}", filename, e);
      process::exit(1);
    }
  };
  let file = BufReader::new(&f);
  let lines: Vec<String> = file.lines()
    .map(|line| line.expect("Could not parse line."))
    .collect();

  let mut tracks = Tracks::new();
  let mut carts = Carts::new();
  let my = lines.len();
  let mx = lines[0].len();
  let mut id = 0;
  for (y, line) in lines.iter().enumerate() {
    let chars: Vec<char> = line.chars().collect();
    for (x, &ch) in chars.iter().enumerate() {
      if is_track(ch) {
        tracks.insert((x, y), ch);
      } else if is_cart(ch) {
        let dir = cart_dir(ch);
        let cart = Cart { dir, next_rot: -1, id };
        carts.insert((x, y), cart);
        id += 1;
      }
    }
  }

  // visualize(&tracks, &carts, my, mx);

  let MAX_ITERS = 100000;
  for iter in 0..MAX_ITERS {
    let mut moved: HashSet<u32> = HashSet::new();
    for y in 0..my {
      for x in 0..mx {
        if !cart_at(&carts, x, y) { continue; }
        let mut cart = carts[&(x, y)].clone();
        if moved.contains(&cart.id) { continue; }
        let next_x = (x as i32 + cart.dir.0) as usize;
        let next_y = (y as i32 + cart.dir.1) as usize;

        if track_at(&tracks, next_x, next_y) {
          let track = tracks[&(next_x, next_y)];
          let new_dir = rot_cart(&cart, track);
          if track == '+' {
            cart.next_rot = (cart.next_rot + 2) % 3 - 1;
          }
          cart.dir = new_dir;
        }

        // Move cart
        carts.remove(&(x, y));
        moved.insert(cart.id);
        if cart_at(&carts, next_x, next_y) {
          println!("#{}: Collision at ({}, {})", iter, next_x, next_y);
          carts.remove(&(next_x, next_y));
        } else {
          carts.insert((next_x, next_y), cart);
        }
      }
    }

    // visualize(&tracks, &carts, my, mx);

    if carts.len() == 1 {
      let keys = carts.keys();
      for (last_x, last_y) in keys {
        println!("#{}: Last position: ({}, {})", iter, last_x, last_y);
        return;
      }
    }
    else if carts.len() == 0 {
      panic!("Even number of carts, no result!");
    }
  }

  println!("Reached end of iterations");
}