Entry 957

# Number of child directories per directory
node_branches = 49

# Number of files per directory
node_items = 51

def make_path(n):
    node = n // node_items
    path = 'f%d' % (n % node_items)
    while node > 0:
        path = '%d/%s' % (node, path)
        node = (node - 1) // node_branches
    return path

def test_make_path(n):
    '''Assert that all paths up to `n` are unique.''' 
    paths = set()
    for i in range(n):
        path = make_path(i)
        assert path not in paths, path
        paths.add(path)

def total_depth(n):
    '''Return sum of depths for all paths up to `n`.'''
    total_depth = 0
    for i in range(n):
        path = make_path(i)
        total_depth += path.count('/')
    return total_depth

# Try all combinations of node_branches/node_items to find optimal
# distribution for large number of paths (lowest total depth is best).
for node_branches in range(2, 99):
    node_items = 100 - node_branches
    print node_branches, node_items, total_depth(50000)