diff options
author | Andinus <andinus@nand.sh> | 2021-11-17 23:12:15 +0530 |
---|---|---|
committer | Andinus <andinus@nand.sh> | 2021-11-17 23:12:15 +0530 |
commit | 428fa000256bd47c121f8b03b94f37e9f29095e0 (patch) | |
tree | df2711156e00a76412bb06948d994ce51b42a0d0 /algorithms/raku/DFS.raku | |
parent | 22aa1c9b322c424724516d70b77d1d5b93155697 (diff) | |
download | fornax-428fa000256bd47c121f8b03b94f37e9f29095e0.tar.gz |
raku/DFS: Add DFS implementation in raku, Add input 06
Diffstat (limited to 'algorithms/raku/DFS.raku')
-rw-r--r-- | algorithms/raku/DFS.raku | 69 |
1 files changed, 69 insertions, 0 deletions
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; + } + } + } +} |