TheAlgorithms-Python

1
"""
2
Creates a random wordsearch with eight different directions
3
that are best described as compass locations.
4

5
@ https://en.wikipedia.org/wiki/Word_search
6
"""
7

8
from random import choice, randint, shuffle
9

10
# The words to display on the word search -
11
# can be made dynamic by randonly selecting a certain number of
12
# words from a predefined word file, while ensuring the character
13
# count fits within the matrix size (n x m)
14
WORDS = ["cat", "dog", "snake", "fish"]
15

16
WIDTH = 10
17
HEIGHT = 10
18

19

20
class WordSearch:
21
    """
22
    >>> ws = WordSearch(WORDS, WIDTH, HEIGHT)
23
    >>> ws.board  # doctest: +ELLIPSIS
24
    [[None, ..., None], ..., [None, ..., None]]
25
    >>> ws.generate_board()
26
    """
27

28
    def __init__(self, words: list[str], width: int, height: int) -> None:
29
        self.words = words
30
        self.width = width
31
        self.height = height
32

33
        # Board matrix holding each letter
34
        self.board: list[list[str | None]] = [[None] * width for _ in range(height)]
35

36
    def insert_north(self, word: str, rows: list[int], cols: list[int]) -> None:
37
        """
38
        >>> ws = WordSearch(WORDS, 3, 3)
39
        >>> ws.insert_north("cat", [2], [2])
40
        >>> ws.board  # doctest: +NORMALIZE_WHITESPACE
41
        [[None, None, 't'],
42
        [None, None, 'a'],
43
        [None, None, 'c']]
44
        >>> ws.insert_north("at", [0, 1, 2], [2, 1])
45
        >>> ws.board  # doctest: +NORMALIZE_WHITESPACE
46
        [[None, 't', 't'],
47
        [None, 'a', 'a'],
48
        [None, None, 'c']]
49
        """
50
        word_length = len(word)
51
        # Attempt to insert the word into each row and when successful, exit
52
        for row in rows:
53
            # Check if there is space above the row to fit in the word
54
            if word_length > row + 1:
55
                continue
56

57
            # Attempt to insert the word into each column
58
            for col in cols:
59
                # Only check to be made here is if there are existing letters
60
                # above the column that will be overwritten
61
                letters_above = [self.board[row - i][col] for i in range(word_length)]
62
                if all(letter is None for letter in letters_above):
63
                    # Successful, insert the word north
64
                    for i in range(word_length):
65
                        self.board[row - i][col] = word[i]
66
                    return
67

68
    def insert_northeast(self, word: str, rows: list[int], cols: list[int]) -> None:
69
        """
70
        >>> ws = WordSearch(WORDS, 3, 3)
71
        >>> ws.insert_northeast("cat", [2], [0])
72
        >>> ws.board  # doctest: +NORMALIZE_WHITESPACE
73
        [[None, None, 't'],
74
        [None, 'a', None],
75
        ['c', None, None]]
76
        >>> ws.insert_northeast("at", [0, 1], [2, 1, 0])
77
        >>> ws.board  # doctest: +NORMALIZE_WHITESPACE
78
        [[None, 't', 't'],
79
        ['a', 'a', None],
80
        ['c', None, None]]
81
        """
82
        word_length = len(word)
83
        # Attempt to insert the word into each row and when successful, exit
84
        for row in rows:
85
            # Check if there is space for the word above the row
86
            if word_length > row + 1:
87
                continue
88

89
            # Attempt to insert the word into each column
90
            for col in cols:
91
                # Check if there is space to the right of the word as well as above
92
                if word_length + col > self.width:
93
                    continue
94

95
                # Check if there are existing letters
96
                # to the right of the column that will be overwritten
97
                letters_diagonal_left = [
98
                    self.board[row - i][col + i] for i in range(word_length)
99
                ]
100
                if all(letter is None for letter in letters_diagonal_left):
101
                    # Successful, insert the word northeast
102
                    for i in range(word_length):
103
                        self.board[row - i][col + i] = word[i]
104
                    return
105

106
    def insert_east(self, word: str, rows: list[int], cols: list[int]) -> None:
107
        """
108
        >>> ws = WordSearch(WORDS, 3, 3)
109
        >>> ws.insert_east("cat", [1], [0])
110
        >>> ws.board  # doctest: +NORMALIZE_WHITESPACE
111
        [[None, None, None],
112
        ['c', 'a', 't'],
113
        [None, None, None]]
114
        >>> ws.insert_east("at", [1, 0], [2, 1, 0])
115
        >>> ws.board  # doctest: +NORMALIZE_WHITESPACE
116
        [[None, 'a', 't'],
117
        ['c', 'a', 't'],
118
        [None, None, None]]
119
        """
120
        word_length = len(word)
121
        # Attempt to insert the word into each row and when successful, exit
122
        for row in rows:
123
            # Attempt to insert the word into each column
124
            for col in cols:
125
                # Check if there is space to the right of the word
126
                if word_length + col > self.width:
127
                    continue
128

129
                # Check if there are existing letters
130
                # to the right of the column that will be overwritten
