about summary refs log tree commit diff stats
path: root/lib/WordSearch.rakumod
diff options
context:
space:
mode:
authorAndinus <andinus@nand.sh>2021-01-19 18:20:23 +0530
committerAndinus <andinus@nand.sh>2021-01-19 18:20:23 +0530
commit5bb0f224483fbc1d57fd1c5a2f4a22dd7263ecd6 (patch)
tree1623478ad72521793c499522a88bf258a39f6464 /lib/WordSearch.rakumod
parenta5fd4afc258afe61adc298101cf2665e0dfb6b9f (diff)
downloadoctans-5bb0f224483fbc1d57fd1c5a2f4a22dd7263ecd6.tar.gz
Re-implement octans, move subroutines to respective modules
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
Diffstat (limited to 'lib/WordSearch.rakumod')
-rw-r--r--lib/WordSearch.rakumod67
1 files changed, 67 insertions, 0 deletions
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;
+    }
+}