common.rs (2431B)
1 use std::collections::{HashMap, HashSet}; 2 3 const DIRECTIONS: [[(i64, i64); 3]; 4] = [ 4 [(-1, 0), (-1, 1), (-1, -1)], 5 [(1, 0), (1, 1), (1, -1)], 6 [(0, -1), (1, -1), (-1, -1)], 7 [(0, 1), (1, 1), (-1, 1)] 8 ]; 9 10 pub fn read_from_stdin() -> (Vec<(i64, i64)>, HashMap<(i64, i64), usize>) { 11 let mut v = vec![]; 12 let mut lookup = HashMap::new(); 13 let mut line = String::new(); 14 let mut i = 0; 15 while std::io::stdin().read_line(&mut line).unwrap() > 0 { 16 let bytes = line.as_bytes(); 17 for j in 0..bytes.len() { 18 if bytes[j] == b'#' { 19 lookup.insert((i, j as i64), v.len()); 20 v.push((i, j as i64)); 21 } 22 } 23 i += 1; 24 line.clear(); 25 } 26 (v, lookup) 27 } 28 29 pub fn free_around(e: (i64, i64), m: &HashMap<(i64, i64), usize>) -> bool { 30 for d in [ 31 (-1, -1), (-1, 0), (-1, 1), 32 ( 0, -1), ( 0, 1), 33 ( 1, -1), ( 1, 0), ( 1, 1) 34 ] { 35 if m.contains_key(&(e.0 + d.0, e.1 + d.1)) { return false; } 36 } 37 true 38 } 39 40 pub fn play( 41 elves: &mut Vec<(i64, i64)>, 42 lookup: &mut HashMap<(i64, i64), usize>, 43 nturns: usize 44 ) -> Option<usize> { 45 let mut claimed = HashMap::<(i64, i64), usize>::new(); 46 let mut stopped = HashSet::<(i64, i64)>::new(); 47 for t in 0..nturns { 48 // First half 49 for i in 0..elves.len() { 50 let e = elves[i]; 51 if free_around(e, &lookup) { continue; } 52 for j in 0..4 { 53 let d = DIRECTIONS[(t+j)%4].iter() 54 .map(|x| (e.0+x.0, e.1+x.1)) 55 .collect::<Vec<_>>(); 56 if !lookup.contains_key(&d[0]) && 57 !lookup.contains_key(&d[1]) && 58 !lookup.contains_key(&d[2]) 59 { 60 if claimed.contains_key(&d[0]) { stopped.insert(d[0]); } 61 claimed.insert(d[0], i); 62 break; 63 } 64 } 65 } 66 67 // Second half 68 let mut any_moved = false; 69 for (moveto, i) in &claimed { 70 if stopped.contains(&moveto) { continue; } 71 any_moved = true; 72 lookup.remove(&elves[*i]); 73 elves[*i] = *moveto; 74 lookup.insert(elves[*i], *i); 75 } 76 if !any_moved { return Some(t); } 77 78 // Cleanup 79 claimed.clear(); 80 stopped.clear(); 81 } 82 None 83 }