cs20ps23as08: Longest Grid Word

Goals

Practice with recursion.
Implement another search algorithm.

Prerequisites

This assignment requires familiarity with the lecture materials presented in class through week 08.

Background

The animations below show in yellow the longest word found in a word-search grid by traveling any non-overlapping sequence of adjacent grid squares in any horizontal, vertical, or diagonal direction. The words and grid letters are in English or Spanish.

<html> <style> @keyframes fadeInLoad {

  from {
      opacity:0;
  }
  to {
      opacity:1;
  }

} .grid {

font-family: monospace;
text-align: center;

} .gridtable {

margin-left: auto;
margin-right: auto;

} .path {

font-weight: bold;

} </style> <center>

</center> <script> let gridFileNames = []; let longestWords = []; let paths = [];

async function loadGridData() {

return await window.fetch('/datasets/random_grids/random-grid_paths', {
  method: 'get'
}).then(response =>
  response.text()
).then(text => {
  lines = text.trim().split('\n');
  for (let i = 0; i < lines.length; ++i) {
    let text = lines[i];
    // ['random-grid-03', 'HEPT', [[0, 1], [1, 2], [2, 2]]]
    let tokens = eval(text);
    gridFileNames.push(tokens[0]);
    longestWords.push(tokens[1]);
    paths.push(tokens[2]);
  }
}).catch(err => {
  console.log('Something bad happened: ' + err);
});

}

let gridIndex = 0; function displayNextGrid() {

let div = document.getElementById('grid');
while (div.firstChild)
  div.removeChild(div.firstChild);
let grid = document.createElement('table');
grid.classList.add('gridtable');
let gridFileName = gridFileNames[gridIndex];
let longestWord = longestWords[gridIndex];
let path = paths[gridIndex];
window.fetch(`/datasets/random_grids/${gridFileName}`, {
  method: 'get'
}).then(response =>
  response.text()
).then(text => {
  let lines = text.split('\n');
  grid.style.fontSize = `${20 / lines[0].length}em`;
  for (let i = 0; i < lines.length; ++i) {
    let line = lines[i].split('');
    let row = document.createElement('tr');
    for (let j = 0; j < line.length; ++j) {
      let col = document.createElement('td');
      col.textContent = line[j];
      for (let k = 0; k < path.length; ++k) {
        if (path[k][0] == i && path[k][1] == j) {
          let hue = Math.round(k / (path.length - 1) * 270);
          col.classList.add('path');
          col.setAttribute('style', `animation: fadeInLoad ${k + 1}s; background-color: hsl(${hue}, 60%, 75%)`);
        }
      }
      row.appendChild(col);
    }
    grid.appendChild(row);
  }
}).catch(err => {
  console.log('Something bad happened: ' + err);
});
div.appendChild(grid);
div = document.getElementById('longest-word');
while (div.firstChild)
  div.removeChild(div.firstChild);
for (let i = 0; i < longestWord.length; ++i) {
  let hue = Math.round(i / (path.length - 1) * 270);
  let letter = document.createElement('span');
  letter.setAttribute('style', `animation: fadeInLoad ${i + 1}s; background-color: hsl(${hue}, 60%, 75%)`);
  letter.textContent = longestWord[i];
  div.appendChild(letter);
}

window.setTimeout(displayNextGrid, longestWords[gridIndex].length * 1000 + 1000);
gridIndex = (gridIndex + 1) % paths.length;

}

loadGridData().then(result ⇒ { displayNextGrid(); }); </script> </html>

Assignment

You shall implement a class named LongestGridWord in a module named longest_grid_word which offers two methods:

A constructor that expects a path to a spell-checking dictionary file as an argument. The contents of this file will consist of a case-insensitive set of the possible words to find in a word-search grid.
A method named longest_word that expects a word-search grid as an argument (as a sequence of string sequences) and recursively determines the longest word found in the grid by traveling any non-overlapping sequence of adjacent grid squares in any horizontal, vertical, or diagonal direction, as demonstrated in the animations above.

Make sure not to perform unnecessary work, and to take advantage of Python's built-in types appropriately! Your code will be expected to run within a reasonable time limit based on these decisions.

Starter Code and Sample Executable

Feel free to use the following starter code. Note that the longest_word method will need to call another helper method that is actually recursive. Normally in Python you would implement this as a nested method as in the memoized-recursion example from lecture, but you may do as you wish. There may be multiple words tied for longest. In such a case, may return any of them.

You will want to call your recursive method once for each square in the grid, beginning the process of finding the longest word that starts at that point.

Sample executable cs20p_longest_grid_word is also available on the server, and you can use it to check your code against a given grid and dictionary file, e.g.:

