path: root/algorithms/raku/DFS.raku

subset File of Str where *.IO.f;

# Cells as defined by fornax format.
constant $PATH = '.';
constant $BLOK = '#';
constant $DEST = '$';
constant $STRT = '^';
constant $VIS = '-';
constant $CUR = '@';
constant $CURPATH = '~';

sub MAIN(File $input) {
    my @maze = $input.IO.lines.map(*.comb);
    die "Inconsistent maze" unless [==] @maze.map(*.elems);

    put "rows:{@maze.elems} cols:{@maze[0].elems}";
    for 0..@maze.end -> $y {
        for 0..@maze[0].cache.end -> $x {
            dfs(@maze, $y, $x) if @maze[$y][$x] eq "^";
        }
    }
    die "Cannot solve maze";
}

sub dfs(
    @maze, Int $y, Int $x, @visited?, @cur-path? --> Bool
) {
    # If @visited was not passed then mark the given cell as visited
    # because it's the cell we're starting at.
    @visited[$y][$x] = True unless @visited;
    @cur-path[$y][$x] = True unless @cur-path;

    # neighbor block loops over the neighbors of $y, $x.
    neighbor: for neighbors(@maze, $y, $x).List.pick(*) -> $pos {
        # Move on to next neighbor if we've already visited this one.
        next neighbor if @visited[$pos[0]][$pos[1]];

        # Printing Marker cells.
        given @maze[$pos[0]][$pos[1]] {
            when $DEST { print "|" }
            when $BLOK { print "!" }
        }

        # Print the maze on every iteration.
        for 0..@maze.end -> $j {
            for 0..@maze[0].end -> $k {
                if @maze[$j][$k] eq $STRT | $DEST {
                    print @maze[$j][$k];
                } else {
                    if $j == $pos[0] and $k == $pos[1] {
                        print "@";
                    } else {
                        print(
                            @cur-path[$j][$k]
                            ?? "~" !! @visited[$j][$k] ?? "-" !! @maze[$j][$k]
                        );
                    }
                }
            }
        }
        print "\n";

        given @maze[$pos[0]][$pos[1]] {
            when $DEST { exit; }
            when $PATH|$STRT {
                @visited[$pos[0]][$pos[1]] = @cur-path[$pos[0]][$pos[1]] = True;
                dfs(@maze, $pos[0], $pos[1], @visited, @cur-path);
                @cur-path[$pos[0]][$pos[1]] = False;
            }
        }
    }
}

# neighbors returns the neighbors of given index. Neighbors are cached
# in @neighbors array. This way we don't have to compute them
# everytime neighbors subroutine is called for the same position. We
# don't need this caching here since every cell will be visited only
# once. This subroutine was taken from Octans::Neighbors.
sub neighbors(
    @puzzle, Int $y, Int $x --> List
) is export {
    # @directions is holding a list of directions we can move in. It's
    # used later for neighbors subroutine.
    state List @directions = (
        # $y, $x
        ( +1, +0 ), # bottom
        ( -1, +0 ), # top
        ( +0, +1 ), # left
        ( +0, -1 ), # right
    );

    # @neighbors holds the neighbors of given position.
    state Array @neighbors;

    if @puzzle[$y][$x] {
        # Don't re-compute neighbors.
        unless @neighbors[$y][$x] {
            # Set it to an empty array because otherwise if it has no
            # neighbors then it would've be recomputed everytime
            # neighbors() was called.
            @neighbors[$y][$x] = [];

            my Int $pos-x;
            my Int $pos-y;

            # Starting from the intital position of $y, $x we move to
            # each direction according to the values specified in
            # @directions array. In this case we're just trying to
            # move in 4 directions (top, bottom, left & right).
            direction: for @directions -> $direction {
                $pos-y = $y + $direction[0];
                $pos-x = $x + $direction[1];

                # If movement in this direction is out of puzzle grid
                # boundary then move on to next direction.
                next direction unless @puzzle[$pos-y][$pos-x];

                # If neighbors exist in this direction then add them
                # to @neighbors[$y][$x] array.
                push @neighbors[$y][$x], [$pos-y, $pos-x];
            }
        }
    } else {
        # If it's out of boundary then return no neighbor.
        @neighbors[$y][$x] = [];
    }

    return @neighbors[$y][$x];
}