day11.rs 5.1 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197
  1. use std::io;
  2. use std::io::BufRead;
  3. use std::cmp;
  4. #[derive(Clone, Debug, PartialEq)]
  5. enum SeatState {
  6. FLOOR,
  7. EMPTY,
  8. OCCUPIED,
  9. }
  10. impl From<char> for SeatState {
  11. fn from(c: char) -> Self {
  12. match c {
  13. '.' => SeatState::FLOOR,
  14. 'L' => SeatState::EMPTY,
  15. '#' => SeatState::OCCUPIED,
  16. _ => panic!("Invalid character: {}", c),
  17. }
  18. }
  19. }
  20. type SeatPlan = Vec<Vec<SeatState>>;
  21. fn occupied_neighbours_of(x: usize, y: usize, plan: &SeatPlan) -> usize {
  22. let mut xrange = (x.checked_sub(1).unwrap_or(0), x + 1);
  23. xrange.1 = cmp::min(xrange.1, plan[0].len() - 1);
  24. let mut yrange = (y.checked_sub(1).unwrap_or(0), y + 1);
  25. yrange.1 = cmp::min(yrange.1, plan.len() - 1);
  26. let mut ret = 0;
  27. for y in yrange.0..=yrange.1 {
  28. for x in xrange.0..=xrange.1 {
  29. if plan[y][x] == SeatState::OCCUPIED {
  30. ret += 1;
  31. }
  32. }
  33. }
  34. if plan[y][x] == SeatState::OCCUPIED {
  35. ret -= 1;
  36. }
  37. ret
  38. }
  39. fn visible_neighbours_of(x: usize, y: usize, plan: &SeatPlan) -> usize {
  40. let rays = [
  41. // (dx, dy)
  42. (-1, -1), (0, -1), (1, -1),
  43. (-1, 0), (1, 0),
  44. (-1, 1), (0, 1), (1, 1),
  45. ];
  46. let mut occupied = 0usize;
  47. for ray in &rays {
  48. let mut x = x as i32;
  49. let mut y = y as i32;
  50. //println!("Casting ray {:?}", ray);
  51. loop {
  52. x += ray.0;
  53. y += ray.1;
  54. if x < 0 || x as usize >= plan[0].len() {
  55. //println!("Ray {:?} died at ({},{})", ray, x, y);
  56. break
  57. }
  58. if y < 0 || y as usize >= plan.len() {
  59. //println!("Ray {:?} died at ({},{})", ray, x, y);
  60. break
  61. }
  62. match plan[y as usize][x as usize] {
  63. SeatState::OCCUPIED => {
  64. occupied += 1;
  65. //println!("Ray {:?} died at ({},{}) (occupied)", ray, x, y);
  66. break
  67. },
  68. SeatState::EMPTY => {
  69. //println!("Ray {:?} died at ({},{}) (empty)", ray, x, y);
  70. break
  71. },
  72. SeatState::FLOOR => {},
  73. };
  74. }
  75. }
  76. occupied
  77. }
  78. #[allow(dead_code)]
  79. fn print(plan: &SeatPlan) {
  80. for row in plan {
  81. for seat in row {
  82. print!("{}", match seat {
  83. SeatState::FLOOR => '.',
  84. SeatState::EMPTY => 'L',
  85. SeatState::OCCUPIED => '#',
  86. });
  87. }
  88. println!("");
  89. }
  90. }
  91. // returns None for no changes
  92. fn step_part1(prev: &SeatPlan) -> Option<SeatPlan> {
  93. let mut next = prev.clone();
  94. let mut changed = false;
  95. for y in 0..prev.len() {
  96. for x in 0..prev[0].len() {
  97. let on = occupied_neighbours_of(x, y, &prev);
  98. if prev[y][x] == SeatState::EMPTY && on == 0 {
  99. changed = true;
  100. next[y][x] = SeatState::OCCUPIED;
  101. }
  102. if prev[y][x] == SeatState::OCCUPIED && on >= 4 {
  103. changed = true;
  104. next[y][x] = SeatState::EMPTY;
  105. }
  106. }
  107. }
  108. if changed {
  109. Some(next)
  110. } else {
  111. None
  112. }
  113. }
  114. fn step_part2(prev: &SeatPlan) -> Option<SeatPlan> {
  115. let mut next = prev.clone();
  116. let mut changed = false;
  117. for y in 0..prev.len() {
  118. for x in 0..prev[0].len() {
  119. let on = visible_neighbours_of(x, y, &prev);
  120. if prev[y][x] == SeatState::EMPTY && on == 0 {
  121. changed = true;
  122. next[y][x] = SeatState::OCCUPIED;
  123. }
  124. if prev[y][x] == SeatState::OCCUPIED && on >= 5 {
  125. changed = true;
  126. next[y][x] = SeatState::EMPTY;
  127. }
  128. }
  129. }
  130. if changed {
  131. Some(next)
  132. } else {
  133. None
  134. }
  135. }
  136. fn iterate_until_stable<F: Fn(&SeatPlan) -> Option<SeatPlan>>(mut plan: SeatPlan, transform: F) -> SeatPlan {
  137. let mut counter = 0;
  138. loop {
  139. let next = transform(&plan);
  140. match next {
  141. Some(next) => {
  142. counter += 1;
  143. plan = next;
  144. //println!("After round {}:", counter);
  145. //print(&plan);
  146. }
  147. None => {
  148. println!("Stabilized after round {}", counter);
  149. return plan;
  150. }
  151. }
  152. }
  153. }
  154. fn count_occupied(plan: &SeatPlan) -> usize {
  155. plan.iter().map(|row| {
  156. row.iter().map(|seat| if *seat == SeatState::OCCUPIED {
  157. 1
  158. } else {
  159. 0
  160. }).sum::<usize>()
  161. }).sum()
  162. }
  163. fn main() {
  164. let stdin = io::stdin();
  165. let original: Vec<_> = stdin.lock().lines().map(|l| l.unwrap())
  166. .map(|line| {
  167. line.chars().map(SeatState::from).collect::<Vec<_>>()
  168. }).collect();
  169. let plan = iterate_until_stable(original.clone(), step_part1);
  170. println!("Occupied seats (part 1): {}", count_occupied(&plan));
  171. let plan = iterate_until_stable(original.clone(), step_part2);
  172. println!("Occupied seats (part 2): {}", count_occupied(&plan));
  173. }