Skip to content

Instantly share code, notes, and snippets.

@DNA

DNA/blocks.rb

Last active Dec 20, 2019
Embed
What would you like to do?
Just tinkering with some algorithms to solve a nonogram
#! /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 ''
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment