SHARE
TWEET

Untitled

a guest Dec 15th, 2018 69 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. use std::io::{self, Read};
  2. use std::iter;
  3. use std::collections::VecDeque;
  4.  
  5. #[derive(PartialEq, Copy, Clone, Debug)]
  6. enum Race {
  7.     Elf,
  8.     Goblin
  9. }
  10.  
  11. #[derive(PartialEq, Copy, Clone)]
  12. struct Creature {
  13.     race: Race,
  14.     hp: usize,
  15. }
  16.  
  17. #[derive(PartialEq, Copy, Clone)]
  18. enum Tile {
  19.     Creature(Creature),
  20.     Floor,
  21.     Wall,
  22. }
  23.  
  24. impl Tile {
  25.     fn from_char(c: char) -> Tile {
  26.         match c {
  27.             'E' => Tile::Creature(Creature { race: Race::Elf, hp: 200 }),
  28.             'G' => Tile::Creature(Creature { race: Race::Goblin, hp: 200 }),
  29.             '#' => Tile::Wall,
  30.             '.' => Tile::Floor,
  31.              _  => unimplemented!(),
  32.         }
  33.     }
  34.  
  35.     fn to_char(&self) -> char {
  36.         match self {
  37.             Tile::Creature(Creature { race: Race::Elf, hp: _ }) => 'E',
  38.             Tile::Creature(Creature { race: Race::Goblin, hp: _ }) => 'G',
  39.             Tile::Floor => '.',
  40.             Tile::Wall => '#',
  41.         }
  42.     }
  43.  
  44.     fn is_creature(&self) -> bool {
  45.         self.to_creature().is_some()
  46.     }
  47.  
  48.     fn to_creature(&self) -> Option<&Creature> {
  49.         match self {
  50.             Tile::Creature(c) => Some(c),
  51.             Tile::Floor | Tile::Wall => None,
  52.         }
  53.     }
  54.  
  55.     fn to_mut_creature(&mut self) -> Option<&mut Creature> {
  56.         match self {
  57.             Tile::Creature(c) => Some(c),
  58.             Tile::Floor | Tile::Wall => None,
  59.         }
  60.     }
  61. }
  62.  
  63. struct State(Vec<Vec<Tile>>, /* Game board */
  64.              usize           /* Elf power */);
  65.  
  66. const NEIGHBORS: [(i32, i32); 4] = [(0, 1), (0, -1), (1, 0), (-1, 0)];
  67.  
  68. impl State {
  69.     fn from_string(buffer: &String, elf_power: usize) -> State {
  70.         State(buffer
  71.                 .lines()
  72.                 .map(|line| line
  73.                      .chars()
  74.                      .map(Tile::from_char)
  75.                      .collect())
  76.                 .collect(),
  77.             elf_power)
  78.     }
  79.  
  80.     fn find(&self, p: impl Fn(&Tile) -> bool) -> Vec<(usize, usize)> {
  81.         let mut out = self.0.iter()
  82.             .enumerate()
  83.             .flat_map(|(y, row)| iter::repeat(y).zip(row.iter().enumerate()))
  84.             .filter(|(_, (_, tile))| p(*tile))
  85.             .map(|(y, (x, _))| (y, x))
  86.             .collect::<Vec<(usize, usize)>>();
  87.         out.sort();
  88.         out.dedup();
  89.         return out;
  90.     }
  91.  
  92.     fn print(&self) {
  93.         for line in self.0.iter() {
  94.             line.iter().map(|t| print!("{}", Tile::to_char(t))).for_each(drop);
  95.             print!("  ");
  96.             line.iter().filter_map(|t| t.to_creature())
  97.                 .map(|c| print!("{}, ", c.hp)).for_each(drop);
  98.             print!("\n");
  99.         }
  100.     }
  101.  
  102.     /*  This is the core game loop updater.  It returns true on termination. */
  103.     fn step(&mut self) -> bool {
  104.         self.find(Tile::is_creature).into_iter()
  105.             .any(|(cy, cx)| self.walk_monster(cy, cx))
  106.     }
  107.  
  108.     /*  Builds a new grid of the same size and the given type + value */
  109.     fn grid<T: Clone>(&self, t: T) -> Vec<Vec<T>> {
  110.         vec![vec![t; self.0[0].len()]; self.0.len()]
  111.     }
  112.  
  113.     fn neighbors(y: usize, x: usize) -> impl Iterator<Item=(usize, usize)>
  114.     {
  115.         NEIGHBORS.iter()
  116.             .map(move |(dy, dx)| ((y as i32 + dy) as usize,
  117.                                   (x as i32 + dx) as usize))
  118.     }
  119.  
  120.     fn try_attack(&mut self, y: usize, x: usize) -> bool {
  121.         // First, check to see if we have someone to fight,
  122.         // sorting by HP then by positions.
  123.         let race = self.0[y][x].to_creature().unwrap().race;
  124.         let mut fightable = State::neighbors(y, x)
  125.             .map(|(y, x)| (self.0[y][x].to_creature(), y, x))
  126.             .filter(|(c, _, _)| c.map(|c| c.race != race).unwrap_or(false))
  127.             .map(|(c, y, x)| (c.unwrap().hp, y, x))
  128.             .collect::<Vec<(usize, usize, usize)>>();
  129.         fightable.sort();
  130.  
  131.         // Hacks to help the elves
  132.         let attack_power = match race {
  133.             Race::Elf => self.1,
  134.             Race::Goblin => 3,
  135.         };
  136.  
  137.         if let Some((_, y, x)) = fightable.get(0) {
  138.             let c = self.0[*y][*x].to_mut_creature().unwrap();
  139.             c.hp = c.hp.saturating_sub(attack_power);
  140.             if c.hp == 0 { // DEAD
  141.                 self.0[*y][*x] = Tile::Floor;
  142.             }
  143.             return true;
  144.         }
  145.         return false;
  146.     }
  147.  
  148.     fn walk_monster(&mut self, y: usize, x: usize) -> bool {
  149.         if !self.0[y][x].is_creature() { // Monster died before its turn
  150.             return false;
  151.         }
  152.  
  153.         // See if we can attack before moving.
  154.         if self.try_attack(y, x) {
  155.             return false;
  156.         }
  157.  
  158.         // Otherwise, pick out enemies and move towards them
  159.         let race = self.0[y][x].to_creature().unwrap().race;
  160.         let enemies = self.find(|tile| tile
  161.                                 .to_creature()
  162.                                 .map(|c| c.race != race)
  163.                                 .unwrap_or(false));
  164.         if enemies.is_empty() {
  165.             return true; // We're done!
  166.         }
  167.  
  168.         let distance = self.flood(y, x);
  169.         let reachable = enemies.into_iter()
  170.             .flat_map(|(y, x)| State::neighbors(y, x))
  171.             .filter(|(y, x)| self.0[*y][*x] == Tile::Floor &&
  172.                              distance[*y][*x].is_some())
  173.             .collect::<Vec<(usize, usize)>>();
  174.         if reachable.is_empty() {
  175.             return false;
  176.         }
  177.  
  178.         let min_distance = reachable.iter()
  179.             .filter_map(|(y, x)| distance[*y][*x])
  180.             .min().unwrap();
  181.  
  182.         // This is where we're trying to move to.
  183.         let target = reachable.into_iter()
  184.             .filter(|(y, x)| distance[*y][*x].unwrap() == min_distance)
  185.             .min()
  186.             .unwrap();
  187.  
  188.         // Backtrack along the path, finding how to walk
  189.         let mut path = self.grid(false);
  190.         path[target.0][target.1] = true;
  191.         {
  192.             let mut todo = VecDeque::new();
  193.             todo.push_back(target);
  194.             while let Some((y, x)) = todo.pop_front() {
  195.                 let d = distance[y][x].unwrap();
  196.                 for (y, x) in State::neighbors(y, x) {
  197.                     if let Some(nd) = distance[y][x] {
  198.                         if d == nd + 1 && !path[y][x] {
  199.                             path[y][x] = true;
  200.                             todo.push_back((y, x));
  201.                         }
  202.                     }
  203.                 }
  204.             }
  205.         }
  206.         let next_pos = State::neighbors(y, x)
  207.             .filter(|(y, x)| path[*y][*x])
  208.             .min().unwrap();
  209.         self.0[next_pos.0][next_pos.1] = self.0[y][x].clone();
  210.         self.0[y][x] = Tile::Floor;
  211.  
  212.         // Try to attack from the new position
  213.         self.try_attack(next_pos.0, next_pos.1);
  214.  
  215.         return false;
  216.     }
  217.  
  218.     fn creatures(&self) -> Vec<Creature> {
  219.         self.find(|t| t.is_creature()).iter()
  220.             .map(|(y, x)| self.0[*y][*x].to_creature().unwrap())
  221.             .cloned()
  222.             .collect()
  223.     }
  224.  
  225.     /*
  226.      *  Executes a flood-fill from the given point, returning a
  227.      *  grid of the same size with distance to that point or None
  228.      */
  229.     fn flood(&self, y: usize, x: usize) -> Vec<Vec<Option<usize>>> {
  230.         let mut todo = VecDeque::new();
  231.         todo.push_back((y, x));
  232.         let mut out = self.grid(None);
  233.         out[y][x] = Some(0);
  234.  
  235.         while let Some((y, x)) = todo.pop_front() {
  236.             let d = out[y][x].unwrap();
  237.  
  238.             for (y, x) in State::neighbors(y, x) {
  239.                 if out[y][x].is_none() && self.0[y][x] == Tile::Floor {
  240.                     out[y][x] = Some(d + 1);
  241.                     todo.push_back((y, x));
  242.                 }
  243.             }
  244.         }
  245.         out
  246.     }
  247. }
  248.  
  249. fn main()
  250. {
  251.     let mut buffer = String::new();
  252.     io::stdin().read_to_string(&mut buffer).unwrap();
  253.     State::from_string(&buffer, 0).print();
  254.  
  255.     for elf_power in 3.. {
  256.         let mut state = State::from_string(&buffer, elf_power);
  257.         let initial_elf_count = state.creatures().into_iter()
  258.             .filter(|c| c.race == Race::Elf)
  259.             .count();
  260.  
  261.         let mut time = 0;
  262.         while !state.step() {
  263.             time += 1;
  264.         }
  265.         let hp = state.creatures().into_iter()
  266.             .map(|c| c.hp)
  267.             .sum::<usize>();
  268.  
  269.         let elf_count = state.creatures().into_iter()
  270.             .filter(|c| c.race == Race::Elf)
  271.             .count();
  272.  
  273.         println!("At elf power {}, ended at time {} with hp {}, outcome: {}",
  274.                  elf_power, time, hp, time * hp);
  275.         if initial_elf_count == elf_count {
  276.             println!("  FLAWLESS ELF VICTORY!");
  277.             state.print();
  278.             break;
  279.         }
  280.     }
  281. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top