fork download
copy 
  1. type mazeBlock = { 
  2.    walkable   : bool;
  3.    isFinish   : bool;
  4.    visited    : bool;
  5.    prevCoordinate : int * int
  6. }
  7.  
  8. let isInBounds (x, y) (xbound, ybound) = (x >= 0) && (x < xbound) && (y >= 0) && (y < ybound)
  9.  
  10. let dimensionPair (someArray: 'a array array) = (Array.length someArray, Array.length someArray.(0))
  11.  
  12. let targetForVisitation (currentX, currentY) (neighborX, neighborY) (theGrid: mazeBlock array array) (theQueue: (int * int) Queue.t) = 
  13.     let (xbound, ybound) = dimensionPair theGrid in
  14.     if isInBounds (neighborX, neighborY) (xbound, ybound) 
  15.         then let neighborBlock = theGrid.(neighborX).(neighborY) in
  16.                  if neighborBlock.walkable && (not neighborBlock.visited)
  17.                      then 
  18.                          let isFinish2 = neighborBlock.isFinish in
  19.                             begin
  20.                             	Queue.add (neighborX, neighborY) theQueue;
  21.                             	theGrid.(neighborX).(neighborY) <- {walkable = true; isFinish = isFinish2; visited = false; prevCoordinate = (currentX, currentY)}
  22.                             end;
  23.                          (theGrid, theQueue)
  24.                  else (theGrid, theQueue)
  25.     else (theGrid, theQueue)
  26.  
  27. let targetAll4Directions (currentX, currentY) (grid: mazeBlock array array) (queue: (int * int) Queue.t) = 
  28. 	let (grid1, queue1) = targetForVisitation (currentX, currentY) (currentX + 1, currentY) grid queue in
  29. 	let (grid2, queue2) = targetForVisitation (currentX, currentY) (currentX - 1, currentY) grid1 queue1 in
  30. 	let (grid3, queue3) = targetForVisitation (currentX, currentY) (currentX, currentY - 1) grid2 queue2 in
  31. 	let (grid4, queue4) = targetForVisitation (currentX, currentY) (currentX, currentY + 1) grid3 queue3 in
  32. 	(grid4, queue4)
  33.  
  34. let assembleTrail (mazeGrid: mazeBlock array array) currentXY = 
  35.     let rec assembleHelper (theGrid: mazeBlock array array) (thisX, thisY) trailList = match (thisX, thisY) with
  36.          | (-1, -1) -> trailList
  37.          | _        -> assembleHelper theGrid (theGrid.(thisX).(thisY).prevCoordinate) ((thisX, thisY) :: trailList)
  38.     in
  39.     assembleHelper mazeGrid currentXY []
  40.  
  41. let rec mazeSolverLoop (mazeGrid: mazeBlock array array) (bfsQueue: (int * int) Queue.t) = 
  42.     if Queue.is_empty bfsQueue then [] else 
  43.        let (currentX, currentY) = (Queue.take bfsQueue) in 
  44.            if mazeGrid.(currentX).(currentY).isFinish then assembleTrail mazeGrid (currentX, currentY)
  45.            else 
  46.                let isFinish1 = mazeGrid.(currentX).(currentY).isFinish in
  47.                let prevCoordinate1 = mazeGrid.(currentX).(currentY).prevCoordinate in
  48.                mazeGrid.(currentX).(currentY) <- {walkable = true; isFinish = isFinish1; visited = true; prevCoordinate = prevCoordinate1};
  49.                let (modifiedMazeGrid, modifiedQueue) = targetAll4Directions (currentX, currentY) mazeGrid bfsQueue in
  50.                    mazeSolverLoop modifiedMazeGrid modifiedQueue
  51.  
  52. let solveMaze (startX, startY) (mazeGrid: mazeBlock array array) = 
  53. 	let xybounds = dimensionPair mazeGrid in
  54.     if (not (isInBounds (startX, startY) xybounds) || not mazeGrid.(startX).(startY).walkable)
  55.         then []
  56.     else let newQueue = Queue.create () in Queue.add (startX, startY) newQueue; mazeSolverLoop mazeGrid newQueue
  57.  
  58. let convertToMaze (numArray: int array array) : mazeBlock array array = 
  59.     Array.map (fun arr -> (Array.map (fun i -> {walkable = (i == 0); isFinish = false; visited = false; prevCoordinate = (-1, -1)}) arr)) numArray
  60.  
  61. let solveThisMaze (startX, startY) (finishX, finishY) numArray = 
  62.     let xybounds = dimensionPair numArray in
  63.     let theMaze = convertToMaze numArray in
  64.     let finishInBounds = isInBounds (finishX, finishY) xybounds in
  65.     let finishReachable = theMaze.(finishX).(finishY).walkable in
  66.     if finishInBounds then 
  67.         if finishReachable then
  68.         begin
  69.             theMaze.(finishX).(finishY) <- {walkable = true; isFinish = true; visited = false; prevCoordinate = (-1, -1)}
  70.         end;
  71.     if (finishInBounds) then if finishReachable then solveMaze (startX, startY) theMaze else [] else []
  72.  
  73.  
  74. let print_tuple_list tupleList = 
  75.     let print_tuple (x, y) = print_endline ((string_of_int x) ^ ", " ^ (string_of_int y))
  76.     in List.iter (fun x -> print_tuple x) tupleList
  77.  
  78. (*
  79.  
  80. how to test run:
  81.  
  82. start ocaml REPL
  83.  
  84. #use "WhateverFolder/mazeSolver2.ml";;
  85.  
  86. 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|]|];;
  87. solveThisMaze (0,0) (4,4) arr;;
  88.  
  89.  
  90. 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|]|];;
  91. solveThisMaze (1,0) (8,6) arr2;;
  92.  
  93.  
  94. let big16emptyarr = [|[|0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0|];
  95. [|0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0|];
  96. [|0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0|];
  97. [|0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0|];
  98. [|0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0|];
  99. [|0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0|];
  100. [|0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0|];
  101. [|0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0|];
  102. [|0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0|];
  103. [|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. |];;
  111.  
  112. solveThisMaze (0,0) (15,15) big16emptyarr;;
  113.  
  114. 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|];
  115. [|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|];
  116. [|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|];
  117. [|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|];
  118. [|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|];
  119. [|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|];
  120. [|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|];
  121. [|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|];
  122. [|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|];
  123. [|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.  
  147. solveThisMaze (0,0) (31,31) big32emptyarr;;
  148.  
  149. *)
  150.  
  151. 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
  152. print_tuple_list (solveThisMaze (1,0) (8,6) arr)
  153.  
  154. let test2 () = let big16emptyarr = [|[|0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0|];
  155. [|0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0|];
  156. [|0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0|];
  157. [|0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0|];
  158. [|0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0|];
  159. [|0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0|];
  160. [|0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0|];
  161. [|0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0|];
  162. [|0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0|];
  163. [|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. |] in
  171. print_tuple_list (solveThisMaze (0,0) (15,15) big16emptyarr)
  172. ;;
  173.  
  174. test1 ();
  175.  
  176. test2 ();
Time limit exceeded #stdin #stdout 5s 43304KB
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/QXyVzR
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!