import random

import math

import string



charPool  = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z', '0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z', '~', '!', '@', '#', '$', '%', '^', '&', '*', '(', ')', '-', '_', '+', '=', '<', '>', '?', '/', '{', '[', '}', ']', '|', '$', ':', ';', ',', '.'] 





def makeRandomPassword(length):

	S = ""

	for i in range(length):

		S += random.choice(charPool)

	return S



# If any function returns False, reject the password.  This allows you to apply a list of requirements

# to a password, and reject it if it fails any of them.  We just keep generating random passwords till

# something passes, or some password generating attempt takes too long--then we give up.  

#

# I'm using one of the funny things Python lets you do--you can pass functions around just like they're any

# other kind of variables.  So I can just hand this function a list of functions to execute as needed.  

#

def rejectionSamplePassword(length, list_of_functions):

	# Do this as a for loop to recover from endless loops from unattainable conditions.

	for i in range(100000):

		P = makeRandomPassword(length)

		okay_flag = True

		for f in list_of_functions:

			okay_flag = okay_flag and f(P)

		if okay_flag: return P

	

	raise ValueError, "Got stuck in an infinite loop--you probably have some impossible conditions."



# Put this function in to get no rejections.  

def alwaysPass(P):

	return True



# Require one of each type.

def oneOfEach(P):



	upper_flag = False

	lower_flag = False

	digit_flag = False

	symbol_flag = False



	for ch in P:

		if ch in string.uppercase: 

			upper_flag = True

		elif ch in string.lowercase: 

			lower_flag = True

		elif ch in string.digits:

			digit_flag = True

		else:

			symbol_flag = True



	return upper_flag and lower_flag and digit_flag and symbol_flag





def dontStartWithUppercase(P):



	if P[0] in string.uppercase:

		return False

	else: 

		return True



def dontEndWithPunctuation(P):



	if P[-1] == "." or P[-1] == "?" or P[-1] == "!": 

		return False

	else:

		return True



def generateRuledPassword(length):

	flist = [oneOfEach, dontStartWithUppercase, dontEndWithPunctuation]

	return rejectionSamplePassword(length, flist)

	

# COUNT CHARACTER TYPES

def countCategories(P):



	upper = 0

	lower = 0

	digit = 0

	symbol = 0



	for ch in P:

		if ch in string.uppercase: 

			upper += 1

		elif ch in string.lowercase: 

			lower += 1

		elif ch in string.digits:

			digit += 1

		else:

			symbol += 1



	return upper, lower, digit, symbol



def fact(n):

	P = 1

	for i in range(2,n+1):

		P *= i

	return P



def choose(n,k):

	return fact(n)/ (fact(n-k)*fact(k) )



# Compute how many passwords will map into the same ending password as this one, using Kristen's mapping-down function.

# Note: the count includes this password!

def fanOut(P):

	u,l,d,s = countCategories(P)

	n = len(P)

	

	return choose(n,u) * choose(n-u,l) * choose(n-u-l,d)



# Show fan-out = number of passwords that will map to the same user-friendly password)

def experimentOne(from_length, to_length, trials):

	print "Fan-out By Password Length: How many passwords map to the same user-friendly password?"

	print "% 12s: % 12s % 12s % 12s % 12s" %("length", "P10", "Median", "P90", "Average")

	for L in range(from_length,to_length+1):

		xl = [generateRuledPassword(L) for i in range(trials)]

		results = [fanOut(P) for P in xl]

		results.sort()

		average = sum(results)*1.0/len(results)

		pct_10 = results[int(trials*0.1)]

		median = results[int(trials*0.5)]

		pct_90 = results[int(trials*0.9)]

		print "% 12d: % 12d % 12d % 12d % 12.1f"%(L,pct_10,median,pct_90, average)



# Show entropy loss in bits

def experimentTwo(from_length, to_length, trials):

	print "Entropy Loss By Password Length: How much entropy is lost by mapping to user-friendly password?"

	print "% 12s: % 8s % 8s % 8s % 8s %s" %("length", "P10", "Median", "P90", "Average", "Additional letters")

	for L in range(from_length,to_length+1):

		xl = [generateRuledPassword(L) for i in range(trials)]

		results = [fanOut(P) for P in xl]

		results.sort()

		average = sum(results)*1.0/len(results)

		pct_10 = results[int(trials*0.1)]

		median = results[int(trials*0.5)]

		pct_90 = results[int(trials*0.9)]



		# Based on average fan out, about how many extra lowercase letters are needed to make up for the

		# loss in entropy?

		letters = math.ceil(math.log(average,26))

		print "% 12d: % 8.1f % 8.1f % 8.1f % 8.1f % 8d"%\

			(L,math.log(pct_10,2), math.log(median,2), math.log(pct_90,2), math.log(average,2), letters)