A* search algorithm: Difference between revisions

← Older edit

A* search algorithm (view source)

Revision as of 09:00, 7 April 2024

96,093 bytes added , 1 month ago

m

→‎{{header|11l}}: X.throw

Alextretyak

1,453

edits

Revision as of 21:13, 6 October 2020 (view source) rosettacode>Lscrd (Change in the way to write the path in "printSolution".) ← Older edit		Latest revision as of 09:00, 7 April 2024 (view source) Alextretyak (talk \| contribs) m (→‎{{header\|11l}}: X.throw)
(31 intermediate revisions by 14 users not shown)
Line 1: {{draft task\|Routing algorithms}} <!-- A* is pronounced as: A star !--> The A* search algorithm is an extension of [[Dijkstra's algorithm]] useful for finding the lowest cost path between two nodes (aka vertices) of a graph. The path may traverse any number of nodes connected by edges (aka arcs) with each edge having an associated cost. The algorithm uses a heuristic which associates an estimate of the lowest cost path from this node to the goal node, such that this estimate is never greater than the actual cost. The algorithm should not assume that all edge costs are the same. It should be possible to start and finish on any node, including ones identified as a barrier in the task. ;Task Consider the problem of finding a route across the diagonal of a chess board-like 8x8 grid. The rows are numbered from 0 to 7. The columns are also numbered 0 to 7. The start position is (0, 0) and the end position is (7, 7). Movement is allow by one square in any direction including diagonals, similar to a king in chess. The standard movement cost is 1. To make things slightly harder, there is a barrier that occupy certain positions of the grid. Moving into any of the barrier positions has a cost of 100. The barrier occupies the positions (2,4), (2,5), (2,6), (3,6), (4,6), (5,6), (5,5), (5,4), (5,3), (5,2), (4,2) and (3,2). A route with the lowest cost should be found using the A* search algorithm (there are multiple optimal solutions with the same total cost). Line 31: * [[Knapsack problem/0-1]] <br><br> =={{header\|11l}}== {{trans\|Python}} <syntaxhighlight lang="11l">F AStarSearch(start, end, barriers) F heuristic(start, goal) V D = 1 V D2 = 1 V dx = abs(start[0] - goal[0]) V dy = abs(start[1] - goal[1]) R D * (dx + dy) + (D2 - 2 * D) * min(dx, dy) F get_vertex_neighbours(pos) [(Int, Int)] n L(dx, dy) [(1, 0), (-1, 0), (0, 1), (0, -1), (1, 1), (-1, 1), (1, -1), (-1, -1)] V x2 = pos[0] + dx V y2 = pos[1] + dy I x2 < 0 \| x2 > 7 \| y2 < 0 \| y2 > 7 L.continue n.append((x2, y2)) R n F move_cost(a, b) L(barrier) @barriers I b C barrier R 100 R 1 [(Int, Int) = Int] G [(Int, Int) = Int] f G[start] = 0 f[start] = heuristic(start, end) Set[(Int, Int)] closedVertices V openVertices = Set([start]) [(Int, Int) = (Int, Int)] cameFrom L openVertices.len > 0 (Int, Int)? current V currentFscore = 0 L(pos) openVertices I current == N \| f[pos] < currentFscore currentFscore = f[pos] current = pos I current == end V path = [current] L current C cameFrom current = cameFrom[current] path.append(current) path.reverse() R (path, f[end]) openVertices.remove(current) closedVertices.add(current) L(neighbour) get_vertex_neighbours(current) I neighbour C closedVertices L.continue V candidateG = G[current] + move_cost(current, neighbour) I neighbour !C openVertices openVertices.add(neighbour) E I candidateG >= G[neighbour] L.continue cameFrom[neighbour] = current G[neighbour] = candidateG V H = heuristic(neighbour, end) f[neighbour] = G[neighbour] + H X.throw RuntimeError(‘A* failed to find a solution’) V (result, cost) = AStarSearch((0, 0), (7, 7), [[(2, 4), (2, 5), (2, 6), (3, 6), (4, 6), (5, 6), (5, 5), (5, 4), (5, 3), (5, 2), (4, 2), (3, 2)]]) print(‘route ’result) print(‘cost ’cost)</syntaxhighlight> {{out}} <pre> route [(0, 0), (1, 1), (2, 2), (3, 1), (4, 1), (5, 1), (6, 2), (6, 3), (6, 4), (6, 5), (6, 6), (7, 7)] cost 11 </pre> =={{header\|C}}== <syntaxhighlight lang="c"> ~~<lang c>~~ #include <stdlib.h> #include <stdio.h> Line 284 ⟶ 367: return 0; } </syntaxhighlight> ~~</lang>~~ {{out}} <pre> Line 310 ⟶ 393: (7, 7) (8, 8) </pre> =={{header\|C sharp\|C#}}== <syntaxhighlight lang="csharp"> using System; using System.Collections.Generic; namespace A_star { class A_star { // Coordinates of a cell - implements the method Equals public class Coordinates : IEquatable<Coordinates> { public int row; public int col; public Coordinates() { this.row = -1; this.col = -1; } public Coordinates(int row, int col) { this.row = row; this.col = col; } public Boolean Equals(Coordinates c) { if (this.row == c.row && this.col == c.col) return true; else return false; } } // Class Cell, with the cost to reach it, the values g and f, and the coordinates // of the cell that precedes it in a possible path public class Cell { public int cost; public int g; public int f; public Coordinates parent; } // Class Astar, which finds the shortest path public class Astar { // The array of the cells public Cell[,] cells = new Cell[8, 8]; // The possible path found public List<Coordinates> path = new List<Coordinates>(); // The list of the opened cells public List<Coordinates> opened = new List<Coordinates>(); // The list of the closed cells public List<Coordinates> closed = new List<Coordinates>(); // The start of the searched path public Coordinates startCell = new Coordinates(0, 0); // The end of the searched path public Coordinates finishCell = new Coordinates(7, 7); // The constructor public Astar() { // Initialization of the cells values for (int i = 0; i < 8; i++) for (int j = 0; j < 8; j++) { cells[i, j] = new Cell(); cells[i, j].parent = new Coordinates(); if (IsAWall(i, j)) cells[i, j].cost = 100; else cells[i, j].cost = 1; } // Adding the start cell on the list opened opened.Add(startCell); // Boolean value which indicates if a path is found Boolean pathFound = false; // Loop until the list opened is empty or a path is found do { List<Coordinates> neighbors = new List<Coordinates>(); // The next cell analyzed Coordinates currentCell = ShorterExpectedPath(); // The list of cells reachable from the actual one neighbors = neighborsCells(currentCell); foreach (Coordinates newCell in neighbors) { // If the cell considered is the final one if (newCell.row == finishCell.row && newCell.col == finishCell.col) { cells[newCell.row, newCell.col].g = cells[currentCell.row, currentCell.col].g + cells[newCell.row, newCell.col].cost; cells[newCell.row, newCell.col].parent.row = currentCell.row; cells[newCell.row, newCell.col].parent.col = currentCell.col; pathFound = true; break; } // If the cell considered is not between the open and closed ones else if (!opened.Contains(newCell) && !closed.Contains(newCell)) { cells[newCell.row, newCell.col].g = cells[currentCell.row, currentCell.col].g + cells[newCell.row, newCell.col].cost; cells[newCell.row, newCell.col].f = cells[newCell.row, newCell.col].g + Heuristic(newCell); cells[newCell.row, newCell.col].parent.row = currentCell.row; cells[newCell.row, newCell.col].parent.col = currentCell.col; SetCell(newCell, opened); } // If the cost to reach the considered cell from the actual one is // smaller than the previous one else if (cells[newCell.row, newCell.col].g > cells[currentCell.row, currentCell.col].g + cells[newCell.row, newCell.col].cost) { cells[newCell.row, newCell.col].g = cells[currentCell.row, currentCell.col].g + cells[newCell.row, newCell.col].cost; cells[newCell.row, newCell.col].f = cells[newCell.row, newCell.col].g + Heuristic(newCell); cells[newCell.row, newCell.col].parent.row = currentCell.row; cells[newCell.row, newCell.col].parent.col = currentCell.col; SetCell(newCell, opened); ResetCell(newCell, closed); } } SetCell(currentCell, closed); ResetCell(currentCell, opened); } while (opened.Count > 0 && pathFound == false); if (pathFound) { path.Add(finishCell); Coordinates currentCell = new Coordinates(finishCell.row, finishCell.col); // It reconstructs the path starting from the end while (cells[currentCell.row, currentCell.col].parent.row >= 0) { path.Add(cells[currentCell.row, currentCell.col].parent); int tmp_row = cells[currentCell.row, currentCell.col].parent.row; currentCell.col = cells[currentCell.row, currentCell.col].parent.col; currentCell.row = tmp_row; } // Printing on the screen the 'chessboard' and the path found for (int i = 0; i < 8; i++) { for (int j = 0; j < 8; j++) { // Symbol for a cell that doesn't belong to the path and isn't // a wall char gr = '.'; // Symbol for a cell that belongs to the path if (path.Contains(new Coordinates(i, j))) { gr = 'X'; } // Symbol for a cell that is a wall else if (cells[i, j].cost > 1) { gr = '\u2588'; } System.Console.Write(gr); } System.Console.WriteLine(); } // Printing the coordinates of the cells of the path System.Console.Write("\nPath: "); for (int i = path.Count - 1; i >= 0; i--) { System.Console.Write("({0},{1})", path[i].row, path[i].col); } // Printing the cost of the path System.Console.WriteLine("\nPath cost: {0}", path.Count - 1); // Waiting to the key Enter to be pressed to end the program String wt = System.Console.ReadLine(); } } // It select the cell between those in the list opened that have the smaller // value of f public Coordinates ShorterExpectedPath() { int sep = 0; if (opened.Count > 1) { for (int i = 1; i < opened.Count; i++) { if (cells[opened[i].row, opened[i].col].f < cells[opened[sep].row, opened[sep].col].f) { sep = i; } } } return opened[sep]; } // It finds che cells that could be reached from c public List<Coordinates> neighborsCells(Coordinates c) { List<Coordinates> lc = new List<Coordinates>(); for (int i = -1; i <= 1; i++) for (int j = -1; j <= 1; j++) if (c.row+i >= 0 && c.row+i < 8 && c.col+j >= 0 && c.col+j < 8 && (i != 0 \|\| j != 0)) { lc.Add(new Coordinates(c.row + i, c.col + j)); } return lc; } // It determines if the cell with coordinates (row, col) is a wall public bool IsAWall(int row, int col) { int[,] walls = new int[,] { { 2, 4 }, { 2, 5 }, { 2, 6 }, { 3, 6 }, { 4, 6 }, { 5, 6 }, { 5, 5 }, { 5, 4 }, { 5, 3 }, { 5, 2 }, { 4, 2 }, { 3, 2 } }; bool found = false; for (int i = 0; i < walls.GetLength(0); i++) if (walls[i,0] == row && walls[i,1] == col) found = true; return found; } // The function Heuristic, which determines the shortest path that a 'king' can do // This is the maximum value between the orizzontal distance and the vertical one public int Heuristic(Coordinates cell) { int dRow = Math.Abs(finishCell.row - cell.row); int dCol = Math.Abs(finishCell.col - cell.col); return Math.Max(dRow, dCol); } // It inserts the coordinates of cell in a list, if it's not already present public void SetCell(Coordinates cell, List<Coordinates> coordinatesList) { if (coordinatesList.Contains(cell) == false) { coordinatesList.Add(cell); } } // It removes the coordinates of cell from a list, if it's already present public void ResetCell(Coordinates cell, List<Coordinates> coordinatesList) { if (coordinatesList.Contains(cell)) { coordinatesList.Remove(cell); } } } // The main method static void Main(string[] args) { Astar astar = new Astar(); } } } </syntaxhighlight> {{out}} <pre> X....... .X...... ..X.███. .X█...█. .X█...█. .X█████. ..XXXXX. .......X Path: (0,0)(1,1)(2,2)(3,1)(4,1)(5,1)(6,2)(6,3)(6,4)(6,5)(6,6)(7,7) Path cost: 11 </pre> =={{header\|C++}}== <~~lang~~syntaxhighlight lang="cpp"> #include <list> #include <algorithm> #include <iostream> class point { public: Line 325 ⟶ 675: int x, y; }; class map { public: Line 344 ⟶ 694: int w, h; }; class node { public: Line 353 ⟶ 703: int dist, cost; }; class aStar { public: Line 362 ⟶ 712: neighbours[6] = point( 0, 1 ); neighbours[7] = point( 1, 0 ); } int calcDist( point& p ){ // need a better heuristic Line 368 ⟶ 718: return( x * x + y * y ); } bool isValid( point& p ) { return ( p.x >-1 && p.y > -1 && p.x < m.w && p.y < m.h ); } bool existPoint( point& p, int cost ) { std::list<node>::iterator i; Line 387 ⟶ 737: return false; } bool fillOpen( node& n ) { int stepCost, nc, dist; Line 397 ⟶ 747: neighbour = n.pos + neighbours[x]; if( neighbour == end ) return true; if( isValid( neighbour ) && m( neighbour.x, neighbour.y ) != 1 ) { nc = stepCost + n.cost; Line 404 ⟶ 754: node m; m.cost = nc; m.dist = dist; m.pos = neighbour; m.parent = n.pos; open.push_back( m ); Line 412 ⟶ 762: return false; } bool search( point& s, point& e, map& mp ) { node n; end = e; start = s; m = mp; n.cost = 0; n.pos = s; n.parent = 0; n.dist = calcDist( s ); open.push_back( n ); while( !open.empty() ) { Line 426 ⟶ 776: return false; } int path( std::list<point>& path ) { path.push_front( end ); int cost = 1 + closed.back().cost; path.push_front( closed.back().pos ); point parent = closed.back().parent; for( std::list<node>::reverse_iterator i = closed.rbegin(); i != closed.rend(); i++ ) { if( ( i ).pos == parent && !( ( i ).pos == start ) ) { Line 442 ⟶ 792: return cost; } map m; point end, start; point neighbours[8]; Line 448 ⟶ 798: std::list<node> closed; }; int main( int argc, char* argv[] ) { map m; point s, e( 7, 7 ); aStar as; if( as.search( s, e, m ) ) { std::list<point> path; Line 469 ⟶ 819: std::cout << "\n"; } std::cout << "\nPath cost " << c << ": "; for( std::list<point>::iterator i = path.begin(); i != path.end(); i++ ) { Line 478 ⟶ 828: return 0; } </syntaxhighlight> ~~</lang>~~ {{out}} <pre> Line 497 ⟶ 847: =={{header\|Common Lisp}}== <~~lang~~syntaxhighlight lang="lisp">;; * Using external libraries with quicklisp (eval-when (:load-toplevel :compile-toplevel :execute) (ql:quickload '("pileup" "iterate"))) Line 611 ⟶ 961: 0))) ;; Check if this state was already looked at (unless (gethash position visited)) ;; Insert the next node into the queue (heap-insert (node :pos position :path (cons position (node-path node)) :cost cost :f-value f-value) queue))))) ;; The actual A* search Line 631 ⟶ 981: ;; Output some information each counter or nothing if information ;; equals 0. (when (and (not (zerop information)) (zerop (mod counter information))) (format t "~Dth Node, heap size: ~D, current costs: ~D~%" counter (heap-count queue) (node-cost current-node))) ;; If the target is not reached continue (until (equalp current-position goal)) Line 653 ⟶ 1,003: (a* start goal heuristics #'next-positions 0) (format t "Found the shortest path from Start (●) to Goal (◆) in ~D steps with cost: ~D~%" steps cost) (print-path path start goal)))</~~lang~~syntaxhighlight> {{out}} Line 673 ⟶ 1,023: =={{header\|D}}== ported from c++ code <syntaxhighlight lang="d"> ~~<lang D>~~ import std.stdio; Line 679 ⟶ 1,029: import std.range; import std.array; struct Point { int x; Line 696 ⟶ 1,046: ]; } struct Node { Point pos; Line 720 ⟶ 1,070: return( x * x + y * y ); } bool isValid(Point b) { return ( b.x >-1 && b.y > -1 && b.x < m.w && b.y < m.h ); } bool existPoint(Point b, int cost) { auto i = closed.countUntil(b); Line 738 ⟶ 1,088: return false; } bool fillOpen( ref Node n ) { int stepCost; Line 744 ⟶ 1,094: int dist; Point neighbour; for( int x = 0; x < 8; ++x ) { // one can make diagonals have different cost Line 750 ⟶ 1,100: neighbour = n.pos + neighbours[x]; if( neighbour == end ) return true; if( isValid( neighbour ) && m.m[neighbour.y][neighbour.x] != 1 ) { nc = stepCost + n.cost; Line 757 ⟶ 1,107: Node m; m.cost = nc; m.dist = dist; m.pos = neighbour; m.parent = n.pos; open ~= m; Line 765 ⟶ 1,115: return false; } bool search( ref Point s, ref Point e, ref Map mp ) { Node n; end = e; start = s; m = mp; n.cost = 0; n.pos = s; n.parent = Point(); n.dist = calcDist( s ); open ~= n ; while( !open.empty() ) { Line 782 ⟶ 1,132: return false; } int path( ref Point[] path ) { path = end ~ path; int cost = 1 + closed.back().cost; path = closed.back().pos ~ path; Point parent = closed.back().parent; foreach(ref i ; closed.retro) { if( i.pos == parent && !( i.pos == start ) ) { Line 799 ⟶ 1,149: } }; int main(string[] argv) { Map m; Line 805 ⟶ 1,155: Point e = Point( 7, 7 ); AStar as; if( as.search( s, e, m ) ) { Point[] path; Line 821 ⟶ 1,171: writeln(); } write("\nPath cost ", c, ": "); foreach( i; path ) { Line 830 ⟶ 1,180: return 0; } </syntaxhighlight> ~~</lang>~~ {{out}} <pre> Line 845 ⟶ 1,195: Path cost 11: (0, 0) (0, 1) (0, 2) (0, 3) (0, 4) (1, 5) (2, 6) (3, 6) (4, 6) (5, 6) (6, 7) (7, 7) </pre> =={{Header\|FreeBASIC}}== <syntaxhighlight lang="freebasic"> '############################### '### A* search algorithm ### '############################### 'A number big enough to be greater than any possible path cost #define MAX_DIST 100000 type coordinates 'coordinates of a cell row as integer col as integer end type type listCoordinates 'list of coordinates length as integer coord(1 to 64) as coordinates end type type cell 'properties of a cell cost as integer g as integer f as integer parent as coordinates end type sub AddCoordinates(list as listCoordinates, c as coordinates) 'Adds coordinates c to the listCoordinates, checking if it's already present dim i as integer, inList as integer = 0 if (list.length > 0) then for i = 1 to list.length if (list.coord(i).row = c.row and list.coord(i).col = c.col) then inList = i exit for end if next if (inList > 0) then exit sub end if end if if (list.length < 64) then list.length = list.length + 1 list.coord(list.length).row = c.row list.coord(list.length).col = c.col end if end sub sub RemoveCoordinates(list as listCoordinates, c as coordinates) 'Removes coordinates c from listCoordinates dim i as integer, inList as integer = 0 if (list.length > 0) then for i = 1 to list.length if (list.coord(i).row = c.row and list.coord(i).col = c.col) then inList = i exit for end if next if (inList > 0) then list.coord(inList).row = list.coord(list.length).row list.coord(inList).col = list.coord(list.length).col list.length = list.length - 1 end if end if end sub function GetOpened(list as listCoordinates, cells() as cell) as coordinates 'Gets the cell between the open ones with the shortest expected cost dim i as integer, minf as integer dim rv as coordinates minf = 1 if (list.length > 1) then for i = 2 to list.length if (cells(list.coord(i).row, list.coord(i).col).f < cells(list.coord(minf).row, list.coord(minf).col).f) then minf = i end if next end if rv.row = list.coord(minf).row rv.col = list.coord(minf).col return rv end function function Heuristic(byval a as coordinates, byval b as coordinates) as integer 'In a chessboard, the shortest path of a king between two cells is the maximum value 'between the orizzontal distance and the vertical one. This could be used as 'heuristic value in the A* algorithm. dim dr as integer, dc as integer dr = abs(a.row - b.row) dc = abs(a.col - b.col) if (dr > dc) then return dr else return dc end if end function function IsACell(r as integer, c as integer) as integer 'It determines if a couple of indeces are inside the chessboard (returns 1) or outside (returns 0) dim isCell as integer if (r < 0 or r > 7 or c < 0 or c > 7) then isCell = 0 else isCell = 1 end if return isCell end function sub AppendCell(p as listCoordinates, c as coordinates) 'It appends che coordinates c at the end of the list p p.length = p.length + 1 p.coord(p.length).row = c.row p.coord(p.length).col = c.col end sub function InList(r as integer, c as integer, p as listCoordinates) as integer 'It determines if the cell with coordinates (r,c) is in the list p dim isInPath as integer = 0 dim i as integer for i = 1 to Ubound(p.coord) if (p.coord(i).row = r and p.coord(i).col = c) then isInPath = 1 exit for end if next return isInPath end function 'Variables declaration 'Cost to go to the cell of coordinates (row, column) dim costs(0 to 7, 0 to 7) as integer => { _ {1, 1, 1, 1, 1, 1, 1, 1}, {1, 1, 1, 1, 1, 1, 1, 1}, _ {1, 1, 1, 1, 100, 100, 100, 1}, {1, 1, 100, 1, 1, 1, 100, 1}, _ {1, 1, 100, 1, 1, 1, 100, 1}, {1, 1, 100, 100, 100, 100, 100, 1}, _ {1, 1, 1, 1, 1, 1, 1, 1}, {1, 1, 1, 1, 1, 1, 1, 1}} dim start as coordinates, finish as coordinates 'the first and the last cell dim opened as listCoordinates, closed as listCoordinates dim aCell as coordinates, nCell as coordinates 'the cell evaluates and the next one dim cells(0 to 7, 0 to 7) as cell 'the cells of the chessboard dim path as listCoordinates 'list used to the path found dim i as integer, j as integer 'MAIN PROCEDURE 'Fixing the starting cell and the finishing one start.row = 0 start.col = 0 finish.row = 7 finish.col = 7 opened.length = 0 closed.length = 0 'Initializing the chessboard for i=0 to 7 for j=0 to 7 cells(i, j).cost = costs(i, j) cells(i, j).g = MAX_DIST cells(i, j).f = MAX_DIST cells(i, j).parent.row = -1 cells(i, j).parent.col = -1 next next cells(start.row, start.col).g = 0 cells(start.row, start.col).f = Heuristic(start, finish) AddCoordinates(opened, start) do while (opened.length > 0) aCell = GetOpened(opened, cells()) for i = -1 to 1 for j = -1 to 1 if ((i <> 0 or j <> 0) and IsACell(aCell.row + i, aCell.col + j)) then nCell.row = aCell.row + i nCell.col = aCell.col + j if (nCell.row = finish.row and nCell.col = finish.col) then 'The final cell is reached cells(finish.row, finish.col).g = cells(aCell.row, aCell.col).g + cells(finish.row, finish.col).cost cells(finish.row, finish.col).parent.row = aCell.row cells(finish.row, finish.col).parent.col = aCell.col exit do end if if (InList(nCell.row, nCell.col, opened) = 0 and InList(nCell.row, nCell.col, closed) = 0) then 'This cell was never visited before cells(nCell.row, nCell.col).g = cells(aCell.row, aCell.col).g + cells(nCell.row, nCell.col).cost cells(nCell.row, nCell.col).f = cells(nCell.row, nCell.col).g + Heuristic(nCell, finish) AddCoordinates(opened, nCell) cells(nCell.row, nCell.col).parent.row = aCell.row cells(nCell.row, nCell.col).parent.col = aCell.col else 'This cell was visited before, it's reopened only if the actual path is shortest of the previous valutation if (cells(aCell.row, aCell.col).g + cells(nCell.row, nCell.col).cost < cells(nCell.row, nCell.col).g) then cells(nCell.row, nCell.col).g = cells(aCell.row, aCell.col).g + cells(nCell.row, nCell.col).cost cells(nCell.row, nCell.col).f = cells(nCell.row, nCell.col).g + Heuristic(nCell, finish) AddCoordinates(opened, nCell) RemoveCoordinates(closed, nCell) cells(nCell.row, nCell.col).parent.row = aCell.row cells(nCell.row, nCell.col).parent.col = aCell.col end if end if end if next next 'The current cell is closed AddCoordinates(closed, aCell) RemoveCoordinates(opened, aCell) loop if (cells(finish.row, finish.col).parent.row >= 0) then 'A possible path was found 'Add the cells of the shortest path to the list 'path', proceding backward path.length = 0 aCell.row = finish.row aCell.col = finish.col do while (cells(aCell.row, aCell.col).parent.row >= 0) AppendCell(path, aCell) nCell.row = cells(aCell.row, aCell.col).parent.row aCell.col = cells(aCell.row, aCell.col).parent.col aCell.row = nCell.row loop 'Drawing the path for i = 0 to 7 for j = 0 to 7 if (costs(i,j) > 1) then print chr(219); elseif (InList(i, j, path)) then print "X"; else print "."; end if next print next 'Writing the cells sequence and the path length print print "Path: " for i = path.length to 1 step -1 print "("; path.coord(i).row; ","; path.coord(i).col; ")"; next print print print "Path cost: "; cells(finish.row, finish.col).g print else print "Path not found" end if end </syntaxhighlight> {{out}} <pre> X....... .X...... ..X.███. .X█...█. .X█...█. .X█████. ..X..... ...XXXXX Path: ( 1, 1)( 2, 2)( 3, 1)( 4, 1)( 5, 1)( 6, 2)( 7, 3)( 7, 4)( 7, 5)( 7, 6)( 7, 7) Path cost: 11 </pre> =={{header\|Go}}== <~~lang~~syntaxhighlight lang="go">// Package astar implements the A* search algorithm with minimal constraints // on the graph representation. package astar Line 960 ⟶ 1,577: h[last].fx = -1 return h[last] }</~~lang~~syntaxhighlight> <~~lang~~syntaxhighlight lang="go">package main import ( Line 1,016 ⟶ 1,633: fmt.Println("Route:", route) fmt.Println("Cost:", cost) }</~~lang~~syntaxhighlight> {{out}} <pre> Line 1,022 ⟶ 1,639: Cost: 11 </pre> =={{header\|Haskell}}== The simplest standalone FIFO priority queue is implemented after Sleator and Tarjan in Louis Wasserman's ''"Playing with Priority Queues"''[https://themonadreader.files.wordpress.com/2010/05/issue16.pdf]. <syntaxhighlight lang="haskell">{-# language DeriveFoldable #-} module PQueue where data PQueue a = EmptyQueue \| Node (Int, a) (PQueue a) (PQueue a) deriving (Show, Foldable) instance Ord a => Semigroup (PQueue a) where h1@(Node (w1, x1) l1 r1) <> h2@(Node (w2, x2) l2 r2) \| w1 < w2 = Node (w1, x1) (h2 <> r1) l1 \| otherwise = Node (w2, x2) (h1 <> r2) l2 EmptyQueue <> h = h h <> EmptyQueue = h entry :: Ord a => a -> Int -> PQueue a entry x w = Node (w, x) EmptyQueue EmptyQueue enque :: Ord a => PQueue a -> a -> Int -> PQueue a enque q x w = if x `notElem` q then entry x w <> q else q deque :: Ord a => PQueue a -> Maybe (a, PQueue a) deque q = case q of EmptyQueue -> Nothing Node (_, x) l r -> Just (x, l <> r)</syntaxhighlight> The simple graph combinators: <syntaxhighlight lang="haskell">import PQueue import Data.Map (Map(..)) import qualified Data.Map as Map import Data.List (unfoldr) newtype Graph n = Graph { links :: n -> Map n Int } grid :: Int -> Int -> Graph (Int,Int) grid a b = Graph $ \(x,y) -> let links = [((x+dx,y+dy), dxdx+dydy) \| dx <- [-1..1], dy <- [-1..1] , not (dx == 0 && dy == 0) , 0 <= x+dx && x+dx <= a , 0 <= y+dy && y+dy <= b] in Map.fromList links withHole :: (Foldable t, Ord n) => Graph n -> t n -> Graph n withHole (Graph g) ns = Graph $ \x -> if x `elem` ns then Map.empty else foldr Map.delete (g x) ns </syntaxhighlight> Finally, the search algorithm, as given in Wikipedia. <syntaxhighlight lang="haskell">get :: (Ord k, Bounded a) => Map k a -> k -> a get m x = Map.findWithDefault maxBound x m set :: Ord k => Map k a -> k -> a -> Map k a set m k x = Map.insert k x m data AstarData n = SetData { cameFrom :: Map n n , gScore :: Map n Int , openSet :: PQueue n } findPath :: Ord n => Graph n -> (n -> n -> Int) -> n -> n -> [n] findPath (Graph links) metric start goal = loop a0 where a0 = SetData { cameFrom = mempty , gScore = Map.singleton start 0 , openSet = entry start (h start) } h = metric goal dist = get . links loop a = case deque (openSet a) of Nothing -> [] Just (current, q') -> if current == goal then getPath (cameFrom a) else loop a' where a' = Map.foldlWithKey go a { openSet = q' } neighbours neighbours = links current go a n _ = let g = get $ gScore a trial_Score = g current + dist current n in if trial_Score >= g n then a else SetData ( set (cameFrom a) n current ) ( set (gScore a) n trial_Score ) ( openSet a `enque` n $ trial_Score + h n ) getPath m = reverse $ goal : unfoldr go goal where go n = (\x -> (x,x)) <$> Map.lookup n m</syntaxhighlight> Example <syntaxhighlight lang="haskell">distL1 (x,y) (a,b) = max (abs $ x-a) (abs $ y-b) main = let g = grid 9 9 `withHole` wall wall = [ (2,4),(2,5),(2,6),(3,6) , (4,6),(5,6),(5,5),(5,4) , (5,3),(5,2),(3,2),(4,2) ] path = shortestPath g distL1 (1,1) (7,7) picture = [ [ case (i,j) of p \| p `elem` path -> '' \| p `elem` wall -> '#' \| otherwise -> ' ' \| i <- [0..8] ] \| j <- [0..8] ] in do print path mapM_ putStrLn picture putStrLn $ "Path score: " <> show (length path) </syntaxhighlight> <pre>λ> main [(1,1),(2,1),(3,1),(4,1),(5,1),(6,2),(6,3),(6,4),(6,5),(6,6),(7,7)] **** ###* #* # #* # #* ####* * Path score: 11</pre> =={{header\|J}}== Implementation: <syntaxhighlight lang="j"> barrier=: 2 4,2 5,2 6,3 6,4 6,5 6,5 5,5 4,5 3,5 2,4 2,:3 2 price=: _,.~_,~100 barrier} 8 8$1 dirs=: 0 0-.~>,{,~<i:1 start=: 0 0 end=: 7 7 next=: {{ frontier=. ~.locs=. ,/dests=. ($price)\|"1 ({:"2 y)+"1/dirs paths=. ,/y,"2 1/"2 dests costs=. ,x+(<"1 dests){price deals=. (1+locs <.//. costs) <. (<"1 frontier) { values keep=. costs < (frontier i. locs) { deals (keep#costs);keep#paths }} Asrch=: {{ values=: ($price)$_ best=: ($price)$a: paths=: ,:,:start costs=: ,0 while. #paths do. dests=. <"1 {:"2 paths values=: costs dests} values best=: (<"2 paths) dests} best 'costs paths'=.costs next paths end. ((<end){values) ; (<end){best }}</syntaxhighlight> Task example: <syntaxhighlight lang="j"> Asrch'' ┌──┬───┐ │11│0 0│ │ │1 1│ │ │2 2│ │ │3 1│ │ │4 1│ │ │5 1│ │ │6 2│ │ │7 3│ │ │7 4│ │ │7 5│ │ │7 6│ │ │7 7│ └──┴───┘ 'A B'=: Asrch'' 'x' (<"1 B)} '. #'{~(i.~~.@,) price x....... .x...... ..x.###. .x#...#. .x#...#. .x#####. ..x..... ...xxxxx </syntaxhighlight> Note that this is based on a literal reading of the task, where we are paying a cost to move into a new square -- here, we are not paying for the cost of the start square, because we never move into that square. If we paid to move into the start square, the final cost would have to include that price. =={{header\|Java}}== <~~lang~~syntaxhighlight lang="java"> package astar; Line 1,030 ⟶ 1,845: import java.util.ArrayList; import java.util.Collections; import java.util.PriorityQueue; import java.util.Comparator; import java.util.LinkedList; import java.util.Queue; class AStar { Line 1,041 ⟶ 1,861: private int xend, yend; private final boolean diag; // Node class for convienience static class Node implements Comparable { Line 1,102 ⟶ 1,922: } /* This ~~Looks~~function inis athe ~~given~~step ~~List<>~~of ~~for~~expanding ~~a node~~nodes @return (bool) NeightborInListFound / public void expandAStar(int[][] maze, int xstart, int ystart, boolean diag){ Queue<Mazecoord> exploreNodes = new LinkedList<Mazecoord>(); if(maze[stateNode.getR()][stateNode.getC()] == 2){ if(isNodeILegal(stateNode, stateNode.expandDirection())){ exploreNodes.add(stateNode.expandDirection()); } } / Calculate distance for goal three methods shown. ** / public void AStarSearch(){ ~~private static boolean findNeighborInList(List<Node> array, Node node) {~~ this.start.setCostToGoal(this.start.calculateCost(this.goal)); ~~return array.stream().anyMatch((n) -> (n.x == node.x && n.y == node.y));~~ this.start.setPathCost(0); this.start.setAStartCost(this.start.getPathCost() + this.start.getCostToGoal()); Mazecoord intialNode = this.start; Mazecoord stateNode = intialNode; frontier.add(intialNode); //explored<Queue> is empty while (true){ if(frontier.isEmpty()){ System.out.println("fail"); System.out.println(explored.size()); System.exit(-1); } } / Second method. ** / /* * calculate the cost from current node to goal. * @param goal : goal * @return : cost from current node to goal. use Manhattan distance. / public int calculateCost(Mazecoord goal){ int rState = this.getR(); int rGoal = goal.getR(); int diffR = rState - rGoal; int diffC = this.getC() - goal.getC(); if(diffR diffC > 0) { // same sign return Math.abs(diffR) + Math.abs(diffC); } else { return Math.max(Math.abs(diffR), Math.abs(diffC)); } } public Coord getFather(){ return this.father; } public void setFather(Mazecoord node){ this.father = node; } public int getAStartCost() { return AStartCost; } public void setAStartCost(int aStartCost) { AStartCost = aStartCost; } public int getCostToGoal() { return costToGoal; } public void setCostToGoal(int costToGoal) { this.costToGoal = costToGoal; } /* Third method. Calulate distance between this.now and xend/yend ~~@return (int) distance~~ / private double distance(int dx, int dy) { Line 1,150 ⟶ 2,039: Collections.sort(this.open); } public static void main(String[] args) { // -1 = blocked Line 1,191 ⟶ 2,080: } } </syntaxhighlight> ~~</lang>~~ {{out}} <pre> [0, 0] [1, 0] [2, 0] [3, 0] [4, 0] [5, 1] [6, 2] [7, 3] [6, 4] [6, 5] [6, 6] [7, 7] Total cost: 11,00 ***___ Line 1,208 ⟶ 2,097: =={{header\|JavaScript}}== Animated.<br />To see how it works on a random map go [http://paulo-jorente.de/tests/astar/ here] <~~lang~~syntaxhighlight lang="javascript"> var ctx, map, opn = [], clsd = [], start = {x:1, y:1, f:0, g:0}, goal = {x:8, y:8, f:0, g:0}, mw = 10, mh = 10, neighbours, path; Line 1,304 ⟶ 2,193: } } map[5][3] = map[6][3] = map[7][3] = map[3][4] = map[7][4] = map[3][5] = map[7][5] = map[3][6] = map[4][6] = map[5][6] = map[6][6] = map[7][6] = 1; //map[start.x][start.y] = 2; map[goal.x][goal.y] = 3; Line 1,315 ⟶ 2,204: document.body.appendChild( canvas ); neighbours = [ {x:1, y:0, c:1}, {x:-1, y:0, c:1}, {x:0, y:1, c:1}, {x:0, y:-1, c:1}, {x:1, y:1, c:1.4}, {x:1, y:-1, c:1.4}, {x:-1, y:1, c:1.4}, {x:-1, y:-1, c:1.4} ]; path = []; createMap(); opn.push( start ); solveMap(); } </syntaxhighlight> ~~</lang>~~ {{out}}<pre> Path: 11 [(1, 1) (2, 2) (2, 3) (2, 4) (2, 5) (2, 6) (3, 7) (4, 8) (5, 8) (6, 8) (7, 8) (8, 8) ] </pre> Implementation using recursive strategy <syntaxhighlight lang="javascript"> function manhattan(x1, y1, x2, y2) { return Math.abs(x1 - x2) + Math.abs(y1 - y2); } function aStar (board, startx, starty, goalx, goaly, open = Array(8 8).fill(null), closed = Array(8 * 8).fill(null), current = { "coord": [startx, starty], "distance": 0, "heuristic": manhattan(startx, starty, goalx, goaly), "previous": null }) { const [x, y] = [...current.coord]; if (x === goalx && y === goaly) { closed[x + y * 8] = current; return (lambda = (closed, x, y, startx, starty) => { if (x === startx && y === starty) { return [[x, y]]; } const [px, py] = closed.filter(e => e !== null) .find(({coord: [nx, ny]}) => { return nx === x && ny === y }).previous; return lambda(closed, px, py, startx, starty).concat([[x,y]]); })(closed, x, y, startx, starty); } let newOpen = open.slice(); [ [x + 1, y + 1], [x - 1, y - 1], [x + 1, y], [x, y + 1], [x - 1, y + 1], [x + 1, y - 1], [x - 1, y], [x, y - 1] ].filter(([x,y]) => x >= 0 && x < 8 && y >= 0 && y < 8 && closed[x + y * 8] === null ).forEach(([x,y]) => { newOpen[x + y * 8] = { "coord": [x,y], "distance": current.distance + (board[x + y * 8] === 1 ? 100 : 1), "heuristic": manhattan(x, y, goalx, goaly), "previous": [...current.coord] }; }); let newClosed = closed.slice(); newClosed[x + y * 8] = current; const [newCurrent,] = newOpen.filter(e => e !== null) .sort((a, b) => { return (a.distance + a.heuristic) - (b.distance + b.heuristic); }); const [newx, newy] = [...newCurrent.coord]; newOpen[newx + newy * 8] = null; return aStar(board, startx, starty, goalx, goaly, newOpen, newClosed, newCurrent); } const board = [ 0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0, 0,0,0,0,1,1,1,0, 0,0,1,0,0,0,1,0, 0,0,1,0,0,0,1,0, 0,0,1,1,1,1,1,0, 0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0 ]; console.log(aStar(board, 0,0, 7,7)); </syntaxhighlight> {{output}} <pre> [ [ 0, 0 ], [ 1, 1 ], [ 2, 2 ], [ 3, 1 ], [ 4, 1 ], [ 5, 1 ], [ 6, 1 ], [ 7, 2 ], [ 7, 3 ], [ 7, 4 ], [ 7, 5 ], [ 7, 6 ], [ 7, 7 ] ] </pre> =={{header\|Julia}}== The graphic in this solution is displayed in the more standard orientation of origin at bottom left and goal at top right. <~~lang~~syntaxhighlight ~~Julia~~lang="julia">using LightGraphs, SimpleWeightedGraphs const chessboardsize = 8 Line 1,366 ⟶ 2,332: println() end end</~~lang~~syntaxhighlight> {{output}} <pre> Solution has cost 11: Tuple{Int64,Int64}[(0, 0), (1, 1), (2, 2), (3, 1), (4, 1), (5, 1), (6, 2), (7, 3), (7, 4), (6, 5), (6, 6), (7, 7)] Line 1,380 ⟶ 2,346: =={{header\|Kotlin}}== <~~lang~~syntaxhighlight lang="kotlin"> import java.lang.Math.abs Line 1,491 ⟶ 2,457: println("Cost: $cost Path: $path") } </syntaxhighlight> ~~</lang>~~ {{out}}<pre> Cost: 11 Line 1,498 ⟶ 2,464: =={{header\|Lua}}== <~~lang~~syntaxhighlight lang="lua"> -- QUEUE ----------------------------------------------------------------------- Queue = {} Line 1,517 ⟶ 2,483: if self[i]:F() < self[1]:F() then s = self[1] self[1] = self[i] self[i] = s end Line 1,575 ⟶ 2,541: -- A-STAR ---------------------------------------------------------------------- local nbours = { { 1, 0, 1 }, { 0, 1, 1 }, { 1, 1, 1.4 }, { 1, -1, 1.4 }, { -1, -1, 1.4 }, { -1, 1, 1.4 }, { 0, -1, 1 }, { -1, 0, 1 } } local map = { 1,1,1,1,1,1,1,1,1,1, 1,0,0,0,0,0,0,0,0,1, 1,0,0,0,0,0,0,0,0,1, Line 1,588 ⟶ 2,554: 1,0,0,0,0,0,0,0,0,1, 1,0,0,0,0,0,0,0,0,1, 1,1,1,1,1,1,1,1,1,1 } local open, closed, start, goal, mapW, mapH = Queue:new(), List:new(), Point:new(), Point:new(), 10, 10 start:set( 2, 2 ); goal:set( 9, 9 ) Line 1,603 ⟶ 2,569: end function isValid( pos ) return pos.x > 0 and pos.x <= mapW and pos.y > 0 and pos.y <= mapH and map[pos.x + mapW * pos.y - mapW] == 0 end Line 1,619 ⟶ 2,585: nNode.cost = node.cost + nbours[n][3] nNode.dist = calcDist( nNode.pos ) if isValid( nNode.pos ) then if nNode.pos:equals( goal ) then closed:push( nNode ) return true end nx = hasNode( closed, nNode.pos ) Line 1,629 ⟶ 2,595: nx = hasNode( open, nNode.pos ) if( nx < 0 ) or ( nx > 0 and nNode:F() < open[nx]:F() ) then if( nx > 0 ) then table.remove( open, nx ) end Line 1,672 ⟶ 2,638: if node == nil then break end closed:push( node ) if addToOpen( node ) == true then makePath() return true end end Line 1,698 ⟶ 2,664: print( "can not find a path!" ) end </syntaxhighlight> ~~</lang>~~ {{out}} <pre> Line 1,717 ⟶ 2,683: =={{header\|Nim}}== Implementation of the Wikipedia pseudocode. <syntaxhighlight lang="nim"> ~~<lang Nim>~~ # A* search algorithm. Line 1,848 ⟶ 2,814: else: printSolution(path, cost) </syntaxhighlight> ~~</lang>~~ {{out}} Line 1,873 ⟶ 2,839: A very close/straightforward implementation of the Wikipedia pseudocode. <~~lang~~syntaxhighlight lang="ocaml"> module IntPairs = struct Line 2,002 ⟶ 2,968: print_newline () ) _board; print_newline ()</~~lang~~syntaxhighlight> {{out}} Line 2,031 ⟶ 2,997: =={{header\|Ol}}== <~~lang~~syntaxhighlight lang="scheme"> ; level: list of lists, any except 1 means the cell is empty ; from: start cell in (x . y) mean Line 2,097 ⟶ 3,063: (cons (+ x 1) y))))) (step1 (- n 1) c-list-set o-list-set)))))))) </syntaxhighlight> ~~</lang>~~ {{out}} <~~lang~~syntaxhighlight lang="scheme"> (define level '( (1 1 1 1 1 1 1 1 1 1) Line 2,155 ⟶ 3,121: (for-each print solved) </syntaxhighlight> ~~</lang>~~ <pre> Line 2,199 ⟶ 3,165: (1 1 1 1 1 1 1 1 1 1) </pre> =={{header\|Perl}}== <syntaxhighlight lang="perl">#!/usr/bin/perl use strict; # https://rosettacode.org/wiki/A_search_algorithm use warnings; use List::AllUtils qw( nsort_by ); sub distance { my ($r1, $c1, $r2, $c2) = split /[, ]/, "@_"; sqrt( ($r1-$r2)2 + ($c1-$c2)2 ); } my $start = '0,0'; my $finish = '7,7'; my %barrier = map {$_, 100} split ' ', '2,4 2,5 2,6 3,6 4,6 5,6 5,5 5,4 5,3 5,2 4,2 3,2'; my %values = ( $start, 0 ); my @new = [ $start, 0 ]; my %from; my $mid; while( ! exists $values{$finish} and @new ) { my $pick = (shift @new)->[0]; for my $n ( nsort_by { distance($_, $finish) } # heuristic grep !/-\|8/ && ! exists $values{$_}, glob $pick =~ s/\d+/{@{[$&-1]},$&,@{[$&+1]}}/gr ) { $from{$n} = $pick; $values{$n} = $values{$pick} + ( $barrier{$n} // 1 ); my $new = [ $n, my $dist = $values{$n} ]; my $low = 0; # binary insertion into @new (the priority queue) my $high = @new; $new[$mid = $low + $high >> 1][1] <= $dist ? ($low = $mid + 1) : ($high = $mid) while $low < $high; splice @new, $low, 0, $new; # insert in order } } my $grid = "s.......\n" . ('.' x 8 . "\n") x 7; substr $grid, /,/ $` * 9 + $', 1, 'b' for keys %barrier; my @path = my $pos = $finish; # the walkback to get path while( $pos ne $start ) { substr $grid, $pos =~ /,/ ? $` * 9 + $' : die, 1, 'x'; unshift @path, $pos = $from{$pos}; } print "$grid\nvalue $values{$finish} path @path\n";</syntaxhighlight> {{out}} <pre> s....... .x...... ..x.bbb. .xb...b. .xb...b. .xbbbbb. ..x..... ...xxxxx value 11 path 0,0 1,1 2,2 3,1 4,1 5,1 6,2 7,3 7,4 7,5 7,6 7,7 </pre> ===Extra Credit=== <syntaxhighlight lang="perl">#!/usr/bin/perl use strict; # https://rosettacode.org/wiki/A_search_algorithm use warnings; # extra credit use List::AllUtils qw( sum ); my $start = <<END; 087 654 321 END my $finish = <<END; 123 456 780 END my @tiles = $finish =~ /[1-9a-z]/g; my $width = index $start, "\n"; my $gap = qr/.{$width}/s; my $mod = $width + 1; my %rc = map {$_, int($_ / $mod) . ',' . ($_ % $mod)} 0 .. length($start) - 2; my %finishrc = map { $_, [ split /,/, $rc{index $finish, $_} ] } @tiles; my %found = ( $start, 1 ); my @new = [ $start, heuristic($start) ]; # a priority queue my %from; my $mid; while( ! exists $found{$finish} and @new ) { my $pick = (shift @new)->[0]; for my $n ( grep ! exists $found{$_}, $pick =~ s/0(\w)/${1}0/r, # up $pick =~ s/(\w)0/0$1/r, # down $pick =~ s/0($gap)(\w)/$2${1}0/r, # left $pick =~ s/(\w)($gap)0/0$2$1/r, # right ) { $found{$n} = $from{$n} = $pick; my $new = [ $n, my $dist = heuristic( $n ) ]; my $low = 0; # binary insertion into @new (the priority queue) my $high = @new; $new[$mid = $low + $high >> 1][1] <= $dist ? ($low = $mid + 1) : ($high = $mid) while $low < $high; splice @new, $low, 0, $new; # insert in order } } #use Data::Dump 'dd'; dd \%found; my $count = keys %found; exists $found{$finish} or die "no solution found with $count\n"; my @path = my $pos = $finish; # the walkback to get path unshift @path, $pos = $from{$pos} while $pos ne $start; my $steps = @path - 1; my $states = keys %found; #print "$_\n" for @path; my (undef, $w) = split ' ', qx(stty size); while( @path ) { my @section = splice @path, 0, int( $w / ($mod + 1) ); while( $section[0] ) { s/(.)\n/ print "$1 "; ''/e for @section; print "\n"; } print "\n"; } print "steps: $steps states: $states\n"; sub heuristic { my $from = shift; sum map { my ($r1, $c1) = split /,/, $rc{index $from, $_}; my ($r2, $c2) = @{ $finishrc{$_} }; abs($r1 - $r2) + abs($c1 - $c2) } @tiles; }</syntaxhighlight> {{out}} <pre> 087 807 870 874 874 874 874 874 074 704 740 741 741 741 741 741 041 654 654 654 650 651 651 651 051 851 851 851 850 852 852 852 052 752 321 321 321 321 320 302 032 632 632 632 632 632 630 603 063 863 863 401 410 412 412 412 412 412 012 102 120 123 123 752 752 750 753 753 753 053 453 453 453 450 456 863 863 863 860 806 086 786 786 786 786 786 780 steps: 28 states: 53 </pre>k =={{header\|Phix}}== rows and columns are numbered 1 to 8. start position is {1,1} and end position is {8,8}. barriers are simply avoided, rather than costed at 100. Note that the 23 visited nodes does not count walls, but with them this algorithm exactly matches the 35 of Racket. ~~<lang Phix>sequence grid = split("""~~ <!--<syntaxhighlight lang="phix">(phixonline)--> ~~x:::::::~~ <span style="color: #004080;">sequence</span> <span style="color: #000000;">grid</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">split</span><span style="color: #0000FF;">(</span><span style="color: #008000;">""" ~~::::::::~~ x::::::~~###~~: ::::#:::#: ::#:::###: ::#~~###~~:::#: ::#:::::#: ::~~:::::~~#####: :::::::: ~~""",'\n')~~ :::::::: """</span><span style="color: #0000FF;">,</span><span style="color: #008000;">'\n'</span><span style="color: #0000FF;">)</span> ~~constant permitted = {{-1,-1},{0,-1},{1,-1},~~ <span style="color: #008080;">constant</span> <span style="color: #000000;">permitted</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{{-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">},</span> ~~{-1, 0}, {1, 0},~~ <span style="color: #0000FF;">{-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">},</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">},</span> ~~{-1, 1},{0,+1},{1,+1}}~~ <span style="color: #0000FF;">{-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">}}</span> <span style="color: #004080;">sequence</span> <span style="color: #000000;">key</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">7</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0</span><span style="color: #0000FF;">},</span> <span style="color: #000080;font-style:italic;">-- chebyshev, cost</span> ~~sequence key = {7,0}, -- chebyshev, cost~~ <span style="color: #000000;">moves</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{{</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">}},</span> ~~moves = {{1,1}},~~ <span style="color: #000000;">data</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">moves</span><span style="color: #0000FF;">},</span> ~~data = {moves},~~ <span style="color: #000000;">acta</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{}</span> <span style="color: #000080;font-style:italic;">-- actually analysed set</span> <span style="color: #7060A8;">setd</span><span style="color: #0000FF;">(</span><span style="color: #000000;">key</span><span style="color: #0000FF;">,</span><span style="color: #000000;">data</span><span style="color: #0000FF;">)</span> ~~setd(key,data)~~ <span style="color: #004080;">bool</span> <span style="color: #000000;">found</span> <span style="color: #0000FF;">=</span> <span style="color: #004600;">false</span> ~~bool found = false~~ <span style="color: #004080;">integer</span> <span style="color: #000000;">count</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span> ~~integer count = 0~~ <span style="color: #008080;">while</span> <span style="color: #008080;">not</span> <span style="color: #000000;">found</span> <span style="color: #008080;">do</span> ~~while not found do~~ <span style="color: #008080;">if</span> <span style="color: #7060A8;">dict_size</span><span style="color: #0000FF;">()=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span> <span style="color: #0000FF;">?</span><span style="color: #008000;">"impossible"</span> <span style="color: #008080;">exit</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span> ~~if dict_size()=0 then ?"impossible" exit end if~~ <span style="color: #000000;">key</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">getd_partial_key</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0</span><span style="color: #0000FF;">)</span> ~~key = getd_partial_key(0)~~ <span style="color: #000000;">data</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">getd</span><span style="color: #0000FF;">(</span><span style="color: #000000;">key</span><span style="color: #0000FF;">)</span> ~~data = getd(key)~~ <span style="color: #000000;">moves</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">data</span><span style="color: #0000FF;">[$]</span> ~~moves = data[$]~~ <span style="color: #008080;">if</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">data</span><span style="color: #0000FF;">)=</span><span style="color: #000000;">1</span> <span style="color: #008080;">then</span> ~~if length(data)=1 then~~ <span style="color: #7060A8;">deld</span><span style="color: #0000FF;">(</span><span style="color: #000000;">key</span><span style="color: #0000FF;">)</span> ~~deld(key)~~ <span style="color: #008080;">else</span> ~~else~~ <span style="color: #000000;">data</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">data</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">..$-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span> ~~data = data[1..$-1]~~ <span style="color: #7060A8;">putd</span><span style="color: #0000FF;">(</span><span style="color: #000000;">key</span><span style="color: #0000FF;">,</span><span style="color: #000000;">data</span><span style="color: #0000FF;">)</span> ~~putd(key,data)~~ <span style="color: #008080;">end</span> <span style="color: #008080;">if</span> ~~end if~~ <span style="color: #000000;">count</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span> ~~count += 1~~ <span style="color: #000000;">acta</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #000000;">acta</span><span style="color: #0000FF;">,</span><span style="color: #000000;">moves</span><span style="color: #0000FF;">[$])</span> ~~acta = append(acta,moves[$])~~ <span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">permitted</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span> ~~for i=1 to length(permitted) do~~ <span style="color: #004080;">sequence</span> <span style="color: #000000;">newpos</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">sq_add</span><span style="color: #0000FF;">(</span><span style="color: #000000;">moves</span><span style="color: #0000FF;">[$],</span><span style="color: #000000;">permitted</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">])</span> ~~sequence newpos = sq_add(moves[$],permitted[i])~~ <span style="color: #004080;">integer</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">nx</span><span style="color: #0000FF;">,</span><span style="color: #000000;">ny</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">newpos</span> ~~integer {nx,ny} = newpos~~ <span style="color: #008080;">if</span> <span style="color: #000000;">nx</span><span style="color: #0000FF;">>=</span><span style="color: #000000;">1</span> <span style="color: #008080;">and</span> <span style="color: #000000;">nx</span><span style="color: #0000FF;"><=</span><span style="color: #000000;">8</span> ~~if nx>=1 and nx<=8~~ <span style="color: #008080;">and</span> <span style="color: #000000;">ny</span><span style="color: #0000FF;">>=</span><span style="color: #000000;">1</span> <span style="color: #008080;">and</span> <span style="color: #000000;">ny</span><span style="color: #0000FF;"><=</span><span style="color: #000000;">8</span> ~~and ny>=1 and ny<=8~~ <span style="color: #008080;">and</span> <span style="color: #000000;">grid</span><span style="color: #0000FF;">[</span><span style="color: #000000;">nx</span><span style="color: #0000FF;">,</span><span style="color: #000000;">ny</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">':'</span> <span style="color: #008080;">then</span> <span style="color: #000080;font-style:italic;">-- (unvisited)</span> ~~and grid[nx,ny] = ':' then -- (unvisited)~~ <span style="color: #000000;">grid</span><span style="color: #0000FF;">[</span><span style="color: #000000;">nx</span><span style="color: #0000FF;">,</span><span style="color: #000000;">ny</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">'.'</span> ~~grid[nx,ny] = '.'~~ <span style="color: #004080;">sequence</span> <span style="color: #000000;">newkey</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #7060A8;">max</span><span style="color: #0000FF;">(</span><span style="color: #000000;">8</span><span style="color: #0000FF;">-</span><span style="color: #000000;">nx</span><span style="color: #0000FF;">,</span><span style="color: #000000;">8</span><span style="color: #0000FF;">-</span><span style="color: #000000;">ny</span><span style="color: #0000FF;">),</span><span style="color: #000000;">key</span><span style="color: #0000FF;">[</span><span style="color: #000000;">2</span><span style="color: #0000FF;">]+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">},</span> ~~sequence newkey = {max(8-nx,8-ny),key[2]+1},~~ <span style="color: #000000;">newmoves</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">deep_copy</span><span style="color: #0000FF;">(</span><span style="color: #000000;">moves</span><span style="color: #0000FF;">)</span> ~~newmoves = append(moves,newpos)~~ <span style="color: #000000;">newmoves</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #000000;">newmoves</span><span style="color: #0000FF;">,</span><span style="color: #000000;">newpos</span><span style="color: #0000FF;">)</span> ~~if newpos = {8,8} then~~ <span style="color: #008080;">if</span> <span style="color: #000000;">newpos</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">8</span><span style="color: #0000FF;">,</span><span style="color: #000000;">8</span><span style="color: #0000FF;">}</span> <span style="color: #008080;">then</span> ~~moves = newmoves~~ <span style="color: #000000;">moves</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">newmoves</span> ~~found = true~~ <span style="color: #000000;">found</span> <span style="color: #0000FF;">=</span> <span style="color: #004600;">true</span> ~~exit~~ ~~end~~ if <span style="color: #008080;">exit</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span> ~~integer k = getd_index(newkey)~~ <span style="color: #004080;">integer</span> <span style="color: #000000;">k</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">getd_index</span><span style="color: #0000FF;">(</span><span style="color: #000000;">newkey</span><span style="color: #0000FF;">)</span> ~~if k=0 then~~ <span style="color: #008080;">if</span> <span style="color: #000000;">k</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span> ~~data = {newmoves}~~ <span style="color: #000000;">data</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{}</span> ~~else~~ <span ~~data~~ style="color: ~~append(getd_by_index(k),newmoves)~~#008080;">else</span> <span style="color: #000000;">data</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">deep_copy</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">getd_by_index</span><span style="color: #0000FF;">(</span><span style="color: #000000;">k</span><span style="color: #0000FF;">))</span> ~~end if~~ <span style="color: #008080;">end</span> <span style="color: #008080;">if</span> ~~putd(newkey,data)~~ <span style="color: #000000;">data</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #000000;">data</span><span style="color: #0000FF;">,</span><span style="color: #000000;">newmoves</span><span style="color: #0000FF;">)</span> ~~end if~~ <span style="color: #7060A8;">putd</span><span style="color: #0000FF;">(</span><span style="color: #000000;">newkey</span><span style="color: #0000FF;">,</span><span style="color: #000000;">data</span><span style="color: #0000FF;">)</span> ~~end for~~ <span style="color: #008080;">end</span> <span style="color: #008080;">if</span> ~~end while~~ <span style="color: #008080;">end</span> <span style="color: #008080;">for</span> ~~if found then~~ <span style="color: #008080;">end</span> <span style="color: #008080;">while</span> ~~printf(1,"visited %d nodes\ncost:%d\npath:%v\n",{count,length(moves)-1,moves})~~ <span style="color: #008080;">if</span> <span style="color: #000000;">found</span> <span style="color: #008080;">then</span> ~~for i=1 to length(acta) do~~ <span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"visited %d nodes\ncost:%d\npath:%v\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">count</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">moves</span><span style="color: #0000FF;">)-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">moves</span><span style="color: #0000FF;">})</span> ~~integer {x,y} = acta[i]~~ <span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">acta</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span> ~~grid[x,y] = '_'~~ <span style="color: #004080;">integer</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">x</span><span style="color: #0000FF;">,</span><span style="color: #000000;">y</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">acta</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span> ~~end for~~ <span style="color: #000000;">grid</span><span style="color: #0000FF;">[</span><span style="color: #000000;">x</span><span style="color: #0000FF;">,</span><span style="color: #000000;">y</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">'_'</span> ~~for i=1 to length(moves) do~~ <span style="color: #008080;">end</span> <span style="color: #008080;">for</span> ~~integer {x,y} = moves[i]~~ <span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">moves</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span> ~~grid[x,y] = 'x'~~ <span style="color: #004080;">integer</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">x</span><span style="color: #0000FF;">,</span><span style="color: #000000;">y</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">moves</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span> ~~end for~~ <span style="color: #000000;">grid</span><span style="color: #0000FF;">[</span><span style="color: #000000;">x</span><span style="color: #0000FF;">,</span><span style="color: #000000;">y</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">'x'</span> ~~puts(1,join(grid,'\n'))~~ <span style="color: #008080;">end</span> <span style="color: #008080;">for</span> ~~end if</lang>~~ <span style="color: #7060A8;">puts</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">join</span><span style="color: #0000FF;">(</span><span style="color: #000000;">grid</span><span style="color: #0000FF;">,</span><span style="color: #008000;">'\n'</span><span style="color: #0000FF;">))</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span> <!--</syntaxhighlight>--> {{out}} <pre> Line 2,295 ⟶ 3,420: task author assumed it would, instead the main loop uses a priority queue to obtain the next lowest cost and a simple dictionary to avoid re-examination/inifinte recursion. ~~<lang Phix>--set_rand(3) -- (for consistent output)~~ ~~constant optimal = false,~~ ~~mtm = true, -- mutli-tile metrics~~ ~~target = {1,2,3,4,5,6,7,8,0},~~ ~~-- <-tile found 0..8->~~ ~~mcost = {{0,0,1,2,1,2,3,2,3}, -- position 1~~ ~~{0,1,0,1,2,1,2,3,2},~~ ~~{0,2,1,0,3,2,1,4,3},~~ ~~{0,1,2,3,0,1,2,1,2},~~ ~~{0,2,1,2,1,0,1,2,1}, -- ...~~ ~~{0,3,2,1,2,1,0,3,2},~~ ~~{0,2,3,4,1,2,3,0,1},~~ ~~{0,3,2,3,2,1,2,1,0},~~ ~~{0,4,3,2,3,2,1,2,1}}, -- position 9~~ ~~udlr = "udlr",~~ ~~dirs = {+3,-3,+1,-1}, -- udlr~~ ~~lims = {{9,9,9,9,9,9,9,9,9}, -- up~~ ~~{1,1,1,1,1,1,1,1,1}, -- down~~ ~~{3,3,3,6,6,6,9,9,9}, -- left~~ ~~{1,1,1,4,4,4,7,7,7}} -- right~~ ~~function get_moves(sequence grid, bool mtm)~~ ~~sequence valid = {}~~ ~~integer p0 = find(0,grid)~~ ~~for dx=1 to length(dirs) do~~ ~~integer step = dirs[dx],~~ ~~lim = lims[dx][p0],~~ ~~count = 1~~ ~~for i=p0+step to lim by step do~~ ~~valid = append(valid,{step,i,udlr[dx],count})~~ ~~if not mtm then exit end if~~ ~~count += 1~~ ~~end for~~ ~~end for~~ ~~return valid~~ ~~end function~~ <!--<syntaxhighlight lang="phix">(phixonline)--> ~~function make_move(sequence grid, move)~~ <span style="color: #000080;font-style:italic;">--set_rand(3) -- (for consistent output)</span> ~~integer p0 = find(0,grid),~~ <span style="color: #008080;">constant</span> <span style="color: #000000;">optimal</span> <span style="color: #0000FF;">=</span> <span style="color: #004600;">false</span><span style="color: #0000FF;">,</span> ~~{step,lim} = move~~ <span style="color: #000000;">mtm</span> <span style="color: #0000FF;">=</span> <span style="color: #004600;">true</span><span style="color: #0000FF;">,</span> <span style="color: #000080;font-style:italic;">-- mutli-tile metrics</span> ~~for i=p0+step to lim by step do~~ <span style="color: #7060A8;">target</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">3</span><span style="color: #0000FF;">,</span><span style="color: #000000;">4</span><span style="color: #0000FF;">,</span><span style="color: #000000;">5</span><span style="color: #0000FF;">,</span><span style="color: #000000;">6</span><span style="color: #0000FF;">,</span><span style="color: #000000;">7</span><span style="color: #0000FF;">,</span><span style="color: #000000;">8</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0</span><span style="color: #0000FF;">},</span> ~~grid[p0] = grid[i]~~ <span style="color: #000080;font-style:italic;">-- <-tile found 0..8-></span> ~~grid[i] = 0~~ <span style="color: #000000;">mcost</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{{</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">3</span><span style="color: #0000FF;">,</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">3</span><span style="color: #0000FF;">},</span> <span style="color: #000080;font-style:italic;">-- position 1</span> ~~p0 = i~~ <span style="color: #0000FF;">{</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">3</span><span style="color: #0000FF;">,</span><span style="color: #000000;">2</span><span style="color: #0000FF;">},</span> ~~end for~~ <span style="color: #0000FF;">{</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">3</span><span style="color: #0000FF;">,</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">4</span><span style="color: #0000FF;">,</span><span style="color: #000000;">3</span><span style="color: #0000FF;">},</span> ~~return grid~~ <span style="color: #0000FF;">{</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">3</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">2</span><span style="color: #0000FF;">},</span> ~~end function~~ <span style="color: #0000FF;">{</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">},</span> <span style="color: #000080;font-style:italic;">-- ...</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">3</span><span style="color: #0000FF;">,</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">3</span><span style="color: #0000FF;">,</span><span style="color: #000000;">2</span><span style="color: #0000FF;">},</span> ~~function manhattan(sequence grid)~~ <span style="color: #0000FF;">{</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">3</span><span style="color: #0000FF;">,</span><span style="color: #000000;">4</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">3</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">},</span> ~~integer res = 0~~ <span style="color: #0000FF;">{</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">3</span><span style="color: #0000FF;">,</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">3</span><span style="color: #0000FF;">,</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0</span><span style="color: #0000FF;">},</span> ~~for i=1 to 9 do~~ <span style="color: #0000FF;">{</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">4</span><span style="color: #0000FF;">,</span><span style="color: #000000;">3</span><span style="color: #0000FF;">,</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">3</span><span style="color: #0000FF;">,</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">}},</span> <span style="color: #000080;font-style:italic;">-- position 9</span> ~~res += mcost[i][grid[i]+1]~~ <span style="color: #000000;">udlr</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">"udlr"</span><span style="color: #0000FF;">,</span> ~~end for~~ <span style="color: #000000;">dirs</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{+</span><span style="color: #000000;">3</span><span style="color: #0000FF;">,-</span><span style="color: #000000;">3</span><span style="color: #0000FF;">,+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">},</span> <span style="color: #000080;font-style:italic;">-- udlr</span> ~~return res~~ <span style="color: #000000;">lims</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{{</span><span style="color: #000000;">9</span><span style="color: #0000FF;">,</span><span style="color: #000000;">9</span><span style="color: #0000FF;">,</span><span style="color: #000000;">9</span><span style="color: #0000FF;">,</span><span style="color: #000000;">9</span><span style="color: #0000FF;">,</span><span style="color: #000000;">9</span><span style="color: #0000FF;">,</span><span style="color: #000000;">9</span><span style="color: #0000FF;">,</span><span style="color: #000000;">9</span><span style="color: #0000FF;">,</span><span style="color: #000000;">9</span><span style="color: #0000FF;">,</span><span style="color: #000000;">9</span><span style="color: #0000FF;">},</span> <span style="color: #000080;font-style:italic;">-- up</span> ~~end function~~ <span style="color: #0000FF;">{</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">},</span> <span style="color: #000080;font-style:italic;">-- down</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">3</span><span style="color: #0000FF;">,</span><span style="color: #000000;">3</span><span style="color: #0000FF;">,</span><span style="color: #000000;">3</span><span style="color: #0000FF;">,</span><span style="color: #000000;">6</span><span style="color: #0000FF;">,</span><span style="color: #000000;">6</span><span style="color: #0000FF;">,</span><span style="color: #000000;">6</span><span style="color: #0000FF;">,</span><span style="color: #000000;">9</span><span style="color: #0000FF;">,</span><span style="color: #000000;">9</span><span style="color: #0000FF;">,</span><span style="color: #000000;">9</span><span style="color: #0000FF;">},</span> <span style="color: #000080;font-style:italic;">-- left</span> ~~sequence problem, grid, new_grid,~~ <span style="color: #0000FF;">{</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">4</span><span style="color: #0000FF;">,</span><span style="color: #000000;">4</span><span style="color: #0000FF;">,</span><span style="color: #000000;">4</span><span style="color: #0000FF;">,</span><span style="color: #000000;">7</span><span style="color: #0000FF;">,</span><span style="color: #000000;">7</span><span style="color: #0000FF;">,</span><span style="color: #000000;">7</span><span style="color: #0000FF;">}}</span> <span style="color: #000080;font-style:italic;">-- right</span> ~~moves, next_moves, move~~ <span style="color: #008080;">function</span> <span style="color: #000000;">get_moves</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">grid</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">bool</span> <span style="color: #000000;">mtm</span><span style="color: #0000FF;">)</span> ~~procedure show_grid()~~ <span style="color: #004080;">sequence</span> <span style="color: #000000;">valid</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{}</span> ~~printf(1,"%s\n",join_by(sq_add(grid,'0'),1,3,""))~~ <span style="color: #004080;">integer</span> <span style="color: #000000;">p0</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">find</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">grid</span><span style="color: #0000FF;">)</span> ~~end procedure~~ <span style="color: #008080;">for</span> <span style="color: #000000;">dx</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">dirs</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span> <span style="color: #004080;">integer</span> <span style="color: #000000;">step</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">dirs</span><span style="color: #0000FF;">[</span><span style="color: #000000;">dx</span><span style="color: #0000FF;">],</span> ~~grid = target~~ <span style="color: #000000;">lim</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">lims</span><span style="color: #0000FF;">[</span><span style="color: #000000;">dx</span><span style="color: #0000FF;">][</span><span style="color: #000000;">p0</span><span style="color: #0000FF;">],</span> ~~for i=1 to 1000 do~~ <span style="color: #000000;">count</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1</span> ~~-- (initially shuffle as if mtm==true, otherwise~~ <span style="color: #004080;">integer</span> <span style="color: #000000;">i</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">p0</span><span style="color: #0000FF;">+</span><span style="color: #000000;">step</span> ~~-- output compares answers to different puzzles)~~ <span style="color: #008080;">while</span> <span style="color: #004600;">true</span> <span style="color: #008080;">do</span> ~~moves = get_moves(grid,true)~~ <span style="color: #008080;">if</span> <span style="color: #000000;">step</span><span style="color: #0000FF;"><</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span> ~~move = moves[rand(length(moves))]~~ <span style="color: #008080;">if</span> <span style="color: #000000;">i</span><span style="color: #0000FF;"><</span><span style="color: #000000;">lim</span> <span style="color: #008080;">then</span> <span style="color: #008080;">exit</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span> ~~grid = make_move(grid,move)~~ <span style="color: #008080;">else</span> ~~end for~~ <span style="color: #008080;">if</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">></span><span style="color: #000000;">lim</span> <span style="color: #008080;">then</span> <span style="color: #008080;">exit</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span> ~~problem = grid~~ <span style="color: #008080;">end</span> <span style="color: #008080;">if</span> ~~printf(1,"problem (manhattan cost is %d):\n",manhattan(grid))~~ <span style="color: #000000;">valid</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #000000;">valid</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">step</span><span style="color: #0000FF;">,</span><span style="color: #000000;">i</span><span style="color: #0000FF;">,</span><span style="color: #000000;">udlr</span><span style="color: #0000FF;">[</span><span style="color: #000000;">dx</span><span style="color: #0000FF;">],</span><span style="color: #000000;">count</span><span style="color: #0000FF;">})</span> ~~show_grid()~~ <span style="color: #008080;">if</span> <span style="color: #008080;">not</span> <span style="color: #000000;">mtm</span> <span style="color: #008080;">then</span> <span style="color: #008080;">exit</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span> <span style="color: #000000;">count</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span> <span style="color: #000000;">i</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">step</span> <span style="color: #008080;">end</span> <span style="color: #008080;">while</span> <span style="color: #008080;">end</span> <span style="color: #008080;">for</span> <span style="color: #008080;">return</span> <span style="color: #000000;">valid</span> <span style="color: #008080;">end</span> <span style="color: #008080;">function</span> <span style="color: #008080;">function</span> <span style="color: #000000;">make_move</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">grid</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">move</span><span style="color: #0000FF;">)</span> <span style="color: #004080;">integer</span> <span style="color: #000000;">p0</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">find</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">grid</span><span style="color: #0000FF;">),</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">step</span><span style="color: #0000FF;">,</span><span style="color: #000000;">lim</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">move</span> <span style="color: #000000;">grid</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">deep_copy</span><span style="color: #0000FF;">(</span><span style="color: #000000;">grid</span><span style="color: #0000FF;">)</span> <span style="color: #004080;">integer</span> <span style="color: #000000;">i</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">p0</span><span style="color: #0000FF;">+</span><span style="color: #000000;">step</span> <span style="color: #008080;">while</span> <span style="color: #004600;">true</span> <span style="color: #008080;">do</span> <span style="color: #008080;">if</span> <span style="color: #000000;">step</span><span style="color: #0000FF;"><</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span> <span style="color: #008080;">if</span> <span style="color: #000000;">i</span><span style="color: #0000FF;"><</span><span style="color: #000000;">lim</span> <span style="color: #008080;">then</span> <span style="color: #008080;">exit</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span> <span style="color: #008080;">else</span> <span style="color: #008080;">if</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">></span><span style="color: #000000;">lim</span> <span style="color: #008080;">then</span> <span style="color: #008080;">exit</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span> <span style="color: #000000;">grid</span><span style="color: #0000FF;">[</span><span style="color: #000000;">p0</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">grid</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span> <span style="color: #000000;">grid</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span> <span style="color: #000000;">p0</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">i</span> <span style="color: #000000;">i</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">step</span> <span style="color: #008080;">end</span> <span style="color: #008080;">while</span> <span style="color: #008080;">return</span> <span style="color: #000000;">grid</span> <span style="color: #008080;">end</span> <span style="color: #008080;">function</span> <span style="color: #008080;">function</span> <span style="color: #000000;">manhattan</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">grid</span><span style="color: #0000FF;">)</span> <span style="color: #004080;">integer</span> <span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span> <span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">9</span> <span style="color: #008080;">do</span> <span style="color: #000000;">res</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">mcost</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">][</span><span style="color: #000000;">grid</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span> <span style="color: #008080;">end</span> <span style="color: #008080;">for</span> <span style="color: #008080;">return</span> <span style="color: #000000;">res</span> <span style="color: #008080;">end</span> <span style="color: #008080;">function</span> <span style="color: #004080;">sequence</span> <span style="color: #000000;">problem</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">grid</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">new_grid</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">moves</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">next_moves</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">move</span> <span style="color: #008080;">procedure</span> <span style="color: #000000;">show_grid</span><span style="color: #0000FF;">()</span> <span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%s\n"</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">join_by</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">sq_add</span><span style="color: #0000FF;">(</span><span style="color: #000000;">grid</span><span style="color: #0000FF;">,</span><span style="color: #008000;">'0'</span><span style="color: #0000FF;">),</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">3</span><span style="color: #0000FF;">,</span><span style="color: #008000;">""</span><span style="color: #0000FF;">))</span> <span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span> <span style="color: #000000;">grid</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">target</span> <span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">1000</span> <span style="color: #008080;">do</span> <span style="color: #000080;font-style:italic;">-- (initially shuffle as if mtm==true, otherwise -- output compares answers to different puzzles)</span> <span style="color: #000000;">moves</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">get_moves</span><span style="color: #0000FF;">(</span><span style="color: #000000;">grid</span><span style="color: #0000FF;">,</span><span style="color: #004600;">true</span><span style="color: #0000FF;">)</span> <span style="color: #000000;">move</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">moves</span><span style="color: #0000FF;">[</span><span style="color: #7060A8;">rand</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">moves</span><span style="color: #0000FF;">))]</span> <span style="color: #000000;">grid</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">make_move</span><span style="color: #0000FF;">(</span><span style="color: #000000;">grid</span><span style="color: #0000FF;">,</span><span style="color: #000000;">move</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">end</span> <span style="color: #008080;">for</span> <span style="color: #000000;">problem</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">grid</span> <span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"problem (manhattan cost is %d):\n"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">manhattan</span><span style="color: #0000FF;">(</span><span style="color: #000000;">grid</span><span style="color: #0000FF;">))</span> <span style="color: #000000;">show_grid</span><span style="color: #0000FF;">()</span> <span style="color: #004080;">integer</span> <span style="color: #000000;">todo</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">pq_new</span><span style="color: #0000FF;">(),</span> <span style="color: #000000;">seen</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">new_dict</span><span style="color: #0000FF;">()</span> <span style="color: #7060A8;">pq_add</span><span style="color: #0000FF;">({{</span><span style="color: #000000;">grid</span><span style="color: #0000FF;">,{}},</span><span style="color: #008080;">iff</span><span style="color: #0000FF;">(</span><span style="color: #000000;">optimal</span><span style="color: #0000FF;">?</span><span style="color: #000000;">0</span><span style="color: #0000FF;">:</span><span style="color: #000000;">manhattan</span><span style="color: #0000FF;">(</span><span style="color: #000000;">grid</span><span style="color: #0000FF;">))},</span><span style="color: #000000;">todo</span><span style="color: #0000FF;">)</span> <span style="color: #7060A8;">setd</span><span style="color: #0000FF;">(</span><span style="color: #000000;">grid</span><span style="color: #0000FF;">,</span><span style="color: #004600;">true</span><span style="color: #0000FF;">,</span><span style="color: #000000;">seen</span><span style="color: #0000FF;">)</span> <span style="color: #004080;">atom</span> <span style="color: #000000;">t1</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">time</span><span style="color: #0000FF;">()+</span><span style="color: #000000;">1</span> <span style="color: #004080;">bool</span> <span style="color: #000000;">found</span> <span style="color: #0000FF;">=</span> <span style="color: #004600;">false</span> <span style="color: #004080;">integer</span> <span style="color: #000000;">count</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">mc</span> <span style="color: #008080;">while</span> <span style="color: #008080;">not</span> <span style="color: #000000;">found</span> <span style="color: #008080;">do</span> <span style="color: #008080;">if</span> <span style="color: #7060A8;">pq_size</span><span style="color: #0000FF;">(</span><span style="color: #000000;">todo</span><span style="color: #0000FF;">)=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span> <span style="color: #0000FF;">?</span><span style="color: #008000;">"impossible"</span> <span style="color: #008080;">exit</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span> <span style="color: #0000FF;">{{</span><span style="color: #000000;">grid</span><span style="color: #0000FF;">,</span><span style="color: #000000;">moves</span><span style="color: #0000FF;">},</span><span style="color: #000000;">mc</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">pq_pop</span><span style="color: #0000FF;">(</span><span style="color: #000000;">todo</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">if</span> <span style="color: #7060A8;">time</span><span style="color: #0000FF;">()></span><span style="color: #000000;">t1</span> <span style="color: #008080;">then</span> <span style="color: #004080;">string</span> <span style="color: #000000;">m</span> <span style="color: #0000FF;">=</span> <span style="color: #008080;">iff</span><span style="color: #0000FF;">(</span><span style="color: #000000;">optimal</span><span style="color: #0000FF;">?</span><span style="color: #008000;">"moves"</span><span style="color: #0000FF;">:</span><span style="color: #008000;">"manhattan"</span><span style="color: #0000FF;">)</span> <span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"searching (count=%d, %s=%d)\r"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">count</span><span style="color: #0000FF;">,</span><span style="color: #000000;">m</span><span style="color: #0000FF;">,</span><span style="color: #000000;">mc</span><span style="color: #0000FF;">})</span> <span style="color: #000000;">t1</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">time</span><span style="color: #0000FF;">()+</span><span style="color: #000000;">1</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span> <span style="color: #000000;">next_moves</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">get_moves</span><span style="color: #0000FF;">(</span><span style="color: #000000;">grid</span><span style="color: #0000FF;">,</span><span style="color: #000000;">mtm</span><span style="color: #0000FF;">)</span> <span style="color: #000000;">count</span> <span style="color: #0000FF;">+=</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">next_moves</span><span style="color: #0000FF;">)</span> <span style="color: #004080;">integer</span> <span style="color: #000000;">l</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">moves</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">next_moves</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span> <span style="color: #000000;">move</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">next_moves</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span> <span style="color: #000000;">new_grid</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">make_move</span><span style="color: #0000FF;">(</span><span style="color: #000000;">grid</span><span style="color: #0000FF;">,</span><span style="color: #000000;">move</span><span style="color: #0000FF;">)</span> <span style="color: #000000;">mc</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">manhattan</span><span style="color: #0000FF;">(</span><span style="color: #000000;">new_grid</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">if</span> <span style="color: #000000;">mc</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span> <span style="color: #008080;">if</span> <span style="color: #000000;">new_grid</span><span style="color: #0000FF;">!=</span><span style="color: #7060A8;">target</span> <span style="color: #008080;">then</span> <span style="color: #0000FF;">?</span><span style="color: #000000;">9</span><span style="color: #0000FF;">/</span><span style="color: #000000;">0</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span> <span style="color: #000000;">moves</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #000000;">moves</span><span style="color: #0000FF;">,</span><span style="color: #000000;">move</span><span style="color: #0000FF;">)</span> <span style="color: #000000;">found</span> <span style="color: #0000FF;">=</span> <span style="color: #004600;">true</span> <span style="color: #008080;">exit</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span> <span style="color: #008080;">if</span> <span style="color: #7060A8;">getd_index</span><span style="color: #0000FF;">(</span><span style="color: #000000;">new_grid</span><span style="color: #0000FF;">,</span><span style="color: #000000;">seen</span><span style="color: #0000FF;">)=</span><span style="color: #004600;">NULL</span> <span style="color: #008080;">then</span> <span style="color: #008080;">if</span> <span style="color: #000000;">optimal</span> <span style="color: #008080;">then</span> <span style="color: #000000;">mc</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">l</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span> <span style="color: #7060A8;">pq_add</span><span style="color: #0000FF;">({{</span><span style="color: #000000;">new_grid</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">deep_copy</span><span style="color: #0000FF;">(</span><span style="color: #000000;">moves</span><span style="color: #0000FF;">),</span><span style="color: #000000;">move</span><span style="color: #0000FF;">)},</span><span style="color: #000000;">mc</span><span style="color: #0000FF;">},</span><span style="color: #000000;">todo</span><span style="color: #0000FF;">)</span> <span style="color: #7060A8;">setd</span><span style="color: #0000FF;">(</span><span style="color: #000000;">new_grid</span><span style="color: #0000FF;">,</span><span style="color: #004600;">true</span><span style="color: #0000FF;">,</span><span style="color: #000000;">seen</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span> <span style="color: #008080;">end</span> <span style="color: #008080;">for</span> <span style="color: #008080;">end</span> <span style="color: #008080;">while</span> <span style="color: #008080;">if</span> <span style="color: #000000;">found</span> <span style="color: #008080;">then</span> <span style="color: #004080;">string</span> <span style="color: #000000;">s</span> <span style="color: #0000FF;">=</span> <span style="color: #008080;">iff</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">moves</span><span style="color: #0000FF;">)=</span><span style="color: #000000;">1</span><span style="color: #0000FF;">?</span><span style="color: #008000;">""</span><span style="color: #0000FF;">:</span><span style="color: #008000;">"s"</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">if</span> <span style="color: #000000;">optimal</span> <span style="color: #008080;">then</span> <span style="color: #000000;">s</span> <span style="color: #0000FF;">&=</span> <span style="color: #7060A8;">sprintf</span><span style="color: #0000FF;">(</span><span style="color: #008000;">" (max shd be %d)"</span><span style="color: #0000FF;">,</span><span style="color: #008080;">iff</span><span style="color: #0000FF;">(</span><span style="color: #000000;">mtm</span><span style="color: #0000FF;">?</span><span style="color: #000000;">24</span><span style="color: #0000FF;">:</span><span style="color: #000000;">31</span><span style="color: #0000FF;">))</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span> <span style="color: #000000;">grid</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">problem</span> <span style="color: #004080;">string</span> <span style="color: #000000;">soln</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">""</span> <span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">moves</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span> <span style="color: #000000;">move</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">moves</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span> <span style="color: #000000;">grid</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">make_move</span><span style="color: #0000FF;">(</span><span style="color: #000000;">grid</span><span style="color: #0000FF;">,</span><span style="color: #000000;">move</span><span style="color: #0000FF;">)</span> <span style="color: #004080;">integer</span> <span style="color: #0000FF;">{{},{},</span><span style="color: #000000;">ch</span><span style="color: #0000FF;">,</span><span style="color: #000000;">c</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">move</span> <span style="color: #000000;">soln</span> <span style="color: #0000FF;">&=</span> <span style="color: #000000;">ch</span> <span style="color: #008080;">if</span> <span style="color: #000000;">c</span><span style="color: #0000FF;">></span><span style="color: #000000;">1</span> <span style="color: #008080;">then</span> <span style="color: #000000;">soln</span><span style="color: #0000FF;">&=</span><span style="color: #008000;">'0'</span><span style="color: #0000FF;">+</span><span style="color: #000000;">c</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span> <span style="color: #000080;font-style:italic;">-- show_grid() -- (set the initial shuffle to eg 5 first!)</span> <span style="color: #008080;">end</span> <span style="color: #008080;">for</span> <span style="color: #000080;font-style:italic;">-- show_grid() -- (not very educational!)</span> <span style="color: #008080;">if</span> <span style="color: #000000;">grid</span><span style="color: #0000FF;">!=</span><span style="color: #7060A8;">target</span> <span style="color: #008080;">then</span> <span style="color: #0000FF;">?</span><span style="color: #000000;">9</span><span style="color: #0000FF;">/</span><span style="color: #000000;">0</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span> <span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"solved in %d move%s:%s\n"</span><span style="color: #0000FF;">,{</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">moves</span><span style="color: #0000FF;">),</span><span style="color: #000000;">s</span><span style="color: #0000FF;">,</span><span style="color: #000000;">soln</span><span style="color: #0000FF;">})</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span> <span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"count:%d, seen:%d, queue:%d\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">count</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">dict_size</span><span style="color: #0000FF;">(</span><span style="color: #000000;">seen</span><span style="color: #0000FF;">),</span><span style="color: #7060A8;">pq_size</span><span style="color: #0000FF;">(</span><span style="color: #000000;">todo</span><span style="color: #0000FF;">)})</span> <!--</syntaxhighlight>--> ~~integer todo = pq_new(),~~ ~~seen = new_dict()~~ ~~pq_add({{grid,{}},iff(optimal?0:manhattan(grid))},todo)~~ ~~setd(grid,true,seen)~~ ~~atom t1 = time()+1~~ ~~bool found = false~~ ~~integer count = 0, mc~~ ~~while not found do~~ ~~if pq_size(todo)=0 then ?"impossible" exit end if~~ ~~{{grid,moves},mc} = pq_pop(todo)~~ ~~if time()>t1 then~~ ~~string m = iff(optimal?"moves":"manhattan")~~ ~~printf(1,"searching (count=%d, %s=%d)\r",{count,m,mc})~~ ~~t1 = time()+1~~ ~~end if~~ ~~next_moves = get_moves(grid,mtm)~~ ~~count += length(next_moves)~~ ~~integer l = length(moves)~~ ~~for i=1 to length(next_moves) do~~ ~~move = next_moves[i]~~ ~~new_grid = make_move(grid,move)~~ ~~mc = manhattan(new_grid)~~ ~~if mc=0 then~~ ~~if new_grid!=target then ?9/0 end if~~ ~~moves = append(moves,move)~~ ~~found = true~~ ~~exit~~ ~~end if~~ ~~if getd_index(new_grid,seen)=NULL then~~ ~~if optimal then mc = l+1 end if~~ ~~pq_add({{new_grid,append(moves,move)},mc},todo)~~ ~~setd(new_grid,true,seen)~~ ~~end if~~ ~~end for~~ ~~end while~~ ~~if found then~~ ~~string s = iff(length(moves)=1?"":"s")~~ ~~if optimal then~~ ~~s &= sprintf(" (max shd be %d)",iff(mtm?24:31))~~ ~~end if~~ ~~grid = problem~~ ~~string soln = ""~~ ~~for i=1 to length(moves) do~~ ~~move = moves[i]~~ ~~grid = make_move(grid,move)~~ ~~integer {{},{},ch,c} = move~~ ~~soln &= ch~~ ~~if c>1 then soln&='0'+c end if~~ ~~-- show_grid() -- (set the initial shuffle to eg 5 first!)~~ ~~end for~~ ~~-- show_grid() -- (not very educational!)~~ ~~if grid!=target then ?9/0 end if~~ ~~printf(1,"solved in %d move%s:%s\n",{length(moves),s,soln})~~ ~~end if~~ ~~printf(1,"count:%d, seen:%d, queue:%d\n",{count,dict_size(seen),pq_size(todo)})</lang>~~ {{out}} Note: The solutions are non-optimal (far from it, in fact), since it searches lowest manhattan() first.<br> Line 2,460 ⟶ 3,603: =={{header\|PowerShell}}== <~~lang~~syntaxhighlight lang="powershell">function CreateGrid($h, $w, $fill) { $grid = 0..($h - 1) \| ForEach-Object { , (, $fill * $w) } return $grid Line 2,572 ⟶ 3,715: Write-Output "Cost: $cost" $routeString = ($route \| ForEach-Object { "($($_[0]), $($_[1]))" }) -join ', ' Write-Output "Route: $routeString"</~~lang~~syntaxhighlight> {{out}} <pre> Line 2,585 ⟶ 3,728: Cost: 11 Route: (0, 0), (1, 1), (2, 2), (3, 1), (4, 1), (5, 1), (6, 2), (7, 3), (6, 4), (7, 5), (6, 6), (7, 7) </pre> =={{header\|Picat}}== <syntaxhighlight lang="picat">% Picat's tabling system uses an algorithm like Dijkstra's to find an optimal solution. % Picat's planner supports A* search with heuristics. % See the program for the 15-puzzle at https://rosettacode.org/wiki/15_puzzle_solver#Picat % main => Maze = new_array(8,8), Obs = [(2,4), (2,5), (2,6), (3,6), (4,6), (5,6), (5,5), (5,4), (5,3), (5,2), (4,2), (3,2)], foreach ((R0,C0) in Obs) Maze[R0+1,C0+1] = 100 end, foreach (R in 1..8, C in 1..8) (var(Maze[R,C]) -> Maze[R,C] = 1; true) end, search((1,1),(8,8),Maze,Cost,Path), writeln(cost=Cost), println([(R0,C0) : (R1,C1) in Path, R0 = R1-1, C0 = C1-1]). table (+,+,+,min,-) search(G,G,_Maze,Cost,Path) => Cost = 0, Path = [G]. search(S@(R,C),G,Maze,Cost,Path) => neibs(R,C,Neibs), member(S1,Neibs), S1 = (R1,C1), search(S1,G,Maze,Cost1,Path1), Cost = Cost1+Maze[R1,C1], Path = [S\|Path1]. neibs(R,C,Neibs) => Neibs = [(R1,C1) : Dr in [-1,0,1], Dc in [-1,0,1], R1 = R+Dr, C1 = C+Dc, R1 >= 1, R1 <= 8, C1 >= 1, C1 <= 8, (R,C) != (R1,C1)]. </syntaxhighlight> {{out}} <pre> cost = 11 [(0,0),(1,0),(2,0),(3,0),(4,0),(5,1),(6,2),(6,3),(6,4),(6,5),(6,6),(7,7)] </pre> =={{header\|Python}}== <~~lang~~syntaxhighlight lang="python">from __future__ import print_function import matplotlib.pyplot as plt class AStarGraph(object): #Define a class board like grid with two barriers def __init__(self): self.barriers = [] Line 2,607 ⟶ 3,788: dy = abs(start[1] - goal[1]) return D * (dx + dy) + (D2 - 2 * D) * min(dx, dy) def get_vertex_neighbours(self, pos): n = [] Line 2,618 ⟶ 3,799: n.append((x2, y2)) return n def move_cost(self, a, b): for barrier in self.barriers: Line 2,624 ⟶ 3,805: return 100 #Extremely high cost to enter barrier squares return 1 #Normal movement cost def AStarSearch(start, end, graph): G = {} #Actual movement cost to each position from the start position F = {} #Estimated movement cost of start to end going via this position #Initialize starting values G[start] = 0 F[start] = graph.heuristic(start, end) closedVertices = set() openVertices = set([start]) cameFrom = {} while len(openVertices) > 0: #Get the vertex in the open list with the lowest F score Line 2,656 ⟶ 3,837: path.reverse() return path, F[end] #Done! #Mark the current vertex as closed openVertices.remove(current) closedVertices.add(current) #Update scores for vertices near the current position for neighbour in graph.get_vertex_neighbours(current): if neighbour in closedVertices: continue #We have already processed this node exhaustively candidateG = G[current] + graph.move_cost(current, neighbour) if neighbour not in openVertices: openVertices.add(neighbour) #Discovered a new vertex elif candidateG >= G[neighbour]: continue #This G score is worse than previously found #Adopt this G score cameFrom[neighbour] = current Line 2,677 ⟶ 3,858: H = graph.heuristic(neighbour, end) F[neighbour] = G[neighbour] + H raise RuntimeError("A* failed to find a solution") if __name__=="__main__": graph = AStarGraph() Line 2,690 ⟶ 3,871: plt.xlim(-1,8) plt.ylim(-1,8) plt.show()</~~lang~~syntaxhighlight> {{out}} Line 2,699 ⟶ 3,880: This code is lifted from: [https://jeapostrophe.github.io/2013-04-15-astar-post.html this blog post]. Read it, it's very good. <~~lang~~syntaxhighlight lang="racket">#lang scribble/lp @(chunk <graph-sig> Line 2,760 ⟶ 3,941: (define count 0) <a-star-setup> (begin0 (let/ec esc <a-star-loop> #f) (printf "visited ~a nodes\n" count)))) Line 2,776 ⟶ 3,957: <a-star-setup-closed> (define node->best-path (make-hash)) (define node->best-path-cost (make-hash)) (hash-set! node->best-path initial empty) (hash-set! node->best-path-cost initial 0)) Line 2,800 ⟶ 3,981: (define h-x (node-cost x)) (define path-x (hash-ref node->best-path x)) (when (zero? h-x) (esc (reverse path-x)))) Line 2,807 ⟶ 3,988: <a-star-loop-body> <a-star-loop-stop?> (define g-x (hash-ref node->best-path-cost x)) (for ([x->y (in-list (node-edges x))]) Line 2,860 ⟶ 4,041: (define-unit map@ (import) (export graph^) (define node? map-node?) (define edge? map-edge?) (define edge-src map-edge-src) (define edge-dest map-edge-dest) <map-graph-cost> <map-graph-edges>)) Line 2,901 ⟶ 4,082: 2htdp/image racket/runtime-path) <graph-sig> <map-generation> <map-graph-rep> <map-graph> <a-star> <map-node-cost> <map-example> Line 2,917 ⟶ 4,098: (cons dx dy)]) random-path)) <map-display> <path-display-line> <path-display> (path-image random-M random-path))</~~lang~~syntaxhighlight> {{out}} Line 2,935 ⟶ 4,116: =={{header\|Raku}}== {{trans\|Sidef}} <syntaxhighlight lang="raku" ~~perl6~~line># 20200427 Raku programming solution class AStarGraph { Line 3,027 ⟶ 4,208: .join.say for @grid ; say "Path cost : ", cost, " and route : ", route;</~~lang~~syntaxhighlight> {{out}}<pre>██████████ █x.......█ Line 3,041 ⟶ 4,222: =={{header\|REXX}}== <~~lang~~syntaxhighlight lang="rexx">/REXX program solves the A search problem for a (general) NxN grid. / parse arg N sCol sRow . /obtain optional arguments from the CL/ if N=='' \| N=="," then N=8 /No grid size specified? Use default./ Line 3,123 ⟶ 4,304: say ind translate(L'│', , .) /display a " " " " / end /c/ /a 19x19 grid can be shown 80 columns./ say ind translate('└'_"┘",'┴',"┼"); return /display the very bottom of the grid. /</~~lang~~syntaxhighlight> {{out\|output\|text=  when using the default input:}} <pre> Line 3,148 ⟶ 4,329: =={{header\|SequenceL}}== <~~lang~~syntaxhighlight lang="sequencel"> import <Utilities/Set.sl>; import <Utilities/Math.sl>; Line 3,175 ⟶ 4,356: newActual[i,j] := 0 foreach i within 1...width, j within 1...height; newCameFrom[i,j] := (x : 0, y : 0) foreach i within 1...width, j within 1...height; searchResults := search((open : [start], closed : [], estimate : newEstimate, actual : newActual, cameFrom : newCameFrom), barriers, end); shortestPath := path(searchResults.cameFrom, start, end) ++ [end]; Line 3,234 ⟶ 4,415: y := n.y + p.y; in (x : x, y : y) when x >= 1 and x <= w and y >= 1 and y <= h; calculateCost(barriers(1), start, end) := 100 when elementOf(end, barriers) else 1; Line 3,248 ⟶ 4,429: value when point.x = i and point.y = j else map[i,j] foreach i within 1 ... size(map), j within 1 ... size(map[1]); </syntaxhighlight> ~~</lang>~~ {{out\|Output\|text= }} <pre> Line 3,266 ⟶ 4,447: =={{header\|Sidef}}== {{trans\|Python}} <~~lang~~syntaxhighlight lang="ruby">class AStarGraph { has barriers = [ Line 3,370 ⟶ 4,551: grid.each { .join.say } say "Path cost #{cost}: #{route}"</~~lang~~syntaxhighlight> {{out}} <pre> Line 3,389 ⟶ 4,570: {{works with\|Bourne Again SHell}} <~~lang~~syntaxhighlight lang="bash"> #!/bin/bash Line 3,762 ⟶ 4,943: main "$@" </syntaxhighlight> ~~</lang>~~ {{out}} <pre> path: 0,0 → 1,0 → 2,0 → 3,0 → 4,0 → 5,1 → 6,2 → 7,3 → 7,4 → 7,5 → 7,6 → 7,7 01234567 0◉ 1↓ 2↓ ■■■ 3↓ ■ ■ 4↘ ■ ■ 5 ↘■■■■■ 6 ↘ 7 →→→→✪ </pre> =={{header\|Wren}}== {{trans\|Sidef}} <syntaxhighlight lang="wren">var Equals = Fn.new { \|p1, p2\| p1[0] == p2[0] && p1[1] == p2[1] } var Contains = Fn.new { \|pairs, p\| for (pair in pairs) { if (Equals.call(p, pair)) return true } return false } var Remove = Fn.new { \|pairs, p\| for (pair in pairs) { if (Equals.call(p, pair)) { pairs.remove(pair) return } } } class AStarGraph { construct new() { _barriers = [[2,4], [2,5], [2,6], [3,6], [4,6], [5,6], [5,5], [5,4], [5,3], [5,2], [4,2], [3,2]] } barriers { _barriers } heuristic(start, goal) { var D1 = 1 var D2 = 1 var dx = (start[0] - goal[0]).abs var dy = (start[1] - goal[1]).abs return D1 (dx + dy) + (D2 - 2D1) dx.min(dy) } getVertexNeighbors(pos) { var n = [] for (d in [[1,0], [-1,0], [0,1], [0,-1], [1,1], [-1,1], [1,-1], [-1,-1]]) { var x2 = pos[0] + d[0] var y2 = pos[1] + d[1] if (x2 < 0 \|\| x2 > 7 \|\| y2 < 0 \|\| y2 > 7) continue n.add([x2, y2]) } return n } moveCost(b) { Contains.call(_barriers, b) ? 100 : 1 } } var AStarSearch = Fn.new { \|start, end, graph\| var G = {start.toString: 0} var F = {start.toString: graph.heuristic(start, end)} var closedVertices = [] var openVertices = [start] var cameFrom = {} while (openVertices.count > 0) { var current = null var currentFscore = 1 / 0 for (pos in openVertices) { var v if ((v = F[pos.toString]) && v && v < currentFscore) { currentFscore = v current = pos } } if (Equals.call(current, end)) { var path = [current] while (cameFrom.containsKey(current.toString)) { current = cameFrom[current.toString] path.add(current) } path = path[-1..0] return [path, F[end.toString]] } Remove.call(openVertices, current) closedVertices.add(current) for (neighbor in graph.getVertexNeighbors(current)) { if (Contains.call(closedVertices, neighbor)) continue var candidateG = G[current.toString] + graph.moveCost(neighbor) if (!Contains.call(openVertices, neighbor)) { openVertices.add(neighbor) } else if (candidateG >= G[neighbor.toString]) continue cameFrom[neighbor.toString] = current G[neighbor.toString] = candidateG var H = graph.heuristic(neighbor, end) F[neighbor.toString] = G[neighbor.toString] + H } } Fiber.abort("A* failed to find a solution") } var graph = AStarGraph.new() var rc = AStarSearch.call([0,0], [7,7], graph) var route = rc[0] var cost = rc[1] var w = 10 var h = 10 var grid = List.filled(h, null) for (i in 0...h) grid[i] = List.filled(w, ".") for (y in 0...h) { grid[y][0] = "█" grid[y][-1] = "█" } for (x in 0...w) { grid[0][x] = "█" grid[-1][x] = "█" } for (p in graph.barriers) { var x = p[0] var y = p[1] grid[x+1][y+1] = "█" } for (p in route) { var x = p[0] var y = p[1] grid[x+1][y+1] = "x" } for (line in grid) System.print(line.join()) System.print("\npath cost %(cost): %(route)")</syntaxhighlight> {{out}} <pre> ██████████ █x.......█ █.x......█ █..x.███.█ █.x█...█.█ █.x█...█.█ █.x█████.█ █..xxxxx.█ █.......x█ ██████████ path cost 11: [[0, 0], [1, 1], [2, 2], [3, 1], [4, 1], [5, 1], [6, 2], [6, 3], [6, 4], [6, 5], [6, 6], [7, 7]] </pre> =={{header\|zkl}}== {{trans\|Python}} <~~lang~~syntaxhighlight lang="zkl"> // we use strings as hash keys: (x,y)-->"x,y", keys are a single pair fcn toKey(xy){ xy.concat(",") } Line 3,790 ⟶ 5,107: F[kstart]=graph.heuristic(start,end); closedVertices,openVertices,cameFrom := List(),List(start),Dictionary(); while(openVertices){ # Get the vertex in the open list with the lowest F score Line 3,798 ⟶ 5,115: if(current==Void or F[kpos]<currentFscore) currentFscore,current = F[kpos],pos; # Check if we have reached the goal if(current==end){ # Yes! Retrace our route backward Line 3,812 ⟶ 5,129: openVertices.remove(current); if(not closedVertices.holds(current)) closedVertices.append(current); # Update scores for vertices near the current position foreach neighbor in (graph.get_vertex_neighbors(current)){ Line 3,819 ⟶ 5,136: kneighbor:=toKey(neighbor); candidateG:=G[toKey(current)] + graph.move_cost(current, neighbor); if(not openVertices.holds(neighbor)) openVertices.append(neighbor); # Discovered a new vertex else if(candidateG>=G[kneighbor]) continue; # This G score is worse than previously found # Adopt this G score cameFrom[kneighbor]=current; Line 3,833 ⟶ 5,150: } // while throw(Exception.AssertionError("A* failed to find a solution")); }</~~lang~~syntaxhighlight> <~~lang~~syntaxhighlight lang="zkl">class [static] AStarGraph{ # Define a class board like grid with barriers var [const] barriers = T( T(3,2),T(4,2),T(5,2), // T is RO List Line 3,860 ⟶ 5,177: 1 # Normal movement cost } }</~~lang~~syntaxhighlight> <~~lang~~syntaxhighlight lang="zkl">graph:=AStarGraph; route,cost := AStarSearch(T(0,0), T(7,7), graph); println("Route: ", route.apply(fcn(xy){ String("(",toKey(xy),")") }).concat(",")); Line 3,870 ⟶ 5,187: foreach x,y in (graph.barriers){ grid[x][y]="#" } foreach x,y in (route){ grid[x][y]="+" } grid[0][0] = "S"; grid[7][7] = "E"; foreach line in (grid){ println(line.concat()) }</~~lang~~syntaxhighlight> {{out}} <pre> Route: (0,0),(1,1),(2,2),(3,1),(4,0),(5,1),(6,2),(7,3),(7,4),(7,5),(7,6),(7,7) Cost: 11 S S + + + ### +# # + # # +##### + ++++E </pre>