about summary refs log tree commit diff stats
path: root/octans.raku
blob: 0c2e3fa4f914046fc1cf2a8c4dcedc9fbba839ab (plain) (blame)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
#!/usr/bin/env raku

use v6.d;
use WWW;

unit sub MAIN (
    Str $url, #= url for Algot's crossword
    Str :$dict = "/usr/share/dict/words", #= dictionary file
    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
    ( -1, +0 ), # top
    ( +0, +1 ), # left
    ( +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 = (
#     <n a t k>,
#     <i m e c>,
#     <a r d e>,
#     <t e c h>
# );

# 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 {
    $toot_url = "https://mastodon.art/api/v1/statuses/" ~ $url.split("/")[*-1];
}

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)<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;
                }
            }
        }
    }
}

if $verbose {
    say "Gray squares: ", @gray-squares;
    say "Puzzle";
    "    $_".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.
        say $word if word-search(@puzzle, $pos[0], $pos[1], $word);
    }
}

# 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:
            #
            # a b e
            # c a f
            #
            # And the word we're looking for is "cabefa". Then let's
            # say that we go through the other 'a' first (bottom-mid
            # 'a') & at this point it would be marked as True but the
            # search would fail (correctly so).
            #
            # And after that failure we move to next neighbor which is
            # top-left 'a'. The search goes on until we reach 'f' &
            # get the list of f's neighbors which would return 'e' &
            # bottom-mid 'a'. Now 'e' would be discarded because it
            # was marked as visited but 'a' also has been marked as
            # visited & it too would be discarded.
            #
            # This would cause us to miss solutions. So we just make
            # it False again if the word wasn't found with this
            # neighbor. After making it False, we move on to the next
            # 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,
                @visited
            ) {
                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;
}

# 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
) {
    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];
}