I create a boogle game, and I need to build a function that receives in input: the letter board (list of lists), the list of legal words and an integer n.
The function must return all n-length tracks of valid words. For example n = 3 then the function must return all the paths on the three-length board which are actually valid words.
I wrote a code that returns in a particular example one route out of three routes that must be returned.
Input:
board1 = [['Q', 'O', 'Q', 'Q'],
['D', 'O', 'G', 'Q'],
['Q', 'O', 'Q', 'Q'],
['Q', 'Q', 'Q', 'Q']]
word_dict = {'DOG': True}
n = 3
board = Board(board1)
length_n_paths(3, board, word_dict)
My Output:
[((1, 0), (1, 1), (1, 2))]
Wanted Output:
[[(1, 0), (0, 1), (1, 2)], [(1, 0), (1, 1), (1, 2)], [(1, 0), (2, 1), (1, 2)]]
I used a combination, first I found all the possible combinations of letters of length n, then I went through a coordinate coordinate and checked if each coordinate is in a valid position according to the coordinate in front of it, and then I checked if the word coming out of the letter combination is a word from the word list. If so - I will return its path in a list with the other legal words paths.
my code:
direct_lst=['Up','Down','Right','Left','Up_right','Up_left','Down_right','Down_left']
class Board:
def __init__(self, board):
self.board = board
def get_board_coordinate(self):
cord_lst = []
row = len(self.board)
col = len(self.board[0])
for i in range(row):
for j in range(col):
cord_lst.append((i, j))
return cord_lst
def possible_directions(self, coordinate, next_coordinate):
y, x = coordinate
directions_funcs = {
# A dictionary that matches between a letter and the direction of the desired search
'Up': (y - 1, x),
'Down': (y 1, x),
'Right': (y, x 1),
'Left': (y, x - 1),
'Up_right': (y - 1, x 1),
'Up_left': (y - 1, x - 1),
'Down_right': (y 1, x 1),
'Down_left': (y 1, x 1)
}
it_ok = False
for direction in direct_lst:
if directions_funcs[direction] == next_coordinate:
it_ok = True
return it_ok
def is_valid_path(board, path, words):
word = board.board[path[0][0]][path[0][1]]
board_coordinates = board.get_board_coordinate()
for cord in range(len(path)-1):
if path[cord] in board_coordinates and path[cord 1] in board_coordinates:
if not board.possible_directions(path[cord], path[cord 1]):
return None
else:
word = board.board[path[cord 1][0]][path[cord 1][1]]
else:
return None
if word in set(words):
return word
import itertools
def create_dict(board, n):
new_dict = dict()
row = len(board.board)
col = len(board.board[0])
for i in range(row):
for j in range(col):
new_dict[(i, j)] = board.board[i][j]
result_list = list(map(list, itertools.combinations(new_dict.items(), n)))
return result_list
def coordinates_lst_and_str_lst(board, n):
combine = create_dict(board, n)
all_cord_dic = dict()
for lst in combine:
is_it_ok = True
cord_lst = []
str_l = ""
for i in range(n):
cord_lst.append(lst[i][0])
str_l = lst[i][1]
try:
if not board.possible_directions(lst[i][0], lst[i 1][0]):
is_it_ok = False
break
except IndexError:
break
if is_it_ok:
all_cord_dic[tuple(cord_lst)] = str_l
all_cord_dic[tuple(cord_lst)[::-1]] = str_l[::-1]
return all_cord_dic
def length_n_paths(n, board, words):
possible_words = coordinates_lst_and_str_lst(board, n)
my_dict = {key:val for key, val in possible_words.items() if val in words}
return list(my_dict.keys())
I think the problem is in the combination but I dont know how to fix it. I would be happy for any help.
CodePudding user response：
After debugging, it's apparent that the result possible_words does not contain the key (1, 0), (0, 1), (1, 2), so that explains why it's not part of the answer - so the question becomes why doesn't the call to coordinates_lst_and_str_lst() generate that tuple (and the other 'missing' one)
If you break after constructing combine in coordinates_lst_and_str_lst, you will find that [((1, 0), 'D'), ((0, 1), 'O'), ((1, 2), 'G')] is not in combine, this means coordinates_lst_and_str_lst can't find it as a solution.
So, the problem must be in create_dict, which apparently isn't creating all the legal moves.
And indeed, in create_dict, you use itertools.combinations(), which gives you all the unique combinations of n items from a collection, disregarding their order, but you care about the order.
So, you don't want itertools.combinations(new_dict.items(), n), you want itertools.permutations(new_dict.items(), n). Have a closer look at the difference between combinations and permutations (of size n).
CodePudding user response：
You said any help was welcome so I started from scratch to create this... which produces the expected answer. I made inline notes to explain what the algorithm is doing. It probably isn't the most efficient solution and has room for optimization, but it should still perform pretty well. And it should give a valid solution for any board and any number of words.
class Board:
def __init__(self, board, word_dict, n):
self.board = board
self.height = len(board)
self.width = len(board[0])
# the list of all directions possible to adjacent characters
self.adj = [(x,y) for x in [-1,0,1] for y in [-1,0,1] if (x,y) != (0,0)]
self.n = n
self.word_dict = word_dict
# list of words that are the same length as n
self.words = [i for i in self.word_dict if len(i) == n]
# list where all the valid solutions will be stored
self.results = []
def is_legal(self,r,c):
if r >= 0 and r < self.height:
if c >= 0 and c < self.width:
return True
return False
def get_combinations(self, row, col, chars, word, path):
if chars == self.n: # base case: if chars == self.n
self.results.append(path) # we have a valid solution so append to results
return #return
for y,x in self.adj: # otherwise iterate through adjacent indeces
r, c = row y, col x # adj space
# if the adjacent space exists on board and isn't already
# in the list of visited spaces
if self.is_legal(r,c) and (r,c) not in path:
if self.board[r][c] == word[chars]: # if adj space contains
# the next character in
# the word
# add it to the current path, and recursively check all
# of the adjacent values for the matching space
self.get_combinations(r,c,chars 1,word,path [(r,c)])
def solve(self):
for i, row in enumerate(self.board): # for each row
for j, col in enumerate(row): # for each character in row
for word in self.words: # for each word with length of n
if word[0] == col: # if character is the same as...
# the first of word
# get all the path solutions for that word from this
# position on the board.
self.get_combinations(i, j, 1, word, [(i,j)])
board1 = [['Q', 'O', 'Q', 'Q'],
['D', 'O', 'G', 'Q'],
['Q', 'O', 'Q', 'Q'],
['Q', 'Q', 'Q', 'Q']]
word_dict = {'DOG': True}
n = 3
board = Board(board1, word_dict, n)
board.solve()
print(board.results)
CodePudding user response：
0
I have a laravel project using SESSION_DRIVER=database, so the session persist in the database, can I/should I use session()->put(), session()->has(), session()->forget() etc in my api controllers?