Skip to content

Instantly share code, notes, and snippets.

@mark
Created August 15, 2018 18:13
Show Gist options
  • Save mark/268310acabc7dee96113d250113e719b to your computer and use it in GitHub Desktop.
Save mark/268310acabc7dee96113d250113e719b to your computer and use it in GitHub Desktop.
Fill in partial row clues for a nonagram row
CHAR_TO_CELL = { '_' => :unknown, 'x' => :empty, '#' => :full, '?' => :multiple }
CELL_TO_CHAR = { empty: 'X', full: '#', multiple: '_', unknown: '_' }
def expand_row raw_row
split = raw_row.split /([_X#]\d*)/
items = split.reject { |s| s == '' }
items.map do |item|
item[0] * [1, item[1..-1].to_i].max
end.join.split('').map { |c| CHAR_TO_CELL[c] }
end
def sum(nums)
nums.inject(0) { |s, v| s + v }
end
def distributions(count, buckets)
return [[0] * buckets] if count == 0
return [[count]] if buckets == 1
(0..count).map do |first|
rest = distributions(count - first, buckets - 1)
rest.map { |r| [first] + r }
end.flatten(1)
end
def build_row(clues, gaps)
adjusted_gaps = gaps.map { |c| c + 1 }
adjusted_gaps[0] -= 1
adjusted_gaps[-1] -= 1
adjusted_gaps.zip(clues).map do |gap, clue|
[:empty] * gap + [:full] * (clue || 0)
end.flatten
end
def compatible?(row1, row2)
row1.zip(row2).none? do |c1, c2|
(c1 == :empty && c2 == :full) || (c1 == :full && c2 == :empty)
end
end
def merge(row1, row2)
row1.zip(row2).map { |c1, c2| (c1 == :unknown || c1 == c2) ? c2 : :multiple }
end
def row_to_string(r)
r.map { |c| CELL_TO_CHAR[c] }.join
end
row = expand_row ARGV[0].downcase
clues = ARGV[1..-1].map &:to_i
total_accounted_for = sum(clues) + (clues.length - 1)
total_missing = row.length - total_accounted_for
total_gaps = clues.length + 1
possible_gaps = distributions(total_missing, total_gaps)
possible_rows = possible_gaps.map { |gaps| build_row(clues, gaps) }
compatible_rows = possible_rows.select { |r| compatible?(r, row) }
merged_row = compatible_rows.inject(row) { |comb, r| merge(comb, r) }
puts row_to_string(merged_row)
Marks-MacBook-Pro:code_scaps markjosef$ ruby nonagram_row.rb '_15' 13 1
#############X#
Marks-MacBook-Pro:code_scaps markjosef$ ruby nonagram_row.rb '_15' 10
_____#####_____
Marks-MacBook-Pro:code_scaps markjosef$ ruby nonagram_row.rb '_15' 4 7
___#____####___
Marks-MacBook-Pro:code_scaps markjosef$ ruby nonagram_row.rb '_7#_7' 4 7
__##___#####__X
Marks-MacBook-Pro:code_scaps markjosef$ ruby nonagram_row.rb '_7X_7' 4 7
___#___X#######
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment