def _sum(enum) ret = 0; enum.each { |v| ret += v } return ret end def _build_choice(info, size, positions) choice = Array.new(size, 0) offset = 0 positions.each_with_index do |p, i| offset += p info[i].times { |j| choice[offset+j] = 1 } offset += info[i]+1 end return choice end def make_choices(info, size) whites = size + 1 - info.length - _sum(info); choices = [] positions = Array.new(info.length, 0) while true choices << _build_choice(info, size, positions) break if positions[0] == whites if _sum(positions) == whites i = -1; i -= 1 while positions[i] == 0 positions[i] = 0 positions[i-1] += 1 else positions[-1] += 1 end end return choices end def find_sure_values(choices) sure_values = choices[0].dup sure_values.length.times do |i| j = 0 while sure_values[i] and j < choices.length sure_values[i] = nil if choices[j][i] != sure_values[i] j += 1 end end return sure_values end def put_sure_values(map, sure_values, rowcolid, is_row) sure_values.each_with_index do |v,i| if is_row map[rowcolid][i] = v if v else map[i][rowcolid] = v if v end end end def limit_choices(sure_values, choices) return choices.select do |choice| is_okay = true i = 0 while is_okay and i < choice.length is_okay = false if sure_values[i] and sure_values[i] != choice[i] i += 1 end is_okay end end def get_row(map, id) map[id] end def get_col(map, id) (0...map.length).collect{|i|map[i][id]} end def dump_map(map) solved = true sym = [ ".", "X" ] mapdump = map.collect{ |row| row.collect{ |f| solved = false if not f; f ? sym[f] : " " }.join + "\n" }.join if solved $stderr.puts mapdump exit end end def progress_start(message, total) backspace = "\b"*(message.length+8) $prg_message = backspace + message + "... " $prg_total = total; $prg_current = 0 $prg_last = 0 $stderr.print $prg_message end def progress() $prg_current += 1 if 100*$prg_current/$prg_total != $prg_last $prg_last = 100*$prg_current/$prg_total $stderr.print $prg_message + $prg_last.to_s + "%" end end def progress_end() $stderr.puts $prg_message + "done!" end def one_step(map, w, h, row_choices, col_choices, showprg) # put sure values progress_start("computing field colors", w+h) if showprg h.times { |row| put_sure_values(map, find_sure_values(row_choices[row]), row, true); progress if showprg } w.times { |col| put_sure_values(map, find_sure_values(col_choices[col]), col, false); progress if showprg } progress_end() if showprg # limit choices progress_start("limiting row/column choices", w+h) if showprg h.times { |row| row_choices[row] = limit_choices(get_row(map, row), row_choices[row]); progress if showprg } w.times { |col| col_choices[col] = limit_choices(get_col(map, col), col_choices[col]); progress if showprg } progress_end() if showprg end def solve(rows, cols) w = cols.length; h = rows.length map = Array.new(h).map{ Array.new(w) } progress_start("initializing row/column choices", w+h) row_choices = rows.map{ |info| progress; make_choices(info, w) } col_choices = cols.map{ |info| progress; make_choices(info, h) } progress_end() first_run = true while true one_step(map, w, h, row_choices, col_choices, first_run); first_run = false dump_map(map) end end def read_array(file) data = [] while true line = file.readline return data if line.chomp == "---" data << line.gsub(/\D+/, " ").strip.split(" ").map{ |s| s.to_i } end end rows = read_array($stdin) cols = read_array($stdin) solve(rows, cols)