Anonymous user
Dinesman's multiple-dwelling problem: Difference between revisions
Dinesman's multiple-dwelling problem (view source)
Revision as of 20:18, 13 February 2012
, 12 years ago→{{header|D}}: generate permutations lazily
m (→{{header|D}}) |
(→{{header|D}}: generate permutations lazily) |
||
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;
pure T fact(T)(T n) {
T result = 1;
result *= i;
size_t[][] res;▼
return result;
}
if (s.length) {▼
struct LazyPermutation {
foreach (i, c; s) {▼
private uint[] seq;
private size_t num;
this (size_t num) {
enforce(num > 1, "LazyPermutation: num must be > 1");
this.seq = array(iota(0, num));
this.tot = fact(num);
this.num = num;
@property uint[] front() {
return seq;
}▼
@property bool empty() {
return tot == 0;
}▼
void popFront(){
size_t j = num - 2;
while (seq[j] > seq[j + 1]) {
j--;
}
while (seq[j] > seq[k]) {
▲ }
swap(seq[k], seq[j]);
size_t r = num - 1;
size_t s = j + 1;
swap(seq[s], seq[r]);
r--;
s++;
}
}
}
}
size_t[] solve(T : size_t, F...)(T len, F predicates) {
outer:
foreach (p;
foreach (pred; predicates)
if (!pred(p))
continue outer;
return p;
Line 161 ⟶ 195:
enum Floors = 5;
enum {Baker, Cooper, Fletcher, Miller, Smith};
auto p1 = (uint[] s){ return s[Baker] != s.length-1; };
auto p2 = (uint[] s){ return s[Cooper] != 0; };
auto p3 = (uint[] s){ return s[Fletcher] != 0 && s[Fletcher] != s.length-1; };
auto p4 = (uint[] s){ return s[Miller] > s[Cooper]; };
auto p5 = (uint[] s){ return abs(cast(int)(s[Smith] - s[Fletcher])) != 1; };
auto p6 = (uint[] s){ return abs(cast(int)(s[Cooper] - s[Fletcher])) != 1; };
if (auto sol = solve(Floors, p1, p2, p3, p4, p5, p6))
writeln(sol);
|