seating-chart.py

#!/usr/bin/env python3

import json
import math
import random
import yaml
import dominate
from dominate.tags import *

def load_yaml (filename):
	with open(filename) as file:
		return yaml.load(file.read())

def unpack_people (object, number_of_seats):
	names = []
	preferences = []
	people = []
	for _ in range(number_of_seats - len(object)):
		object.append({
			"name": "[nobody]",
			"preferences": []
		})
	for index, person in enumerate(object):
		people.append(index)
		names.append(person["name"])
	for person in object:
		for preference in person["preferences"]:
			preferences.append((
				names.index(person["name"]),
				names.index(preference["name"]),
				preference["strength"]
			))
	return names, people, preferences

def uniquify_list_of_lists (list_of_lists):
	unique = []
	for element in list_of_lists:
		if tuple(element) not in unique:
			unique.append(tuple(element))
	return [list(element) for element in unique]

def unpack_seats (object):
	seats = []
	for seat in object:
		seats.append((int(seat[0]), int(seat[1])))
	return seats

def generate_seats (number_of_people, rows):
	seats = []
	columns = math.ceil(number_of_people / rows)
	for row in range(rows):
		for column in range(columns):
			seats.append((column, row))
	return seats

def generate_random_population (people, preferences, seats, population_size):
	raw = [random.sample(people, len(people)) for _ in range(population_size)]
	return [(chromosome, score(chromosome, preferences, seats)) for chromosome in raw]

def get_distance (a, b):
	x = a[0] - b[0]
	y = a[1] - b[1]
	return ((x ** 2) + (y ** 2)) ** (1 / 2)

def score (chromosome, preferences, seats):
	score = 0
	for preference in preferences:
		source = preference[0]
		target = preference[1]
		strength = preference[2]
		distance = get_distance(seats[chromosome[source]], seats[chromosome[target]])
		score += strength / distance
	return score

def select (population):
	total_weight = sum([chromosome[1] for chromosome in population])
	value = random.random() * total_weight
	for chromosome in population:
		value -= chromosome[1]
		if value <= 0:
			return chromosome
	return population[-1]

def select_parents (population):
	a = select(population)
	b = select([chromosome for chromosome in population if chromosome != a])
	return [a, b]

def mutate (chromosome, mutation_rate): # not perfect; sometimes a gene is switched with itself. get_mutation_rate accounts for this flaw
	enumerated = list(enumerate(chromosome)) # for random.choice later on
	old = chromosome[:]
	for index, gene in enumerated:
		if random.random() < mutation_rate:
			chosen = random.choice(enumerated)[0]
			chromosome[index], chromosome[chosen] = chromosome[chosen], chromosome[index]
	return chromosome

def create_charts (global_best, population, seats, filename, count):
	def make_chart (chromosome, rows, columns):
		chart = [[None for _ in range(columns + 1)] for _ in range(rows + 1)] # range is to n - 1
		for person, seat in enumerate(chromosome[0]):
			name = names[person]
			row = seats[seat][1]
			column = seats[seat][0]
			chart[row][column] = name
		return chart
	rows    = max(seats, key = lambda seat: seat[1])[1] - min(seats, key = lambda seat: seat[1])[1]
	columns = max(seats, key = lambda seat: seat[0])[0] - min(seats, key = lambda seat: seat[0])[0]

	doc = dominate.document(title = filename)
	with doc.head:
		style("""
			table, td, th {
				border: 1px solid black;
			}
			table {
				border-collapse: collapse;
				margin-bottom: 8px;
			}
			td, th {
				padding: 0.5rem;
			}
		""")

	if len(global_best[0]):
		chart = make_chart(global_best, rows, columns)
		with doc:
			p(" ".join(["after", str(count), "generations: "]))
			p("best so far:")
			with table():
				with tr():
					th("score: " + str(global_best[1]))
				for row in chart:
					with tr():
						for name in row:
							td(name)

	for chromosome in population:
		chart = make_chart(chromosome, rows, columns)
		with doc:
			with table():
				with tr():
					th("score: " + str(chromosome[1]))
				for row in chart:
					with tr():
						for name in row:
							td(name)
	with open(filename, "w") as file:
		file.write(doc.render())


