# 
# Distributes under the terms of the WTFPL v2 
# (c) Guillot Yoann 2008
#
# a picross solver, written in ruby
#
# usage: ruby picross.rb <szh>[x<szv>] l1 l2 l3 l4 ... c1 c2 c3 c4
#
# ex: ruby picross.rb 5x4  1 1,1 3 1,1  0 3 1,1 3 0
#

class Grid
	Unknown = ?.
	Present = ?x
	Absent  = ?\ 

	attr_accessor :sizeh, :sizev, :constraints
	def initialize(szh, szv=szh)
		@sizeh = szh
		@sizev = szv
		@lines = Unknown.chr * @sizeh * @sizev
	end

	def constraints(lines, cols)
		@constraints = { :line => lines, :col => cols }
		update_possible
		throw :impossible if (@possible[:line]+@possible[:col]).include? []
	end

	def dup
		o = Grid.new(@sizeh, @sizev)
		o.constraints = @constraints
		o.update_possible
		@sizeh.times { |x| @sizev.times { |y| o[x, y] = self[x, y] } }
		o
	end

	def to_s
		'/' +'-'*(@sizeh*2-1)+'\\'+"\n"+
		@lines.unpack("a#@sizeh"*@sizev).map { |l| '|' + l.unpack('a'*@sizeh).join(' ') + '|' + "\n" }.join +
		'\\'+'-'*(@sizeh*2-1)+'/'
	end

	def [](x, y)
		@lines[y*@sizeh+x]
	end

	def []=(x, y, v)
		@lines[y*@sizeh+x] = v
		if v != Unknown and defined? @possible
			@possible[:line][y].delete_if { |p| p[x] != Unknown and p[x] != v }
			@possible[:col ][x].delete_if { |p| p[y] != Unknown and p[y] != v }
			throw :impossible if (@possible[:line]+@possible[:col]).include? []
		end
	end

	def solve_step
		xprev = nil
		while xprev != @lines
		xprev = @lines.dup

		prev_lines = nil
		while prev_lines != @lines
		prev_lines = @lines.dup
		@sizeh.times { |x| @sizev.times { |y|
			pl = @possible[:line][y]
			if pl[0][x] != Unknown and pl.all? { |l| pl[0][x] == l[x] }
				self[x, y] = pl[0][x]
				pl = @possible[:line][y]
			end
		} }
		end
puts self if @lines.index Unknown

		prev_lines = nil
		while prev_lines != @lines
		prev_lines = @lines.dup
		@sizeh.times { |x| @sizev.times { |y|
			pc = @possible[:col][x]
			if pc[0][y] != Unknown and pc.all? { |c| pc[0][y] == c[y] }
				self[x, y] = pc[0][y]
				pc = @possible[:col ][x]
			end
		} }
		end
puts self if @lines.index Unknown
		end
	end

	def update_possible
		@possible ||= {:line => [], :col => []}
		[:line, :col].each { |dir|
			(dir == :line ? @sizev : @sizeh).times { |i|
				if not p = @possible[dir][i]
					p = @possible[dir][i] = []
					cst = @constraints[dir][i]
					margin = (dir == :line ? @sizeh : @sizev) - cst.inject { |a, b| a+b }
					foo = proc { |base, marg, cstr|
						if seqlen = cstr[0]
							(0..marg).each { |m|
								if cstr[1]
									foo[base + Absent.chr*m + Present.chr*seqlen + Absent.chr, marg-m-1, cstr[1..-1]]
								else
									foo[base + Absent.chr*m + Present.chr*seqlen, marg-m, cstr[1..-1]]
								end
							}
						else
							p << (base + Absent.chr*marg)
						end
					}
					foo['', margin, cst]

				end
				(dir == :line ? @sizeh : @sizev).times { |j| p.delete_if { |l| v = (dir == :line ? self[i, j] : self[j, i]) and v != Unknown and v != l[j] } }
			}
		}
	end

	def solve
		self.class.solve(self)
	end

	def self.solve(g)
		g.solve_step
		g.sizeh.times { |x| g.sizev.times { |y|
				if g[x, y] == Unknown
					puts "bruteforce [#{x}, #{y}]"
					catch(:impossible) {
						d = g.dup
						d[x, y] = Present
						solve(d)
					}
					catch(:impossible) {
						d = g.dup
						d[x, y] = Absent
						solve(d)
					}
					return
				end
		} }
		puts g
	end

end

if $0 == __FILE__
	if ARGV.empty?
		ARGV << '5x4' << '1' << '1,1' << '3' << '1,1' << '0' << '3' << '1,1' << '3' << '0'
	end

	sz = ARGV.shift.split('x').map { |i| i.to_i }
	sz[1] ||= sz[0]
	c = ARGV.map { |a| a.split(',').map { |i| i.to_i } }
	raise "bad constrainst count" if c.length != sz[0] + sz[1]
	g = Grid.new sz[0], sz[1]
	g.constraints c[0, sz[1]], c[sz[1], sz[0]]
	g.solve
end