$ cat /srv/datasets/random_grids/random-grid-20
TKSNYLESETRURCEOULEJ
SENMCIRECBLBOVAUEONR
TQISIILDSNOTCRIINIBT
SLRYAPIOIAYSOAOSALOS
AAUDCINPMHLOLZOWGONI
EPHUCVERSAAPFTOLNYQE
NIRSEYPIMBSICEEEENHW
PUIVDECOLMELVFEESTIS
VUGSWSVEGEOEURLRLBZL
WCDENEAREAOIYOAALRTO
XGNRCSCRHEHNLIANLSKS
ILNAGAOOTTCABSPTRSOD
AEOIIRAOLOESSATLSTNU
OHINOSSISAAILIERSSSB
IRIMREAOOOGLSENEBIDG
HSDEIKFHADSAASOISDXL
EUNRINLOCSFRNARONLII
DCOSTCIPASLRYNUNNILN
STCSMOAIRIEOEAOCDOTT
SNAOCBLPEOANASINAOYC
 
$ cs20p_longest_grid_word /usr/share/dict/words /srv/datasets/random_grids/random-grid-20 
HALISTERESIS
IMPERISHABLE
PERISCOPICAL

""" Recursively searching a word-search grid for the longest "snake" word. """
from collections.abc import Sequence
 
 
class LongestGridWord:
  """ Offers a recursive search for the longest word in a word-search grid. """
 
  def __init__(self, word_list_file_path: str):
    """
    Constructs a LongestGridWord object prepared to search grids containing words from the given
    word-dictionary file. The file is assumed to be in class spell-checking dicitonary format,
    i.e. one word per line.
    """
    pass # TODO
 
  def longest_word(self, grid: Sequence[Sequence[str]]) -> str:
    """
    Recursively determines the longest word found in a grid by traveling any non-overlapping
    sequence of adjacent grid squares in any horizontal, vertical, or diagonal direction.
    The grid is assumed to consist of uppercase letters, and to be square.
    """
    pass # TODO

Leaderboard

As submissions are received, this leaderboard will be updated with the top-performing solutions that are fully functional in at least 90% of tests.

<html>

<table> <thead> <tr><th>Rank</th><th>Test Time</th><th>Memory Usage (kB)</th><th>SLOC (lines)</th><th>User</th></tr> </thead> <tbody id=“leaderboard-table”> </tbody> </table> <script> function updateLeaderboard() { window.fetch('/~turnin/leaderboard-cs20ps23as08.txt', {

method: 'get'

}).then(response ⇒

response.text()

).then(text ⇒ {

let updated = document.getElementById('leaderboard-updated');
updated.innerText = `(Last updated: ${new Date()})`;
let lines = text.split('\n');
let table = document.getElementById('leaderboard-table');
while (table.firstChild)
  table.removeChild(table.firstChild);
for (let i = 0; i < lines.length; ++i) {
  let tokens = lines[i].split(' ').filter(token => token.length > 0);
  if (tokens.length < 2)
    continue;
  let tdRank = document.createElement('td');
  tdRank.textContent = i + 1;
  let tdTime = document.createElement('td');
  tdTime.textContent = Number(tokens[0]).toFixed(4);
  let tdMemUsage = document.createElement('td');
  tdMemUsage.textContent = tokens[1];
  let tdSloc = document.createElement('td');
  tdSloc.textContent = tokens[2];
  let tdUser = document.createElement('td');
  let userLink = document.createElement('a');
  userLink.href = `/~${tokens[3]}/`;
  userLink.target = '_blank';
  userLink.textContent = tokens[3];
  tdUser.appendChild(userLink);
  let tr = document.createElement('tr');
  tr.appendChild(tdRank);
  tr.appendChild(tdTime);
  tr.appendChild(tdMemUsage);
  tr.appendChild(tdSloc);
  tr.appendChild(tdUser);
  table.appendChild(tr);
}

}).catch(err ⇒ {

console.log('Something bad happened: ' + err);

});

window.setTimeout(updateLeaderboard, 60000);

} updateLeaderboard(); </script> </html>

Submission

Submit longest_grid_word.py via turnin.

Feedback Robot

This project has a feedback robot that will run some tests on your submission and provide you with a feedback report via email within roughly one minute.

Please read the feedback carefully.

Due Date and Point Value

Due at 23:59:59 on the date listed on the syllabus.

Assignment 08 is worth 60 points of extra credit.

Possible point values per category:
---------------------------------------
Properly functioning class           60
Possible deductions:
  Style and practices            10–20%
Possible extra credit:
  Submission via Git                 5%
---------------------------------------

portfolio

Table of Contents