Finished up efficient elimination of found ships

1 files changed, 74 insertions, 16 deletions

diff --git a/src/knowledge.rs b/src/knowledge.rs
index 01c098d..f009c10 100644
--- a/src/knowledge.rs
+++ b/src/knowledge.rs
@@ -8,21 +8,24 @@ use std::collections::HashMap;
 #[derive(Serialize, Deserialize, Clone, Debug)]
 pub struct Knowledge {
     pub last_action: Action,
-    pub opponent_map: OpponentMapKnowledge
+    pub opponent_map: OpponentMapKnowledge,
+    pub map_size: u16
 }
 
 impl Knowledge {
     pub fn new(map_size: u16, action: Action) -> Knowledge {
         Knowledge {
             last_action: action,
-            opponent_map: OpponentMapKnowledge::new(map_size)
+            opponent_map: OpponentMapKnowledge::new(map_size),
+            map_size: map_size
         }
     }
 
     pub fn with_action(&self, action: Action) -> Knowledge {
         Knowledge {
             last_action: action,
-            opponent_map: self.opponent_map.clone()
+            opponent_map: self.opponent_map.clone(),
+            map_size: self.map_size
         }
     }
 
@@ -38,7 +41,39 @@ impl Knowledge {
         new_knowledge
     }
 
-    
+    pub fn has_unknown_hits(&self) -> bool {
+        self.opponent_map.cells.iter().fold(false, |acc, x| {
+            x.iter().fold(acc, |acc, y| acc || y.unknown_hit())
+        })
+    }
+
+    pub fn get_best_adjacent_shots(&self) -> Vec<Point> {
+        let unknown_hits = self.opponent_map.cells_with_unknown_hits();
+        let adjacent_cells = self.opponent_map.adjacent_unshot_cells(&unknown_hits);
+      
+        let possible_placements = self.opponent_map
+            .ships
+            .values()
+            .flat_map(|knowledge| knowledge.possible_placements.clone());
+
+        let mut max_score = 1;
+        let mut best_cells = Vec::new();
+            
+        for placement in possible_placements {
+            for &cell in &adjacent_cells {
+                let score = placement.count_hit_cells(cell, &unknown_hits);
+                if score > max_score {
+                    max_score = score;
+                    best_cells = vec!(cell);
+                }
+                else if score == max_score {
+                    best_cells.push(cell);
+                }
+            }
+        }
+
+        best_cells
+    }
 }
 
 #[derive(Serialize, Deserialize, Clone, Debug)]
@@ -68,7 +103,6 @@ impl OpponentMapKnowledge {
     }
 
     fn update_from_shot(&mut self, p: Point, state: &State) {
-        let cells_copy = self.cells.clone();
         let ref shot_cell = state.opponent_map.cells[p.x as usize][p.y as usize];
         let sunk_ship = self.ships.iter()
             .filter(|&(_, x)| !x.destroyed)
@@ -90,15 +124,16 @@ impl OpponentMapKnowledge {
         else {
             self.cells[p.x as usize][p.y as usize].hit = true;
             self.cells[p.x as usize][p.y as usize].known_ship = sunk_ship;
+        }
 
-            if sunk_ship.is_some() {
-                for knowledge in self.ships.values_mut() {                
-                    knowledge.possible_placements.retain(|x| {
-                        (sunk_ship != Some(x.ship) && !x.touches_point(p)) ||
+        let cells_copy = self.cells.clone();
+        if sunk_ship.is_some() {
+            for knowledge in self.ships.values_mut() {                
+                knowledge.possible_placements.retain(|x| {
+                    (sunk_ship != Some(x.ship) && !x.touches_point(p)) ||
                         (sunk_ship == Some(x.ship) && x.touches_point(p) && x.all_are_hits(&cells_copy))
 
-                    });
-                }
+                });
             }
         }
 
@@ -123,6 +158,21 @@ impl OpponentMapKnowledge {
             knowledge.possible_placements.retain(|x| x.all_could_be_hits(&cells));
         }
     }
+
+    fn cells_with_unknown_hits(&self) -> Vec<Point> {
+        self.cells.iter().flat_map(|x| {
+            x.iter().filter(|y| y.unknown_hit()).map(|y| y.position)
+        }).collect()
+    }
+
+    fn adjacent_unshot_cells(&self, cells: &Vec<Point>) -> Vec<Point> {
+        self.cells.iter().flat_map(|x| {
+            x.iter()
+                .filter(|y| !y.shot_attempted())
+                .map(|y| y.position)
+                .filter(|&y| cells.iter().any(|z| z.is_adjacent(y)))
+        }).collect()
+    }
 }
 
 #[derive(Serialize, Deserialize, Clone, Debug)]
@@ -161,7 +211,7 @@ impl PossibleShipPlacement {
                     },
                     PossibleShipPlacement {
                         ship: ship,
-                        direction: Direction::South,
+                        direction: Direction::North,
                         position: Point::new(per, par)
                     }
                 )
@@ -169,11 +219,11 @@ impl PossibleShipPlacement {
         }).collect()
     }
 
-    fn touches_point(&self, p: Point) -> bool {
+    pub fn touches_point(&self, p: Point) -> bool {
         p.check_for_ship_collision(self.position, self.direction, self.ship.length())
     }
 
-    fn points_on_ship(&self) -> Vec<Point> {
+    pub fn points_on_ship(&self) -> Vec<Point> {
         (0..self.ship.length() as i32).map(|i| {
             self.position.move_point_no_bounds_check(self.direction, i)
         }).collect()
@@ -194,6 +244,14 @@ impl PossibleShipPlacement {
                     cell.known_ship.map(|ship| ship == self.ship).unwrap_or(true)
             })
     }
+
+    fn count_hit_cells(&self, required: Point, wanted: &Vec<Point>) -> u16 {
+        if !self.touches_point(required) {
+            return 0;
+        }
+
+        wanted.iter().filter(|&&x| self.touches_point(x)).count() as u16
+    }
 }
 
 #[derive(Serialize, Deserialize, Clone, Debug)]
@@ -214,11 +272,11 @@ impl KnowledgeCell {
         }
     }
 
-    fn shot_attempted(&self) -> bool {
+    pub fn shot_attempted(&self) -> bool {
         self.missed || self.hit
     }
 
-    fn unknown_hit(&self) -> bool {
+    pub fn unknown_hit(&self) -> bool {
         self.hit && self.known_ship.is_none()
     }