Gale–Shapley stable matching.

// Gale–Shapley stable matching, also called deferred acceptance. One side proposes down its ranked
// list; the other side holds the best offer it has had so far and trades up when a better one
// arrives. When nobody has anyone left to ask, the held offers are the matching, and no two people
// would both rather be with each other than with the partners they got.
export const MAX_PEOPLE = 32;

// A person's ranking, best first. Anyone left off the list is someone they won't be matched with.
export type Person = { name: string; ranks: string[] };

export type Outcome = 'held' | 'replaced' | 'rejected' | 'unacceptable';
// `other` is the proposer the receiver let go (replaced) or kept (rejected); otherwise null.
export type Proposal = { from: string; to: string; outcome: Outcome; other: string | null };
export type Pair = { proposer: string; receiver: string };
export type Matching = {
	pairs: Pair[];
	unmatchedProposers: string[];
	unmatchedReceivers: string[];
	proposals: Proposal[];
};

export type MatchingErrorCode = 'too-many' | 'bad-name' | 'bad-ranking' | 'bad-pair';

export class MatchingError extends Error {
	readonly code: MatchingErrorCode;
	constructor(code: MatchingErrorCode, message: string) {
		super(message);
		this.name = 'MatchingError';
		this.code = code;
	}
}

export function checkSides(proposers: Person[], receivers: Person[]): void {
	if (proposers.length > MAX_PEOPLE || receivers.length > MAX_PEOPLE)
		throw new MatchingError('too-many', `up to ${MAX_PEOPLE} people on each side`);
	const names = new Set<string>();
	for (const person of [...proposers, ...receivers]) {
		if (!/^[a-z][a-z0-9-]{0,31}$/.test(person.name) || names.has(person.name))
			throw new MatchingError('bad-name', `names are unique lowercase slugs: ${person.name}`);
		names.add(person.name);
	}
	for (const [side, other] of [
		[proposers, receivers],
		[receivers, proposers]
	]) {
		const allowed = new Set(other.map((person) => person.name));
		for (const person of side)
			if (
				new Set(person.ranks).size !== person.ranks.length ||
				person.ranks.some((name) => !allowed.has(name))
			)
				throw new MatchingError(
					'bad-ranking',
					`${person.name} can rank each person on the other side once`
				);
	}
}

export function match(proposers: Person[], receivers: Person[]): Matching {
	checkSides(proposers, receivers);
	// Each receiver's ranking as a lookup, so comparing two offers is one step.
	const place = new Map(
		receivers.map((r) => [r.name, new Map(r.ranks.map((name, i) => [name, i]))])
	);
	const listOf = new Map(proposers.map((p) => [p.name, p.ranks]));
	const next = new Map(proposers.map((p) => [p.name, 0])); // where each proposer is on their list
	const held = new Map<string, string>(); // receiver → proposer whose offer it holds
	const proposals: Proposal[] = [];
	// Proposers without a held offer, in listed order. Someone let go joins the back of the line.
	const line = proposers.map((p) => p.name);

	for (let head = 0; head < line.length; head++) {
		const from = line[head];
		const list = listOf.get(from)!;
		// Ask down the list until someone holds the offer or the list runs out.
		while (next.get(from)! < list.length) {
			const to = list[next.get(from)!];
			next.set(from, next.get(from)! + 1);
			const ranks = place.get(to)!;
			const current = held.get(to) ?? null;
			if (!ranks.has(from)) {
				proposals.push({ from, to, outcome: 'unacceptable', other: null });
			} else if (current === null) {
				held.set(to, from);
				proposals.push({ from, to, outcome: 'held', other: null });
				break;
			} else if (ranks.get(from)! < ranks.get(current)!) {
				held.set(to, from);
				proposals.push({ from, to, outcome: 'replaced', other: current });
				line.push(current);
				break;
			} else {
				proposals.push({ from, to, outcome: 'rejected', other: current });
			}
		}
	}

	const partner = new Map([...held].map(([receiver, proposer]) => [proposer, receiver]));
	return {
		pairs: proposers
			.filter((p) => partner.has(p.name))
			.map((p) => ({ proposer: p.name, receiver: partner.get(p.name)! })),
		unmatchedProposers: proposers.filter((p) => !partner.has(p.name)).map((p) => p.name),
		unmatchedReceivers: receivers.filter((r) => !held.has(r.name)).map((r) => r.name),
		proposals
	};
}

