119 lines
4.3 KiB
D
119 lines
4.3 KiB
D
import std.stdio, std.algorithm, std.array;
|
|
|
|
enum F { abi, bea, cath, dee, eve, fay, gay, hope, ivy, jan }
|
|
enum M { abe, bob, col, dan, ed, fred, gav, hal, ian, jon }
|
|
|
|
alias PrefMapF = M[][F];
|
|
alias PrefMapM = F[][M];
|
|
alias Couples = M[F];
|
|
|
|
immutable PrefMapF womenPref;
|
|
immutable PrefMapM menPref;
|
|
|
|
static this() pure nothrow @safe {
|
|
with (F) with (M) {
|
|
womenPref = [
|
|
abi: [bob, fred, jon, gav, ian, abe, dan, ed, col, hal],
|
|
bea: [bob, abe, col, fred, gav, dan, ian, ed, jon, hal],
|
|
cath: [fred, bob, ed, gav, hal, col, ian, abe, dan, jon],
|
|
dee: [fred, jon, col, abe, ian, hal, gav, dan, bob, ed],
|
|
eve: [jon, hal, fred, dan, abe, gav, col, ed, ian, bob],
|
|
fay: [bob, abe, ed, ian, jon, dan, fred, gav, col, hal],
|
|
gay: [jon, gav, hal, fred, bob, abe, col, ed, dan, ian],
|
|
hope: [gav, jon, bob, abe, ian, dan, hal, ed, col, fred],
|
|
ivy: [ian, col, hal, gav, fred, bob, abe, ed, jon, dan],
|
|
jan: [ed, hal, gav, abe, bob, jon, col, ian, fred, dan]
|
|
];
|
|
|
|
menPref = [
|
|
abe: [abi, eve, cath, ivy, jan, dee, fay, bea, hope, gay],
|
|
bob: [cath, hope, abi, dee, eve, fay, bea, jan, ivy, gay],
|
|
col: [hope, eve, abi, dee, bea, fay, ivy, gay, cath, jan],
|
|
dan: [ivy, fay, dee, gay, hope, eve, jan, bea, cath, abi],
|
|
ed: [jan, dee, bea, cath, fay, eve, abi, ivy, hope, gay],
|
|
fred: [bea, abi, dee, gay, eve, ivy, cath, jan, hope, fay],
|
|
gav: [gay, eve, ivy, bea, cath, abi, dee, hope, jan, fay],
|
|
hal: [abi, eve, hope, fay, ivy, cath, jan, bea, gay, dee],
|
|
ian: [hope, cath, dee, gay, bea, abi, fay, ivy, jan, eve],
|
|
jon: [abi, fay, jan, gay, eve, bea, dee, cath, ivy, hope]
|
|
];
|
|
}
|
|
}
|
|
|
|
/// Does 'first' appear before 'second' in preference list?
|
|
bool prefers(T)(in T[] preference, in T first, in T second)
|
|
pure nothrow @safe @nogc if (is(T == F) || is(T == M)) {
|
|
//const found = preference.findAmong([first, second]);
|
|
immutable T[2] two = [first, second];
|
|
const found = preference.findAmong(two[]);
|
|
return !(found.empty || found.front == second);
|
|
}
|
|
|
|
void checkStability(in Couples engaged, in PrefMapM menPref,
|
|
in PrefMapF womenPref) @safe {
|
|
"Stablility:".writeln;
|
|
bool stable = true;
|
|
foreach (immutable bride, immutable groom; engaged) {
|
|
const prefList = menPref[groom];
|
|
|
|
foreach (immutable pr; prefList) {
|
|
if (pr == bride) // He prefers his bride.
|
|
break;
|
|
|
|
if (prefers(prefList, pr, bride) &&
|
|
// He prefers another woman.
|
|
prefers(womenPref[pr], groom, engaged[pr])) {
|
|
// Other woman prefers him.
|
|
writeln("\t", pr, " prefers ", groom, " over ",
|
|
engaged[pr], " and ", groom, " prefers ",
|
|
pr, " over ", bride);
|
|
stable = false;
|
|
}
|
|
}
|
|
}
|
|
|
|
if (stable)
|
|
"\t(all marriages stable)".writeln;
|
|
}
|
|
|
|
void main() /*@safe*/ {
|
|
auto bachelors = menPref.keys.sort().release;// No queue in Phobos.
|
|
Couples engaged;
|
|
|
|
"Matchmaking:".writeln;
|
|
while (!bachelors.empty) {
|
|
immutable suitor = bachelors[0];
|
|
bachelors.popFront;
|
|
immutable prefList = menPref[suitor];
|
|
|
|
foreach (immutable bride; prefList) {
|
|
if (bride !in engaged) { // She's available.
|
|
writeln("\t", bride, " and ", suitor);
|
|
engaged[bride] = suitor; // Hook up.
|
|
break;
|
|
}
|
|
|
|
immutable groom = engaged[bride];
|
|
if (prefers(womenPref[bride], suitor, groom)) {
|
|
writeln("\t", bride, " dumped ", groom,
|
|
" for ", suitor);
|
|
bachelors ~= groom; // Dump that zero.
|
|
engaged[bride] = suitor; // Get a hero.
|
|
break;
|
|
}
|
|
}
|
|
}
|
|
|
|
"Engagements:".writeln;
|
|
foreach (immutable first, immutable second; engaged)
|
|
writeln("\t", first, " and ", second);
|
|
|
|
checkStability(engaged, menPref, womenPref);
|
|
|
|
"Perturb:".writeln;
|
|
engaged[F.abi].swap(engaged[F.bea]);
|
|
writeln("\tengage abi with ", engaged[F.abi],
|
|
" and bea with ", engaged[F.bea]);
|
|
|
|
checkStability(engaged, menPref, womenPref);
|
|
}
|