Jump to content

Nonoblock: Difference between revisions

Nonoblock (view source)

Revision as of 14:26, 1 November 2014

79 bytes added ,  9 years ago
Updated D entry
(→‎Tcl: Added implementation)
(Updated D entry)
Line 61:
=={{header|D}}==
{{trans|python}}
<lang d>import std.stdio, std.array, std.algorithm, std.exception, std.conv;,
std.concurrency, std.range;
 
struct Solution { uint pos, len; }
 
Generator!(Solution[]) nonoBlocks(in uint[] blocks, in uint cells) {
struct NonoBlocks {
return new typeof(return)({
const uint[] blocks;
if (blocks.empty || blocks[0] == 0) {▼
const uint cells;
const vec = yield([Solution(0, 0)]);▼
} else {▼
enforce(blocks.sum + blocks.length - 1 <= cells,▼
// of placing the restBl "Those blocks cannot fit in thethose cells one.");▼
immutable newCells =immutable cellsfirstBl -= offsetblocks[0];▼
const restBl = blocks.dropOne;
 
// The other blocks need space.▼
int opApply(int delegate(ref const Solution[]) dg) {
immutable minS = restBl.map!(b => b + 1).sum;▼
int result;
 
// Slide the start position from left to max RH▼
▲ if (blocks.empty || blocks[0] == 0) {
// index allowing for other blocks.▼
▲ const vec = [Solution(0, 0)];
foreach (immutable bPos; 0 .. cells - minS - firstBl + 1) {
result = dg(vec);
if (resultrestBl.empty) return result;{
// MoreNo other blocks to the right so create ajust sub-problemyield▼
} else {
// this one.▼
▲ enforce(blocks.sum + blocks.length - 1 <= cells,
"Those blocks cannot fit in those cells."yield([Solution(bPos, firstBl)]);
immutable firstBl = blocks[0]; } else {
const restBl = // More blocks[1 ..to the right so create a $];sub-problem
// of placing the restBl blocks in the cells one
// space to the right of the RHS of this block.▼
immutable offset = bPos + firstBl + 1;▼
immutable newCells = cells - offset;
 
// Recursive call to nonoBlocks yields multiple▼
▲ // The other blocks need space.
// sub-positions.▼
▲ immutable minS = restBl.map!(b => b + 1).sum;
foreach (const subPos; NonoBlocksnonoBlocks(restBl, newCells)) {▼
// Remove the offset from sub block positions.▼
const auto rest = subPos.map!(sol => Solution(offset + sol.pos, sol.len));▼
 
// Yield this block plus sub blocks positions.▼
▲ // Slide the start position from left to max RH
const vec = [ yield(Solution(bPos, firstBl)] ~ rest.array);▼
▲ // index allowing for other blocks.
foreach (immutable bPos; 0 .. cells - minS - firstBl + 1) { }
if (restBl.empty) { }
// No other blocks to the right so just yield}
▲ // this one.
const vec = [Solution(bPos, firstBl)];
result = dg(vec);
if (result) return result;
▲ } else {
▲ // More blocks to the right so create a sub-problem
▲ // of placing the restBl blocks in the cells one
▲ // space to the right of the RHS of this block.
▲ immutable offset = bPos + firstBl + 1;
▲ immutable newCells = cells - offset;
 
▲ // Recursive call to nonoBlocks yields multiple
▲ // sub-positions.
▲ foreach (const subPos; NonoBlocks(restBl, newCells)) {
▲ // Remove the offset from sub block positions.
▲ const rest = subPos.map!(sol => Solution(offset + sol.pos,
sol.len)).array;
 
▲ // Yield this block plus sub blocks positions.
▲ const vec = [Solution(bPos, firstBl)] ~ rest;
result = dg(vec);
if (result) return result;
}▼
}
});
}
 
return result;
}
}
 
 
/// Pretty prints each run of blocks with a
/// different letter for each block of filled cells.
string show(in Solution[] vec, in uint nCells) pure {
auto result = ['_'].replicate(nCells);
foreach (immutable i, immutable sol; vec)
foreach (immutable j; sol.pos .. sol.pos + sol.len)
result[j] = (result[j] == '_') ? to!char('A' + i) : '?';
return '[' ~ result ~ ']';
}
 
void main() {
static struct Problem { uint[] blocks; uint nCells; }
 
immutable Problem[] problems = [{[2, 1], 5},
{[], 5},
{[8], 10},
{[2, 3, 2, 3], 15},
{[4, 3], 10},
{[2, 1], 5},
{[3, 1], 10},
{[2, 3], 5}];
 
foreach (immutable prob; problems) {
writefln("Configuration (%d cells and %s blocks):",
prob.nCells, prob.blocks);
show([], prob.nCells).writeln;
"Possibilities:".writeln;
auto nConfigs = 0;
foreach (const sol; NonoBlocksnonoBlocks(prob.tupleof)) {
show(sol, prob.nCells).writeln;
nConfigs++;
▲ }
writefln("A total of %d possible configurations.", nConfigs);▼
writeln;▼
}
▲ writefln("A total of %d possible configurations.", nConfigs);
▲ writeln;
}
}</lang>
{{out}}
Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/245637"
Cookies help us deliver our services. By using our services, you agree to our use of cookies.
More information