diff options
Diffstat (limited to 'lib')
| -rw-r--r-- | lib/Neighbors.rakumod | 53 | ||||
| -rw-r--r-- | lib/Puzzle.rakumod | 56 | ||||
| -rw-r--r-- | lib/RangeSearch.rakumod | 70 | ||||
| -rw-r--r-- | lib/WordSearch.rakumod | 67 |
4 files changed, 246 insertions, 0 deletions
diff --git a/lib/Neighbors.rakumod b/lib/Neighbors.rakumod new file mode 100644 index 0000000..41cb35d --- /dev/null +++ b/lib/Neighbors.rakumod @@ -0,0 +1,53 @@ +unit module Neighbors; + +# 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. +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] { + + # 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] = []; + } + + return @neighbors[$y][$x]; +} diff --git a/lib/Puzzle.rakumod b/lib/Puzzle.rakumod new file mode 100644 index 0000000..bf4f8c3 --- /dev/null +++ b/lib/Puzzle.rakumod @@ -0,0 +1,56 @@ +unit module Puzzle; + +use WWW; + +# get-puzzle returns the @puzzle along with it's @gray-squares. +sub get-puzzle ( + Str $url, + + # @puzzle will hold the puzzle grid. + @puzzle, + + # @gray-squares will hold the position of gray squares. Algot + # marks them with an asterisk ("*") after the character. + @gray-squares +) is export { + # $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 { + $toot_url = "https://mastodon.art/api/v1/statuses/" ~ $url.split("/")[*-1]; + } + + # @gray-squares should be empty. + @gray-squares = (); + + # jget just get's the url & decodes the json. We access the + # description field of 1st media attachment. + if (jget($toot_url)<media_attachments>[0]<description> ~~ + + # 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]; + } else { + @puzzle[$y][$x] = $char; + } + } + } + } + } +} diff --git a/lib/RangeSearch.rakumod b/lib/RangeSearch.rakumod new file mode 100644 index 0000000..16e43c1 --- /dev/null +++ b/lib/RangeSearch.rakumod @@ -0,0 +1,70 @@ +unit module RangeSearch; + +# range-starts-with returns a subset of given @dict list that start +# with $str. It should be faster than: +# +# @dict.grep: *.starts-with($str) +# +# @dict should be a sorted list of words. It performs binary lookup on +# the list. +sub range-starts-with ( + @dict, Str $str --> List +) is export { + # $lower, $upper hold the lower and upper index of the range + # respectively. + my Int ($lower, $upper); + + # Lookup the whole dictionary. + my Int ($start, $end) = (0, @dict.end); + + # Loop until we end up on the lower index of range. + while $start < $end { + # Divide the list into 2 parts. + my Int $mid = ($start + $end) div 2; + + # Check if $mid word is le (less than or equal to) $str. If + # true then discard the bottom end of the list, if not then + # discard the top end. + if $str le @dict[$mid].substr(0, $str.chars).lc { + $end = $mid; + } else { + $start = $mid + 1; + } + } + + # Found the lower index. + $lower = $start; + + # Set $end to the end of list but keep $start at the lower index. + $end = @dict.end; + + # Loop until we end up on the upper index of range. + while $start < $end { + # Divide the list into 2 parts. Adds 1 because we have to find + # the upper index in this part. `div' performs Interger + # division, output is floor'ed. + my Int $mid = (($start + $end) div 2) + 1; + + # Check if $mid word is lt (less than) $str. If true then + # discard the bottom end of the list, if not then discard the + # top end. + if $str lt @dict[$mid].substr(0, $str.chars).lc { + $end = $mid - 1; + } else { + $start = $mid; + } + } + + # Found the upper index. + $upper = $end; + + with @dict[$lower..$upper] -> @list { + # Maybe the word doesn't exist in the list, in that case there + # will be a single element in @list. We return an empty list + # unless that single element starts with $str. + if @list.elems == 1 { + return () unless @list[0].starts-with($str); + } + return @list; + } +} diff --git a/lib/WordSearch.rakumod b/lib/WordSearch.rakumod new file mode 100644 index 0000000..14d29b8 --- /dev/null +++ b/lib/WordSearch.rakumod @@ -0,0 +1,67 @@ +unit module WordSearch; + +use Neighbors; +use RangeSearch; + +# word-search walks the given grid & tries to find words in the +# dictionary. It walks in Depth-First manner (lookup Depth-First +# search). +sub word-search ( + # @dict holds the dictionary. @puzzle holds the puzzle. + @dict, @puzzle, + + # $y, $x is the position of the current cell, we have to follow + # this path. $str is the string we've looked up until now. If it's + # not passed then assume that we're starting at $y, $x and take + # @puzzle[$y][$x] as the string. + # + # $str should be passed in recursive calls, it's not required when + # $y, $x is the starting position. + Int $y, Int $x, $str? = @puzzle[$y][$x], + + # @visited holds the positions that we've already visited. + @visited? is copy --> List +) is export { + # 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; + + # neighbor block loops over the neighbors of $y, $x. + neighbor: for neighbors(@puzzle, $y, $x).List -> $pos { + # Move on to next neighbor if we've already visited this one. + next neighbor if @visited[$pos[0]][$pos[1]]; + + # Mark this cell as visited but only until we search this + # path. When moving to next neighbor, mark it False. + @visited[$pos[0]][$pos[1]] = True; + + # $word is the string that we're going to lookup in the + # dictionary. + my Str $word = $str ~ @puzzle[$pos[0]][$pos[1]]; + + # range-starts-with returns a list of all words in the + # dictionary that start with $word. + with range-starts-with(@dict, $word) -> @list { + if @list.elems > 0 { + # If $word exist in the dictionary then it should be + # the first element in the list. + take @list[0], @visited if @list[0] eq $word; + + # Continue on this path because there are 1 or more + # elements in @list which means we could find a word. + word-search( + # Don't pass the whole dictionary for next search. + # Words that start with "ab" will always be a + # subset of words that start with "a", so keeping + # this in mind we pass the output of last + # range-starts-with (@list). + @list, @puzzle, $pos[0], $pos[1], $word, @visited + ); + } + } + + # We're done looking up this path, mark this cell as False & + # move on to another neighbor. + @visited[$pos[0]][$pos[1]] = False; + } +} |