Advertisement
rdm

pushed some issues into computational leaves

rdm
Jul 10th, 2012
426
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. NB. true for rows in x which index true value in y
  2. validIn =: (<"1@(|~ #) { ]) *. (|~ #) -:"1 [  
  3.  
  4. filter =: 1 : '#~ u' NB. removes all elements of y where u(y[i]) is false
  5.  
  6. manhattanDistance =: +/@:|@:- NB. x={vect}, y={vect}; z={num}dist
  7. manhattanDeltas=: 3 :'(,-)=i.#$y' NB. unit vectors oriented on coordinate axes
  8.  
  9. NB. x = [[bit]]  valid squares
  10. NB. y = [num]    index
  11. NB. z = [[num]]  neighbors
  12. gridNeighbors =: 1 : 0
  13.     [: validIn&m filter (manhattanDeltas m) +"1 ]
  14. )
  15.  
  16. NB. m = [[bit]]        valid squares
  17. NB. y = Path<tuple>
  18. NB. z = [Path<tuple>]  extended paths
  19. gridExtendPath =: 1 : 0
  20.     > <@,"_ 1 m gridNeighbors@{:@>
  21. )
  22.  
  23. NB. x = Node                        goal
  24. NB. u = (Path<Node>)->[Path<Node>]  extendPath
  25. NB. v = (Node,Node)->num            heuristicDist
  26. NB. y = Node                        start
  27. NB. z = Path<Node>                  shortest path
  28. aStar =: 2 : 0
  29. :
  30.     closed   =. (0,$y) $ 0
  31.     frontier =. ,<,:y
  32.     while. #frontier do.
  33.         currentPath =. {. frontier
  34.         frontier    =. }. frontier
  35.         last        =. {: > currentPath
  36.         if. last e. closed do. continue.            end.
  37.         if. last -: x      do. >currentPath return. end.
  38.         closed   =. closed, last
  39.         frontier =. frontier, u currentPath
  40.         NB. SORT FRONTIER
  41.         scores   =. (# +  x v {:)&> frontier
  42.         frontier =. frontier /: scores
  43.     end.
  44.     exception_message=:'No path found.' throw.
  45. )
  46.  
  47. exampleG =: '#' = ];._2]0 :0
  48. ....##..##
  49. .##.##..##
  50. #..#####..
  51. #.#...##..
  52. .##...###.
  53. .##.####.#
  54. ..#..##.#.
  55. ###.##..##
  56. #.#####..#
  57. ...####..#
  58. )
  59.  
  60. exampleSolution =: 0 8 (((|:exampleG) gridExtendPath) aStar manhattanDistance) 5 0
  61.  
  62. NB. to inspect this solution, use:
  63.    '*' (<"1 exampleSolution)} '.#' {~ |:exampleG
  64.  
  65. NB. or
  66.  
  67.    '*' (<@|."1 exampleSolution)} '.#' {~ exampleG
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement