Stable marriage problem: Difference between revisions

Content added Content deleted

Inline

@@ Line 44: / Line 44: @@
 #  [http://www.cs.columbia.edu/~evs/intro/stable/writeup.html The Stable Marriage Problem]. (Eloquent description and background information).
 # [http://sephlietz.com/gale-shapley/ Gale-Shapley Algorithm Demonstration].
+=={{header|D}}==
+D v.2, adapted from the Python and Java versions.
+<lang d>import std.stdio: writeln, writefln;
+import std.array: popFront;
+import std.algorithm: indexOf, swap;
+import std.string: split, splitlines;
+string[string] matchmaker(const string[][string] guyPrefers,
+                          const string[][string] girlPrefers) {
+    string[string] engagedTo;
+    string[] freeGuys = guyPrefers.keys;
+    while (freeGuys.length) {
+        const auto string thisGuy = freeGuys[0];
+        freeGuys.popFront();
+        const auto thisGuyPrefers = guyPrefers[thisGuy];
+        foreach (girl; thisGuyPrefers) {
+            if (girl !in engagedTo) { // girl is free
+                engagedTo[girl] = thisGuy;
+                break;
+            } else {
+                string otherGuy = engagedTo[girl];
+                const string[] thisGirlPrefers = girlPrefers[girl];
+                if (thisGirlPrefers.indexOf(thisGuy) < thisGirlPrefers.indexOf(otherGuy)) {
+                    // this girl prefers this guy to the guy she's engagedTo to
+                    engagedTo[girl] = thisGuy;
+                    freeGuys ~= otherGuy;
+                    break;
+                }
+                // else no change, keep looking for this guy
+            }
+        }
+    }
+    return engagedTo;
+}
+bool check(bool doPrint=false)(const string[string] engagedTo,
+                               const string[][string] guyPrefers,
+                               const string[][string] galPrefers) {
+    enum MSG = "%s likes %s better than %s and %s likes %s better than their current partner";
+    string[string] inverseEngaged;
+    foreach (k, v; engagedTo)
+        inverseEngaged[v] = k;
+    foreach (she, he; engagedTo) {
+        const auto sheLikes = galPrefers[she];
+        const auto sheLikesBetter = sheLikes[0 .. sheLikes.indexOf(he)];
+        const auto heLikes = guyPrefers[he];
+        const auto heLikesBetter = heLikes[0 .. heLikes.indexOf(she)];
+        foreach (guy; sheLikesBetter) {
+            const auto guysGirl = inverseEngaged[guy];
+            const auto guyLikes = guyPrefers[guy];
+            if (guyLikes.indexOf(guysGirl) > guyLikes.indexOf(she)) {
+                static if (doPrint)
+                    writefln(MSG, she, guy, he, guy, she);
+                return false;
+            }
+        }
+        foreach (gal; heLikesBetter) {
+            const auto girlsGuy = engagedTo[gal];
+            const auto galLikes = galPrefers[gal];
+            if (galLikes.indexOf(girlsGuy) > galLikes.indexOf(he)) {
+                static if (doPrint)
+                    writefln(MSG, he, gal, she, gal, he);
+                return false;
+            }
+        }
+    }
+    return true;
+}
+void main() {
+    auto guyData = "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";
+    auto galData = "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";
+    string[][string] guyPrefers, galPrefers;
+    foreach (line; guyData.splitlines())
+        guyPrefers[split(line)[0]] = split(line)[1..$];
+    foreach (line; galData.splitlines())
+        galPrefers[split(line)[0]] = split(line)[1..$];
+    writeln("Engagements:");
+    auto engagedTo = matchmaker(guyPrefers, galPrefers);
+    writeln("\nCouples:");
+    string[] parts;
+    foreach (k; engagedTo.keys.sort)
+        writefln("%s is engagedTo to %s", k, engagedTo[k]);
+    writeln();
+    bool c = check!(true)(engagedTo, guyPrefers, galPrefers);
+    writeln("Marriages are ", c ? "stable" : "unstable");
+    writeln("\n\nSwapping two fiances to introduce an error");
+    auto gals = galPrefers.keys.sort;
+    swap(engagedTo[gals[0]], engagedTo[gals[1]]);
+    foreach (gal; gals[0 .. 2])
+        writefln("  %s is now engagedTo to %s", gal, engagedTo[gal]);
+    writeln();
+    c = check!(true)(engagedTo, guyPrefers, galPrefers);
+    writeln("Marriages are ", c ? "stable" : "unstable");
+}</lang>
+Output:
+<pre>Engagements:
+Couples:
+abi is engagedTo to jon
+bea is engagedTo to fred
+cath is engagedTo to bob
+dee is engagedTo to col
+eve is engagedTo to hal
+fay is engagedTo to dan
+gay is engagedTo to gav
+hope is engagedTo to ian
+ivy is engagedTo to abe
+jan is engagedTo to ed
+Marriages are stable
+Swapping two fiances to introduce an error
+  abi is now engagedTo to fred
+  bea is now engagedTo to jon
+fred likes bea better than abi and bea likes fred better than their current partner
+Marriages are unstable</pre>
 =={{header|Java}}==
 This is not a direct translation of [[#Python|Python]], but it's fairly close (especially the stability check).
@@ Line 196: / Line 350: @@
 fred likes bea better than abi and bea likes fred better than their current partner
 Marriages are unstable</pre>
 =={{header|Python}}==
 <lang python>import copy