Ukrainian Oxford event

#!/usr/bin/env python3

OXFORD = 10  # The number of Oxford students
AMERICA = 21  # The number of American students
ITERATIONS = 5  # The number of times breakout rooms change / sessions

MAX_ATTEMPTS = 10_000_000  # The maximum number of times to randomize the group selection before giving up
SEED = 0x1305  # The random seed value --- same seed means same random choices
"""
This script solves the following problem.

There is a virtual event for Ukrainian students studying at Oxford and at American universities.
The idea is to organize breakout rooms in a way that all Oxford students can meet as many American students as possible.
Breakout rooms are small --- there is one Oxford student and a number of Americans --- in a way that the rooms are roughly the same size.
Each new session, the participants of breakout rooms change.

The task is, given the number of Oxford and American students and the number of sessions (iterations) to create a schedule subject to a constraint.
The constraint is that no two people (both Oxford<>American and American<>American) can meet again in the same room (to maximize the number of non-repeating connections).

This script solves the problem in a randomized fashion.
For each session, the script keeps generating breakout rooms at random until the configuration satisfies the constraint.
After such grouping is found, the new connections are remembered, and the process repeats.

Because the algorithm is randomized there is no telling how many attempts it would take to a valid grouping.
Every new session the space of available groupings shrinks and it takes more cycles to find a solution.
In order to avoid having the script to get infinitely stuck, there is a maximum number of attempts that are made before telling that the solution does not exist.
You can increase the max number of attempts to try more.
"""

import numpy as np

# cSpell:ignore oxfordian oxfordians arange


def generate():
	"""
	Returns a random grouping of students.

	Groups is a list of lists, where the outer list is of size OXFORD, and each sublist contains the students in the group.
	The first element of a sublist is an Oxford student, the rest are Americans.
	The grouping size is uniform in a sense that all groups have the same number of students +/- 1.

	The actual algorithm works like this.
	The quotient is the minimum number of Americans per each Oxfordian in a group.
	The remainder is the number of groups that will have one more American to make groups uniform in size.
	We first shuffle the list of Oxford and American students, then we go over the Oxford students, creating a group for each.
	In parallel, we go over Americans list and add quotient (optionally + 1) Americans per group.
	"""
	americans = list(np.arange(AMERICA))
	oxford = list(np.arange(OXFORD))
	np.random.shuffle(americans)
	np.random.shuffle(oxford)

	quotient = int(AMERICA / OXFORD)
	remainder = AMERICA % OXFORD

	groups = []
	index_american = 0
	for index_oxford in range(OXFORD):
		group = [oxford[index_oxford]]
		americans_in_group = quotient
		if index_oxford < remainder:
			americans_in_group += 1

		for _ in range(americans_in_group):
			group += [americans[index_american]]
			index_american += 1

		groups += [group]

	return groups


def check(groups, state, record):
	"""
	Checks or records the groups with respect to the state.

	Groups must be generated with `generate()`, and the state is a dictionary of two lists --- one for Oxford and one for American students.
	Each list contains sets of students who have been in the same group as the student indicated by the index of element in the list.
	For example,
		state["oxfordians"][2] = {4, 5, 7}
	means that the Oxford student number 2 (zero indexed) has been in the group with American students 4, 5 and 7 (zero indexed).
	
	The `record` argument controls whether the function should check or should record the groups in the state.
	If the the `record` is False, the function will check if any of the students in the given groups have not already been in the same group.
	If any two students have, the function returns False, else True.
	If the `record` is True, the function will mutate the state and add new connections given the input groups.
	"""
	for group in groups:
		oxfordian = group[0]
		americans = set(group[1:])
		if record:
			state["oxfordians"][oxfordian] |= americans
		else:
			if state["oxfordians"][oxfordian] & americans:
				return False
		for american in americans:
			other_americans = americans - set([american])
			if record:
				state["americans"][american] |= other_americans
			else:
				if state["americans"][american] & other_americans:
					return False

	return True


def output(groups, iteration, attempt):
	"""
	Prints the groups to the console.
	
	Adds 1 to all values to make them look 1-indexed.
	"""
	print(f"Iteration {iteration + 1} (took {attempt + 1:,} attempt(s)):")
	groups.sort(key=lambda group: group[0])
	for group in groups:
		print(f"\tOxford student: {group[0] + 1: <2}, American student(s): {[x + 1 for x in group[1:]]}")


def main():
	assert OXFORD <= AMERICA, "OXFORD must be <= AMERICA"
	np.random.seed(seed=SEED)

	state = {
		"oxfordians": [set() for _ in range(OXFORD)],
		"americans": [set() for _ in range(AMERICA)],
	}

	for iteration in range(ITERATIONS):
		solution_found = False
		for attempt in range(MAX_ATTEMPTS):
			groups = generate()
			if check(groups, state, record=False):
				check(groups, state, record=True)
				output(groups, iteration, attempt)
				solution_found = True
				break
		assert solution_found, "Could not generate more groups, likely not possible"


if __name__ == "__main__":
	main()