Amazingly Raku - Part 3: The Wall
[94.3] Published 28. September 2020.See also: The Introduction | Part 1: The Maze | Part 2: The Path.
In the previous part we solved the mazes with the Shortest Path Algorithm. They are efficient, in that we get the shortest path. But they require that we have a map of the maze (as we do).
But what if the maze is real, and we are standing just inside the entrance. Without a map, and have to find the way through it?
The Wall Follower Algorithm is the solution. You choose between left or right initiallty. Let us say you choose right. You are standing just inside the entrance to the maze. Raise your right arm, and touch the wall on the right hand side of the entrance. Then go forward, following that wall - without letting go of it. If you arrive at the exit, the maze is indeed traversable. If you find yourself back at the entry point (*), it is not. Quite simple, but the path it follows can be terribly long-winded, as shown here:
| Left Wall Path | Right Wall Path |
|
|
*= In the same direction, i.e. following the same wall. The "Left Wall Path» illustration (above left) illustrates this beautifully; you are back at the [0,0] position after the eastern dead end detour, but the maze is traversable.
The output can simply be a «yes» or «no», like this:
$ ./maze-solver-wall 5x5-ok.txt
yes
$ ./maze-solver-wall 5x5-fail.txt
no
But a Verbose mode explaining what is going on is a must. E.g.
$ ./maze-solver-wall --verbose --right 5x5-ok.txt
: At [0,0]: █ (with directions: ES). Heading: S. Turning: L (E)
: At [0,1]: ╩ (with directions: EW). Heading: E. Turning: A (E)
: ----
: At [4,4]: █ (with directions: N). Heading: S.
yes
The directions (heading) are: L=Left, R=Right, A=Ahead, B=Back (turn around).
We are travelling one cell (character) at a
time, so I ignore the North exit at [0,1] (╩), as it leads to nothing.
In a real life maze we would follow the wall north, reach the end, come back the other wall,
and then continue left - as if the dead end wasn't there.
#! /usr/bin/env raku
unit sub MAIN ($maze where $maze.IO.e && $maze.IO.r, # [1]
:l(:$left), # [2]
:v(:$verbose), # [3]
:s(:$show), # [4]
:h(:$html));
constant $end = '█';
my @maze = $maze.IO.lines>>.comb>>.list; # [1]
my $rows = @maze.elems;
my $cols = @maze[0].elems;
die "Missing entrypoint '█' in maze" unless @maze[0][0] eq $end;
die "Missing exit point '█' in maze" unless @maze[$rows-1][$cols-1] eq $end;
[1] Load the maze, in a two dimentional array.
[2] I have chosen the «Right Wall Path». Use this command line option to follow the «Left Wall Path» instead.
[3] Show the maze with the path highlighted.
[4] Use HTML markup, instead of ANSI coded.
File: maze-solver-wall (partial)
my %desc2symbol = (
SW => '╗',
EW => '═',
NW => '╝',
ES => '╔',
NS => '║',
NE => '╚',
ESW => '╦',
NES => '╠',
NSW => '╣',
NEW => '╩',
NESW => '╬'
);
my %symbol2desc = %desc2symbol.antipairs;
%symbol2desc{'█'} = 'WNES';
%symbol2desc{' '} = '';
my $col-blue = "\e[44m";
my $col-green = "\e[42m";
my $col-red = "\e[101m";
my $col-stop = "\e[0m";
if ($html)
{
$col-blue = '<span class="text-primary">';
$col-green = '<span class="text-success">';
$col-red = '<span class="text-danger">';
$col-stop = '';
}
if $verbose # [5]
{
say ": Turn: { $left ?? 'left' !! 'right' }";
say ": Rows: $rows";
say ": Cols: $cols";
say ": Row: { @$_.join }" for @maze;
}
[5] Show the direction; left or right. Also note the last line, where we print the entire maze, one row at a time.
File: maze-solver-wall (partial)
my @visited; # [6]
my $heading = "S"; # [7]
my $traversable = False; # [8]
my $row = 0; # [7a]
my $col = 0; # [7b]
my %zero; # [9]
loop # [10]
{
@visited[$row][$col] = True; # [6]
my $directions = get_directions($row, $col); # [11]
my $turn = $left # [12]
?? new_direction_right($heading, $directions)
!! new_direction_left($heading, $directions);
my $new_heading = new_heading($heading, $turn); # [13]
say ": At [$row,$col]: { @maze[$row][$col] } \
(with directions: $directions). Heading: $heading. \
Turning: $turn ($new_heading)" if $verbose;
if $row == 0 && $col == 0 # [14]
{
last if %zero{$new_heading}; # [14a]
%zero{$new_heading} = True; # [14b]
}
if $row == $rows-1 && $col == $cols-1 # [15]
{
$traversable = True; # [15a]
last; # [15b]
}
$heading = $new_heading; # [16]
($row, $col) = new_position($row, $col, $heading); # [17]
}
say $traversable
?? "yes"
!! "no";
show-path if $show;
[6] This is a red herring now. We re only using it for the coverage map!
[7] We must head in a direction (as the concept of left and right is not absolute). South is a good start, at the entrance [0,0] ([7a] and [7b]).
[8] We set this to True if the maze as traversable, like we used
$path in «maze-solver-spa».
[9] In an untraversable maze we'll be back where we started eventually. With the hand against the same wall. We check for this by registering the heading (direction) we are in when we get there.
[10] An eternal loop. We go on until we are back at the entrance [14a] or arrive at the exit [15].
[11] Get the available exits from the current position.
[12] Get the turn to take, depending on the initial choice of left or right wall path, the current heading and available exits.
[13] Get the new heading.
[14] Are we at the entrance? If so check the direction and exit if we have done a complete loop [14a]. if not, mark the wall so that we can check that one as well later.
[15] At the exit? Mark the maze as traversable [15a] and exit the loop [15b].
[16] Change the geading.
[17] Change the position.
File: maze-solver-wall (partial)
sub get_directions ($row, $col) # [18]
{
my @directions;
return '' unless %symbol2desc{@maze[$row][$col]};
for %symbol2desc{@maze[$row][$col]}.comb -> $direction
{
@directions.push: 'N'
if $direction eq 'N' && has_direction($row -1, $col, 'S');
@directions.push: 'S'
if $direction eq 'S' && has_direction($row +1, $col, 'N');
@directions.push: 'W'
if $direction eq 'W' && has_direction($row, $col -1, 'E');
@directions.push: 'E'
if $direction eq 'E' && has_direction($row, $col +1, 'W');
}
return @directions.join;
}
sub has_direction ($row, $col, $direction) # [19]
{
return False unless @maze[$row][$col].defined;
return %symbol2desc{@maze[$row][$col]}.contains: $direction;
}
sub new_direction_right ($heading, $directions) # [20]
{
if $heading eq "N"
{
return "R" if $directions ~~ /E/;
return "A" if $directions ~~ /N/;
return "L" if $directions ~~ /W/;
return "B" if $directions ~~ /S/;
}
if $heading eq "W"
{
return "R" if $directions ~~ /N/;
return "A" if $directions ~~ /W/;
return "L" if $directions ~~ /S/;
return "B" if $directions ~~ /E/;
}
if $heading eq "S"
{
return "R" if $directions ~~ /W/;
return "A" if $directions ~~ /S/;
return "L" if $directions ~~ /E/;
return "B" if $directions ~~ /N/;
}
if $heading eq "E"
{
return "R" if $directions ~~ /S/;
return "A" if $directions ~~ /E/;
return "L" if $directions ~~ /N/;
return "B" if $directions ~~ /W/;
}
}
sub new_direction_left ($heading, $directions) # [21]
{
if $heading eq "N"
{
return "L" if $directions ~~ /W/;
return "A" if $directions ~~ /N/;
return "R" if $directions ~~ /E/;
return "B" if $directions ~~ /S/;
}
if $heading eq "W"
{
return "L" if $directions ~~ /S/;
return "A" if $directions ~~ /W/;
return "R" if $directions ~~ /N/;
return "B" if $directions ~~ /E/;
}
if $heading eq "S"
{
return "L" if $directions ~~ /E/;
return "A" if $directions ~~ /S/;
return "R" if $directions ~~ /W/;
return "B" if $directions ~~ /N/;
}
if $heading eq "E"
{
return "L" if $directions ~~ /N/;
return "A" if $directions ~~ /E/;
return "R" if $directions ~~ /S/;
return "B" if $directions ~~ /W/;
}
}
sub new_heading ($old_heading, $turn) # [22]
{
return "N" if $old_heading eq "N" && $turn eq "A";
return "N" if $old_heading eq "E" && $turn eq "L";
return "N" if $old_heading eq "S" && $turn eq "B";
return "N" if $old_heading eq "W" && $turn eq "R";
return "E" if $old_heading eq "N" && $turn eq "R";
return "E" if $old_heading eq "E" && $turn eq "A";
return "E" if $old_heading eq "S" && $turn eq "L";
return "E" if $old_heading eq "W" && $turn eq "B";
return "S" if $old_heading eq "N" && $turn eq "B";
return "S" if $old_heading eq "E" && $turn eq "R";
return "S" if $old_heading eq "S" && $turn eq "A";
return "S" if $old_heading eq "W" && $turn eq "L";
return "W" if $old_heading eq "N" && $turn eq "L";
return "W" if $old_heading eq "E" && $turn eq "B";
return "W" if $old_heading eq "S" && $turn eq "R";
return "W" if $old_heading eq "W" && $turn eq "A";
}
sub new_position ($row, $col, $heading) # [23]
{
return ($row-1, $col ) if $heading eq "N";
return ($row, $col+1) if $heading eq "E";
return ($row+1, $col ) if $heading eq "S";
return ($row, $col-1) if $heading eq "W";
}
sub show-path # [24]
{
my $col-start = $traversable ?? $col-green !! $col-red;
for ^$rows -> $row
{
for ^$cols -> $col
{
print @visited[$row][$col]
?? $col-start ~ @maze[$row][$col] ~ $col-stop
!! @maze[$row][$col];
}
say '';
}
}
[18] This procedure should be familiar by now.
[19] This procedure should also be familiar.
[20] Which turn to take, using the «Right Wall Path». The first argument is the current heading, and the second is the available directions. The content is a lot of choices.
[21] Which turn to take, using the «Left Wall Path».
[22] Get the new heading. The first parameter is the current (or old) heading, and the second is the turn to make.
[23] Get the new position. This is easy-ish, as we use the heading (and not the turn)
[24] This procedure should be familiar by now. But note that it will turn on an off the colour for each cell, even when we have a lot of them after each other that should be highlighted. I have fixed this manually in this HTML file.
Running it, first on a traversable maze:
./maze-solver-wall 5x5-ok.txt
yes
$ ./maze-solver-wall -v 5x5-ok.txt
: Turn: right
: Rows: 5
: Cols: 5
: Row: █╩╩║╬
: Row: ╠╬╬╔╦
: Row: ╬╬╬═╣
: Row: ╠╩╩╩╣
: Row: ╩╬╬║█
: At [0,0]: █ (with directions: ES). Heading: S. Turning: L (E)
: At [0,1]: ╩ (with directions: EW). Heading: E. Turning: A (E)
: At [0,2]: ╩ (with directions: W). Heading: E. Turning: B (W)
: At [0,1]: ╩ (with directions: EW). Heading: W. Turning: A (W)
: At [0,0]: █ (with directions: ES). Heading: W. Turning: L (S)
: At [1,0]: ╠ (with directions: NES). Heading: S. Turning: L (E)
: At [1,1]: ╬ (with directions: ESW). Heading: E. Turning: A (E)
: At [1,2]: ╬ (with directions: SW). Heading: E. Turning: R (S)
: At [2,2]: ╬ (with directions: NESW). Heading: S. Turning: L (E)
: At [2,3]: ═ (with directions: EW). Heading: E. Turning: A (E)
: At [2,4]: ╣ (with directions: NSW). Heading: E. Turning: L (N)
: At [1,4]: ╦ (with directions: SW). Heading: N. Turning: L (W)
: At [1,3]: ╔ (with directions: E). Heading: W. Turning: B (E)
: At [1,4]: ╦ (with directions: SW). Heading: E. Turning: R (S)
: At [2,4]: ╣ (with directions: NSW). Heading: S. Turning: A (S)
: At [3,4]: ╣ (with directions: NSW). Heading: S. Turning: A (S)
: At [4,4]: █ (with directions: N). Heading: S. Turning: B (N)
yes
We can show the path, with all the dead ends:
$ ./maze-solver-wall -s 5x5-ok.txt
yes
█╩╩║╬
╠╬╬╔╦
╬╬╬═╣
╠╩╩╩╣
╩╬╬║█
$ ./maze-solver-wall -v -l 5x5-ok.txt
: Turn: left
: Rows: 5
: Cols: 5
: Row: █╩╩║╬
: Row: ╠╬╬╔╦
: Row: ╬╬╬═╣
: Row: ╠╩╩╩╣
: Row: ╩╬╬║█
: At [0,0]: █ (with directions: ES). Heading: S. Turning: A (S)
: At [1,0]: ╠ (with directions: NES). Heading: S. Turning: A (S)
: At [2,0]: ╬ (with directions: NES). Heading: S. Turning: A (S)
: At [3,0]: ╠ (with directions: NES). Heading: S. Turning: A (S)
: At [4,0]: ╩ (with directions: NE). Heading: S. Turning: L (E)
: At [4,1]: ╬ (with directions: EW). Heading: E. Turning: A (E)
: At [4,2]: ╬ (with directions: W). Heading: E. Turning: B (W)
: At [4,1]: ╬ (with directions: EW). Heading: W. Turning: A (W)
: At [4,0]: ╩ (with directions: NE). Heading: W. Turning: R (N)
: At [3,0]: ╠ (with directions: NES). Heading: N. Turning: R (E)
: At [3,1]: ╩ (with directions: NEW). Heading: E. Turning: A (E)
: At [3,2]: ╩ (with directions: NEW). Heading: E. Turning: A (E)
: At [3,3]: ╩ (with directions: EW). Heading: E. Turning: A (E)
: At [3,4]: ╣ (with directions: NSW). Heading: E. Turning: R (S)
: At [4,4]: █ (with directions: N). Heading: S. Turning: B (N)
yes
$ ./maze-solver-wall -s -l 5x5-ok.txt
yes
█╩╩║╬
╠╬╬╔╦
╬╬╬═╣
╠╩╩╩╣
╩╬╬║█
Then on an untraversable one:
$ ./maze-solver-wall 5x5-fail.txt
no
$ ./maze-solver-wall -v 5x5-fail.txt
: Turn: right
: Rows: 5
: Cols: 5
: Row: █╠╠╠╦
: Row: ╬╦╬╬╩
: Row: ╠╩╣╦╬
: Row: ╬╠╝╬╦
: Row: ╣╣╦╣█
: At [0,0]: █ (with directions: S). Heading: S. Turning: A (S)
: At [1,0]: ╬ (with directions: NES). Heading: S. Turning: L (E)
: At [1,1]: ╦ (with directions: ESW). Heading: E. Turning: A (E)
: At [1,2]: ╬ (with directions: NESW). Heading: E. Turning: L (N)
: At [0,2]: ╠ (with directions: S). Heading: N. Turning: B (S)
: At [1,2]: ╬ (with directions: NESW). Heading: S. Turning: L (E)
: At [1,3]: ╬ (with directions: NEW). Heading: E. Turning: L (N)
: At [0,3]: ╠ (with directions: ES). Heading: N. Turning: R (E)
: At [0,4]: ╦ (with directions: SW). Heading: E. Turning: R (S)
: At [1,4]: ╩ (with directions: NW). Heading: S. Turning: R (W)
: At [1,3]: ╬ (with directions: NEW). Heading: W. Turning: A (W)
: At [1,2]: ╬ (with directions: NESW). Heading: W. Turning: L (S)
: At [2,2]: ╣ (with directions: NSW). Heading: S. Turning: A (S)
: At [3,2]: ╝ (with directions: NW). Heading: S. Turning: R (W)
: At [3,1]: ╠ (with directions: ES). Heading: W. Turning: L (S)
: At [4,1]: ╣ (with directions: N). Heading: S. Turning: B (N)
: At [3,1]: ╠ (with directions: ES). Heading: N. Turning: R (E)
: At [3,2]: ╝ (with directions: NW). Heading: E. Turning: L (N)
: At [2,2]: ╣ (with directions: NSW). Heading: N. Turning: L (W)
: At [2,1]: ╩ (with directions: NEW). Heading: W. Turning: A (W)
: At [2,0]: ╠ (with directions: NES). Heading: W. Turning: L (S)
: At [3,0]: ╬ (with directions: NS). Heading: S. Turning: A (S)
: At [4,0]: ╣ (with directions: N). Heading: S. Turning: B (N)
: At [3,0]: ╬ (with directions: NS). Heading: N. Turning: A (N)
: At [2,0]: ╠ (with directions: NES). Heading: N. Turning: A (N)
: At [1,0]: ╬ (with directions: NES). Heading: N. Turning: A (N)
: At [0,0]: █ (with directions: S). Heading: N. Turning: B (S)
no
Not a path as such, but a coverage map:
$ ./maze-solver-wall -s 5x5-fail.txt
no
█╠╠╠╦
╬╦╬╬╩
╠╩╣╦╬
╬╠╝╬╦
╣╣╦╣█
It is easy to see the divide, where the maze is no longer continous.
The «Left Wall path»:
$ ./maze-solver-wall -v -l 5x5-fail.txt
: Turn: left
: Rows: 5
: Cols: 5
: Row: █╠╠╠╦
: Row: ╬╦╬╬╩
: Row: ╠╩╣╦╬
: Row: ╬╠╝╬╦
: Row: ╣╣╦╣█
: At [0,0]: █ (with directions: S). Heading: S. Turning: A (S)
: At [1,0]: ╬ (with directions: NES). Heading: S. Turning: A (S)
: At [2,0]: ╠ (with directions: NES). Heading: S. Turning: A (S)
: At [3,0]: ╬ (with directions: NS). Heading: S. Turning: A (S)
: At [4,0]: ╣ (with directions: N). Heading: S. Turning: B (N)
: At [3,0]: ╬ (with directions: NS). Heading: N. Turning: A (N)
: At [2,0]: ╠ (with directions: NES). Heading: N. Turning: R (E)
: At [2,1]: ╩ (with directions: NEW). Heading: E. Turning: A (E)
: At [2,2]: ╣ (with directions: NSW). Heading: E. Turning: R (S)
: At [3,2]: ╝ (with directions: NW). Heading: S. Turning: R (W)
: At [3,1]: ╠ (with directions: ES). Heading: W. Turning: L (S)
: At [4,1]: ╣ (with directions: N). Heading: S. Turning: B (N)
: At [3,1]: ╠ (with directions: ES). Heading: N. Turning: R (E)
: At [3,2]: ╝ (with directions: NW). Heading: E. Turning: L (N)
: At [2,2]: ╣ (with directions: NSW). Heading: N. Turning: A (N)
: At [1,2]: ╬ (with directions: NESW). Heading: N. Turning: R (E)
: At [1,3]: ╬ (with directions: NEW). Heading: E. Turning: A (E)
: At [1,4]: ╩ (with directions: NW). Heading: E. Turning: L (N)
: At [0,4]: ╦ (with directions: SW). Heading: N. Turning: L (W)
: At [0,3]: ╠ (with directions: ES). Heading: W. Turning: L (S)
: At [1,3]: ╬ (with directions: NEW). Heading: S. Turning: R (W)
: At [1,2]: ╬ (with directions: NESW). Heading: W. Turning: R (N)
: At [0,2]: ╠ (with directions: S). Heading: N. Turning: B (S)
: At [1,2]: ╬ (with directions: NESW). Heading: S. Turning: R (W)
: At [1,1]: ╦ (with directions: ESW). Heading: W. Turning: A (W)
: At [1,0]: ╬ (with directions: NES). Heading: W. Turning: R (N)
: At [0,0]: █ (with directions: S). Heading: N. Turning: B (S)
no
The coverage map is the same, regardless of Left or Right Wall Path.
$ ./maze-solver-wall -s -l 5x5-fail.txt
no
█╠╠╠╦
╬╦╬╬╩
╠╩╣╦╬
╬╠╝╬╦
╣╣╦╣█
The «50x50-03.txt» maze is interesting, as we almost reach the exit. Trying it out, in both directions:
$ ./maze-solver-wall -v 50x50-03.txt
: Turn: right
: Rows: 50
: Cols: 50
: Row: █═╗═╗╔╔══ ╔╦═╦═╦═══╦╦╦╗╔╗╗╦═╦ ╔═╔╔╗╗╔═╔╔╦═╔═╗╗═╦╗╗
< a lot of lines not shown >
: Row: ═╚╩╩═╩ ╚╚══╩╩╝╩╩╩╩╩╩╚╝╩═╚╩═╝╚╝╩╩═╩ ═╩ ═ ╚╩╩═ ╩╩╝█
: At [0,0]: █ (with directions: ES). Heading: S. Turning: L (E)
: At [0,1]: ═ (with directions: EW). Heading: E. Turning: A (E)
: At [0,2]: ╗ (with directions: SW). Heading: E. Turning: R (S)
: At [1,2]: ╠ (with directions: NES). Heading: S. Turning: L (E)
: At [1,3]: ╩ (with directions: W). Heading: E. Turning: B (W)
< an awful lot of lines not shown >
: At [0,0]: █ (with directions: ES). Heading: W. Turning: L (S)
: At [1,0]: ╠ (with directions: N). Heading: S. Turning: B (N)
: At [0,0]: █ (with directions: ES). Heading: N. Turning: R (E)
no
$ ./maze-solver-wall -s 50x50-03.txt
no
█═╗═╗╔╔══ ╔╦═╦═╦═══╦╦╦╗╔╗╗╦═╦ ╔═╔╔╗╗╔═╔╔╦═╔═╗╗═╦╗╗
╠║╠╩╔╣╚╣╠╣╬╦╬╦═╬╚╩╣╚╬╦╦╣═╠╦╬╠╩═╩╬╦═╬╦╠╗╠╬╠╣╚╩╣╣╣╦╗
╔╬╬╣╣╩╣╩╦╠╩╩╠╔╠╩╣╠╩╬╬╩╣╝╩╦╦╦╦╬╦╠╦╬╣╬╦╬╣╚╦╣╦╦╦╣╦╣╬╣
╚╚╬╦╦╗╬╠╬╠╚╠╣╦═╬═╠╔╦╗║╩╦╚╔╬╚╣╩╣╣╬╚╗╩╣╣╬╬╦╩╣╩╬║╩╦╩╗
╔║╬╠╦╬╔╩╠╣╠╣╣╦╣╗╝╚╣╠╠╬╬╗╣╬╬═╠╩╣╣╣╬╠╠═╠╣╦╣═╦╣╦╦╠╠═║
╚╔╠╬╠╦══╦╣╠╝═╠╦╦╦╣╠╬╣╩╬╬╦╦╗═╠╦╬╣╠╬╬╬╣╠╣╣╣╬╣╔╣╣║╣╬╣
╚╩╩╣╣╠╣╦╩╣╬╦╩╦╠╬╩╠╝╠╩╣║╦╗╦╠╣╬═╔╝╦╬╩╣╬╣╦╦╚╣╣╬╦╩╗╣╬╣
╠╦╠╠╠╦╠╠╬╬╦╠╬╦╣╠╚╣╦╣╩╣╩╣╣╬╔╣╩╬╣╦╣╦╣╬╩╣╦╩╚╦╠╣╠╬╩╩╦║
║╦╩╠╠╬╚╠╣╠╩╩╦╦╣╦╬╬╔╬╬╝╦╬╬╦╩╩╣╠╠╣╬╠╩║╣╠╩╣╠╬╣╦╬║╬╠═╗
║╣╠╠╠╔╠═╦╦╠╬╩╬╬╩║╬╠╣╠╬╝╬╦╣╠═╠╩╩╣╬╣╩╦╦╗╔╦╔╦╦╬╝╠╣╣╠╣
╚╩╠╚╣╣╦╬╩╣╣╩║╠╠╣╦╩╠╬╣╬╝╬╩╦╩╦╠╬╬╣╩╣╠╬╩╠╬╠╠╬╣╬╠╣╣╩╦╝
╚╬╦╬╩╣╩╠╦╠╬╗╠╠╠╬╩╩╠╣╣╝╣╗╬╠╦╣╩╦╦╦╠╔╬╗╩║╬╦╩╣╣╬╦╩╣╚╣╣
╚╦╠╔╠╬╠╣╠╚║╝╣╝╬╠╠╦╣╠╬╬╦╠╣╣╔╩╦═╬╩═╣╠╣╔╔╬╩╣╠╦╠╠╠╣╠╦╗
╠╣╦╠╠╩╣╠╬╩╦╣╠╠╗║╚╬╦╣║╔╗╩╣═╬╩╠╬╦╩╣╬╩╠╬╬╠╣╠╬╣╗╣╩╬╦╠╝
╦╣╦╦╣╬╠║╦╩╔╬╠╠╠╠╣╦╩╩╝╬╩╣╗╠╩╣╠╣╣╗╦╦╠═╔╣╩╣╔╔╬╠╦╠╬╠╗
║╣╦═╠╬╬╣╠═╠╩╬╬╝╬╔╦╠╩╩╬╚╚╦╦╣╩╦╣╣╦╣╠╣╬╩╩╬╣╩╔╠╬╬╦╦╩╦╣
╠║╩╦╦╦║╩║╦╬╦╣╦╩╩╣╩╬╠╣╩╣╬═╬╦╚╠╦╣║╩╣╩╦╠║╩╬╠╩╔╣╩╣╩║╣╣
╔═╩╣╦╣╩║═╗═╩╦╣╦╦═╩╔╚═╠╩╦╩╦╔╠╔╩═╦╣╬╝╠║╚╩╦╔╬╣╦╠╚╩╣╠╗
╔╩╬╩╬╣╬╬╗╣╩╠╩╦╦╦╩╦╣╣╩╩╬╬╗╦╦╩╣╩╬╠╦╣╣╩╬╬╣╬╬╠╩╩╔║╩╦╣║
╬╬╣╣╦╠╠╦╦╦╬╩╔╣╦═╠╩╩╠╬═╬╠╬╬╩╩═╠╦╗╦╦║╦╦╩╣║╬╦╠╦╠╬╦╬╣
╔╣╠╝╠╬╬╬╠╩╚╦╚╣╦╦╣╬╦╬╦╩╦╣═╣═╦╠╣╣╬╠╠╦╦╩╩╦╦╦╠╬╦╠╦╣╣╩╣
╔╦╩╣╩╝╬╣╩╩╬╣╬╦╦╩╚╬╔╠╩╠╠╗╠╣╠╠╩║╠╩╣╠║╣╩╠╠╝╩╣╩╬╦╣╬╠╣╣
╔╠╬╚╠╣╝═╦╦╬╬╬╬╠╠╩╦╩╦╠╩╣╦╦╣╣╠╬╦╬╬╩╣║╔╠╠╩╚╦╩╩╠╠╦╠╬╬╗
╚╠╩╬║╦╔╩╬╣╣╣╩╠╬╠╬╠╬╝╣╩╦╠╬╬╔╣═╣╦═╬╩╣╣╬╦╠╦╬╠╩║╝╣╬╣╬╣
╔╠╦╬╠╦╬╬╠╩╩╩╩╠╠╦╠═╠╠╠╠╣╩╩╬╠╬╩╦╬╩╬╬╝╬╣╠╠╣╦╣╠╣╬╩═╗╠╣
╠╣╩╠╦╣╣╦╬╩╣╣╦╠╩╩╬╦╠╦╔╠╚╬╦╣╦╦╠╩╣╠╝╦╠╠╦╣╩╬╬╠╬╩╣╦╩╬║╝
╣╠╬╬╬╦╩╣╠╦╩╠╬╩╦╣╗╣╦╬╠╠╦╬╬╦══╔╦╬╣═╬╩╩╩╦╩╬╠╦╬╠╗╩╬╬║
╠╔╦╠╬╠╩╩╔╠╣╩╬╦╣╝╠╬╬╬╣╬╠╩╦╣╠╩╦╗╣╦╩╦╗╦╗╬╩╩╩╠╠╩╣╠╠╠╩╝
╚╣╗╝╩╠╬╬╣╦╩╩╠╬╣╩╠╩╬╦║╬╠╗╠╦╣╗╦╠╝╦╦╣╠╝╠╦╬╠╣╩╦╩╠╠╠╬╬╣
╠═╣╠╣╬╦╣╬╩║╩╦╣╠╠╬╬╣╣╣╠╣╝╚╬╩╦╠╣╦╬╝╠╦║╠╩╣╩╣╣╩╣╩╣╩═╝╗
╠╩╩╩╠╣╩╚╠╩╦╦╩╩╦╔╠╣╬╩╩╩╦╣╚╦╬╦╩╔╩╝╠╔╩═╬╦╣╠╩╣╬╣╔╣╬╦╦
╔╦╬╩╦╣╠╦╩╬╩╬╦╬╠╠╬╠╦╦╠╣╠╩╩═╣╣╠╬╩╠╠╩╩╦╬╝╠╦╩╣╣╦╩╠═╗╗╝
╠╠╦╔╬╦╩╠╝╗╗╬╣╩╬╩╩╬╠╣╠╬╬╩╠╠╣╬╠╬╩╬╬╠╚╦╠╣╦╔╝╠╩╩╬╬╦╩╠
╠╠╦╩╣╩╣╦╠╩╩╚╠║╩╦╬╦╦╠╬╦╣╔╩╣╩╬╦╣╣╩╩╗╣╠╔╣╩╝╩╣╣╣╩╩╠╣╣╣
║╠╝╣╗╬╣╩╠║╬╦║╬╠╩╬╬╩╬═╩╦╬╣╬╬╠╠╠╣║╠║╠╠╦╠╦╣╗╦╔╠╬╬╣╦╩╣
╚╦╬╬║╬╬╠╠║╣╠╠╣╩╣╦╬╠╠╣║╠╣╠╠╩╣╠╣╬╩╦╦╠╦╦╣╣╩╩╣╩╩╦╣╠╠╩╝
╔╚╬╗╠╣╦╣╬╬╦╩╩╣╩╣╬╠╚╩╩╬╣╬╠╩═╩╠╦╚╦╣╦╬╩╣╗╦╣╩╦╬╔╦╬╝╚╦╣
╚╬╦╬║╬╦╩╩╦╣╦╠╦╦╦═╩╔╔╣╗╩╩╦╠╣╬╦╠╬╣╩╚║╣╩╝╣╦╬╬╠╦╣╠╠╝╠╝
╔╝╦╩╩╦╩╣╬╣╣║╣╝═╩╣╝╦╦╬╠╚╗╩╩╠╦╣╠╦╦╬╝╚╦═╣╩╬╣╦╝╦╬╗╣╬╬╝
╠╩╦╠╚╠╩╬╬╦╣╠╬╦╩╦╬╬╩╬╝╦╩╦╩╣╠╬╠╠╣╚╣╬╠╠╠╩╠╠╦╩╔╬╠╠╩╣╗
╚╠╣╣╔╣╣╝═╣╬╝═╦╩╣╗╬╦╔╠╩╦╬║╬╣╬╗╠╬╬║║╬╩╬╔╩╔╠╬╔╬╦╦║╠╠╗
╚╦╬╚╠╝╦╬╬╠╠╣╦╠╣║╠║╚╬╠╦╦╝╣╚╬╔╩╬╬╦╩╦╔╬╩╠╦╩╚╠╠╩╠╠╠╦╦╣
╚╗╬╩╚╩╬╬╣╣╚╦╣╝║╣╩╠╬╠╬╬╣╣╠╬╬╔╬╩╬╩╣╩╦╩╠╩╩╩╣║╠╩╠╬╣╦╗╣
╠╬╦╠╬╩╝╩╬╩╣╩╬╦╠╩╦╠╠╩╬╩╦╦║╬╠╣╣╬╣╬╦╗╗╦╣╦╬╩╩╬╦╩╬╦╬╩╗║
╔╦╠╦╠╬╣╦╠╦╠╩╣╬╦╦╠╦╠╔╩╩╣╩╦═╠╬╦╝║╩╠╠╣╦╔╣╠╦╬╬╦═╩╦╩╬═╣
╔╣╠╦╩╠╔╣╣╣╩╬╬╦╦╦╬╬╬╠╩╣╣╬╠║╠╩╦╩╦╩╬╦║╬╬╣╣╠╦╔╬╠╬╦╠╗╣╣
╚╣╬╠╠╗╠╬╠╣╣╣╝╠╣╬╦╦╣╦╬╬╚╦╩═╔╩╦╣╦╣╠╠╦╩╩╬╣╬╣╔╝╦╣╦╣╩╠║
║╠╬╦╩╬╩╣╬╔╦╔╬╣╦╦╣╩╬╠╗╣╩╣╚╩╠╩╣╦╩╬╣╣╠╣╦╦╔╦║╠╬╦╗╬╣╩╬╗
╚╬╠╝╣╗║╣╬╦╦╣╠╣╬╬╬╩╦╬╦╬╠╦╠╩╦╦╬╩╦╦╬╬╦╣╩╦╬╬╠╠╦╬╠╣╣╣╣╝
═╚╩╩═╩ ╚╚══╩╩╝╩╩╩╩╩╩╚╝╩═╚╩═╝╚╝╩╩═╩ ═╩ ═ ╚╩╩═ ╩╩╝█
$ ./maze-solver-wall -v -l 50x50-03.txt
: Turn: left
: Rows: 50
: Cols: 50
: Row: █═╗═╗╔╔══ ╔╦═╦═╦═══╦╦╦╗╔╗╗╦═╦ ╔═╔╔╗╗╔═╔╔╦═╔═╗╗═╦╗╗
< a lot of lines not shown >
: Row: ═╚╩╩═╩ ╚╚══╩╩╝╩╩╩╩╩╩╚╝╩═╚╩═╝╚╝╩╩═╩ ═╩ ═ ╚╩╩═ ╩╩╝█
: At [0,0]: █ (with directions: ES). Heading: S. Turning: A (S)
: At [1,0]: ╠ (with directions: N). Heading: S. Turning: B (N)
: At [0,0]: █ (with directions: ES). Heading: N. Turning: R (E)
: At [0,1]: ═ (with directions: EW). Heading: E. Turning: A (E)
: At [0,2]: ╗ (with directions: SW). Heading: E. Turning: R (S)
: At [1,2]: ╠ (with directions: NES). Heading: S. Turning: A (S)
< an awful lot of lines not shown >
: At [0,2]: ╗ (with directions: SW). Heading: N. Turning: L (W)
: At [0,1]: ═ (with directions: EW). Heading: W. Turning: A (W)
: At [0,0]: █ (with directions: ES). Heading: W. Turning: L (S)
no
$ ./maze-solver-wall -l -s 50x50-03.txt
no
█═╗═╗╔╔══ ╔╦═╦═╦═══╦╦╦╗╔╗╗╦═╦ ╔═╔╔╗╗╔═╔╔╦═╔═╗╗═╦╗╗
╠║╠╩╔╣╚╣╠╣╬╦╬╦═╬╚╩╣╚╬╦╦╣═╠╦╬╠╩═╩╬╦═╬╦╠╗╠╬╠╣╚╩╣╣╣╦╗
╔╬╬╣╣╩╣╩╦╠╩╩╠╔╠╩╣╠╩╬╬╩╣╝╩╦╦╦╦╬╦╠╦╬╣╬╦╬╣╚╦╣╦╦╦╣╦╣╬╣
╚╚╬╦╦╗╬╠╬╠╚╠╣╦═╬═╠╔╦╗║╩╦╚╔╬╚╣╩╣╣╬╚╗╩╣╣╬╬╦╩╣╩╬║╩╦╩╗
╔║╬╠╦╬╔╩╠╣╠╣╣╦╣╗╝╚╣╠╠╬╬╗╣╬╬═╠╩╣╣╣╬╠╠═╠╣╦╣═╦╣╦╦╠╠═║
╚╔╠╬╠╦══╦╣╠╝═╠╦╦╦╣╠╬╣╩╬╬╦╦╗═╠╦╬╣╠╬╬╬╣╠╣╣╣╬╣╔╣╣║╣╬╣
╚╩╩╣╣╠╣╦╩╣╬╦╩╦╠╬╩╠╝╠╩╣║╦╗╦╠╣╬═╔╝╦╬╩╣╬╣╦╦╚╣╣╬╦╩╗╣╬╣
╠╦╠╠╠╦╠╠╬╬╦╠╬╦╣╠╚╣╦╣╩╣╩╣╣╬╔╣╩╬╣╦╣╦╣╬╩╣╦╩╚╦╠╣╠╬╩╩╦║
║╦╩╠╠╬╚╠╣╠╩╩╦╦╣╦╬╬╔╬╬╝╦╬╬╦╩╩╣╠╠╣╬╠╩║╣╠╩╣╠╬╣╦╬║╬╠═╗
║╣╠╠╠╔╠═╦╦╠╬╩╬╬╩║╬╠╣╠╬╝╬╦╣╠═╠╩╩╣╬╣╩╦╦╗╔╦╔╦╦╬╝╠╣╣╠╣
╚╩╠╚╣╣╦╬╩╣╣╩║╠╠╣╦╩╠╬╣╬╝╬╩╦╩╦╠╬╬╣╩╣╠╬╩╠╬╠╠╬╣╬╠╣╣╩╦╝
╚╬╦╬╩╣╩╠╦╠╬╗╠╠╠╬╩╩╠╣╣╝╣╗╬╠╦╣╩╦╦╦╠╔╬╗╩║╬╦╩╣╣╬╦╩╣╚╣╣
╚╦╠╔╠╬╠╣╠╚║╝╣╝╬╠╠╦╣╠╬╬╦╠╣╣╔╩╦═╬╩═╣╠╣╔╔╬╩╣╠╦╠╠╠╣╠╦╗
╠╣╦╠╠╩╣╠╬╩╦╣╠╠╗║╚╬╦╣║╔╗╩╣═╬╩╠╬╦╩╣╬╩╠╬╬╠╣╠╬╣╗╣╩╬╦╠╝
╦╣╦╦╣╬╠║╦╩╔╬╠╠╠╠╣╦╩╩╝╬╩╣╗╠╩╣╠╣╣╗╦╦╠═╔╣╩╣╔╔╬╠╦╠╬╠╗
║╣╦═╠╬╬╣╠═╠╩╬╬╝╬╔╦╠╩╩╬╚╚╦╦╣╩╦╣╣╦╣╠╣╬╩╩╬╣╩╔╠╬╬╦╦╩╦╣
╠║╩╦╦╦║╩║╦╬╦╣╦╩╩╣╩╬╠╣╩╣╬═╬╦╚╠╦╣║╩╣╩╦╠║╩╬╠╩╔╣╩╣╩║╣╣
╔═╩╣╦╣╩║═╗═╩╦╣╦╦═╩╔╚═╠╩╦╩╦╔╠╔╩═╦╣╬╝╠║╚╩╦╔╬╣╦╠╚╩╣╠╗
╔╩╬╩╬╣╬╬╗╣╩╠╩╦╦╦╩╦╣╣╩╩╬╬╗╦╦╩╣╩╬╠╦╣╣╩╬╬╣╬╬╠╩╩╔║╩╦╣║
╬╬╣╣╦╠╠╦╦╦╬╩╔╣╦═╠╩╩╠╬═╬╠╬╬╩╩═╠╦╗╦╦║╦╦╩╣║╬╦╠╦╠╬╦╬╣
╔╣╠╝╠╬╬╬╠╩╚╦╚╣╦╦╣╬╦╬╦╩╦╣═╣═╦╠╣╣╬╠╠╦╦╩╩╦╦╦╠╬╦╠╦╣╣╩╣
╔╦╩╣╩╝╬╣╩╩╬╣╬╦╦╩╚╬╔╠╩╠╠╗╠╣╠╠╩║╠╩╣╠║╣╩╠╠╝╩╣╩╬╦╣╬╠╣╣
╔╠╬╚╠╣╝═╦╦╬╬╬╬╠╠╩╦╩╦╠╩╣╦╦╣╣╠╬╦╬╬╩╣║╔╠╠╩╚╦╩╩╠╠╦╠╬╬╗
╚╠╩╬║╦╔╩╬╣╣╣╩╠╬╠╬╠╬╝╣╩╦╠╬╬╔╣═╣╦═╬╩╣╣╬╦╠╦╬╠╩║╝╣╬╣╬╣
╔╠╦╬╠╦╬╬╠╩╩╩╩╠╠╦╠═╠╠╠╠╣╩╩╬╠╬╩╦╬╩╬╬╝╬╣╠╠╣╦╣╠╣╬╩═╗╠╣
╠╣╩╠╦╣╣╦╬╩╣╣╦╠╩╩╬╦╠╦╔╠╚╬╦╣╦╦╠╩╣╠╝╦╠╠╦╣╩╬╬╠╬╩╣╦╩╬║╝
╣╠╬╬╬╦╩╣╠╦╩╠╬╩╦╣╗╣╦╬╠╠╦╬╬╦══╔╦╬╣═╬╩╩╩╦╩╬╠╦╬╠╗╩╬╬║
╠╔╦╠╬╠╩╩╔╠╣╩╬╦╣╝╠╬╬╬╣╬╠╩╦╣╠╩╦╗╣╦╩╦╗╦╗╬╩╩╩╠╠╩╣╠╠╠╩╝
╚╣╗╝╩╠╬╬╣╦╩╩╠╬╣╩╠╩╬╦║╬╠╗╠╦╣╗╦╠╝╦╦╣╠╝╠╦╬╠╣╩╦╩╠╠╠╬╬╣
╠═╣╠╣╬╦╣╬╩║╩╦╣╠╠╬╬╣╣╣╠╣╝╚╬╩╦╠╣╦╬╝╠╦║╠╩╣╩╣╣╩╣╩╣╩═╝╗
╠╩╩╩╠╣╩╚╠╩╦╦╩╩╦╔╠╣╬╩╩╩╦╣╚╦╬╦╩╔╩╝╠╔╩═╬╦╣╠╩╣╬╣╔╣╬╦╦
╔╦╬╩╦╣╠╦╩╬╩╬╦╬╠╠╬╠╦╦╠╣╠╩╩═╣╣╠╬╩╠╠╩╩╦╬╝╠╦╩╣╣╦╩╠═╗╗╝
╠╠╦╔╬╦╩╠╝╗╗╬╣╩╬╩╩╬╠╣╠╬╬╩╠╠╣╬╠╬╩╬╬╠╚╦╠╣╦╔╝╠╩╩╬╬╦╩╠
╠╠╦╩╣╩╣╦╠╩╩╚╠║╩╦╬╦╦╠╬╦╣╔╩╣╩╬╦╣╣╩╩╗╣╠╔╣╩╝╩╣╣╣╩╩╠╣╣╣
║╠╝╣╗╬╣╩╠║╬╦║╬╠╩╬╬╩╬═╩╦╬╣╬╬╠╠╠╣║╠║╠╠╦╠╦╣╗╦╔╠╬╬╣╦╩╣
╚╦╬╬║╬╬╠╠║╣╠╠╣╩╣╦╬╠╠╣║╠╣╠╠╩╣╠╣╬╩╦╦╠╦╦╣╣╩╩╣╩╩╦╣╠╠╩╝
╔╚╬╗╠╣╦╣╬╬╦╩╩╣╩╣╬╠╚╩╩╬╣╬╠╩═╩╠╦╚╦╣╦╬╩╣╗╦╣╩╦╬╔╦╬╝╚╦╣
╚╬╦╬║╬╦╩╩╦╣╦╠╦╦╦═╩╔╔╣╗╩╩╦╠╣╬╦╠╬╣╩╚║╣╩╝╣╦╬╬╠╦╣╠╠╝╠╝
╔╝╦╩╩╦╩╣╬╣╣║╣╝═╩╣╝╦╦╬╠╚╗╩╩╠╦╣╠╦╦╬╝╚╦═╣╩╬╣╦╝╦╬╗╣╬╬╝
╠╩╦╠╚╠╩╬╬╦╣╠╬╦╩╦╬╬╩╬╝╦╩╦╩╣╠╬╠╠╣╚╣╬╠╠╠╩╠╠╦╩╔╬╠╠╩╣╗
╚╠╣╣╔╣╣╝═╣╬╝═╦╩╣╗╬╦╔╠╩╦╬║╬╣╬╗╠╬╬║║╬╩╬╔╩╔╠╬╔╬╦╦║╠╠╗
╚╦╬╚╠╝╦╬╬╠╠╣╦╠╣║╠║╚╬╠╦╦╝╣╚╬╔╩╬╬╦╩╦╔╬╩╠╦╩╚╠╠╩╠╠╠╦╦╣
╚╗╬╩╚╩╬╬╣╣╚╦╣╝║╣╩╠╬╠╬╬╣╣╠╬╬╔╬╩╬╩╣╩╦╩╠╩╩╩╣║╠╩╠╬╣╦╗╣
╠╬╦╠╬╩╝╩╬╩╣╩╬╦╠╩╦╠╠╩╬╩╦╦║╬╠╣╣╬╣╬╦╗╗╦╣╦╬╩╩╬╦╩╬╦╬╩╗║
╔╦╠╦╠╬╣╦╠╦╠╩╣╬╦╦╠╦╠╔╩╩╣╩╦═╠╬╦╝║╩╠╠╣╦╔╣╠╦╬╬╦═╩╦╩╬═╣
╔╣╠╦╩╠╔╣╣╣╩╬╬╦╦╦╬╬╬╠╩╣╣╬╠║╠╩╦╩╦╩╬╦║╬╬╣╣╠╦╔╬╠╬╦╠╗╣╣
╚╣╬╠╠╗╠╬╠╣╣╣╝╠╣╬╦╦╣╦╬╬╚╦╩═╔╩╦╣╦╣╠╠╦╩╩╬╣╬╣╔╝╦╣╦╣╩╠║
║╠╬╦╩╬╩╣╬╔╦╔╬╣╦╦╣╩╬╠╗╣╩╣╚╩╠╩╣╦╩╬╣╣╠╣╦╦╔╦║╠╬╦╗╬╣╩╬╗
╚╬╠╝╣╗║╣╬╦╦╣╠╣╬╬╬╩╦╬╦╬╠╦╠╩╦╦╬╩╦╦╬╬╦╣╩╦╬╬╠╠╦╬╠╣╣╣╣╝
═╚╩╩═╩ ╚╚══╩╩╝╩╩╩╩╩╩╚╝╩═╚╩═╝╚╝╩╩═╩ ═╩ ═ ╚╩╩═ ╩╩╝█
Run the commands shown if you want to see the whole output. All the 1259 lines!
The Left Wall Path is identical to the Right Wall Path, when the maze is untraversable. The left goes clockwise, and the right counter clockwise.
A Tropical Island Observation
We could consider the maze as an island instead (isolated and tropical, according to tradition), which we are shipwrecked on. It has a high mountain (a former vulcano) inland, and a dense forrest, so the first thing we do is to go around it. At the shore. We come across huge rocks and rivers, that forces us to detour inland, more or less briefly, before we are back at the beach. And so we go round the entire island. The path shown above (for an untraversable maze) is our route around the island. (The entance is where we drifted ashore, but the exit does not fit the picture so should be ignored. Unless it is the location of the pirate treasure...)Part 4: The Class
See the next part; Part 4: The Class where I turn the code presented so far (or most of it anyway) into a class and module.