Nonoblock: Difference between revisions
(Add ref.) |
(+ D entry) |
||
Line 52: | Line 52: | ||
;Reference: |
;Reference: |
||
* The blog post [http://paddy3118.blogspot.co.uk/2014/03/nonogram-puzzle-solver-part-1.html Nonogram puzzle solver (part 1)] Inspired this task and donated its Python solution. |
* The blog post [http://paddy3118.blogspot.co.uk/2014/03/nonogram-puzzle-solver-part-1.html Nonogram puzzle solver (part 1)] Inspired this task and donated its Python solution. |
||
=={{header|D}}== |
|||
{{trans|python}} |
|||
<lang d>import std.stdio, std.array, std.algorithm, std.exception, std.conv; |
|||
struct Solution { uint pos, len; } |
|||
struct NonoBlocks { |
|||
const uint[] blocks; |
|||
const uint cells; |
|||
int opApply(int delegate(ref const Solution[]) dg) { |
|||
int result; |
|||
if (blocks.empty || blocks[0] == 0) { |
|||
const vec = [Solution(0, 0)]; |
|||
result = dg(vec); |
|||
if (result) return result; |
|||
} else { |
|||
enforce(sum(cast(uint[])blocks) + blocks.length - 1 <= cells,//** |
|||
"Those blocks cannot fit in those cells."); |
|||
immutable firstBl = blocks[0]; |
|||
const restBl = blocks[1 .. $]; |
|||
// The other blocks need space. |
|||
immutable minS = restBl.map!(b => b + 1).sum; |
|||
// Slide the start position from left to max RH |
|||
// 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; |
|||
foreach (const sol; NonoBlocks(prob.tupleof)) |
|||
show(sol, prob.nCells).writeln; |
|||
writeln; |
|||
} |
|||
}</lang> |
|||
{{out}} |
|||
<pre>Configuration (5 cells and [2, 1] blocks): |
|||
[_____] |
|||
Possibilities: |
|||
[AA_B_] |
|||
[AA__B] |
|||
[_AA_B] |
|||
Configuration (5 cells and [] blocks): |
|||
[_____] |
|||
Possibilities: |
|||
[_____] |
|||
Configuration (10 cells and [8] blocks): |
|||
[__________] |
|||
Possibilities: |
|||
[AAAAAAAA__] |
|||
[_AAAAAAAA_] |
|||
[__AAAAAAAA] |
|||
Configuration (15 cells and [2, 3, 2, 3] blocks): |
|||
[_______________] |
|||
Possibilities: |
|||
[AA_BBB_CC_DDD__] |
|||
[AA_BBB_CC__DDD_] |
|||
[AA_BBB_CC___DDD] |
|||
[AA_BBB__CC_DDD_] |
|||
[AA_BBB__CC__DDD] |
|||
[AA_BBB___CC_DDD] |
|||
[AA__BBB_CC_DDD_] |
|||
[AA__BBB_CC__DDD] |
|||
[AA__BBB__CC_DDD] |
|||
[AA___BBB_CC_DDD] |
|||
[_AA_BBB_CC_DDD_] |
|||
[_AA_BBB_CC__DDD] |
|||
[_AA_BBB__CC_DDD] |
|||
[_AA__BBB_CC_DDD] |
|||
[__AA_BBB_CC_DDD] |
|||
Configuration (10 cells and [4, 3] blocks): |
|||
[__________] |
|||
Possibilities: |
|||
[AAAA_BBB__] |
|||
[AAAA__BBB_] |
|||
[AAAA___BBB] |
|||
[_AAAA_BBB_] |
|||
[_AAAA__BBB] |
|||
[__AAAA_BBB] |
|||
Configuration (5 cells and [2, 1] blocks): |
|||
[_____] |
|||
Possibilities: |
|||
[AA_B_] |
|||
[AA__B] |
|||
[_AA_B] |
|||
Configuration (10 cells and [3, 1] blocks): |
|||
[__________] |
|||
Possibilities: |
|||
[AAA_B_____] |
|||
[AAA__B____] |
|||
[AAA___B___] |
|||
[AAA____B__] |
|||
[AAA_____B_] |
|||
[AAA______B] |
|||
[_AAA_B____] |
|||
[_AAA__B___] |
|||
[_AAA___B__] |
|||
[_AAA____B_] |
|||
[_AAA_____B] |
|||
[__AAA_B___] |
|||
[__AAA__B__] |
|||
[__AAA___B_] |
|||
[__AAA____B] |
|||
[___AAA_B__] |
|||
[___AAA__B_] |
|||
[___AAA___B] |
|||
[____AAA_B_] |
|||
[____AAA__B] |
|||
[_____AAA_B] |
|||
Configuration (5 cells and [2, 3] blocks): |
|||
[_____] |
|||
Possibilities: |
|||
Possibilities: |
|||
object.Exception@nonoblock.d(17): Those blocks cannot fit in those cells. |
|||
---------------- |
|||
0x0040AC17 in pure @safe void std.exception.bailOut(immutable(char)[], uint, const(char[])) |
|||
...</pre> |
|||
=={{header|Python}}== |
=={{header|Python}}== |
Revision as of 13:15, 5 April 2014
Nonoblock is a chip off the old Nonogram puzzle.
- Given
- The number of cells in a row
- The size of each, (space separated), connected block of cells to fit in the row, in left-to right order
The task is to
- show all possible positions
- and the number of positions
of the blocks for the following cases within the row. On this page. Using a "neat" diagram of the block positions.
- Enumerate the following configurations
- 5 cells and [2, 1] blocks
- 5 cells and [] blocks (no blocks)
- 10 cells and [8] blocks
- 15 cells and [2, 3, 2, 3] blocks
- 5 cells and [2, 3] blocks (Should give some indication of this not being possible).
- Example
Given a row of five cells and a block of two cells followed by a block of 1 cell - in that order, the example could be shown as:
|_|_|_|_|_| # 5 cells and [2, 1] blocks
And would expand to the following 3 possible rows of block positions:
|A|A|_|B|_| |A|A|_|_|B| |_|A|A|_|B|
Note how the sets of blocks are always separated by a space
Note also that it is not necessary for each block to have a separate letter. Output approximating
This:
|#|#|_|#|_| |#|#|_|_|#| |_|#|#|_|#|
Or even this:
##.#. ##..# .##.#
Would also work.
- Reference
- The blog post Nonogram puzzle solver (part 1) Inspired this task and donated its Python solution.
D
<lang d>import std.stdio, std.array, std.algorithm, std.exception, std.conv;
struct Solution { uint pos, len; }
struct NonoBlocks {
const uint[] blocks; const uint cells;
int opApply(int delegate(ref const Solution[]) dg) { int result;
if (blocks.empty || blocks[0] == 0) { const vec = [Solution(0, 0)]; result = dg(vec); if (result) return result; } else { enforce(sum(cast(uint[])blocks) + blocks.length - 1 <= cells,//** "Those blocks cannot fit in those cells."); immutable firstBl = blocks[0]; const restBl = blocks[1 .. $];
// The other blocks need space. immutable minS = restBl.map!(b => b + 1).sum;
// Slide the start position from left to max RH // 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; foreach (const sol; NonoBlocks(prob.tupleof)) show(sol, prob.nCells).writeln; writeln; }
}</lang>
- Output:
Configuration (5 cells and [2, 1] blocks): [_____] Possibilities: [AA_B_] [AA__B] [_AA_B] Configuration (5 cells and [] blocks): [_____] Possibilities: [_____] Configuration (10 cells and [8] blocks): [__________] Possibilities: [AAAAAAAA__] [_AAAAAAAA_] [__AAAAAAAA] Configuration (15 cells and [2, 3, 2, 3] blocks): [_______________] Possibilities: [AA_BBB_CC_DDD__] [AA_BBB_CC__DDD_] [AA_BBB_CC___DDD] [AA_BBB__CC_DDD_] [AA_BBB__CC__DDD] [AA_BBB___CC_DDD] [AA__BBB_CC_DDD_] [AA__BBB_CC__DDD] [AA__BBB__CC_DDD] [AA___BBB_CC_DDD] [_AA_BBB_CC_DDD_] [_AA_BBB_CC__DDD] [_AA_BBB__CC_DDD] [_AA__BBB_CC_DDD] [__AA_BBB_CC_DDD] Configuration (10 cells and [4, 3] blocks): [__________] Possibilities: [AAAA_BBB__] [AAAA__BBB_] [AAAA___BBB] [_AAAA_BBB_] [_AAAA__BBB] [__AAAA_BBB] Configuration (5 cells and [2, 1] blocks): [_____] Possibilities: [AA_B_] [AA__B] [_AA_B] Configuration (10 cells and [3, 1] blocks): [__________] Possibilities: [AAA_B_____] [AAA__B____] [AAA___B___] [AAA____B__] [AAA_____B_] [AAA______B] [_AAA_B____] [_AAA__B___] [_AAA___B__] [_AAA____B_] [_AAA_____B] [__AAA_B___] [__AAA__B__] [__AAA___B_] [__AAA____B] [___AAA_B__] [___AAA__B_] [___AAA___B] [____AAA_B_] [____AAA__B] [_____AAA_B] Configuration (5 cells and [2, 3] blocks): [_____] Possibilities: Possibilities: object.Exception@nonoblock.d(17): Those blocks cannot fit in those cells. ---------------- 0x0040AC17 in pure @safe void std.exception.bailOut(immutable(char)[], uint, const(char[])) ...
Python
<lang python>def nonoblocks(blocks, cells):
if not blocks or blocks[0] == 0: yield [(0, 0)] else: assert sum(blocks) + len(blocks)-1 <= cells, \ 'Those blocks will not fit in those cells' blength, brest = blocks[0], blocks[1:] # Deal with the first block of length minspace4rest = sum(1+b for b in brest) # The other blocks need space # Slide the start position from left to max RH index allowing for other blocks. for bpos in range(0, cells - minspace4rest - blength + 1): if not brest: # No other blocks to the right so just yield this one. yield [(bpos, blength)] else: # More blocks to the right so create a *sub-problem* of placing # the brest blocks in the cells one space to the right of the RHS of # this block. offset = bpos + blength +1 nonoargs = (brest, cells - offset) # Pre-compute arguments to nonoargs # recursive call to nonoblocks yields multiple sub-positions for subpos in nonoblocks(*nonoargs): # Remove the offset from sub block positions rest = [(offset + bp, bl) for bp, bl in subpos] # Yield this block plus sub blocks positions vec = [(bpos, blength)] + rest yield vec
def pblock(vec, cells):
'Prettyprints each run of blocks with a different letter A.. for each block of filled cells' vector = ['_'] * cells for ch, (bp, bl) in enumerate(vec, ord('A')): for i in range(bp, bp + bl): vector[i] = chr(ch) if vector[i] == '_' else'?' return '|' + '|'.join(vector) + '|'
if __name__ == '__main__':
for blocks, cells in ( ([2, 1], 5), ([], 5), ([8], 10), ([2, 3, 2, 3], 15), # ([4, 3], 10), # ([2, 1], 5), # ([3, 1], 10), ([2, 3], 5), ): print('\nConfiguration:\n %s # %i cells and %r blocks' % (pblock([], cells), cells, blocks)) print(' Possibilities:') for i, vector in enumerate(nonoblocks(blocks, cells)): print(' ', pblock(vector, cells)) print(' A total of %i Possible configurations.' % (i+1))</lang>
- Output:
Configuration: |_|_|_|_|_| # 5 cells and [2, 1] blocks Possibilities: |A|A|_|B|_| |A|A|_|_|B| |_|A|A|_|B| A total of 3 Possible configurations. Configuration: |_|_|_|_|_| # 5 cells and [] blocks Possibilities: |_|_|_|_|_| A total of 1 Possible configurations. Configuration: |_|_|_|_|_|_|_|_|_|_| # 10 cells and [8] blocks Possibilities: |A|A|A|A|A|A|A|A|_|_| |_|A|A|A|A|A|A|A|A|_| |_|_|A|A|A|A|A|A|A|A| A total of 3 Possible configurations. Configuration: |_|_|_|_|_|_|_|_|_|_|_|_|_|_|_| # 15 cells and [2, 3, 2, 3] blocks Possibilities: |A|A|_|B|B|B|_|C|C|_|D|D|D|_|_| |A|A|_|B|B|B|_|C|C|_|_|D|D|D|_| |A|A|_|B|B|B|_|C|C|_|_|_|D|D|D| |A|A|_|B|B|B|_|_|C|C|_|D|D|D|_| |A|A|_|B|B|B|_|_|C|C|_|_|D|D|D| |A|A|_|B|B|B|_|_|_|C|C|_|D|D|D| |A|A|_|_|B|B|B|_|C|C|_|D|D|D|_| |A|A|_|_|B|B|B|_|C|C|_|_|D|D|D| |A|A|_|_|B|B|B|_|_|C|C|_|D|D|D| |A|A|_|_|_|B|B|B|_|C|C|_|D|D|D| |_|A|A|_|B|B|B|_|C|C|_|D|D|D|_| |_|A|A|_|B|B|B|_|C|C|_|_|D|D|D| |_|A|A|_|B|B|B|_|_|C|C|_|D|D|D| |_|A|A|_|_|B|B|B|_|C|C|_|D|D|D| |_|_|A|A|_|B|B|B|_|C|C|_|D|D|D| A total of 15 Possible configurations. Configuration: |_|_|_|_|_| # 5 cells and [2, 3] blocks Possibilities: Traceback (most recent call last): File "C:/Users/Paddy/Google Drive/Code/nonoblocks.py", line 104, in <module> for i, vector in enumerate(nonoblocks(blocks, cells)): File "C:/Users/Paddy/Google Drive/Code/nonoblocks.py", line 60, in nonoblocks 'Those blocks will not fit in those cells' AssertionError: Those blocks will not fit in those cells