====== 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 [[:lecture materials/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.

----- ====== 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.
RankTest TimeMemory Usage (kB)SLOC (lines)User
----- ====== Submission ====== Submit ''longest_grid_word.py'' via [[info:turnin]]. {{https://jeff.cis.cabrillo.edu/images/feedback-robot.png?nolink }} //**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|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% ---------------------------------------