fork download
copy 
  1. type maze_block = { 
  2.    walkable        : bool;
  3.    is_finish        : bool;
  4.    visited         : bool;
  5.    prev_coordinate : int * int
  6. }
  7.  
  8. let is_in_bounds (x, y) (xbound, ybound) = (x >= 0) && (x < xbound) && (y >= 0) && (y < ybound)
  9.  
  10. let dimensions (grid: 'a array array) = (Array.length grid, Array.length grid.(0))
  11.  
  12. let access_grid (grid: 'a array array) (x, y) = grid.(x).(y)
  13.  
  14. let mutate_grid (grid: 'a array array) (x, y) (new_elem: 'a) = begin grid.(x).(y) <- new_elem; () end
  15.  
  16. let target_for_visitation currentXY neighborXY (grid: maze_block array array) (q: (int * int) Queue.t) = 
  17.     let xybounds = dimensions grid in
  18.     if not (is_in_bounds neighborXY xybounds) then (grid, q)
  19.     else let neighbor_block = access_grid grid neighborXY in
  20.          if neighbor_block.visited || (not neighbor_block.walkable) then (grid, q)
  21.          else
  22.              begin
  23.                  Queue.add neighborXY q;
  24.                  mutate_grid grid neighborXY {neighbor_block with prev_coordinate = currentXY};
  25.                  (grid, q)
  26.              end
  27.  
  28.  
  29. let target_all_4directions (currentX, currentY) (grid: maze_block array array) (q: (int * int) Queue.t) = 
  30.   let (grid1, q1) = target_for_visitation (currentX, currentY) (currentX + 1, currentY) grid q in
  31.   let (grid2, q2) = target_for_visitation (currentX, currentY) (currentX - 1, currentY) grid1 q1 in
  32.   let (grid3, q3) = target_for_visitation (currentX, currentY) (currentX, currentY - 1) grid2 q2 in
  33.   let (grid4, q4) = target_for_visitation (currentX, currentY) (currentX, currentY + 1) grid3 q3 in
  34.   (grid4, q4)
  35.  
  36. let assemble_trail (maze_grid: maze_block array array) currentXY = 
  37.     let rec assemble_helper (grid: maze_block array array) (thisX, thisY) trailList = match (thisX, thisY) with
  38.          | (-1, -1) -> trailList
  39.          | _        -> assemble_helper grid (grid.(thisX).(thisY).prev_coordinate) ((thisX, thisY) :: trailList)
  40.     in
  41.     assemble_helper maze_grid currentXY []
  42.  
  43. let rec maze_solver_loop (maze_grid: maze_block array array) (q: (int * int) Queue.t) = 
  44.     if Queue.is_empty q then [] else 
  45.        let currentXY = (Queue.take q) in
  46.        let current_block = access_grid maze_grid currentXY in
  47.            if current_block.is_finish then assemble_trail maze_grid currentXY
  48.            else let (modified_maze_grid, modified_queue) = target_all_4directions currentXY maze_grid q in
  49.                 begin
  50.                     mutate_grid maze_grid currentXY {current_block with visited = true};
  51.                     maze_solver_loop modified_maze_grid modified_queue
  52.                 end
  53.  
  54. let solve_maze startXY (maze_grid: maze_block array array) = 
  55.   let xybounds = dimensions maze_grid in
  56.   let start_block = access_grid maze_grid startXY in
  57.     if (not (is_in_bounds startXY xybounds) || not start_block.walkable)
  58.         then []
  59.     else let new_queue = Queue.create () in 
  60.          begin 
  61.              Queue.add startXY new_queue; 
  62.              maze_solver_loop maze_grid new_queue
  63.          end
  64.  
  65. let convert_to_maze (num_array: int array array) : maze_block array array = 
  66.     Array.map (fun arr -> (Array.map (fun i -> {walkable = (i == 0); is_finish = false; visited = false; prev_coordinate = (-1, -1)}) arr)) num_array
  67.  
  68. let solve_this_maze startXY finishXY num_array = 
  69.     let xybounds = dimensions num_array in
  70.     let maze = convert_to_maze num_array in
  71.     let finish_in_bounds = is_in_bounds finishXY xybounds in
  72.         if not finish_in_bounds then []
  73.         else
  74.             let finish_block = access_grid maze finishXY in
  75.             let finish_reachable = finish_block.walkable in
  76.                 if finish_reachable then
  77.                     begin
  78.                         mutate_grid maze finishXY {finish_block with is_finish = true};
  79.                         solve_maze startXY maze
  80.                     end
  81.                 else []
  82.  
  83. let print_tuple_list tuple_list = 
  84.     let print_tuple (x, y) = print_endline ((string_of_int x) ^ ", " ^ (string_of_int y))
  85.     in List.iter (fun x -> print_tuple x) tuple_list
  86.  
  87. (*
  88.  
  89. how to test run:
  90.  
  91. start ocaml REPL
  92.  
  93. #use "WhateverFolder/mazeSolver2.ml";;
  94.  
  95. 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|]|];;
  96. solve_this_maze (0,0) (4,4) arr;;
  97.  
  98.  
  99. 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|]|];;
  100. solve_this_maze (1,0) (8,6) arr2;;
  101.  
  102.  
  103. let big16emptyarr = [|[|0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0|];
  104. [|0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0|];
  105. [|0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0|];
  106. [|0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0|];
  107. [|0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0|];
  108. [|0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0|];
  109. [|0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0|];
  110. [|0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0|];
  111. [|0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0|];
  112. [|0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0|];
  113. [|0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0|];
  114. [|0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0|];
  115. [|0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0|];
  116. [|0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0|];
  117. [|0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0|];
  118. [|0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0|];
  119. |];;
  120.  
  121. solve_this_maze (0,0) (15,15) big16emptyarr;;
  122.  
  123. let big32emptyarr = [|[|0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0|];
  124. [|0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0|];
  125. [|0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0|];
  126. [|0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0|];
  127. [|0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0|];
  128. [|0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0|];
  129. [|0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0|];
  130. [|0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0|];
  131. [|0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0|];
  132. [|0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0|];
  133. [|0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0|];
  134. [|0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0|];
  135. [|0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0|];
  136. [|0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0|];
  137. [|0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0|];
  138. [|0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0|];
  139. [|0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0|];
  140. [|0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0|];
  141. [|0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0|];
  142. [|0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0|];
  143. [|0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0|];
  144. [|0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0|];
  145. [|0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0|];
  146. [|0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0|];
  147. [|0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0|];
  148. [|0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0|];
  149. [|0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0|];
  150. [|0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0|];
  151. [|0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0|];
  152. [|0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0|];
  153. [|0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0|];
  154. [|0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0|]|];;
  155.  
  156. solve_this_maze (0,0) (31,31) big32emptyarr;;
  157.  
  158. *)
  159.  
  160. let test1 () = 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
  161. print_tuple_list (solve_this_maze (1,0) (8,6) arr)
  162.  
  163. let test2 () = let big16emptyarr = [|[|0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0|];
  164. [|0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0|];
  165. [|0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0|];
  166. [|0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0|];
  167. [|0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0|];
  168. [|0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0|];
  169. [|0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0|];
  170. [|0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0|];
  171. [|0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0|];
  172. [|0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0|];
  173. [|0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0|];
  174. [|0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0|];
  175. [|0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0|];
  176. [|0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0|];
  177. [|0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0|];
  178. [|0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0|];
  179. |] in
  180. print_tuple_list (solve_this_maze (0,0) (15,15) big16emptyarr)
  181. ;;
  182.  
  183. test1 ();
  184.  
  185. test2 ();
Time limit exceeded #stdin #stdout 5s 44544KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1, 0
1, 1
1, 2
1, 3
1, 4
1, 5
1, 6
2, 6
3, 6
3, 5
3, 4
3, 3
3, 2
3, 1
3, 0
4, 0
5, 0
5, 1
5, 2
5, 3
6, 3
7, 3
7, 4
7, 5
7, 6
8, 6
https://ideone.com/W0leMv
language:
OCaml (ocamlopt 4.05.0)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!