From 428fa000256bd47c121f8b03b94f37e9f29095e0 Mon Sep 17 00:00:00 2001
From: Andinus <andinus@nand.sh>
Date: Wed, 17 Nov 2021 23:12:15 +0530
Subject: raku/DFS: Add DFS implementation in raku, Add input 06

---
 algorithms/raku/DFS.raku | 69 ++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 69 insertions(+)
 create mode 100644 algorithms/raku/DFS.raku

(limited to 'algorithms/raku/DFS.raku')

diff --git a/algorithms/raku/DFS.raku b/algorithms/raku/DFS.raku
new file mode 100644
index 0000000..4789ce9
--- /dev/null
+++ b/algorithms/raku/DFS.raku
@@ -0,0 +1,69 @@
+use Octans::Neighbors;
+
+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}";
+    dfs(@maze, 0, 0);
+}
+
+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;
+            }
+        }
+    }
+}
-- 
cgit 1.4.1-2-gfad0


From 03745f7ce6b53054560f1c35d256de00c1113fd8 Mon Sep 17 00:00:00 2001
From: Andinus <andinus@nand.sh>
Date: Thu, 18 Nov 2021 16:43:05 +0530
Subject: Copy neighbors subroutine

---
 algorithms/raku/DFS.raku | 59 ++++++++++++++++++++++++++++++++++++++++++++++--
 1 file changed, 57 insertions(+), 2 deletions(-)

(limited to 'algorithms/raku/DFS.raku')

diff --git a/algorithms/raku/DFS.raku b/algorithms/raku/DFS.raku
index 4789ce9..0cc7207 100644
--- a/algorithms/raku/DFS.raku
+++ b/algorithms/raku/DFS.raku
@@ -1,5 +1,3 @@
-use Octans::Neighbors;
-
 subset File of Str where *.IO.f;
 
 # Cells as defined by fornax format.
@@ -67,3 +65,60 @@ sub dfs(
         }
     }
 }
+
+# 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];
+}
-- 
cgit 1.4.1-2-gfad0