def breed (parents, preferences, seats, mutation_rate): # https://en.wikipedia.org/wiki/Edge_recombination_operator
	parent_chromosomes = [parent[0] for parent in parents] # scores aren't needed at this point, though we could potentially weight parents
	child_chromosome = []
	length = len(parent_chromosomes[0])
	adjacency_matrix = {}
	for parent_chromosome in parent_chromosomes: # build adjacency matrix
		for index, gene in enumerate(parent_chromosome):
			if gene not in adjacency_matrix:
				adjacency_matrix[gene] = set()
			if index > 0:
				adjacency_matrix[gene].add(parent_chromosome[index - 1])
			if index < length - 1:
				adjacency_matrix[gene].add(parent_chromosome[index + 1])
	a = random.choice(parent_chromosomes)[0] # first node of a random parent
	while True:
		child_chromosome.append(a)
		if len(child_chromosome) == length:
			break
		adjacency_matrix = {index: {gene for gene in adjacent_list if gene != a} for index, adjacent_list in adjacency_matrix.items()} # remove a from neighbor lists
		b = None
		if len(adjacency_matrix[a]): # b becomes neighbor of a with fewest neighbors in its list
			fewest = ([], float("inf"))
			for neighbor in adjacency_matrix[a]:
				neighbor_matrix_length = len(adjacency_matrix[neighbor])
				if neighbor_matrix_length < fewest[1]:
					fewest = ([neighbor], neighbor_matrix_length)
				elif neighbor_matrix_length == fewest[1]:
					fewest[0].append(neighbor)
			b = random.choice(fewest[0])
		else: # b becomes a randomly chosen node not in child_chromosome
			b = random.choice([gene for gene in parent_chromosomes[0] if gene not in child_chromosome])
		a = b
	mutated_chromosome = mutate(child_chromosome, mutation_rate)
	return (mutated_chromosome, score(mutated_chromosome, preferences, seats))

def generation (population, preferences, seats, mutation_rate):
	next_generation = []
	while len(next_generation) < len(population):
		next_generation.append(breed(select_parents(population), preferences, seats, mutation_rate))
	return next_generation

def get_average_fitness (population):
	return sum([chromosome[1] for chromosome in population]) / len(population)

def get_most_fit (population, count):
	# maximum = max(population, key = lambda chromosome: chromosome[1])
	sorted_population = sorted(population, key = lambda chromosome: -chromosome[1])
	# un_uniquified = [chromosome for chromosome in population if chromosome[1] == maximum[1]]
	# return uniquify_list_of_lists(un_uniquified)
	return sorted_population[-count:]

def get_mutation_rate (chromosome_mutation_probability, chromosome_length):
	return (1 - ((1 - chromosome_mutation_probability) ** (1 / chromosome_length))) * (chromosome_length / (chromosome_length - 1))

population_size = 100
# population_size = 1
chromosome_mutation_probability = 0.01
number_of_rows = 2
people_yaml = "people.yaml"
out_html = "tables.html"

loaded_people_yaml = load_yaml(people_yaml)
seats = generate_seats(len(loaded_people_yaml), number_of_rows)
names, people, preferences = unpack_people(loaded_people_yaml, len(seats))

mutation_rate = get_mutation_rate(chromosome_mutation_probability, len(people))
population = generate_random_population(people, preferences, seats, population_size)

global_best = ([], float("-inf"))

power = 5
for counter in range(10 ** power):
	if not counter % (10 ** (power - 2)):
		print(counter)
		create_charts(global_best, get_most_fit(population, 10), seats, out_html, counter)
	population = generation(population, preferences, seats, mutation_rate)
	best = max(population, key = lambda chromosome: chromosome[1])
	if best[1] > global_best[1]:
		global_best = best
create_charts(global_best, get_most_fit(population, 10), seats, out_html, counter)