///|
let inf = 1_000_000_000

///|
pub(all) struct Point {
  x : Int
  y : Int
} derive(Eq, Debug)

///|
pub(all) enum Neighbors {
  Four
  Eight
} derive(Eq, Debug)

///|
pub(all) enum Heuristic {
  Manhattan
  Chebyshev
  EuclideanSquared
} derive(Eq, Debug)

///|
pub(all) struct Grid {
  width : Int
  height : Int
  passable : Array[Bool]
} derive(Eq, Debug)

///|
pub(all) struct PathResult {
  found : Bool
  cost : Int
  nodes : Array[Point]
} derive(Eq, Debug)

///|
pub fn Grid::new(width : Int, height : Int, passable : Array[Bool]) -> Grid {
  if width < 0 || height < 0 {
    abort("grid dimensions must be non-negative")
  }
  if passable.length() != width * height {
    abort("passable length must equal width * height")
  }
  { width, height, passable }
}

///|
pub fn Grid::open(width : Int, height : Int) -> Grid {
  Grid::new(width, height, Array::make(width * height, true))
}

///|
pub fn Grid::from_ascii(rows : Array[String], wall : Char) -> Grid {
  if rows.length() == 0 {
    return Grid::new(0, 0, [])
  }
  let height = rows.length()
  let width = rows[0].to_array().length()
  let passable = Array::new(capacity=width * height)
  for y in 0.. Bool {
  point.x >= 0 && point.y >= 0 && point.x < self.width && point.y < self.height
}

///|
pub fn Grid::id(self : Grid, point : Point) -> Int {
  point.y * self.width + point.x
}

///|
pub fn Grid::point(self : Grid, id : Int) -> Point {
  { x: id % self.width, y: id / self.width }
}

///|
pub fn Grid::is_passable(self : Grid, point : Point) -> Bool {
  self.contains(point) && self.passable[self.id(point)]
}

///|
pub fn Grid::set_passable(self : Grid, point : Point, value : Bool) -> Unit {
  if !self.contains(point) {
    abort("point is outside the grid")
  }
  self.passable[self.id(point)] = value
}

///|
pub fn manhattan(a : Point, b : Point) -> Int {
  abs(a.x - b.x) + abs(a.y - b.y)
}

///|
pub fn chebyshev(a : Point, b : Point) -> Int {
  max(abs(a.x - b.x), abs(a.y - b.y))
}

///|
pub fn euclidean_squared(a : Point, b : Point) -> Int {
  let dx = a.x - b.x
  let dy = a.y - b.y
  dx * dx + dy * dy
}

///|
pub fn estimate(a : Point, b : Point, heuristic : Heuristic) -> Int {
  match heuristic {
    Manhattan => manhattan(a, b)
    Chebyshev => chebyshev(a, b)
    EuclideanSquared => euclidean_squared(a, b)
  }
}

///|
pub fn bfs_grid(
  grid : Grid,
  start : Point,
  goal : Point,
  neighbors : Neighbors,
) -> PathResult {
  search_grid(grid, start, goal, neighbors, use_weights=false, heuristic=None)
}

///|
pub fn dijkstra_grid(
  grid : Grid,
  start : Point,
  goal : Point,
  neighbors : Neighbors,
) -> PathResult {
  search_grid(grid, start, goal, neighbors, use_weights=true, heuristic=None)
}

///|
pub fn astar_grid(
  grid : Grid,
  start : Point,
  goal : Point,
  neighbors : Neighbors,
  heuristic : Heuristic,
) -> PathResult {
  search_grid(
    grid,
    start,
    goal,
    neighbors,
    use_weights=true,
    heuristic=Some(heuristic),
  )
}

///|
fn search_grid(
  grid : Grid,
  start : Point,
  goal : Point,
  neighbors : Neighbors,
  use_weights~ : Bool,
  heuristic~ : Heuristic?,
) -> PathResult {
  if !grid.is_passable(start) || !grid.is_passable(goal) {
    return not_found()
  }
  let total = grid.width * grid.height
  let start_id = grid.id(start)
  let goal_id = grid.id(goal)
  let dist = Array::make(total, inf)
  let came_from = Array::make(total, -1)
  let closed = Array::make(total, false)
  let open = Array::new(capacity=total)
  dist[start_id] = 0
  open.push(start_id)
  while open.length() > 0 {
    let current = pop_best(open, grid, goal, neighbors, dist, heuristic)
    if current == goal_id {
      return {
        found: true,
        cost: dist[current],
        nodes: reconstruct_path(grid, came_from, current),
      }
    }
    if !closed[current] {
      closed[current] = true
      let current_point = grid.point(current)
      visit_neighbors(grid, current_point, neighbors, fn(next_id) {
        if !closed[next_id] {
          let step_cost = if use_weights { 1 } else { 1 }
          let next_cost = dist[current] + step_cost
          if next_cost < dist[next_id] {
            dist[next_id] = next_cost
            came_from[next_id] = current
            if !array_contains(open, next_id) {
              open.push(next_id)
            }
          }
        }
      })
    }
  }
  not_found()
}

///|
fn visit_neighbors(
  grid : Grid,
  point : Point,
  neighbors : Neighbors,
  visit : (Int) -> Unit,
) -> Unit {
  let dx = [-1, 1, 0, 0, -1, -1, 1, 1]
  let dy = [0, 0, -1, 1, -1, 1, -1, 1]
  let count = match neighbors {
    Four => 4
    Eight => 8
  }
  for i in 0.. Int {
  let mut best_pos = 0
  let mut best_score = score(open[0], grid, goal, neighbors, dist, heuristic)
  for i in 1.. Int {
  match heuristic {
    None => dist[id]
    Some(h) =>
      dist[id] + admissible_estimate(grid.point(id), goal, neighbors, h)
  }
}

///|
fn admissible_estimate(
  point : Point,
  goal : Point,
  neighbors : Neighbors,
  heuristic : Heuristic,
) -> Int {
  let requested = estimate(point, goal, heuristic)
  let upper_bound = match neighbors {
    Four => manhattan(point, goal)
    Eight => chebyshev(point, goal)
  }
  min(requested, upper_bound)
}

///|
fn reconstruct_path(
  grid : Grid,
  came_from : Array[Int],
  end_id : Int,
) -> Array[Point] {
  let path = Array::new()
  let mut current = end_id
  while current != -1 {
    path.push(grid.point(current))
    current = came_from[current]
  }
  path.rev()
}

///|
fn not_found() -> PathResult {
  { found: false, cost: -1, nodes: [] }
}

///|
fn array_contains(values : Array[Int], needle : Int) -> Bool {
  for value in values {
    if value == needle {
      return true
    }
  }
  false
}

///|
fn abs(value : Int) -> Int {
  if value < 0 {
    -value
  } else {
    value
  }
}

///|
fn max(left : Int, right : Int) -> Int {
  if left > right {
    left
  } else {
    right
  }
}

///|
fn min(left : Int, right : Int) -> Int {
  if left < right {
    left
  } else {
    right
  }
}