#!/usr/bin/ruby

# gen all possible shapes with a given nr of componants, ignoring dupes (reoriented)

# (c) 2009 y guillot
# distributes under the terms of the WtfPLv2

def xy2pt(x, y)
	#[x, y]	# suboptimal
	x + (y<<8)
end

def pt2xy(pt)
	#pt	# suboptimal
	[pt&255, (pt>>8) & 255]
end

# add 1 box to curpath, recurse until sz == cnt, add all mutants to all
def gen_shape(all, cur, cnt)
	if cnt <= 1
		all << cur
	else
		new_shape(cur).each { |ns|
			gen_shape(all, ns, cnt-1)
		}
	end
end

# generate new shapes from sh: add all possible random neighbours
def new_shape(sh)
	neigh = []
	sh.each { |pt|
		x, y = pt2xy(pt)
		neigh << xy2pt(x+1, y) << xy2pt(x, y+1)
		neigh << xy2pt(x-1, y) if x > 0
		neigh << xy2pt(x, y-1) if y > 0
	}
	neigh -= sh
	neigh.uniq.sort.map { |n|
		sh + [n]
	}
end

# move all shapes to upleft, sort boxes, uniq!
def normalize(ar)
	ar.each { |sh|
		mx = sh.map { |pt| pt2xy(pt)[0] }.min
		my = sh.map { |pt| pt2xy(pt)[1] }.min
		sh.map! { |pt| x, y = pt2xy(pt) ; xy2pt(x-mx, y-my) }
		sh.sort!
	}
	ar.uniq!
	ar
end

def normalize_all(ar)
	# optimize, knowing that all boxes start at y=0 and pt encoding
	ar.each { |sh|
		mx = sh.map { |pt| pt & 255 }.min
		sh.map! { |pt| pt-mx }
		sh.sort!
	}
	ar.uniq!
	ar
end


# generate rotated/mirrored variants of a shape
def symetrize(sh)
	ar = [sh]
	ar = ar + ar.map { |s| s.map { |pt| x, y = pt2xy(pt) ; xy2pt(255-x, y) } }	# vt mirror
	ar = ar + ar.map { |s| s.map { |pt| x, y = pt2xy(pt) ; xy2pt(x, 255-y) } }	# hz mirror
	ar = ar + ar.map { |s| s.map { |pt| x, y = pt2xy(pt) ; xy2pt(y, x) } }		# diag mirror
	normalize(ar)
end

# remove dups/symetrics from ar
def uniq(ar)
	all = ar.dup
	ar.clear
	while sh = all.shift
		ar << sh
		all -= symetrize(sh)
	end
	ar
end

# show shapes on stdout
def display(ar)
	puts "cnt: #{ar.length}"
#return
	ar.each { |sh|
		str = []
		sh.each { |pt|
			x, y = pt2xy(pt)
			str[y] ||= '  ' * sh.length
			str[y][2*x, 2] = '[]'
		}
		puts str, ''
	}
end


(4..6).each { |cnt|
	# nr of elements
	puts cnt
	all = []
	(0..cnt/2).each { |p1|
		gen_shape(all, [xy2pt(p1, 0)], cnt)
	}
	normalize_all(all)
	uniq(all)
	display(all)
}