Brute-force generation of "fights" for MAIG/Unit 1: 'The Battle of Heslington'

MAIG-battle-of-heslington

#!/usr/local/bin/pypy

'''
RESULTS
========

6850 / 10276  wins,  6066 :  [4, 4, 4, 4, 4]
6745 / 10276  wins,  5003 :  [3, 4, 4, 4, 5]
6745 / 10276  wins,  5004 :  [3, 4, 4, 5, 4]
6745 / 10276  wins,  5013 :  [3, 4, 5, 4, 4]
6745 / 10276  wins,  5104 :  [3, 5, 4, 4, 4]
6745 / 10276  wins,  5965 :  [4, 3, 4, 4, 5]
6745 / 10276  wins,  5966 :  [4, 3, 4, 5, 4]
6745 / 10276  wins,  5975 :  [4, 3, 5, 4, 4]
6745 / 10276  wins,  6056 :  [4, 4, 3, 4, 5]
6745 / 10276  wins,  6057 :  [4, 4, 3, 5, 4]
6745 / 10276  wins,  6065 :  [4, 4, 4, 3, 5]
6745 / 10276  wins,  6067 :  [4, 4, 4, 5, 3]
6745 / 10276  wins,  6074 :  [4, 4, 5, 3, 4]
6745 / 10276  wins,  6075 :  [4, 4, 5, 4, 3]
6745 / 10276  wins,  6144 :  [4, 5, 3, 4, 4]
6745 / 10276  wins,  6152 :  [4, 5, 4, 3, 4]
6745 / 10276  wins,  6153 :  [4, 5, 4, 4, 3]
6745 / 10276  wins,  6881 :  [5, 3, 4, 4, 4]
6745 / 10276  wins,  6959 :  [5, 4, 3, 4, 4]
6745 / 10276  wins,  6967 :  [5, 4, 4, 3, 4]
'''

def sumOfDigits(number):
    if number < 0:
		return None

	out = 0
	while number > 0:
		out += number % 16
		number = number // 16

	return out

def numberOfDigits(number):
	if number < 0:
		number = number * (-1)

	out = 0
	while number > 0:
		out += 1
		number = number // 16

	return out

def digitsAsList(number, minSize):
	out = []
	numberCopy = number

	while number > 0:
		out.append(number % 16)
		number = number // 16

	while minSize > numberOfDigits(numberCopy):
		out.append(0)
		minSize = minSize - 1

	return out[::-1] # reverses a list

# 'first' and 'second' are "players" i.e. distributions of the 'sMax' students
def battle(first, second):
	if len(first) != len(second):
		return None

	firstWins = 0
	secondWins = 0

	for i in range(len(first)):
		if first[i] > second[i]:
			firstWins += 1
		elif first[i] < second[i]:
			secondWins += 1

	if firstWins > secondWins:
		return 1
	elif secondWins > firstWins:
		return 2
	
	return None

if __name__ == '__main__':
	sMax = 20   # 20 maximum students (100 / 5 so it ends in a reasonable time)
	count = 5   # 5 places

	studentsLeft = sMax
	player = []

	for crt in range(0, 0xF5001):
		if sumOfDigits(crt) == sMax: 
			player.append(digitsAsList(crt, count))

	wins = [0] * len(player)

	for i in range(len(player)):
		if i % 100 == 0:
			print '%i/%i done...' % (i//100, len(player)//100)

		for j in range(i+1, len(player)):
			result = battle(player[i], player[j])

			if result == 1:
				wins[i] += 1
			elif result == 2:
				wins[j] += 1

	best = [0] * 20

	for i in range(len(wins)):
		if wins[i] > wins[best[0]]:
			best[0] = i

			for j in range(len(best)-1):
				if wins[best[j]] > wins[best[j+1]]:
					best[j], best[j+1] = best[j+1], best[j]
				else:
					break

	for crt in best[::-1]:
		print wins[crt], '/', len(player), ' wins, ', crt, ': ', player[crt]