Task

For a maze generated by this task, write a function
that finds (and displays) the shortest path between two cells.



Note that because these mazes are generated by the Depth-first search algorithm, they contain no circular paths,
and a simple depth-first tree search can be used.




main =>
    Maze0 = ["+---+---+---+---+---+---+---+---+",
             "|   |       |       |           |",
             "+   +   +   +---+   +   +---+   +",
             "|       |   |       |       |   |",
             "+---+---+   +   +---+---+   +   +",
             "|       |   |               |   |",
             "+---+   +   +   +---+---+---+   +",
             "|       |   |               |   |",
             "+   +   +   +---+---+---+   +   +",
             "|   |   |   |               |   |",
             "+   +   +   +---+   +---+---+   +",
             "|   |   |       |           |   |",
             "+   +---+---+   +---+---+---+   +",
             "|           |       |           |",
             "+   +---+   +---+   +   +---+   +",
             "|       |               |       |",
             "+---+---+---+---+---+---+---+---+"],
    MaxR = len(Maze0) div 2,
    MaxC = len(Maze0[1]) div 4,
    Maze = new_array(MaxR,MaxC),
    foreach (R in 1..MaxR, C in 1..MaxC)
        Maze[R,C] = 0
    end,
    fill_maze(Maze0,Maze,1),
    solve_maze(Maze,(1,1),(MaxR,MaxC),Cost,Plan),
    OutputMaze = new_array(MaxR,MaxC),
    foreach ((R,C) in Plan)
        OutputMaze[R,C] = '*'
    end,
    output_maze(Maze0,OutputMaze,1).
 
fill_maze([Line1,Line2|Maze0],Maze,R) =>
    fill_maze_cols(Line1,Maze,R,1),
    fill_maze_cols(Line2,Maze,R,1),
    fill_maze(Maze0,Maze,R+1).
fill_maze(_,_,_) =>    true.
 
fill_maze_cols(['+',' ',' ',' '|Line],Maze,R,C) =>
    Maze[R,C] := Maze[R,C] \/ 4,     % up
    Maze[R-1,C] := Maze[R-1,C] \/ 8, % down
    fill_maze_cols(Line,Maze,R,C+1).
fill_maze_cols([' ',' ',' ',' '|Line],Maze,R,C) =>
    Maze[R,C] := Maze[R,C] \/ 1,     % left
    Maze[R,C-1] := Maze[R,C-1] \/ 2, % right
     fill_maze_cols(Line,Maze,R,C+1).
fill_maze_cols([_,_,_,_|Line],Maze,R,C) =>
    fill_maze_cols(Line,Maze,R,C+1).
fill_maze_cols(_,_,_,_) => true.
 
table (+,+,+,min,-)
solve_maze(_Maze,FPos,FPos,Cost,Plan) =>
    Cost = 0,
    Plan = [FPos].
solve_maze(Maze,Pos@(R,C),FPos,Cost,Plan) ?=>
    Maze[R,C] /\ 1 == 1,             % left
    solve_maze(Maze,(R,C-1),FPos,Cost1,Plan1),
    Plan = [Pos|Plan1],
    Cost = Cost1+1.
solve_maze(Maze,Pos@(R,C),FPos,Cost,Plan) ?=>
    Maze[R,C] /\ 2 == 2,             % right
    solve_maze(Maze,(R,C+1),FPos,Cost1,Plan1),
    Plan = [Pos|Plan1],
    Cost = Cost1+1.
solve_maze(Maze,Pos@(R,C),FPos,Cost,Plan) ?=>
    Maze[R,C] /\ 4 == 4,             % up
    solve_maze(Maze,(R-1,C),FPos,Cost1,Plan1),
    Plan = [Pos|Plan1],
    Cost = Cost1+1.
solve_maze(Maze,Pos@(R,C),FPos,Cost,Plan) ?=>
    Maze[R,C] /\ 8 == 8,             % down
    solve_maze(Maze,(R+1,C),FPos,Cost1,Plan1),
    Plan = [Pos|Plan1],
    Cost = Cost1+1.
 
output_maze([Line1,Line2|Maze0],Maze,R) =>
    output_maze_cols(Line1,Maze,R,1),
    output_maze_cols(Line2,Maze,R,1),
    output_maze(Maze0,Maze,R+1).
output_maze([Line],_,_) =>    println(Line).
 
output_maze_cols([' ',' ',' ',' '|Line],Maze,R,C) =>
    if Maze[R,C] == '*' then
        print("  * ")
    else
        print("    ")
    end,
     output_maze_cols(Line,Maze,R,C+1).
output_maze_cols(['|',' ',' ',' '|Line],Maze,R,C) =>
    if Maze[R,C] == '*' then
        print("| * ")
    else
        print("|   ")
    end,
     output_maze_cols(Line,Maze,R,C+1).
output_maze_cols(['+',' ',' ',' '|Line],Maze,R,C) =>
    if Maze[R,C] == '*' && Maze[R-1,C] == '*' then
        print("+ * ")
    else
        print("+   ")
    end,
    output_maze_cols(Line,Maze,R,C+1).
output_maze_cols([C1,C2,C3,C4|Line],Maze,R,C) =>
    printf("%c%c%c%c",C1,C3,C3,C4),
    output_maze_cols(Line,Maze,R,C+1).
output_maze_cols(Line,_,_,_) => println(Line).
 