orchard.rs

type BoardBits = u64;

const BOARD_SIZE: i64 = 8;
const ROW_SIZE: i64 = 4;
const ROW_COUNT: i64 = 5;
const ORCHARD_COUNT: i64 = 10;
const TYPE_COUNT: usize = 4;

fn row_bits(row_positions: i64) -> Vec<i64> {
  let mut ret = Vec::new();
  for i in 0..(1i64 << row_positions) {
    if i.count_ones() as i64 == ROW_SIZE {
      ret.push(i);
    }
  }
  ret
}

fn plot(x: i64, y: i64) -> BoardBits {
  1 << (x + y*BOARD_SIZE) as BoardBits
}

fn make_line_configurations_vector(start_x: i64, start_y: i64, dx: i64, dy: i64, visited_starts: &mut BoardBits, out: &mut Vec<Vec<BoardBits>>) {
  if *visited_starts & plot(start_x, start_y) != 0 {
    return;
  }
  *visited_starts |= plot(start_x, start_y);
  let mut ret = Vec::new();
  let mut step_count = 0;
  while start_x + dx*(step_count + 1) < BOARD_SIZE && start_y + dy*(step_count + 1) < BOARD_SIZE &&
      start_x + dx*(step_count + 1) >= 0 && start_y + dy*(step_count + 1) >= 0 {
    step_count += 1;
    *visited_starts |= plot(start_x + dx*step_count, start_y + dy*step_count);
  }
  if step_count >= ROW_SIZE - 1 {
    let all_row_bits = row_bits(step_count + 1);
    for bits in all_row_bits {
      let mut v = 0;
      for i in 0..=step_count {
        if bits & (1 << i) != 0 {
          v |= plot(start_x + dx*i, start_y + dy*i);
        }
      }
      ret.push(v);
    }
  }
  if !ret.is_empty() {
    out.push(ret);
  }
}

fn make_line_configurations() -> Vec<Vec<BoardBits>> {
  let mut ret = Vec::new();
  let mut visited_starts = [0; 8];
  for start_y in 0..BOARD_SIZE {
    for start_x in 0..BOARD_SIZE {
      make_line_configurations_vector(start_x, start_y, 0, 1, &mut visited_starts[0], &mut ret);
      make_line_configurations_vector(start_x, start_y, 1, 0, &mut visited_starts[1], &mut ret);
      make_line_configurations_vector(start_x, start_y, 1, 1, &mut visited_starts[2], &mut ret);
      make_line_configurations_vector(start_x, start_y, 1, 2, &mut visited_starts[3], &mut ret);
      make_line_configurations_vector(start_x, start_y, 2, 1, &mut visited_starts[4], &mut ret);
    }
    for start_x in (0..BOARD_SIZE).rev() {
      make_line_configurations_vector(start_x, start_y, -1, 1, &mut visited_starts[5], &mut ret);
      make_line_configurations_vector(start_x, start_y, -1, 2, &mut visited_starts[6], &mut ret);
      make_line_configurations_vector(start_x, start_y, -2, 1, &mut visited_starts[7], &mut ret);
    }
  }
  ret
}

fn make_same_tree_boards(board: BoardBits, current_rows: i64, line_configurations: &[Vec<BoardBits>], ret: &mut Vec<BoardBits>) {
  for i in 0..line_configurations.len() {
    for line_configuration in line_configurations[i].iter() {
      let new_board = board | *line_configuration;
      if new_board.count_ones() > ORCHARD_COUNT as u32 {
        continue;
      }
      if current_rows + 1 < ROW_COUNT {
        make_same_tree_boards(new_board, current_rows + 1, &line_configurations[(i + 1)..], ret);
      } else {
        if new_board.count_ones() < ORCHARD_COUNT as u32 {
          panic!("Did it with fewer trees!");
        }
        ret.push(new_board);
      }
    }
  }
}

fn house() -> BoardBits {
  plot(3, 0) | plot(4, 0) | plot(3, 1) | plot(4, 1)
}

fn print_board(bits: BoardBits) -> String {
  let mut ret = String::new();
  for y in 0..BOARD_SIZE {
    for x in 0..BOARD_SIZE {
      ret.push(if bits & plot(x, y) != 0 { '0' } else { '.' });
    }
    ret.push('\n');
  }
  ret
}

fn make_solution_boards(occupied: BoardBits, first_board_index: usize, orchard_boards: &[BoardBits], solution: &mut Vec<usize>, solution_boards: &mut Vec<Vec<usize>>) {
  for i in first_board_index..orchard_boards.len() {
    if occupied & orchard_boards[i] != 0 {
      continue;
    }
    solution.push(i);
    if solution.len() == TYPE_COUNT {
      solution_boards.push(solution.clone());
    } else {
      let new_occupied = occupied | orchard_boards[i];
      make_solution_boards(new_occupied, first_board_index + 1, orchard_boards, solution, solution_boards);
    }
    solution.pop();
  }
}

fn print_solution(solution: Vec<usize>, orchard_boards: &[BoardBits]) -> String {
  let mut chars = ['X'; 64];
  let labels = ['A', 'B', 'C', 'D'];
  for i in 0..TYPE_COUNT {
    let b = orchard_boards[solution[i]];
    for j in 0..64 {
      if b & (1 << j) != 0 {
        chars[j] = labels[i];
      }
    }
  }
  let mut ret = String::new();
  ret.push_str("<div style='white-space:pre'>");
  for y in 0..BOARD_SIZE {
    for x in 0..BOARD_SIZE {
      ret.push_str("<div class='");
      ret.push(chars[(y*BOARD_SIZE + x) as usize]);
      ret.push_str("'></div>");
    }
    ret.push('\n');
  }
  ret.push_str("</div>");
  ret
}

fn main() {
  let mut line_configurations = make_line_configurations();
  // println!("Total line configurations: {}", line_configurations.iter().map(|v| v.len()).sum::<usize>());

  let h = house();
  for cfg in line_configurations.iter_mut() {
    cfg.retain(|v| (v & h) == 0);
  }
  line_configurations.retain(|v| !v.is_empty());
  // println!("House-checked line configurations: {}", line_configurations.iter().map(|v| v.len()).sum::<usize>());

  let mut orchard_boards = Vec::new();
  make_same_tree_boards(0, 0, &line_configurations, &mut orchard_boards);
  /* println!("Found {} boards", orchard_boards.len());
  for b in orchard_boards {
    println!("{}", print_board(b));
  }*/

  let mut solutions = Vec::new();
  make_solution_boards(0, 0, &orchard_boards, &mut Vec::new(), &mut solutions);
  println!("Found {} solutions", solutions.len());
  for s in solutions {
    println!("{}", print_solution(s, &orchard_boards));
  }
}