From b6a295a9eaf5fec16f72870baae84e6eadd1be33 Mon Sep 17 00:00:00 2001
From: Justin Worthe <justin.worthe@gmail.com>
Date: Sat, 20 May 2017 22:46:00 +0200
Subject: Implemented lattice restricted battleship searching

---
 src/knowledge.rs | 53 +++++++++++++++++++++++++++++++++++++++++++++++++----
 src/math.rs      | 20 ++++++++++++++++++++
 src/shooting.rs  | 20 ++++++++++++--------
 3 files changed, 81 insertions(+), 12 deletions(-)

(limited to 'src')

diff --git a/src/knowledge.rs b/src/knowledge.rs
index f009c10..5e45f07 100644
--- a/src/knowledge.rs
+++ b/src/knowledge.rs
@@ -51,10 +51,7 @@ impl Knowledge {
         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 possible_placements = self.opponent_map.possible_placements();
 
         let mut max_score = 1;
         let mut best_cells = Vec::new();
@@ -74,6 +71,39 @@ impl Knowledge {
 
         best_cells
     }
+
+    pub fn get_most_possibility_shots_on_lattice(&self) -> Vec<Point> {
+        let on_lattice = self.opponent_map.cells_on_lattice(self.lattice_size());
+        let possible_placements = self.opponent_map.possible_placements();
+
+        let mut max_possibilities = 1;
+        let mut best_cells = Vec::new();
+
+        for cell in on_lattice {
+            let possibilities = possible_placements.iter()
+                .filter(|placement| placement.touches_point(cell)).count();
+            if possibilities > max_possibilities {
+                max_possibilities = possibilities;
+                best_cells = vec!(cell);
+            }
+            else if possibilities == max_possibilities {
+                best_cells.push(cell);
+            }
+        }
+
+        best_cells
+    }
+
+    fn lattice_size(&self) -> u16 {
+        let any_long_ships = self.opponent_map.ships.iter()
+            .any(|(ship, knowledge)| ship.length() >= 4 && !knowledge.destroyed);
+        if any_long_ships {
+            4
+        }
+        else {
+            2
+        }
+    }
 }
 
 #[derive(Serialize, Deserialize, Clone, Debug)]
@@ -173,6 +203,21 @@ impl OpponentMapKnowledge {
                 .filter(|&y| cells.iter().any(|z| z.is_adjacent(y)))
         }).collect()
     }
+
+    fn cells_on_lattice(&self, lattice_size: u16) -> Vec<Point> {
+        self.cells.iter().flat_map(|x| {
+            x.iter()
+                .filter(|y| !y.shot_attempted() && y.position.is_on_lattice(lattice_size))
+                .map(|y| y.position)
+        }).collect()
+    }
+
+    fn possible_placements(&self) -> Vec<PossibleShipPlacement> {
+        self.ships
+            .values()
+            .flat_map(|knowledge| knowledge.possible_placements.clone())
+            .collect()
+    }
 }
 
 #[derive(Serialize, Deserialize, Clone, Debug)]
diff --git a/src/math.rs b/src/math.rs
index ce9d885..da06622 100644
--- a/src/math.rs
+++ b/src/math.rs
@@ -131,4 +131,24 @@ impl Point {
             (dx == 1 && dy == 0)
         
     }
+
+    pub fn is_on_lattice(&self, lattice_size: u16) -> bool {
+        (self.x + self.y) % lattice_size == 0
+    }
+}
+
+
+#[cfg(test)]
+mod tests {
+    use super::*;
+    
+    #[test]
+    fn point_on_lattice_works() {
+        assert_eq!(true, Point::new(0,0).is_on_lattice(4));
+        assert_eq!(true, Point::new(4,0).is_on_lattice(4));
+        assert_eq!(true, Point::new(0,4).is_on_lattice(4));
+        assert_eq!(true, Point::new(4,4).is_on_lattice(4));
+        assert_eq!(true, Point::new(1,3).is_on_lattice(4));
+        assert_eq!(true, Point::new(3,1).is_on_lattice(4));        
+    }
 }
diff --git a/src/shooting.rs b/src/shooting.rs
index 616ebf3..4d87d86 100644
--- a/src/shooting.rs
+++ b/src/shooting.rs
@@ -17,14 +17,18 @@ pub fn shoot_smartly(knowledge: &Knowledge) -> Action {
 }
 
 fn seek_shoot(knowledge: &Knowledge) -> Point {
-    let mut shot: Point;
-    
-    while {
-        shot = Point::random(knowledge.map_size);
-        let ref target = knowledge.opponent_map.cells[shot.x as usize][shot.y as usize];
-        target.shot_attempted()
-    } {}
-    shot
+    let possibilities = knowledge.get_most_possibility_shots_on_lattice();
+    if possibilities.is_empty() {
+        println!("All possible shots on the current lattice have been tried!");
+        Point::new(0,0)
+    }
+    else {
+        let mut rng = rand::thread_rng();
+        let between = Range::new(0, possibilities.len());
+        let i = between.ind_sample(&mut rng);
+        
+        possibilities[i as usize]
+    }
 }
 
 fn destroy_shoot(knowledge: &Knowledge) -> Point {
-- 
cgit v1.2.3