path: root/src/knowledge.rs

use actions::*;
use ships::*;
use state::*;
use math::*;

use std::collections::HashMap;

#[derive(Serialize, Deserialize, Clone, Debug)]
pub struct Knowledge {
    pub last_action: Action,
    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),
            map_size: map_size
        }
    }

    pub fn with_action(&self, action: Action) -> Knowledge {
        Knowledge {
            last_action: action,
            opponent_map: self.opponent_map.clone(),
            map_size: self.map_size
        }
    }

    pub fn resolve_last_action(&self, state: &State) -> Knowledge {
        let mut new_knowledge = self.clone();
        match self.last_action {
            Action::PlaceShips(_) => {},
            Action::Shoot(p) => {
                new_knowledge.opponent_map.update_from_shot(p, &state);
            }
        };
        
        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)]
pub struct OpponentMapKnowledge {
    pub ships: HashMap<Ship, OpponentShipKnowledge>,
    pub cells: Vec<Vec<KnowledgeCell>>
}

impl OpponentMapKnowledge {
    fn new(map_size: u16) -> OpponentMapKnowledge {
        let mut cells = Vec::with_capacity(map_size as usize);
        for x in 0..map_size {
            cells.push(Vec::with_capacity(map_size as usize));
            for y in 0..map_size {
                cells[x as usize].push(KnowledgeCell::new(x, y));
            }
        }

        let ships = Ship::all_types().iter()
            .map(|s| (s.clone(), OpponentShipKnowledge::new(s.clone(), map_size)))
            .collect::<HashMap<_, _>>();
            
        OpponentMapKnowledge {
            ships: ships,
            cells: cells
        }
    }

    fn update_from_shot(&mut self, p: Point, state: &State) {
        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)
            .filter(|&(s, _)| state.opponent_map.ships.get(s).map(|x| x.destroyed) == Some(true))
            .map(|(s, _)| s.clone())
            .next(); //only one ship can be sunk at a time

       
        sunk_ship
            .and_then(|ship| self.ships.get_mut(&ship))
            .map(|ref mut ship_knowledge| ship_knowledge.destroyed = true);

        if shot_cell.missed {
            self.cells[p.x as usize][p.y as usize].missed = true;
            for knowledge in self.ships.values_mut() {
                knowledge.possible_placements.retain(|x| !x.touches_point(p));
            }
        }
        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;
        }

        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))

                });
            }
        }

        self.derive_ship_positions();
    }

    fn derive_ship_positions(&mut self) {
        for knowledge in self.ships.values() {
            if knowledge.possible_placements.len() == 1 {
                let ref true_placement = knowledge.possible_placements[0];
                for p in true_placement.points_on_ship() {
                    self.cells[p.x as usize][p.y as usize].known_ship = Some(true_placement.ship);
                }
            }
        }
        self.clear_impossible_placements();
    }

    fn clear_impossible_placements(&mut self) {
        let ref cells = self.cells;
        for knowledge in self.ships.values_mut() {
            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)]
pub struct OpponentShipKnowledge {
    pub ship: Ship,
    pub destroyed: bool,
    pub possible_placements: Vec<PossibleShipPlacement>
}

impl OpponentShipKnowledge {
    fn new(ship: Ship, map_size: u16) -> OpponentShipKnowledge {
        OpponentShipKnowledge {
            ship: ship,
            destroyed: false,
            possible_placements: PossibleShipPlacement::enumerate(ship, map_size)
        }
    }
}

#[derive(Serialize, Deserialize, Clone, Debug)]
pub struct PossibleShipPlacement {
    pub ship: Ship,
    pub direction: Direction,
    pub position: Point
}

impl PossibleShipPlacement {
    fn enumerate(ship: Ship, map_size: u16) -> Vec<PossibleShipPlacement> {
        (0..(map_size-ship.length()+1)).flat_map(move |par| {
            (0..map_size).flat_map(move |per| {
                vec!(
                    PossibleShipPlacement {
                        ship: ship,
                        direction: Direction::East,
                        position: Point::new(par, per)
                    },
                    PossibleShipPlacement {
                        ship: ship,
                        direction: Direction::North,
                        position: Point::new(per, par)
                    }
                )
            })
        }).collect()
    }

    pub fn touches_point(&self, p: Point) -> bool {
        p.check_for_ship_collision(self.position, self.direction, self.ship.length())
    }

    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()
    }

    fn all_are_hits(&self, cells: &Vec<Vec<KnowledgeCell>>) -> bool {
        self.points_on_ship()
            .iter()
            .fold(true, |acc, p| acc && cells[p.x as usize][p.y as usize].hit)
    }

    fn all_could_be_hits(&self, cells: &Vec<Vec<KnowledgeCell>>) -> bool {
        self.points_on_ship()
            .iter()
            .fold(true, |acc, p| {
                let ref cell = cells[p.x as usize][p.y as usize];
                acc && !cell.missed &&
                    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)]
pub struct KnowledgeCell {
    pub missed: bool,
    pub hit: bool,
    pub known_ship: Option<Ship>,
    pub position: Point
}

impl KnowledgeCell {
    fn new(x: u16, y: u16) -> KnowledgeCell {
        KnowledgeCell {
            missed: false,
            hit: false,
            position: Point::new(x, y),
            known_ship: None
        }
    }

    pub fn shot_attempted(&self) -> bool {
        self.missed || self.hit
    }

    pub fn unknown_hit(&self) -> bool {
        self.hit && self.known_ship.is_none()
    }

}