Programming question - Boggle
Jump to navigation
Jump to search
About
NOTE: This page is a daughter page of: Programming questions and Python
So I heard once that some of the best open-ended programming questions are explained in very few words. An amazing example they gave would be just two words:
- "Program Boggle"
Of course, this does assume you know the game boggle.
PROBLEM: Boggle
Create a Python program program that finds valid scores in a boggle grid.
SOLUTION: In Python3
Here's what I came up with:
<syntaxhighlight lang="python">
# Program a game of boggle in python.
# Here I allow a custom size grid, a custom set of valid words,
# and a custom alphabet letter frequency.
#
# BOARD:
#
# | A | S | A | A |
# | S | B | T | A |
# | A | T | C | S |
# | C | A | S | S |
#
# ... has the words: [as, sat, at, ass, cat].
from typing import Any
from random import randrange, seed
NUM_ROWS = 4 # TODO(noske): Set to 4.
NUM_COLS = 4 # TODO(noske): Set to 4.
# Alphabet with more common letters more frequent (dupes are deliberate).
ALPHABET_FREQ = ['a', 'a', 'a', 'b', 'c', 't', 's', 's'] # TODO(noske): Whole alphabet.
VALID_WORDS = ['at', 'as', 'ass', 'bat', 'bats', 'bass', 'cat', 'cats', 'sat', 'sass', 'tab', 'tabs']
## TRIE STRUCTURE:
class TrieNode:
"""A node in the trie representing a letter in a valid word."""
def __init__(self, letter: str, len: int):
self.letter = letter
self.is_word = False # Is the last letter in a valid word.
self.children = []
# TODO(noske): Optimzation, this array would be left empty unless needed.
for i in range(len):
self.children.append(None)
def child(self, idx: int) -> Any:
"""Get the child at the given index."""
return self.children[idx]
def set_child(self, idx: int, new_node: Any) -> None:
"""Sets the child at the given index."""
self.children[idx] = new_node
class Trie:
"""A trie containing all valid words."""
def __init__(self, valid_words: list[str], alphabet_freq: list[str]):
# Setup dict to map letters to index.
self.alphabet = []
self.alphabet_idx_dict = {}
for i in range(len(alphabet_freq)):
char = alphabet_freq[i]
if char not in self.alphabet_idx_dict:
self.alphabet.append(char)
self.alphabet_idx_dict[char] = len(self.alphabet) - 1
alphabet_len = len(self.alphabet)
# Setup trie itself.
self.root = TrieNode('-', alphabet_len) # The root node doesn't have a letter.
for word in valid_words:
curr: TrieNode = self.root
for i in range(len(word)):
letter = word[i]
letter_idx = self.alphabet_to_idx(letter)
if curr.child(letter_idx) == None:
new_node = TrieNode(letter, alphabet_len)
curr.set_child(letter_idx, new_node)
trie_node = curr.child(letter_idx)
if i > 0 and i == len(word) - 1: # If last letter - mark as complete word.
trie_node.is_word = True
curr = trie_node
def alphabet_to_idx(self, letter: str) -> int:
return self.alphabet_idx_dict[letter]
def is_valid_word(self, letters) -> (bool, bool):
"""Determines if the given word is in the trie.
Args:
letter: The letters to check.
Return:
is_word: Is a complete word.
is_prefix: May not be a word, but forms prefix of one or more words.
"""
node = self.root
for letter in letters:
letter_idx = self.alphabet_to_idx(letter)
if node.child(letter_idx) == None:
return False, False
node = node.child(letter_idx)
return node.is_word, True
def to_string(self) -> str:
return 'Trie: ' + self.to_string_recursive(self.root)
def to_string_recursive(self, trie_node: TrieNode) -> str:
if trie_node == None:
return ''
children_str = ''
for child in trie_node.children:
children_str += self.to_string_recursive(child)
if children_str:
children_str = '(' + children_str + ')'
return trie_node.letter + children_str
## BOGOGLE GRID:
class Cell:
"""Boggle grid cell"""
def __init__(self):
self.letter = '-'
self.visited = False
self.neighbors = [] # Cells that this cell is connected to.
def set_random_letter(self):
"""Sets to a random letter."""
rand_idx = randrange(0, len(ALPHABET_FREQ))
self.letter = ALPHABET_FREQ[rand_idx]
# To get even letter distribution: chr(ord('A') + rand_int)
def neighbors_to_string(self) -> str:
return_str = ''
for i in range(len(self.neighbors)):
return_str += self.neighbors[i].letter
return '(' + return_str + ')'
class Boggle:
def __init__(self):
"""Initialize the boggle grid (usually a grid of 4x4 cells)."""
seed()
self.cells = [[Cell() for y in range(NUM_COLS)] for x in range(NUM_ROWS)]
self.trie = None
self.found_words = {}
c = self.cells
for y in range (0, NUM_ROWS):
for x in range (0, NUM_COLS):
if y > 0:
c[y][x].neighbors.append( c[y-1][x] )
if y < NUM_ROWS - 1:
c[y][x].neighbors.append( c[y+1][x] )
if x > 0:
c[y][x].neighbors.append( c[y][x-1] )
if x < NUM_COLS - 1:
c[y][x].neighbors.append( c[y][x+1] )
# TODO(anoske): Call `find_words()` - if the grid has no valid words
# then is not point showing the user the grid.
def cell(self, x, y) -> Cell:
return self.cells[y][x]
def render_board(self, list_neighbors: bool = False) -> None:
for y in range (0, NUM_ROWS):
line = ' |'
for x in range (0, NUM_COLS):
cell = self.cell(x, y)
if list_neighbors:
line += cell.neighbors_to_string().lower()
line += ' ' + cell.letter.upper() + ' |'
print(line)
print('\n')
def shuffle_board(self) -> None:
"""Randomly picks letters for each grid cell.
Note: The set_random_letter function just randomly pics from an alphabet,
whereas a more realistic representation of the original game would have
6-sided dice that are shuffled in order, then rolled for each cell.
"""
for y in range (0, NUM_ROWS):
for x in range (0, NUM_COLS):
self.cell(x, y).set_random_letter()
self.found_words = {}
def reset_visited(self) -> None:
for y in range (0, NUM_ROWS):
for x in range (0, NUM_COLS):
self.cell(x, y).visited = False
def find_words(self, trie: Trie) -> None:
"""Finds words and prints them."""
# Lazy initialize tree:
if self.trie == None:
self.trie = trie
# Iterate every pathway of the board and find real words:
self.found_words = {} # Found words and frequency.
for y in range (0, NUM_ROWS):
for x in range (0, NUM_COLS):
self.reset_visited()
cell = self.cell(x, y)
new_words = self.recursive_find_word(cell, '')
# self.found_words['bat'] = 1
# self.found_words['bat'] += 1
# self.found_words['cat'] = 1
# Print results:
for key, value in self.found_words.items():
print('- ', key, ' \t', value)
print('\n')
def add_found_word(self, word: str) -> None:
if word not in self.found_words:
self.found_words[word] = 0
self.found_words[word] += 1
def recursive_find_word(self, cell: Cell, letters: str) -> None:
"""Look recursively for any words connected to this cell.
Args:
cell: Current cell for this call.
# trie_node: Current trie node we are up to for finding matching words.
letters: Currrent letters to get to this point.
Returns:
matching words.
"""
# Base case:
# TODO(anoske): Pass in trie_node to be more efficient.
if cell.visited == True:
return
# Determine if we just found a word:
letter = cell.letter
letters += letter
is_valid_word, is_prefix = self.trie.is_valid_word(letters)
if is_valid_word:
self.add_found_word(letters)
if not is_prefix: # Exit early.
return
# Recursion case:
cell.visited = True # So we don't loop around and visit again.
for neighbor_cell in cell.neighbors:
self.recursive_find_word(neighbor_cell, letters)
cell.visited = False
return
if __name__ == '__main__':
# Setup trie:
trie = Trie(VALID_WORDS, ALPHABET_FREQ)
print('TRIE:\n', trie.to_string(), '\n')
# Test trie:
# print('... test "bat": ', trie.is_valid_word('bat')) # Test trie.
# print('... test "ba": ', trie.is_valid_word('ba')) # Test trie.
# print('... test "batttab": ', trie.is_valid_word('batttab')) # Test trie.
# Setup boggle board:
boggle = Boggle()
boggle.shuffle_board()
print('BOARD:')
boggle.render_board()
print('FOUND WORDS:')
boggle.find_words(trie)
Output:
TRIE:
Trie: -(a(ts(s))b(a(t(s)s(s)))c(a(t(s)))t(a(b(s)))s(a(ts(s))))
BOARD:
| A | S | A | A |
| S | B | T | A |
| A | T | C | S |
| C | A | S | S |
FOUND WORDS:
- as 6
- sat 4
- at 4
- ass 2
- cat 2