Just tinkering with some algorithms to solve a nonogram

blocks.rb

#! /usr/bin/env ruby

require 'matrix'

# puts "▀▁▂▃▄▅▆▇█▉▊▋▌▍▎▏▐░▒▓▔▕▖▗▘▙▚▛▜▝▞▟"

EMPTY = ' '
BLOCK = '░'
BOX   = '█'

ARGV.map!(&:to_i)

def box_possibilities(max_blocks, boxes)
  total_blocks = boxes.reduce(&:+)

  # free_areas are the areas within the boxes. Eg:
  # ░██░░ => A box with two blocks surrounded by two free areas
  # ░██░██░ => Two boxes with three free areas around them
  # ██░░░ => A box with 2 free areas around it (the leftmost has value 0)
  free_areas   = boxes.count + 1
  free_blocks  = max_blocks - total_blocks

  # Here we generate all possible permutations from
  # zero to the number of free blocks on all free areas
  all_possibilities = (0..free_blocks).to_a.repeated_permutation(free_areas)

  # Now we filter all the real possibilities. 
  real_possibilities = all_possibilities.reject do |possibility|
    possibility[1...-1].any?(0) || possibility.reduce(&:+) != free_blocks
  end

  real_possibilities.map! do |p|
    line = p.zip(boxes).flatten.compact

    line.map!.with_index do |l, index|
      Array.new(l) { index.odd? }
    end

    line.flatten
  end

  Matrix[*real_possibilities].column_vectors.map { |vector| vector.all? true }
end

box_possibilities(ARGV.shift, ARGV).each do |pos|
  if pos
    print BOX
  else
    print BLOCK
  end
end

puts ''