from math import inf, log from typing import List, Optional from utils import max_word_length, is_valid, word_prob # Part A: Naive reconstruction def naive_reconstruct(document: str) -> Optional[str]: """ Finds any valid reconstruction of a string with no whitespace. :param document: A nonempty string with no whitespace. :return: A reconstruction of the string, with spaces (no added punctuation), or None if it does not form a sequence of valid dictionary words. """ if len(document.split()) > 1: raise ValueError('Document must not contain any whitespace.') # todo def backtrack(document: str, indices: List[Optional[int]]) -> str: """ :param document: A nonempty string of n letters, stripped of all whitespace and punctuation. :param indices: A list of length (n+1) used for backtracking. If the first i characters of document form a valid sequence of words, then indices [i] contains the starting index of the last word. Otherwise, if document[:i+1] is invalid, indices[i] contains None. If document[:i+1] forms a valid sequence of words, then indices[i] contains the starting index of the last word, or None if document[:i+1] is invalid. :return: The reconstructed document, with spaces between words. >>> backtrack("xylophoneplayer", [None, None, None, None, 0, None, None, 4, 4, 0, 7, 8, 9, 9, 9, 9]) 'xylophone player' """ assert indices[-1] is not None # todo

Given a string S[1..n] with no whitespace, your goal is to reconstruct the string by splitting it into valid words separated by spaces (if possible). For example, "it was the best of times" is a reconstruction of "itwasthebestoftimes". Words may also contain punctuation: "I'llhavewhatshe'shaving" can be reconstructed as "I'll have what she's having" . Some strings cannot be reconstructed, such as "qwertyuiop". Install dependencies We need an English dictionary, so install the wordfreq library by running pip install wordfreq (Windows) or pip3 install wordfreq (Mac/Linux). Part A The first part of your assignment is to complete the naive_reconstruct function in hw3.py, which should take a string with no whitespace and return a reconstruction if possible, or None if not. Your algorithm should run in O(nk), where k is the length of the longest word in the dictionary. This is provided as max_word_length. Use the provided is_valid function to check if a word is in the dictionary. This will ignore whitespace and leading / trailing punctuation. >>> is_valid("the") True >>> is_valid("end.") True >>> is_valid("en.d") False >>> is_valid("zxcvbnm") False >>> is_valid("not a word") Traceback (most recent call last): ValueError: Invalid argument: 'not a word Words must not contain whitespace A second signature is provided for backtrack, a helper function which uses information about the starting positions of words in the string to reconstruct the document. Implementing this function is not required - you may also define your own backtracking function, or include all backtracking code in your reconstruct function - but you may find it helpful. Note: Certain strings may become ambiguous when the spaces are removed. For example, "listentoyourheart" can be reconstructed in several ways, including "listen to your heart" and "listen toy our he art" . For this part of the problem, don't worry about finding the "correct" reconstruction - any sequence of dictionary words is fine. Given a string S[1..n] with no whitespace, your goal is to reconstruct the string by splitting it into valid words separated by spaces (if possible). For example, "it was the best of times" is a reconstruction of "itwasthebestoftimes". Words may also contain punctuation: "I'llhavewhatshe'shaving" can be reconstructed as "I'll have what she's having" . Some strings cannot be reconstructed, such as "qwertyuiop". Install dependencies We need an English dictionary, so install the wordfreq library by running pip install wordfreq (Windows) or pip3 install wordfreq (Mac/Linux). Part A The first part of your assignment is to complete the naive_reconstruct function in hw3.py, which should take a string with no whitespace and return a reconstruction if possible, or None if not. Your algorithm should run in O(nk), where k is the length of the longest word in the dictionary. This is provided as max_word_length. Use the provided is_valid function to check if a word is in the dictionary. This will ignore whitespace and leading / trailing punctuation. >>> is_valid("the") True >>> is_valid("end.") True >>> is_valid("en.d") False >>> is_valid("zxcvbnm") False >>> is_valid("not a word") Traceback (most recent call last): ValueError: Invalid argument: 'not a word Words must not contain whitespace A second signature is provided for backtrack, a helper function which uses information about the starting positions of words in the string to reconstruct the document. Implementing this function is not required - you may also define your own backtracking function, or include all backtracking code in your reconstruct function - but you may find it helpful. Note: Certain strings may become ambiguous when the spaces are removed. For example, "listentoyourheart" can be reconstructed in several ways, including "listen to your heart" and "listen toy our he art" . For this part of the problem, don't worry about finding the "correct" reconstruction - any sequence of dictionary words is fine