Instructions
Requirements and Specifications
Source Code
CURSOR
import random
class Cursor:
"""
This class defines a cursor, which is used to iterate through the grid
The cursor will store the index of the current position (row, column( and also
will have the the values of the direction in which the word will be stored in the grid
"""
def __init__(self, row, column, dirr, dirc):
self.row = row
self.column = column
self.dir_row = dirr
self.dir_col = dirc
if self.dir_row == 0 and self.dir_col == 0:
self.dir_col = 1
def step(self):
"""
Given the current position of the cursor defined by row and column, advance one step
in the direction of the cursor (to left, right, up, down, diagonal, etc)
:param steps:
:return: None
"""
self.column += self.dir_col
self.row += self.dir_row
def __str__(self):
"""
Print info of the cursor about the current position and direction
:return: None
"""
return f"[{self.row} {self.dir_row} {self.column} {self.dir_column}]"
GRID
import numpy as np
from cursor import *
import string
class Grid:
"""
This class will define the grid of letters. This will contain the Alphabet Soup
"""
def __init__(self, N):
# First, create a list of lists that represents the grid
# This list of lists is a matrix of size NxN filled with empty spaces
self.N = N # size of the grid
self.grid = np.array([' ']* N * N).reshape((N,N)) # initial grid
self.free_cells = N*N # number of free cells
self.words = [] # store the words in the grid
self.words_hints = [] # store the info about words added into the grid (position and direction(
def __getitem__(self, cursor: Cursor):
"""
Override the getitem method
:param cursor: Cursor object that contaons the row and position
:return:
"""
if self.valid(cursor):
return self.grid[cursor.row, cursor.column]
else:
return ' '
def __setitem__(self, cursor: Cursor, value):
"""
Override the set item method
:param cursor: Cursor object that contains the row and position
:param value: Value to be set
:return:
"""
if self.valid(cursor):
if self.grid[cursor.row, cursor.column] == ' ':
self.free_cells -= 1
self.grid[cursor.row, cursor.column] = value
def valid(self, cursor):
"""
Check if the position of the given cursor is inside the boundaries
:return: Value in the grid or ''
"""
if 0 <= cursor.row < self.N and 0 <= cursor.column < self.N:
return True
else:
return False
def put(self, word):
"""
This function will put the words in a random direction and position inside the grid
:param word: Word in str
:return: None
"""
directions = [0, 1] # Define the possitlbe directions for x and y
dir_row = directions[random.randint(0,1)] # Pick the y direction
dir_col = directions[random.randint(0,1)] # pick the x direction
reverse = False # Variable that tells if the word must be reversed or not
"""
The reverse variable is used so that the word is put reversed in the grid
For example, if we have the word 'shoe' and we have to put it in the grid in the ...
... direction left->right, then we just put the word 'shoe'
But if we have to put the word in the direction right->left, then it is the same
as putting the word in the direction left->right but instead of putting 'shoe', we put 'eohs'
"""
"""
The following lines of code are used to determine the boundaries of the position
If we put a word in direction left->right, we need to pick an starting poition x,y such that
the word do not goes outside the grid. The same happens if the direction is top->bottom, diagonal, etc
"""
if dir_col == 1 and dir_row == 0: # left to right
row, col = random.randint(0, self.N-1), random.randint(0, self.N-len(word))
elif dir_col == 0 and dir_row == 1: # top to bottom
row, col =random.randint(0, self.N-len(word)), random.randint(0, self.N-1)
elif dir_col == 1 and dir_row == 1: # diagonal top-left to bottom-right
row, col = random.randint(0, self.N - len(word)), random.randint(0, self.N - len(word))
elif dir_col == 0 and dir_row == 0:
dir_col = 1
row, col = random.randint(0, self.N - len(word)), random.randint(0, self.N - 1)
# Generate a random between 0 and 1 to chose if the word is reversed
if random.randint(0, 1) == 1:
reverse = True
# Create the cursos
cursor = Cursor(row, col, dir_row, dir_col)
word_len = len(word)
orig_word = word # original word without being reversed
if reverse:
word = word[::-1]
remaining = word_len
for index in range(word_len): # iterate through the characters in the word
if self[cursor] == ' ' or self[cursor] == word[index]: # if the current position is empty, then put the letter there
self[cursor] = word[index]
remaining -= 1
cursor.step() # advance one position
if remaining == 0: # The word was put in the grid successfully
self.words_hints.append((row,col, cursor.dir_row, cursor.dir_col, orig_word))
self.words.append(orig_word)
return True
def fill_rest(self):
"""
Once the words have been put, then fill the rest with random letters
:return:
"""
for row in range(self.N):
for col in range(self.N):
if self.grid[row,col] == ' ':
self.grid[row, col] = random.choice(string.ascii_lowercase)
def search(self):
"""
This function will take the words in the list 'words' and search them in the grid.
The function will then return a list of tuples, where each tuple will contain
the starting position in the grid, the direction to follow and the word
:return: list of tuples
"""
words_found = []
for word in self.words: # iterate through word
found = False # Variable to know if the word was found
# First, start search from left to right or right to left
for row in range(self.N):
found = False
idx = 0
for col in range(0, self.N-len(word)+1):
option = self.grid[row, col:col+len(word)]
w = ''.join(option)
w_rev = ''.join(option[::-1])
if word == w or word == w_rev: # we found the word
dir = (1,0)
x = col
y = row
if word == w_rev:
dir = (-1, 0)
x += len(word)-1
words_found.append((y,x, dir[0], dir[1], word))
found = True
break
if found:
break
if found: # The word has been found, then continue with next word
continue
# Now, top to bottom
for row in range(0, self.N-len(word)+1):
found = False
idx = 0
for col in range(0, self.N):
option = self.grid[row:row+len(word), col]
w = ''.join(option)
w_rev = ''.join(option[::-1])
if word == w or word == w_rev: # we found the word
dir = (0, 1)
x = col
y = row
if word == w_rev:
dir = (0, -1)
y += len(word)-1
words_found.append((x, y, dir[0], dir[1], word))
found = True
break
if found:
break
if found: # The word has been found, then continue with next word
continue
# Now, diagonal top-left to bottom-right
for row in range(0, self.N-len(word)+1):
for col in range(0, self.N-len(word)+1):
w = ""
for i in range(len(word)):
w += self.grid[row+i, col+i]
w_rev = w[::-1]
if word == w or word == w_rev: # we found the word
dir = (1, 1)
x = col
y = row
if word == w_rev:
dir = (-1, -1)
x += len(word)-1
y += len(word)-1
words_found.append((x, y, dir[0], dir[1], word))
found = True
break
if found:
break
if found:
break
if found: # The word has been found, then continue with next word
continue
# Now, diagonal bottom-left to top-right
for row in range(self.N-1, self.N-len(word)-2, -1):
for col in range(0, self.N - len(word) + 1):
w = ""
for i in range(len(word)):
w += self.grid[row-i, col + i]
w_rev = w[::-1]
if word == w or word == w_rev: # we found the word
dir = (-1, -1)
x = col
y = row
if word == w_rev:
dir = (1, 1)
x -= len(word)+1
y -= len(word)+1
words_found.append((x, y, dir[0], dir[1], word))
found = True
break
if found:
break
if found:
break
if found: # The word has been found, then continue with next word
continue
return words_found
def __str__(self):
ret = ""
for i in range(self.N):
ret += f"{' '.join(self.grid[i].tolist())}\n"
return ret