type maze_block = { 
   walkable        : bool;
   is_finish       : bool;
   marked          : bool;
   prev_coordinate : int * int
}
 
let is_in_bounds (x, y) (xbound, ybound) = (x >= 0) && (x < xbound) && (y >= 0) && (y < ybound)
 
let dimensions (grid: 'a array array) = (Array.length grid, Array.length grid.(0))
 
let access_grid (grid: 'a array array) (x, y) = grid.(x).(y)
 
let mutate_grid (grid: 'a array array) (x, y) (new_elem: 'a) = begin grid.(x).(y) <- new_elem; () end
 
let mark_for_visitation currentXY neighborXY (grid: maze_block array array) (q: (int * int) Queue.t) = 
    let xybounds = dimensions grid in
    if not (is_in_bounds neighborXY xybounds) then ()
    else let neighbor_block = access_grid grid neighborXY in
         if neighbor_block.marked || (not neighbor_block.walkable) then ()
         else
             begin
                 Queue.add neighborXY q;
                 mutate_grid grid neighborXY {neighbor_block with marked = true; prev_coordinate = currentXY}
             end
 
 
let mark_all_4directions (currentX, currentY) (grid: maze_block array array) (q: (int * int) Queue.t) = 
    begin
        mark_for_visitation (currentX, currentY) (currentX + 1, currentY) grid q;
        mark_for_visitation (currentX, currentY) (currentX - 1, currentY) grid q;
        mark_for_visitation (currentX, currentY) (currentX, currentY - 1) grid q;
        mark_for_visitation (currentX, currentY) (currentX, currentY + 1) grid q
    end
 
let assemble_trail (maze_grid: maze_block array array) currentXY = 
    let rec assemble_helper (grid: maze_block array array) (thisX, thisY) trailList = match (thisX, thisY) with
         | (-1, -1) -> trailList
         | _        -> assemble_helper grid (grid.(thisX).(thisY).prev_coordinate) ((thisX, thisY) :: trailList)
    in
    assemble_helper maze_grid currentXY []
 
let rec maze_solver_loop (maze_grid: maze_block array array) (q: (int * int) Queue.t) = 
    if Queue.is_empty q then [] else 
       let currentXY = (Queue.take q) in
       let current_block = access_grid maze_grid currentXY in
           if current_block.is_finish then assemble_trail maze_grid currentXY
           else
               begin
                   mark_all_4directions currentXY maze_grid q;
                   maze_solver_loop maze_grid q
               end
 
let solve_maze startXY (maze_grid: maze_block array array) = 
  let xybounds = dimensions maze_grid in
  let start_block = access_grid maze_grid startXY in
    if (not (is_in_bounds startXY xybounds) || not start_block.walkable)
        then []
    else let new_queue = Queue.create () in 
         begin 
             Queue.add startXY new_queue;
             mutate_grid maze_grid startXY {start_block with marked = true};
             maze_solver_loop maze_grid new_queue
         end
 
let convert_to_maze (num_array: int array array) : maze_block array array = 
    Array.map (fun arr -> (Array.map (fun i -> {walkable = (i == 0); is_finish = false; marked = false; prev_coordinate = (-1, -1)}) arr)) num_array
 
let solve_this_maze startXY finishXY num_array = 
    let xybounds = dimensions num_array in
    let maze = convert_to_maze num_array in
    let finish_in_bounds = is_in_bounds finishXY xybounds in
        if not finish_in_bounds then []
        else
            let finish_block = access_grid maze finishXY in
            let finish_reachable = finish_block.walkable in
                if finish_reachable then
                    begin
                        mutate_grid maze finishXY {finish_block with is_finish = true};
                        solve_maze startXY maze
                    end
                else []
 
let print_tuple_list tuple_list = 
    let print_tuple (x, y) = print_endline ((string_of_int x) ^ ", " ^ (string_of_int y))
    in List.iter (fun x -> print_tuple x) tuple_list
 
;;
 
(*
 
how to test run:
 
start ocaml REPL
 
#use "WhateverFolder/mazeSolver2.ml";;
 
let arr = [|[|0;0;0;0;0|]; [|1;1;1;1;0|]; [|0;0;0;0;0|]; [|0;1;1;1;1|]; [|0;0;0;0;0|]|];;
solve_this_maze (0,0) (4,4) arr;;
 
 
let arr2 = [|[|1;1;1;1;1;1;0|];[|0;0;0;0;0;0;0|];[|1;1;1;1;1;1;0|];[|0;0;0;0;0;0;0|];[|0;1;1;1;1;1;1|];[|0;0;0;0;0;0;0|];[|1;1;1;0;1;1;1|];[|0;0;0;0;0;0;0|];[|0;1;1;1;1;1;0|]|];;
solve_this_maze (1,0) (8,6) arr2;;
*)
 
let arr = [|[|1;1;1;1;1;1;0|];[|0;0;0;0;0;0;0|];[|1;1;1;1;1;1;0|];[|0;0;0;0;0;0;0|];[|0;1;1;1;1;1;1|];[|0;0;0;0;0;0;0|];[|1;1;1;0;1;1;1|];[|0;0;0;0;0;0;0|];[|0;1;1;1;1;1;0|]|] in
print_tuple_list (solve_this_maze (1,0) (8,6) arr);
 
print_newline ();
 
print_tuple_list (solve_this_maze (0,0) (15,15) (Array.make_matrix 16 16 0));
 
print_newline ();
 
print_tuple_list (solve_this_maze (0,0) (31,31) (Array.make_matrix 32 32 0));
 
print_newline ();
 
print_tuple_list (solve_this_maze (0,0) (255,255) (Array.make_matrix 256 256 0));

dHlwZSBtYXplX2Jsb2NrID0geyAKICAgd2Fsa2FibGUgICAgICAgIDogYm9vbDsKICAgaXNfZmluaXNoICAgICAgIDogYm9vbDsKICAgbWFya2VkICAgICAgICAgIDogYm9vbDsKICAgcHJldl9jb29yZGluYXRlIDogaW50ICogaW50Cn0KCmxldCBpc19pbl9ib3VuZHMgKHgsIHkpICh4Ym91bmQsIHlib3VuZCkgPSAoeCA+PSAwKSAmJiAoeCA8IHhib3VuZCkgJiYgKHkgPj0gMCkgJiYgKHkgPCB5Ym91bmQpCgpsZXQgZGltZW5zaW9ucyAoZ3JpZDogJ2EgYXJyYXkgYXJyYXkpID0gKEFycmF5Lmxlbmd0aCBncmlkLCBBcnJheS5sZW5ndGggZ3JpZC4oMCkpCgpsZXQgYWNjZXNzX2dyaWQgKGdyaWQ6ICdhIGFycmF5IGFycmF5KSAoeCwgeSkgPSBncmlkLih4KS4oeSkKCmxldCBtdXRhdGVfZ3JpZCAoZ3JpZDogJ2EgYXJyYXkgYXJyYXkpICh4LCB5KSAobmV3X2VsZW06ICdhKSA9IGJlZ2luIGdyaWQuKHgpLih5KSA8LSBuZXdfZWxlbTsgKCkgZW5kCgpsZXQgbWFya19mb3JfdmlzaXRhdGlvbiBjdXJyZW50WFkgbmVpZ2hib3JYWSAoZ3JpZDogbWF6ZV9ibG9jayBhcnJheSBhcnJheSkgKHE6IChpbnQgKiBpbnQpIFF1ZXVlLnQpID0gCiAgICBsZXQgeHlib3VuZHMgPSBkaW1lbnNpb25zIGdyaWQgaW4KICAgIGlmIG5vdCAoaXNfaW5fYm91bmRzIG5laWdoYm9yWFkgeHlib3VuZHMpIHRoZW4gKCkKICAgIGVsc2UgbGV0IG5laWdoYm9yX2Jsb2NrID0gYWNjZXNzX2dyaWQgZ3JpZCBuZWlnaGJvclhZIGluCiAgICAgICAgIGlmIG5laWdoYm9yX2Jsb2NrLm1hcmtlZCB8fCAobm90IG5laWdoYm9yX2Jsb2NrLndhbGthYmxlKSB0aGVuICgpCiAgICAgICAgIGVsc2UKICAgICAgICAgICAgIGJlZ2luCiAgICAgICAgICAgICAgICAgUXVldWUuYWRkIG5laWdoYm9yWFkgcTsKICAgICAgICAgICAgICAgICBtdXRhdGVfZ3JpZCBncmlkIG5laWdoYm9yWFkge25laWdoYm9yX2Jsb2NrIHdpdGggbWFya2VkID0gdHJ1ZTsgcHJldl9jb29yZGluYXRlID0gY3VycmVudFhZfQogICAgICAgICAgICAgZW5kCiAgICAgICAgICAgICAKCmxldCBtYXJrX2FsbF80ZGlyZWN0aW9ucyAoY3VycmVudFgsIGN1cnJlbnRZKSAoZ3JpZDogbWF6ZV9ibG9jayBhcnJheSBhcnJheSkgKHE6IChpbnQgKiBpbnQpIFF1ZXVlLnQpID0gCiAgICBiZWdpbgogICAgICAgIG1hcmtfZm9yX3Zpc2l0YXRpb24gKGN1cnJlbnRYLCBjdXJyZW50WSkgKGN1cnJlbnRYICsgMSwgY3VycmVudFkpIGdyaWQgcTsKICAgICAgICBtYXJrX2Zvcl92aXNpdGF0aW9uIChjdXJyZW50WCwgY3VycmVudFkpIChjdXJyZW50WCAtIDEsIGN1cnJlbnRZKSBncmlkIHE7CiAgICAgICAgbWFya19mb3JfdmlzaXRhdGlvbiAoY3VycmVudFgsIGN1cnJlbnRZKSAoY3VycmVudFgsIGN1cnJlbnRZIC0gMSkgZ3JpZCBxOwogICAgICAgIG1hcmtfZm9yX3Zpc2l0YXRpb24gKGN1cnJlbnRYLCBjdXJyZW50WSkgKGN1cnJlbnRYLCBjdXJyZW50WSArIDEpIGdyaWQgcQogICAgZW5kCgpsZXQgYXNzZW1ibGVfdHJhaWwgKG1hemVfZ3JpZDogbWF6ZV9ibG9jayBhcnJheSBhcnJheSkgY3VycmVudFhZID0gCiAgICBsZXQgcmVjIGFzc2VtYmxlX2hlbHBlciAoZ3JpZDogbWF6ZV9ibG9jayBhcnJheSBhcnJheSkgKHRoaXNYLCB0aGlzWSkgdHJhaWxMaXN0ID0gbWF0Y2ggKHRoaXNYLCB0aGlzWSkgd2l0aAogICAgICAgICB8ICgtMSwgLTEpIC0+IHRyYWlsTGlzdAogICAgICAgICB8IF8gICAgICAgIC0+IGFzc2VtYmxlX2hlbHBlciBncmlkIChncmlkLih0aGlzWCkuKHRoaXNZKS5wcmV2X2Nvb3JkaW5hdGUpICgodGhpc1gsIHRoaXNZKSA6OiB0cmFpbExpc3QpCiAgICBpbgogICAgYXNzZW1ibGVfaGVscGVyIG1hemVfZ3JpZCBjdXJyZW50WFkgW10KCmxldCByZWMgbWF6ZV9zb2x2ZXJfbG9vcCAobWF6ZV9ncmlkOiBtYXplX2Jsb2NrIGFycmF5IGFycmF5KSAocTogKGludCAqIGludCkgUXVldWUudCkgPSAKICAgIGlmIFF1ZXVlLmlzX2VtcHR5IHEgdGhlbiBbXSBlbHNlIAogICAgICAgbGV0IGN1cnJlbnRYWSA9IChRdWV1ZS50YWtlIHEpIGluCiAgICAgICBsZXQgY3VycmVudF9ibG9jayA9IGFjY2Vzc19ncmlkIG1hemVfZ3JpZCBjdXJyZW50WFkgaW4KICAgICAgICAgICBpZiBjdXJyZW50X2Jsb2NrLmlzX2ZpbmlzaCB0aGVuIGFzc2VtYmxlX3RyYWlsIG1hemVfZ3JpZCBjdXJyZW50WFkKICAgICAgICAgICBlbHNlCiAgICAgICAgICAgICAgIGJlZ2luCiAgICAgICAgICAgICAgICAgICBtYXJrX2FsbF80ZGlyZWN0aW9ucyBjdXJyZW50WFkgbWF6ZV9ncmlkIHE7CiAgICAgICAgICAgICAgICAgICBtYXplX3NvbHZlcl9sb29wIG1hemVfZ3JpZCBxCiAgICAgICAgICAgICAgIGVuZAogICAgICAgICAgICAgICAgICAgICAgICAgICAgIApsZXQgc29sdmVfbWF6ZSBzdGFydFhZIChtYXplX2dyaWQ6IG1hemVfYmxvY2sgYXJyYXkgYXJyYXkpID0gCiAgbGV0IHh5Ym91bmRzID0gZGltZW5zaW9ucyBtYXplX2dyaWQgaW4KICBsZXQgc3RhcnRfYmxvY2sgPSBhY2Nlc3NfZ3JpZCBtYXplX2dyaWQgc3RhcnRYWSBpbgogICAgaWYgKG5vdCAoaXNfaW5fYm91bmRzIHN0YXJ0WFkgeHlib3VuZHMpIHx8IG5vdCBzdGFydF9ibG9jay53YWxrYWJsZSkKICAgICAgICB0aGVuIFtdCiAgICBlbHNlIGxldCBuZXdfcXVldWUgPSBRdWV1ZS5jcmVhdGUgKCkgaW4gCiAgICAgICAgIGJlZ2luIAogICAgICAgICAgICAgUXVldWUuYWRkIHN0YXJ0WFkgbmV3X3F1ZXVlOwogICAgICAgICAgICAgbXV0YXRlX2dyaWQgbWF6ZV9ncmlkIHN0YXJ0WFkge3N0YXJ0X2Jsb2NrIHdpdGggbWFya2VkID0gdHJ1ZX07CiAgICAgICAgICAgICBtYXplX3NvbHZlcl9sb29wIG1hemVfZ3JpZCBuZXdfcXVldWUKICAgICAgICAgZW5kCgpsZXQgY29udmVydF90b19tYXplIChudW1fYXJyYXk6IGludCBhcnJheSBhcnJheSkgOiBtYXplX2Jsb2NrIGFycmF5IGFycmF5ID0gCiAgICBBcnJheS5tYXAgKGZ1biBhcnIgLT4gKEFycmF5Lm1hcCAoZnVuIGkgLT4ge3dhbGthYmxlID0gKGkgPT0gMCk7IGlzX2ZpbmlzaCA9IGZhbHNlOyBtYXJrZWQgPSBmYWxzZTsgcHJldl9jb29yZGluYXRlID0gKC0xLCAtMSl9KSBhcnIpKSBudW1fYXJyYXkKCmxldCBzb2x2ZV90aGlzX21hemUgc3RhcnRYWSBmaW5pc2hYWSBudW1fYXJyYXkgPSAKICAgIGxldCB4eWJvdW5kcyA9IGRpbWVuc2lvbnMgbnVtX2FycmF5IGluCiAgICBsZXQgbWF6ZSA9IGNvbnZlcnRfdG9fbWF6ZSBudW1fYXJyYXkgaW4KICAgIGxldCBmaW5pc2hfaW5fYm91bmRzID0gaXNfaW5fYm91bmRzIGZpbmlzaFhZIHh5Ym91bmRzIGluCiAgICAgICAgaWYgbm90IGZpbmlzaF9pbl9ib3VuZHMgdGhlbiBbXQogICAgICAgIGVsc2UKICAgICAgICAgICAgbGV0IGZpbmlzaF9ibG9jayA9IGFjY2Vzc19ncmlkIG1hemUgZmluaXNoWFkgaW4KICAgICAgICAgICAgbGV0IGZpbmlzaF9yZWFjaGFibGUgPSBmaW5pc2hfYmxvY2sud2Fsa2FibGUgaW4KICAgICAgICAgICAgICAgIGlmIGZpbmlzaF9yZWFjaGFibGUgdGhlbgogICAgICAgICAgICAgICAgICAgIGJlZ2luCiAgICAgICAgICAgICAgICAgICAgICAgIG11dGF0ZV9ncmlkIG1hemUgZmluaXNoWFkge2ZpbmlzaF9ibG9jayB3aXRoIGlzX2ZpbmlzaCA9IHRydWV9OwogICAgICAgICAgICAgICAgICAgICAgICBzb2x2ZV9tYXplIHN0YXJ0WFkgbWF6ZQogICAgICAgICAgICAgICAgICAgIGVuZAogICAgICAgICAgICAgICAgZWxzZSBbXQoKbGV0IHByaW50X3R1cGxlX2xpc3QgdHVwbGVfbGlzdCA9IAogICAgbGV0IHByaW50X3R1cGxlICh4LCB5KSA9IHByaW50X2VuZGxpbmUgKChzdHJpbmdfb2ZfaW50IHgpIF4gIiwgIiBeIChzdHJpbmdfb2ZfaW50IHkpKQogICAgaW4gTGlzdC5pdGVyIChmdW4geCAtPiBwcmludF90dXBsZSB4KSB0dXBsZV9saXN0Cgo7OwoKKCoKCmhvdyB0byB0ZXN0IHJ1bjoKCnN0YXJ0IG9jYW1sIFJFUEwKCiN1c2UgIldoYXRldmVyRm9sZGVyL21hemVTb2x2ZXIyLm1sIjs7CgpsZXQgYXJyID0gW3xbfDA7MDswOzA7MHxdOyBbfDE7MTsxOzE7MHxdOyBbfDA7MDswOzA7MHxdOyBbfDA7MTsxOzE7MXxdOyBbfDA7MDswOzA7MHxdfF07Owpzb2x2ZV90aGlzX21hemUgKDAsMCkgKDQsNCkgYXJyOzsKCgpsZXQgYXJyMiA9IFt8W3wxOzE7MTsxOzE7MTswfF07W3wwOzA7MDswOzA7MDswfF07W3wxOzE7MTsxOzE7MTswfF07W3wwOzA7MDswOzA7MDswfF07W3wwOzE7MTsxOzE7MTsxfF07W3wwOzA7MDswOzA7MDswfF07W3wxOzE7MTswOzE7MTsxfF07W3wwOzA7MDswOzA7MDswfF07W3wwOzE7MTsxOzE7MTswfF18XTs7CnNvbHZlX3RoaXNfbWF6ZSAoMSwwKSAoOCw2KSBhcnIyOzsKKikKCmxldCBhcnIgPSBbfFt8MTsxOzE7MTsxOzE7MHxdO1t8MDswOzA7MDswOzA7MHxdO1t8MTsxOzE7MTsxOzE7MHxdO1t8MDswOzA7MDswOzA7MHxdO1t8MDsxOzE7MTsxOzE7MXxdO1t8MDswOzA7MDswOzA7MHxdO1t8MTsxOzE7MDsxOzE7MXxdO1t8MDswOzA7MDswOzA7MHxdO1t8MDsxOzE7MTsxOzE7MHxdfF0gaW4KcHJpbnRfdHVwbGVfbGlzdCAoc29sdmVfdGhpc19tYXplICgxLDApICg4LDYpIGFycik7CgpwcmludF9uZXdsaW5lICgpOwoKcHJpbnRfdHVwbGVfbGlzdCAoc29sdmVfdGhpc19tYXplICgwLDApICgxNSwxNSkgKEFycmF5Lm1ha2VfbWF0cml4IDE2IDE2IDApKTsKCnByaW50X25ld2xpbmUgKCk7CgpwcmludF90dXBsZV9saXN0IChzb2x2ZV90aGlzX21hemUgKDAsMCkgKDMxLDMxKSAoQXJyYXkubWFrZV9tYXRyaXggMzIgMzIgMCkpOwoKcHJpbnRfbmV3bGluZSAoKTsKCnByaW50X3R1cGxlX2xpc3QgKHNvbHZlX3RoaXNfbWF6ZSAoMCwwKSAoMjU1LDI1NSkgKEFycmF5Lm1ha2VfbWF0cml4IDI1NiAyNTYgMCkpOw==