maze_solver.mere

// maze_solver: BFS pathfinding on a grid maze (Phase 36)
//
// Input: ASCII maze. `#` = wall, `.` = passage, `S` = start, `G` = goal.
// Output: shortest distance from S to G + path visualization.
//
// Algorithm: BFS records each cell's distance in a Map, and once the goal
//   is reached the path is reconstructed by walking back through the prev Map.
//
// Phase 36 sugar combined dogfood:
//   - `for r in 0..rows do for c in 0..cols do ...`
//   - `if let Some d = ... then ... else ...`
//   - `[(dr, dc) | dr <- -1..1, dc <- -1..1, ...]` (builds 4-neighborhood, but
//     here it's hardcoded)
//   - string interpolation
//
// Execution modes: diff = 0 across the 4 backends (interp + C + LLVM + Wasm)

// Maze (fixed 8x12)
let raw_maze =
  ["############",
   "#S.........#",
   "#.######.#.#",
   "#.#....#.#.#",
   "#.#.##.#.#.#",
   "#...##...#G#",
   "########.#.#",
   "############"];

let rows = list_len raw_maze;
let cols = str_len (match raw_maze with | Cons (h, _) -> h | Nil -> "");

let key = fn (r: int) -> fn (c: int) -> show r ++ "," ++ show c;

let cell_at = fn (r: int) -> fn (c: int) ->
  let rec nth = fn (xs: str list) -> fn (i: int) ->
    match xs with
    | Nil -> ""
    | Cons (h, t) -> if i == 0 then h else nth t (i - 1) in
  let row = nth raw_maze r in
  char_at row c;

let is_open = fn (r: int) -> fn (c: int) ->
  if r < 0 || r >= rows || c < 0 || c >= cols then false
  else
    let c_str = cell_at r c in
    c_str != "#";

// find start / goal
let find_char = fn (target: str) ->
  let cell = map_new () in
  let _ = map_set cell "r" (-1) in
  let _ = map_set cell "c" (-1) in
  let _ = for r in 0..(rows - 1) do
    for c in 0..(cols - 1) do
      if cell_at r c == target then
        let _ = map_set cell "r" r in
        let _ = map_set cell "c" c in
        ()
      else () in
  (map_get cell "r", map_get cell "c");

let start = find_char "S";
let goal = find_char "G";

let _ = print "=== maze_solver (Phase 36) ===";
let _ = print "rows = {show rows}, cols = {show cols}";
let _ = print "start = ({show (fst start)}, {show (snd start)})";
let _ = print "goal  = ({show (fst goal)}, {show (snd goal)})";

// BFS: queue is OwnedVec[str] (keys); distance + prev are stored in Maps
let dist = map_new ();
let prev = map_new ();

let push = fn (q: OwnedVec[str]) -> fn (v: str) ->
  let _ = owned_vec_push q v in ();

// track queue head position in a Map (OwnedVec has no shift)
let qhead = map_new ();
let _ = map_set qhead "i" 0;

let queue = owned_vec_new ();
let start_key = key (fst start) (snd start);
let _ = push queue start_key;
let _ = map_set dist start_key 0;

let goal_key = key (fst goal) (snd goal);

// (dr, dc) for the 4-neighborhood
let dirs = [(-1, 0), (1, 0), (0, -1), (0, 1)];

let parse_key = fn (k: str) ->
  let parts = str_split k "," in
  match parts with
  | Cons (rs, Cons (cs, _)) -> (int_of_str rs, int_of_str cs)
  | _ -> (-1, -1);

// BFS body via recursion
let rec bfs = fn (_unused: unit) ->
  let i = map_get qhead "i" in
  if i >= owned_vec_len queue then ()
  else
    let _ = map_set qhead "i" (i + 1) in
    let here = owned_vec_get queue i in
    if here == goal_key then ()    // early termination (continue also works)
    else
      let coord = parse_key here in
      let r = fst coord in
      let c = snd coord in
      let d = map_get dist here in
      let _ = list_iter dirs (fn (dlt: int * int) ->
        let nr = r + fst dlt in
        let nc = c + snd dlt in
        if is_open nr nc then
          let nk = key nr nc in
          if map_has dist nk then ()
          else
            let _ = map_set dist nk (d + 1) in
            let _ = map_set prev nk here in
            let _ = push queue nk in
            ()
        else ()) in
      bfs ();

let _ = bfs ();

let _ = if map_has dist goal_key then
  print "found! distance = {show (map_get dist goal_key)}"
else
  print "no path";

// path reconstruction
let rec collect_path = fn (k: str) -> fn (acc: str list) ->
  if k == start_key then Cons (k, acc)
  else if map_has prev k then
    collect_path (map_get prev k) (Cons (k, acc))
  else acc;

let path =
  if map_has dist goal_key then collect_path goal_key Nil else Nil;

// register path cells in a Map
let on_path = map_new ();
let _ = list_iter path (fn (k: str) -> let _ = map_set on_path k 1 in ());

let _ = print "--- maze (with path) ---";
let _ = for r in 0..(rows - 1) do
  let buf = strbuf_new () in
  let _ = for c in 0..(cols - 1) do
    let k = key r c in
    let ch =
      if map_has on_path k then
        if cell_at r c == "S" then "S"
        else if cell_at r c == "G" then "G"
        else "*"
      else cell_at r c in
    let _ = strbuf_push buf ch in
    () in
  print (strbuf_to_str buf);

0