// Gale–Shapley stable matching, also called deferred acceptance. One side proposes down its ranked
// list; the other side holds the best offer it has had so far and trades up when a better one
// arrives. When nobody has anyone left to ask, the held offers are the matching, and no two people
// would both rather be with each other than with the partners they got.
const MaxPeople = 32

// Person is a ranking, best first. Anyone left off the list is someone they won't be matched with.
type Person struct {
	Name  string
	Ranks []string
}

// Proposal records one offer. Other is the proposer the receiver let go (replaced) or kept
// (rejected); otherwise nil.
type Proposal struct {
	From, To, Outcome string
	Other             *string
}

type Pair struct{ Proposer, Receiver string }

type Matching struct {
	Pairs              []Pair
	UnmatchedProposers []string
	UnmatchedReceivers []string
	Proposals          []Proposal
}

type MatchingError struct{ Code, Message string }

func (e *MatchingError) Error() string { return e.Message }

var slug = regexp.MustCompile(`^[a-z][a-z0-9-]{0,31}$`)

func CheckSides(proposers, receivers []Person) error {
	if len(proposers) > MaxPeople || len(receivers) > MaxPeople {
		return &MatchingError{"too-many", fmt.Sprintf("up to %d people on each side", MaxPeople)}
	}
	names := map[string]bool{}
	for _, person := range slices.Concat(proposers, receivers) {
		if !slug.MatchString(person.Name) || names[person.Name] {
			return &MatchingError{"bad-name", "names are unique lowercase slugs: " + person.Name}
		}
		names[person.Name] = true
	}
	for _, sides := range [][2][]Person{{proposers, receivers}, {receivers, proposers}} {
		allowed := map[string]bool{}
		for _, other := range sides[1] {
			allowed[other.Name] = true
		}
		for _, person := range sides[0] {
			seen := map[string]bool{}
			for _, name := range person.Ranks {
				if seen[name] || !allowed[name] {
					return &MatchingError{"bad-ranking", person.Name + " can rank each person on the other side once"}
				}
				seen[name] = true
			}
		}
	}
	return nil
}

func Match(proposers, receivers []Person) (Matching, error) {
	if err := CheckSides(proposers, receivers); err != nil {
		return Matching{}, err
	}
	// Each receiver's ranking as a lookup, so comparing two offers is one step.
	place := map[string]map[string]int{}
	for _, r := range receivers {
		place[r.Name] = map[string]int{}
		for i, name := range r.Ranks {
			place[r.Name][name] = i
		}
	}
	lists := map[string][]string{}
	// Proposers without a held offer, in listed order. Someone let go joins the back of the line.
	line := make([]string, 0, len(proposers))
	for _, p := range proposers {
		lists[p.Name] = p.Ranks
		line = append(line, p.Name)
	}
	next := map[string]int{}    // where each proposer is on their list
	held := map[string]string{} // receiver → proposer whose offer it holds
	proposals := []Proposal{}

	for head := 0; head < len(line); head++ {
		from := line[head]
		list := lists[from]
		// Ask down the list until someone holds the offer or the list runs out.
	asking:
		for next[from] < len(list) {
			to := list[next[from]]
			next[from]++
			ranks := place[to]
			current, holding := held[to]
			fromPlace, acceptable := ranks[from]
			switch {
			case !acceptable:
				proposals = append(proposals, Proposal{from, to, "unacceptable", nil})
			case !holding:
				held[to] = from
				proposals = append(proposals, Proposal{from, to, "held", nil})
				break asking
			case fromPlace < ranks[current]:
				held[to] = from
				proposals = append(proposals, Proposal{from, to, "replaced", &current})
				line = append(line, current)
				break asking
			default:
				proposals = append(proposals, Proposal{from, to, "rejected", &current})
			}
		}
	}

	partner := map[string]string{}
	for receiver, proposer := range held {
		partner[proposer] = receiver
	}
	m := Matching{[]Pair{}, []string{}, []string{}, proposals}
	for _, p := range proposers {
		if r, ok := partner[p.Name]; ok {
			m.Pairs = append(m.Pairs, Pair{p.Name, r})
		} else {
			m.UnmatchedProposers = append(m.UnmatchedProposers, p.Name)
		}
	}
	for _, r := range receivers {
		if _, ok := held[r.Name]; !ok {
			m.UnmatchedReceivers = append(m.UnmatchedReceivers, r.Name)
		}
	}
	return m, nil
}