From a5fd4afc258afe61adc298101cf2665e0dfb6b9f Mon Sep 17 00:00:00 2001 From: Andinus Date: Thu, 14 Jan 2021 20:36:33 +0530 Subject: Document the implementation --- octans.raku | 72 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++- 1 file changed, 71 insertions(+), 1 deletion(-) diff --git a/octans.raku b/octans.raku index fc070e9..0c2e3fa 100755 --- a/octans.raku +++ b/octans.raku @@ -9,6 +9,8 @@ unit sub MAIN ( Bool :v($verbose), #= increase verbosity ); +# @directions is holding a list of directions we can move in. It's +# used later for neighbors subroutine. my List @directions[4] = ( # $y, $x ( +1, +0 ), # bottom @@ -17,6 +19,14 @@ my List @directions[4] = ( ( +0, -1 ), # right ); +# This code is just for testing purpose. The code below that is +# getting the puzzle & parsing it will set @puzzle & @gray-squares +# like this: + +# We can call @puzzle[$y][$x] to get the character. $y stands for +# column & $x for row, so @puzzle[0][3] will return `k' for this +# sample @puzzle: + # my List @puzzle = ( # , # , @@ -26,10 +36,19 @@ my List @directions[4] = ( # my List @gray-squares = (3, 0), (2, 0); # $y, $x +# @puzzle will hold the puzzle grid. my @puzzle; + +# @gray-squares will hold the position of gray squares. Algot marks +# them with an asterisk ("*") after the character. my @gray-squares; +# $toot_url will hold the url that we'll call to get the toot data. my Str $toot_url; + +# User can pass 2 types of links, either it will be the one when they +# view it from their local instance or the one they get from Algot's +# profile. We set $toot_url from it. if $url.match("web/statuses") -> $match { $toot_url = $match.replace-with("api/v1/statuses"); } else { @@ -38,12 +57,21 @@ if $url.match("web/statuses") -> $match { say "Fetching: $toot_url" if $verbose; +# jget just get's the url & decodes the json. We access the +# description field of 1st media attachment. if (jget($toot_url)[0] ~~ + # This regex gets the puzzle in $match. / [[(\w [\*]?) \s*] ** 4] ** 4 $/) -> $match { + + # We have each character of the puzzle stored in $match. It's + # assumed that it'll be a 4x4 grid. for 0 .. 3 -> $y { for 0 .. 3 -> $x { with $match[0][($y * 4) + $x].Str.lc -> $char { + + # If it ends with an asterisk then we push the + # position to @gray-squares. if $char.ends-with("*") { @puzzle[$y][$x] = $char.comb[0]; push @gray-squares, [$y, $x]; @@ -61,14 +89,24 @@ if $verbose { " $_".say for @puzzle; } +# This for block loops over every word in the dictionary & searches +# the puzzle grid for it's presence. word: for $dict.IO.lines -> $word { + # We don't want words whose length is less than 7. next word unless $word.chars >= 7; + # start-pos block loops over each starting position. In normal + # case every position could be the start position but for Algot's + # puzzle they're limited to a few blocks. start-pos: for @gray-squares -> $pos { + + # If the dictionary word doesn't start with the starting + # position character then move on to the next start position. next start-pos unless $word.starts-with( @puzzle[$pos[0]][$pos[1]] ); + # Check if each letter of word is present in puzzle grid. next word unless $word.comb ⊆ @puzzle[*;*]; # Print the word if the search is successful. @@ -76,23 +114,34 @@ word: for $dict.IO.lines -> $word { } } -# word-search performs a Depth-First search on @puzzle. +# word-search performs a Depth-First search on @puzzle. word-search +# matches the word character by character. sub word-search ( @puzzle, Int $y, Int $x, + # $count will keep the count of character's of $word present in # the puzzle. Str $word, Int $count = 1, @visited? is copy --> Bool ) { + # If the number of character's we've found is equal to the length + # of $word then return True because we've found the whole word. return True if $count == $word.chars; # For each neighbor, we perform a Depth-First search to find the # word. neighbor: for neighbors(@puzzle, $y, $x).List -> $pos { + + # Move on to next neighbor if we've already visited this one. + # This is because we cannot reuse a grid. next neighbor if @visited[$pos[0]][$pos[1]]; if @puzzle[$pos[0]][$pos[1]] eq $word.comb[$count] { + + # This explains why we have to mark this position as False + # if the search fails: + # # Here we're marking this position as True. This approach # might cause us to miss possible solutions. If the puzzle # is like so: @@ -118,6 +167,10 @@ sub word-search ( # neighbor. @visited[$pos[0]][$pos[1]] = True; + + # Call word-search recursively & increment $count as we + # find each character. If the search was successful then + # return True. if word-search( @puzzle, $pos[0], $pos[1], $word, $count + 1, @@ -125,11 +178,15 @@ sub word-search ( ) { return True; } else { + # Mark this as not visited if the search was + # unsuccessful and move on to next neighbor. @visited[$pos[0]][$pos[1]] = False; next neighbor; } } } + + # return False if no neighbor matches the character. return False; } @@ -142,19 +199,32 @@ sub neighbors ( state Array @neighbors; if @puzzle[$y][$x] { + + # If we've already computed the neighbors then no need to do + # it again. unless @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] = []; } -- cgit 1.4.1-2-gfad0