Dinesman's multiple-dwelling problem: Difference between revisions

Content added Content deleted

Inline

@@ Line 129: / Line 129: @@
 =={{header|D}}==
 As for flexibility: the solve function is parameterized, accepting a length argument and a variable number of function predicates.
-<lang d>import std.stdio, std.exception, std.range, std.algorithm, std.math;
+<lang d>import std.stdio, std.exception, std.range, std.algorithm,
+       std.math, std.traits;
+struct Permutations {
-pure ulong fact(uint n) {
-    ulong result = 1;
+    private immutable size_t num;
-    for (uint i = 2; i <= n; i++)
-        result *= i;
-    return result;
-}
-struct LazyPermutation {
     private uint[] seq;
     private ulong tot;
-    private size_t num;
-    this (size_t num) {
+    this (in size_t n) /*pure*/ nothrow
+    in {
-        enforce(num > 1, "LazyPermutation: num must be > 1");
-        this.seq = array(iota(num));
+        enforce(n > 1, "Permutations: n must be > 1");
+    } body {
-        this.tot = fact(num);
+        static ulong factorial(in uint n) pure nothrow {
-        this.num = num;
+            ulong result = 1;
+            foreach (i; 2 .. n + 1)
+                result *= i;
+            return result;
+        }
+        this.seq = array(iota(n)); // not pure
+        this.tot = factorial(n);
+        this.num = n;
     }
-    @property uint[] front() {
+    @property const(uint[]) front() const pure nothrow {
         return seq;
     }
-    @property bool empty() {
+    @property bool empty() const pure nothrow {
         return tot == 0;
     }
-    void popFront(){
+    void popFront() pure nothrow {
-        if (--tot > 0) {
+        tot--;
+        if (tot > 0) {
             size_t j = num - 2;
-            while (seq[j] > seq[j + 1]) {
+            while (seq[j] > seq[j + 1])
                 j--;
-            }
             size_t k = num - 1;
-            while (seq[j] > seq[k]) {
+            while (seq[j] > seq[k])
                 k--;
-            }
             swap(seq[k], seq[j]);
@@ Line 181: / Line 183: @@
 }
-size_t[] solve(T : size_t, F...)(T len, F predicates) {
+const(uint[]) solve(T : size_t, F...)(in T len, in F predicates)
+/*pure*/ nothrow {
     outer:
-    foreach (p; LazyPermutation(len)) {
+    foreach (p; Permutations(len)) {
         foreach (pred; predicates)
             if (!pred(p))
@@ Line 193: / Line 196: @@
 void main() {
+    enum N { Baker, Cooper, Fletcher, Miller, Smith } // names
-    enum Floors = 5;
-    enum {Baker, Cooper, Fletcher, Miller, Smith};
-    auto p1 = (uint[] s){ return s[Baker] != s.length-1; };
+    alias bool function(in uint[]) pure nothrow MutablePredicate;
+    alias immutable(MutablePredicate) P;
-    auto p2 = (uint[] s){ return s[Cooper] != 0; };
-    auto p3 = (uint[] s){ return s[Fletcher] != 0 && s[Fletcher] != s.length-1; };
+    P p1 = s => s[N.Baker] != s.length-1;
-    auto p4 = (uint[] s){ return s[Miller] > s[Cooper]; };
+    P p2 = s => s[N.Cooper] != 0;
-    auto p5 = (uint[] s){ return abs(cast(int)(s[Smith] - s[Fletcher])) != 1; };
+    P p3 = s => s[N.Fletcher] != 0 && s[N.Fletcher] != s.length-1;
-    auto p6 = (uint[] s){ return abs(cast(int)(s[Cooper] - s[Fletcher])) != 1; };
+    P p4 = s => s[N.Miller] > s[N.Cooper];
+    P p5 = s => abs(cast(int)(s[N.Smith] - s[N.Fletcher])) != 1;
+    P p6 = s => abs(cast(int)(s[N.Cooper] - s[N.Fletcher])) != 1;
+    enum nFloors = EnumMembers!N.length;
-    if (auto sol = solve(Floors, p1, p2, p3, p4, p5, p6))
+    if (auto sol = solve(nFloors, p1, p2, p3, p4, p5, p6))
-        writeln(sol);
+        writeln(map!(p => [EnumMembers!N][p])(sol));
 }</lang>
+Output:
-<pre>[2, 1, 3, 4, 0]</pre>
+<pre>[Fletcher, Cooper, Miller, Smith, Baker]</pre>
 =={{header|Haskell}}==