Nonoblock

Nonoblock is a chip of 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.

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