use rand::random;
use siphasher::sip::SipHasher24;

use std::hash::Hasher;

struct Solver {
  size: usize,
  key: u64,
  nodes: Vec<u32>,
  edges: Vec<bool>,
  round: u64,
}

impl Solver {
  fn new(size: usize, key: u64) -> Solver {
    Solver {
      nodes: Vec::new(),
      edges: Vec::new(),
      round: 0,
      key,
      size,
    }.initialize()
  }

  fn count(&self) -> usize {
    2usize.pow(self.size as u32)
  }

  fn edge_mask(&self) -> usize {
    self.count() - 1
  }

  fn initialize(mut self) -> Solver {
    self.edges.resize(self.count(), true);
    self.nodes.resize(self.count() * 2, 0);

    for i in 0..self.edges.len() {
      *self.top_mut(i) += 1;
      *self.bottom_mut(i) += 1;
    }

    self
  }

  fn top(&self, edge: usize) -> u32 {
    self.nodes[(self.hash(2 * edge + 0) % self.edge_mask()) * 2 + 0]
  }

  fn bottom(&self, edge: usize) -> u32 {
    self.nodes[(self.hash(2 * edge + 1) % self.edge_mask()) * 2 + 1]
  }

  fn top_mut(&mut self, edge: usize) -> &mut u32 {
    let i = (self.hash(2 * edge + 0) % self.edge_mask()) * 2 + 0;
    &mut self.nodes[i]
  }

  fn bottom_mut(&mut self, edge: usize) -> &mut u32 {
    let i = (self.hash(2 * edge + 1) % self.edge_mask()) * 2 + 1;
    &mut self.nodes[i]
  }

  fn trim(&mut self) {
    let start = self.alive();

    for i in 0..self.edges.len() {
      if !self.edges[i] {
        continue;
      }

      if self.top(i) < 2 || self.bottom(i) < 2 {
        *self.top_mut(i) -= 1;
        *self.bottom_mut(i) -= 1;
        self.edges[i] = false;
      }
    }

    let end = self.alive();

    println!(
      "Size {}, Round {}: {:9} -> {:9} -{:2}%",
      self.size,
      self.round,
      start,
      end,
      ((1.0 - (end as f64 / start as f64)) * 100.0) as u64
    );

    self.round += 1;
  }

  fn hash(&self, node: usize) -> usize {
    let mut hasher = SipHasher24::new_with_keys(self.key, self.key);
    hasher.write_usize(node);
    hasher.finish() as usize
  }

  fn alive(&self) -> usize {
    self
      .edges
      .iter()
      .cloned()
      .map(|edge| if edge { 1 } else { 0 })
      .sum()
  }
}

fn main() {
  for size in 16..19 {
    println!("------------------------------------------------");
    let mut solver = Solver::new(size, random());
    for _ in 0..3 {
      solver.trim();
    }
  }
}