pointset.rb

#!/usr/bin/ruby

def normalize_pointset(pointset)
  minx = 1000;
	miny = 1000;
	pointset.each{|p|
		minx = [minx, p[0]].min
		miny = [miny, p[1]].min
	}
	normalized_pointset = []
	pointset.each{|p|
		normalized_pointset.push([p[0]-minx, p[1]-miny])
	}
	return normalized_pointset
end

def get_order_number(pointset)
	order_number = 0
	(0..$ROWS-1).each{|y|
		(0..$COLS-1).each{|x|
			if pointset.index([x,y]) then
				pnum = y*4 + x;
				order_number *= 16;
				order_number += pnum;
			end
		}
	}
	return order_number;
end

def is_unique(pointset)
	pointset1 = []
	pointset2 = []
	pointset3 = []
	pointset.each{|p|
		pointset1.push([-p[1], p[0]])
		pointset2.push([p[1], -p[0]])
		pointset3.push([-p[0], -p[1]])
	}
	pointset1 = normalize_pointset(pointset1)
	pointset2 = normalize_pointset(pointset2)
	pointset3 = normalize_pointset(pointset3)
	order = get_order_number(pointset)
	order1 = get_order_number(pointset1)
	order2 = get_order_number(pointset2)
	order3 = get_order_number(pointset3)
	# print "order=#{order}, order1=#{order1}, order2=#{order2}, order3=#{order3}¥n"
	if order1 < order || order2 < order || order3 < order then
		return false
	end
	return true

end
def print_pointset(pointset)
	print "----¥n";
	pointset.each{|p|
		print "(#{p[0]}, #{p[1]})¥n"
	}
	(0..$ROWS-1).each{|y|
		(0..$COLS-1).each{|x|
			if pointset.index([x,y]) then
				print "o"
			else
				print "x"
			end
		}
		print "¥n";
	}
end

@total_uniq_patterns = 0;
def get_point(pointset, count, pos)
	if count == $POINTNUM then
		if ! is_unique(pointset) then
			return
		end
		print_pointset pointset
		@total_uniq_patterns = @total_uniq_patterns + 1
		return
	end
	(pos..($INDEXES-1)).each{|pos|
		x = pos % $COLS;
		y = pos / $COLS;
		if(count == 0 && y==1)then
			break
		end
		pointset.push([x,y]);
		get_point(pointset, count+1, pos+1)
		pointset.pop
	}
end


def usage
	print "blockpatterns [COLS] [ROWS] [POINTNUM]¥n"
end

if ARGV.length != 3
	usage
	exit(1)
end
$COLS=ARGV[0].to_i
$ROWS=ARGV[1].to_i
$INDEXES=$COLS * $ROWS
$POINTNUM=ARGV[2].to_i

get_point([], 0, 0);
print "total_uniq_patterns=#{@total_uniq_patterns}¥n"