I created a Trie for my assignment and I have a problem creating a list that includes autocompleted prefix strings and how many times they are inserted in my Trie. Please do not change my functions arguments, because of the test cases, we are strictly to abide by to stay the same. I am adding an example for my problem and I will add the test cases to check the code. This is the third time I am posting this question if you can not solve it please do not act like you are solving it. TY

This is my code: (When I pasted it here it creates some indentation problem please do not think that my code does not work because of indentation)

import sys

# We will use a class called my trie node class TrieRoot: # Initialize some fields def __init__(self,isRootNode): #The initialization below is just a suggestion. #Change it as you will. # But do not change the signature of the constructor. self.isRoot = isRootNode self.isWordEnd = False # is this node a word ending node self.isRoot = False # is this a root node self.children = {} # Dictionary mapping each character from a-z to # the child node if any corresponding to that character. self.count = 0 class MyTrieNode: def __init__(self,isRootNode): self.isRoot= TrieRoot(isRootNode) self.word_list = []

def addWord(self,w): assert(len(w) > 0)

# YOUR CODE HERE # If you want to create helper/auxiliary functions, please do so. current = self.isRoot for i in w: ch = i node = current.children.get(ch) if node == None: node = TrieRoot(True) current.children.update({ch:node}) current = node current.isWordEnd= True current.count +=1 def lookupWord(self,w): # Return frequency of occurrence of the word w in the trie # returns a number for the frequency and 0 if the word w does not occur.

# YOUR CODE HERE currentNode = self.isRoot for i in w: node = currentNode.children.get(i) if node == None: currentNode.count = 0 return currentNode.count currentNode= node if currentNode.isWordEnd == True: return currentNode.count else: return currentNode.count def dfs(self, node, prefix): """Depth-first traversal of the trie Args: - node: the node to start with - prefix: the current prefix, for tracing a word while traversing the trie """ if node.isWordEnd: self.output.append((prefix + node.isRoot, node.count)) for child in node.children.values(): self.dfs(child, prefix + node.isRoot) def autoComplete(self, w): """Given an input (a prefix), retrieve all words stored in the trie with that prefix, sort the words by the number of times they have been inserted """ node = self.isRoot not_found = False temp_word = '' final = [] for a in list(w): if not node.children.get(a): not_found = True break temp_word += a node = node.children[a] if not_found: return 0 elif node.isWordEnd and not node.children: return -1 self.suggestionsRec(node, temp_word) for s in self.word_list: final.append((s,self.lookupWord(s))) return final

def suggestionsRec(self, node, w): if node.isWordEnd: self.word_list.append(w) for a,n in node.children.items(): self.suggestionsRec(n, w + a)

This is the main test case:

import sys

def lookupTest(t, lstToLookup): retValue = True for (w,k) in lstToLookup: j = t.lookupWord(w) if (j != k): print('\t Lookup for word %s failed. Expected result: %d, obtained from your trie: %d '%(w,k,j)) retValue = False return retValue

def autoCompleteTest(t, stem, expResult): lst1 = sorted(t.autoComplete(stem)) lstRet = sorted(expResult) if (len(lst1) != len(lstRet)): print('\t autoComplete(\"%s\") failed'%(stem)) print('\t\t Expected: ',lstRet) print('\t\t Got: ', lst1) return False n = len(lstRet) for i in range(0,n): (expI,freqI) = lstRet[i] (gotI,freqJ) = lst1[i] if (expI != gotI or freqI != freqJ): print('autoComplete(\"%s\") failed'%(stem)) print('\t Expected: ',lstRet) print('\t Got: ', lst1 ) return False return True

def runTest(specs): try: t = MyTrieNode(True) lNum = 0 result = True spec_lines = specs.split(' ') for line in spec_lines: lNum += 1 lst = [x.strip() for x in line.split(',')] if (lst[0] == 'W'): print('\t Insert:',lst[1]) t.addWord(lst[1]) elif (lst[0] == 'L'): print('\t Lookup:', lst[1]) j = t.lookupWord(lst[1]) if (j != int(lst[2])): print('\t\t Failed --> expected : %s, got %d'%(lst[2],j)) result=False elif (lst[0] == 'A'): wrd = lst[1] rList = lst[2::] rWords = rList[0::2] print('\t Autocomplete: ',lst[1]) rNums = [int(x) for x in rList[1::2] ] retList = sorted(zip (rWords,rNums)) result = (autoCompleteTest(t,wrd, retList)) and result else: print('Error in test specification line number %d -- Unknown command spec %s'%(lNum,lst[0])) sys.exit(1) return result except IOError: print('Unable to open',fileName)

The first check:

str_spec1='''W,hello W,hello W,he W,jello W,jelly L,hello,2 L,hell,0 L,howdy,0 A,he,hello,2,he,1 A,je,jello,1,jelly,1'''

rslt = runTest(str_spec1) if (rslt): print('Test 1 PASSED') else: print('Test 1 FAILED')

The second check:

str_spec2 = '''W,hello W,how W,are W,you W,hell L,howdy,0 W,howdy W,arid W,arachnid L,orange,0 L,hello,1 L,hell,1 L,howdy,1 A,ho,howdy,1,how,1'''

rslt = runTest(str_spec2) if (rslt): print('Test 2 PASSED') else: print('Test 2 FAILED')

print(1st4) 0 0 2 Completions for "pi" are : [('pin', 1), ('ping', 1), ('pink', 1), ('pine', 1), ('pinetree', 1), ('pint', 1)] Completions for "tes" are : ['pin', 1), ('ping', 1), ('pink', 1), ('pine', 1), ('pinetree', 1), ('pint', 1), ('test', 0), ('testament', 1), ('testing', 2)]