Advertisement
krzysz00

Advent of code, day 16

Dec 16th, 2017
117
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #![feature(try_trait)]
  2. use std::io::{stdin};
  3. use std::collections::VecDeque;
  4. use std::error::Error;
  5. use std::str::FromStr;
  6.  
  7. #[derive(Clone,Copy,PartialEq,Eq,Hash,Debug)]
  8. enum Command {
  9.     Shuffle(usize),
  10.     Exchange(usize, usize),
  11.     Partner(char, char),
  12. }
  13.  
  14. impl FromStr for Command {
  15.     type Err = Box<Error>;
  16.  
  17.     fn from_str(input: &str) -> Result<Command, Box<Error>> {
  18.         use Command::*;
  19.         let (cmd, args) = input.split_at(1);
  20.         match cmd.chars().next().ok_or("Empty command")? {
  21.             's' => args.parse().map_err(|e: ::std::num::ParseIntError| e.into())
  22.                 .map(&Shuffle),
  23.             'x' => {
  24.                 let mut iter = args.split('/').map(|x| x.parse::<usize>());
  25.                 let i1 = iter.next().ok_or("First arg missing")??;
  26.                 let i2 = iter.next().ok_or("Second arg missing")??;
  27.                 Ok(Exchange(i1, i2))
  28.             }
  29.             'p' => {
  30.                 let mut chars = args.chars();
  31.                 let c1 = chars.next().ok_or("First partner missing")?;
  32.                 let c2 = chars.nth(1).ok_or("Second partner missing")?; // first char is gone
  33.                 Ok(Partner(c1, c2))
  34.             },
  35.             _ => Err("Unknown command letter")?
  36.         }
  37.     }
  38. }
  39.  
  40. type State = VecDeque<char>;
  41.  
  42. fn find_both<T: PartialEq>(slice: &VecDeque<T>, v1: &T, v2: &T) -> Option<(usize, usize)> {
  43.     let mut i1 = None;
  44.     let mut i2 = None;
  45.     for (idx, v) in slice.iter().enumerate() {
  46.         if v == v1 {
  47.             i1 = Some(idx);
  48.         }
  49.         if v == v2 {
  50.             i2 = Some(idx);
  51.         }
  52.         if i1.is_some() && i2.is_some() {
  53.             return Some((i1.unwrap(), i2.unwrap()));
  54.         }
  55.     }
  56.     None
  57. }
  58.  
  59. fn eval_command(state: &mut State, command: &Command) {
  60.     use Command::*;
  61.     match command {
  62.         &Shuffle(n) => {
  63.             for _ in 0..n {
  64.                 let e = state.pop_back().expect("Elements should exist");
  65.                 state.push_front(e);
  66.             }
  67.         },
  68.         &Exchange(i, j) => { state.swap(i, j); },
  69.         &Partner(ref a, ref b) => {
  70.             let (i1, i2) = find_both(state, a, b).expect("Partners should exist");
  71.             state.swap(i1, i2);
  72.         }
  73.     }
  74. }
  75.  
  76. fn init_state(n: usize) -> State {
  77.     const A_BYTE: u8 = 97;
  78.     let mut ret = VecDeque::with_capacity(n);
  79.     for i in 0..n {
  80.         ret.push_back((A_BYTE + (i as u8)) as char);
  81.     }
  82.     ret
  83. }
  84.  
  85. fn apply_commands(state: &mut State, commands: &Vec<Command>) {
  86.     for command in commands {
  87.         eval_command(state, command);
  88.     }
  89. }
  90.  
  91. fn print_state(state: &State) {
  92.     for c in state {
  93.         print!("{}", c);
  94.     }
  95.     println!("");
  96. }
  97.  
  98. fn cycle_length(state: &mut State, commands: &Vec<Command>) -> usize {
  99.     // After this, `state` is unchanged
  100.     let mut cycle_order = 0;
  101.     let initial = init_state(state.len());
  102.     loop {
  103.         apply_commands(state, commands);
  104.         if cycle_order == 0 {
  105.             print_state(state);
  106.         }
  107.         cycle_order += 1;
  108.         if state == &initial {
  109.             break;
  110.         }
  111.     }
  112.     cycle_order
  113. }
  114.  
  115. fn main() {
  116.     const PERMUTATION_LENGTH: usize = 16;
  117.     const N_DANCES: usize = 1_000_000_000;
  118.  
  119.     let mut line: String = String::new();
  120.     stdin().read_line(&mut line).expect("Error reading input");
  121.  
  122.     let mut state = init_state(PERMUTATION_LENGTH);
  123.     let commands: Vec<Command> = line.trim_right().split(',')
  124.         .map(|w| w.parse().expect("Failure parsing command")).collect();
  125.  
  126.     let order = cycle_length(&mut state, &commands);
  127.     println!("Order of input is {}", order);
  128.  
  129.     for _ in 0..(N_DANCES % order) {
  130.         apply_commands(&mut state, &commands);
  131.     }
  132.     print_state(&state);
  133. }
Advertisement
Advertisement
Advertisement
RAW Paste Data Copied
Advertisement