CODEWITHSUNDEEP
pythondictionarysetmaxdepth-first-search
Tiocrash
Tiocrash

Reputation: 357

Finding the max depth of a set in a dictionary

I have a dictionary where the key is a string and the values of the key are a set of strings that also contain the key (word chaining). I'm having trouble finding the max depth of a graph, which would be the set with the most elements in the dictionary, and I'm try print out that max graph as well.

Right now my code prints:

{'DOG': [],
 'HIPPOPOTIMUS': [],
 'POT': ['SUPERPOT', 'HIPPOPOTIMUS'],
 'SUPERPOT': []}
1

Where 1 is my maximum dictionary depth. I was expecting the depth to be two, but there appears to be only 1 layer to the graph of 'POT'

How can I find the maximum value set from the set of keys in a dictionary?

import pprint

def dict_depth(d, depth=0):
    if not isinstance(d, dict) or not d:
        return depth
    print max(dict_depth(v, depth+1) for k, v in d.iteritems())


def main():
    for keyCheck in wordDict:
        for keyCompare in wordDict:
            if keyCheck in keyCompare:
                if keyCheck != keyCompare:
                    wordDict[keyCheck].append(keyCompare)

if __name__ == "__main__":
    #load the words into a dictionary
    wordDict = dict((x.strip(), []) for x in open("testwordlist.txt"))
    main()
    pprint.pprint (wordDict)
    dict_depth(wordDict)

testwordlist.txt:

POT
SUPERPOT
HIPPOPOTIMUS
DOG

Upvotes: 0

Views: 709

Answers (2)

Rob Kennedy
Rob Kennedy

Reputation: 163317

The "depth" of a dictionary will naturally be 1 plus the maximum depth of its entries. You've defined the depth of a non-dictionary to be zero. Since your top-level dictionary doesn't contain any dictionaries of its own, the depth of your dictionary is clearly 1. Your function reports that value correctly.

However, your function isn't written expecting the data format you're providing it. We can easily come up with inputs where the depth of substring chains is more than just one. For example:

DOG
DOGMA
DOGMATIC
DOGHOUSE
POT

Output of your current script:

{'DOG': ['DOGMATIC', 'DOGMA', 'DOGHOUSE'],
 'DOGHOUSE': [],
 'DOGMA': ['DOGMATIC'],
 'DOGMATIC': [],
 'POT': []}
1

I think you want to get 2 for that input because the longest substring chain is DOG → DOGMA → DOGMATIC, which contains two hops.

To get the depth of a dictionary as you've structured it, you want to calculate the chain length for each word. That's 1 plus the maximum chain length of each of its substrings, which gives us the following two functions:

def word_chain_length(d, w):
    if len(d[w]) == 0:
        return 0
    return 1 + max(word_chain_length(d, ww) for ww in d[w])

def dict_depth(d):
    print(max(word_chain_length(d, w) for w in d))

The word_chain_length function given here isn't particularly efficient. It may end up calculating the lengths of the same chain multiple times if a string is a substring of many words. Dynamic programming is a simple way to mitigate that, which I'll leave as an exercise.

Upvotes: 1

Jay
Jay

Reputation: 2686

Sorry my examples wont be in python because my python is rusty but you should get the idea.

Lets say this is a binary tree:
(written in c++)

int depth(TreeNode* root){
  if(!root) return 0;
  return 1+max(depth(root->left), depth(root->right));
}

Simple. Now lets expand this too more then just a left and right.
(golang code)

func depthfunc(Dic dic) (int){
   if dic == nil {
     return 0
   }
   level := make([]int,0)
   for key, anotherDic := range dic{
      depth := 1
      if ok := anotherDic.(Dic); ok { // check if it does down further
        depth = 1 + depthfunc(anotherDic)
      }
        level = append(level, depth)          
   }

   //find max
   max := 0
   for _, value := range level{
     if value > max {
       max = value
     }
   }
   return max
}

The idea is that you just go down each dictionary until there is no more dictionaries to go down adding 1 to each level you traverse.

Upvotes: 1

Related Questions