Nonoblock

Nonoblock is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

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

1. 5 cells and [2, 1] blocks
2. 5 cells and [] blocks (no blocks)
3. 10 cells and [8] blocks
4. 15 cells and [2, 3, 2, 3] blocks
5. 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

Translation of: 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>

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