From 5bb0f224483fbc1d57fd1c5a2f4a22dd7263ecd6 Mon Sep 17 00:00:00 2001
From: Andinus <andinus@nand.sh>
Date: Tue, 19 Jan 2021 18:20:23 +0530
Subject: Re-implement octans, move subroutines to respective modules
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 8bit

Initially it went over the list of words & checked if they exist in
the grid. This was very slow.

Currently it walks the grid & checks if the current string exist in
the dictionary. This is faster for these reasons:

• The dictionary is sorted, we perform binary range search on the
  dictionary to return the list of all words that start with specific
  string.
• Starting positions are limited.

If the dictionary wasn't sorted then this probably would've been
---
 lib/Neighbors.rakumod   | 53 +++++++++++++++++++++++++++++++++++++
 lib/Puzzle.rakumod      | 56 +++++++++++++++++++++++++++++++++++++++
 lib/RangeSearch.rakumod | 70 +++++++++++++++++++++++++++++++++++++++++++++++++
 lib/WordSearch.rakumod  | 67 ++++++++++++++++++++++++++++++++++++++++++++++
 4 files changed, 246 insertions(+)
 create mode 100644 lib/Neighbors.rakumod
 create mode 100644 lib/Puzzle.rakumod
 create mode 100644 lib/RangeSearch.rakumod
 create mode 100644 lib/WordSearch.rakumod

(limited to 'lib')

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;
+    }
+}
-- 
cgit 1.4.1-2-gfad0