131
                letters_left = [self.board[row][col + i] for i in range(word_length)]
132
                if all(letter is None for letter in letters_left):
133
                    # Successful, insert the word east
134
                    for i in range(word_length):
135
                        self.board[row][col + i] = word[i]
136
                    return
137

138
    def insert_southeast(self, word: str, rows: list[int], cols: list[int]) -> None:
139
        """
140
        >>> ws = WordSearch(WORDS, 3, 3)
141
        >>> ws.insert_southeast("cat", [0], [0])
142
        >>> ws.board  # doctest: +NORMALIZE_WHITESPACE
143
        [['c', None, None],
144
        [None, 'a', None],
145
        [None, None, 't']]
146
        >>> ws.insert_southeast("at", [1, 0], [2, 1, 0])
147
        >>> ws.board  # doctest: +NORMALIZE_WHITESPACE
148
        [['c', None, None],
149
        ['a', 'a', None],
150
        [None, 't', 't']]
151
        """
152
        word_length = len(word)
153
        # Attempt to insert the word into each row and when successful, exit
154
        for row in rows:
155
            # Check if there is space for the word below the row
156
            if word_length + row > self.height:
157
                continue
158

159
            # Attempt to insert the word into each column
160
            for col in cols:
161
                # Check if there is space to the right of the word as well as below
162
                if word_length + col > self.width:
163
                    continue
164

165
                # Check if there are existing letters
166
                # to the right of the column that will be overwritten
167
                letters_diagonal_left = [
168
                    self.board[row + i][col + i] for i in range(word_length)
169
                ]
170
                if all(letter is None for letter in letters_diagonal_left):
171
                    # Successful, insert the word southeast
172
                    for i in range(word_length):
173
                        self.board[row + i][col + i] = word[i]
174
                    return
175

176
    def insert_south(self, word: str, rows: list[int], cols: list[int]) -> None:
177
        """
178
        >>> ws = WordSearch(WORDS, 3, 3)
179
        >>> ws.insert_south("cat", [0], [0])
180
        >>> ws.board  # doctest: +NORMALIZE_WHITESPACE
181
        [['c', None, None],
182
        ['a', None, None],
183
        ['t', None, None]]
184
        >>> ws.insert_south("at", [2, 1, 0], [0, 1, 2])
185
        >>> ws.board  # doctest: +NORMALIZE_WHITESPACE
186
        [['c', None, None],
187
        ['a', 'a', None],
188
        ['t', 't', None]]
189
        """
190
        word_length = len(word)
191
        # Attempt to insert the word into each row and when successful, exit
192
        for row in rows:
193
            # Check if there is space below the row to fit in the word
194
            if word_length + row > self.height:
195
                continue
196

197
            # Attempt to insert the word into each column
198
            for col in cols:
199
                # Only check to be made here is if there are existing letters
200
                # below the column that will be overwritten
201
                letters_below = [self.board[row + i][col] for i in range(word_length)]
202
                if all(letter is None for letter in letters_below):
203
                    # Successful, insert the word south
204
                    for i in range(word_length):
205
                        self.board[row + i][col] = word[i]
206
                    return
207

208
    def insert_southwest(self, word: str, rows: list[int], cols: list[int]) -> None:
209
        """
210
        >>> ws = WordSearch(WORDS, 3, 3)
211
        >>> ws.insert_southwest("cat", [0], [2])
212
        >>> ws.board  # doctest: +NORMALIZE_WHITESPACE
213
        [[None, None, 'c'],
214
        [None, 'a', None],
215
        ['t', None, None]]
216
        >>> ws.insert_southwest("at", [1, 2], [2, 1, 0])
217
        >>> ws.board  # doctest: +NORMALIZE_WHITESPACE
218
        [[None, None, 'c'],
219
        [None, 'a', 'a'],
220
        ['t', 't', None]]
221
        """
222
        word_length = len(word)
223
        # Attempt to insert the word into each row and when successful, exit
224
        for row in rows:
225
            # Check if there is space for the word below the row
226
            if word_length + row > self.height:
227
                continue
228

229
            # Attempt to insert the word into each column
230
            for col in cols:
231
                # Check if there is space to the left of the word as well as below
232
                if word_length > col + 1:
233
                    continue
234

235
                # Check if there are existing letters
236
                # to the right of the column that will be overwritten
237
                letters_diagonal_left = [
238
                    self.board[row + i][col - i] for i in range(word_length)
239
                ]
240
                if all(letter is None for letter in letters_diagonal_left):
241
                    # Successful, insert the word southwest
242
                    for i in range(word_length):
243
                        self.board[row + i][col - i] = word[i]
244
                    return
245

246
    def insert_west(self, word: str, rows: list[int], cols: list[int]) -> None:
247
        """
248
        >>> ws = WordSearch(WORDS, 3, 3)
249
        >>> ws.insert_west("cat", [1], [2])
250
        >>> ws.board  # doctest: +NORMALIZE_WHITESPACE
251
        [[None, None, None],
252
        ['t', 'a', 'c'],
253
        [None, None, None]]
254
        >>> ws.insert_west("at", [1, 0], [1, 2, 0])
255
        >>> ws.board  # doctest: +NORMALIZE_WHITESPACE
256
        [['t', 'a', None],
257
        ['t', 'a', 'c'],
258
        [None, None, None]]
259
        """
