Entry 972

# see the discussion at:
# http://www.willmcgugan.com/2008/08/25/a-python-challenge-better-than-rentacoder/

import os
import random

def unbase(digits, base):
    n = 0
    for x in digits:
        n = n*base + x
    return n

def positionalbase(n, base):
    orign = n
    parts = []
    while n >= base:
        parts.append(n % base)
        n = n // base
    parts.append(n % base)
    parts.reverse()
    assert unbase(parts, base) == orign
    return parts

MAXFILES = 100
def make_path1(n):
    pathparts = ['%d' % x for x in positionalbase(n, MAXFILES//2)]
    pathparts[-1] = 'f' + pathparts[-1]
    return os.path.join(*pathparts), len(pathparts)

def make_path2(n):
    pathparts = ['%d' % x for x in positionalbase(n, MAXFILES-1)]
    pathparts.append('leaf')
    return os.path.join(*pathparts), len(pathparts)

def evaluate(strategy, nmax):
    nsamples = 10000
    depths = [strategy(random.randint(0, nmax-1))[1] for n in xrange(nsamples)]
    avgdepth = sum(depths)/float(nsamples)
    maxdepth = max(depths)
    print 'Nmax=%d, Avg depth: %.2f, max depth: %d' % (nmax, avgdepth, maxdepth)

def main():
    print 'Strategy 1'
    evaluate(make_path1, 100)
    evaluate(make_path1, 1000)
    evaluate(make_path1, 1000000)
    evaluate(make_path1, 1000000000)
    evaluate(make_path1, 1000000000000)

    print 'Strategy 2'
    evaluate(make_path2, 100)
    evaluate(make_path2, 1000)
    evaluate(make_path2, 1000000)
    evaluate(make_path2, 1000000000)
    evaluate(make_path2, 1000000000000)

if __name__ == '__main__':
    main()