Programming question - Boggle

From NoskeWiki
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


See Also