260
        word_length = len(word)
261
        # Attempt to insert the word into each row and when successful, exit
262
        for row in rows:
263
            # Attempt to insert the word into each column
264
            for col in cols:
265
                # Check if there is space to the left of the word
266
                if word_length > col + 1:
267
                    continue
268

269
                # Check if there are existing letters
270
                # to the left of the column that will be overwritten
271
                letters_left = [self.board[row][col - i] for i in range(word_length)]
272
                if all(letter is None for letter in letters_left):
273
                    # Successful, insert the word west
274
                    for i in range(word_length):
275
                        self.board[row][col - i] = word[i]
276
                    return
277

278
    def insert_northwest(self, word: str, rows: list[int], cols: list[int]) -> None:
279
        """
280
        >>> ws = WordSearch(WORDS, 3, 3)
281
        >>> ws.insert_northwest("cat", [2], [2])
282
        >>> ws.board  # doctest: +NORMALIZE_WHITESPACE
283
        [['t', None, None],
284
        [None, 'a', None],
285
        [None, None, 'c']]
286
        >>> ws.insert_northwest("at", [1, 2], [0, 1])
287
        >>> ws.board  # doctest: +NORMALIZE_WHITESPACE
288
        [['t', None, None],
289
        ['t', 'a', None],
290
        [None, 'a', 'c']]
291
        """
292
        word_length = len(word)
293
        # Attempt to insert the word into each row and when successful, exit
294
        for row in rows:
295
            # Check if there is space for the word above the row
296
            if word_length > row + 1:
297
                continue
298

299
            # Attempt to insert the word into each column
300
            for col in cols:
301
                # Check if there is space to the left of the word as well as above
302
                if word_length > col + 1:
303
                    continue
304

305
                # Check if there are existing letters
306
                # to the right of the column that will be overwritten
307
                letters_diagonal_left = [
308
                    self.board[row - i][col - i] for i in range(word_length)
309
                ]
310
                if all(letter is None for letter in letters_diagonal_left):
311
                    # Successful, insert the word northwest
312
                    for i in range(word_length):
313
                        self.board[row - i][col - i] = word[i]
314
                    return
315

316
    def generate_board(self) -> None:
317
        """
318
        Generates a board with a random direction for each word.
319

320
        >>> wt = WordSearch(WORDS, WIDTH, HEIGHT)
321
        >>> wt.generate_board()
322
        >>> len(list(filter(lambda word: word is not None, sum(wt.board, start=[])))
323
        ... ) == sum(map(lambda word: len(word), WORDS))
324
        True
325
        """
326
        directions = (
327
            self.insert_north,
328
            self.insert_northeast,
329
            self.insert_east,
330
            self.insert_southeast,
331
            self.insert_south,
332
            self.insert_southwest,
333
            self.insert_west,
334
            self.insert_northwest,
335
        )
336
        for word in self.words:
337
            # Shuffle the row order and column order that is used when brute forcing
338
            # the insertion of the word
339
            rows, cols = list(range(self.height)), list(range(self.width))
340
            shuffle(rows)
341
            shuffle(cols)
342

343
            # Insert the word via the direction
344
            choice(directions)(word, rows, cols)
345

346

347
def visualise_word_search(
348
    board: list[list[str | None]] | None = None, *, add_fake_chars: bool = True
349
) -> None:
350
    """
351
    Graphically displays the word search in the terminal.
352

353
    >>> ws = WordSearch(WORDS, 5, 5)
354
    >>> ws.insert_north("cat", [4], [4])
355
    >>> visualise_word_search(
356
    ...     ws.board, add_fake_chars=False)  # doctest: +NORMALIZE_WHITESPACE
357
    # # # # #
358
    # # # # #
359
    # # # # t
360
    # # # # a
361
    # # # # c
362
    >>> ws.insert_northeast("snake", [4], [4, 3, 2, 1, 0])
363
    >>> visualise_word_search(
364
    ...     ws.board, add_fake_chars=False)  # doctest: +NORMALIZE_WHITESPACE
365
    # # # # e
366
    # # # k #
367
    # # a # t
368
    # n # # a
369
    s # # # c
370
    """
371
    if board is None:
372
        word_search = WordSearch(WORDS, WIDTH, HEIGHT)
373
        word_search.generate_board()
374
        board = word_search.board
375

376
    result = ""
377
    for row in range(len(board)):
378
        for col in range(len(board[0])):
379
            character = "#"
380
            if (letter := board[row][col]) is not None:
381
                character = letter
382
            # Empty char, so add a fake char
383
            elif add_fake_chars:
384
                character = chr(randint(97, 122))
385
            result += f"{character} "
386
        result += "\n"
387
    print(result, end="")
388

389

390
if __name__ == "__main__":
391
    import doctest
392

393
    doctest.testmod()
394

395
    visualise_word_search()
396