Free polyominoes enumeration: Difference between revisions
Content added Content deleted
(Added c# version) |
(Added Sidef) |
||
Line 2,057: | Line 2,057: | ||
(0,0) (0,1) (0,2) (1,0) (2,0) |
(0,0) (0,1) (0,2) (1,0) (2,0) |
||
(0,0) (0,1) (0,2) (0,3) (0,4)</pre> |
(0,0) (0,1) (0,2) (0,3) (0,4)</pre> |
||
=={{header|Sidef}}== |
|||
{{trans|Ruby}} |
|||
<lang ruby>func translate2origin(poly) { |
|||
# Finds the min x and y coordiate of a Polyomino. |
|||
var minx = poly.map(:head).min |
|||
var miny = poly.map(:tail).min |
|||
poly.map {|p| [p.head-minx, p.tail-miny] }.sort |
|||
} |
|||
func rotate90(x,y) { [y, -x] } |
|||
func reflect(x,y) { [-x, y] } |
|||
# All the plane symmetries of a rectangular region. |
|||
func rotations_and_reflections(poly) { |
|||
gather { |
|||
take(poly) |
|||
take(poly.map!{ rotate90(_...) }) |
|||
take(poly.map!{ rotate90(_...) }) |
|||
take(poly.map!{ rotate90(_...) }) |
|||
take(poly.map!{ reflect(_...) }) |
|||
take(poly.map!{ rotate90(_...) }) |
|||
take(poly.map!{ rotate90(_...) }) |
|||
take(poly.map!{ rotate90(_...) }) |
|||
} |
|||
} |
|||
func canonical(poly) { |
|||
rotations_and_reflections(poly).map{|pl| translate2origin(pl) } |
|||
} |
|||
# All four points in Von Neumann neighborhood. |
|||
func contiguous(x, y) { |
|||
[[x-1, y], [x+1, y], [x, y-1], [x, y+1]] |
|||
} |
|||
# Finds all distinct points that can be added to a Polyomino. |
|||
func new_points(poly) { |
|||
var points = Set() |
|||
poly.each { points << contiguous(_...)... } |
|||
points - poly |
|||
} |
|||
func new_polys(polys) { |
|||
var pattern = Set() |
|||
polys.map { |poly| |
|||
gather { |
|||
new_points(poly).each { |point| |
|||
var pl = translate2origin(poly + [point]) |
|||
next if pattern.has(pl) |
|||
take canonical(pl).each{ pattern << _ }.min |
|||
} |
|||
}... |
|||
} |
|||
} |
|||
# Generates polyominoes of rank n recursively. |
|||
func rank(n) { |
|||
given (n) { |
|||
when (0) { [[]] } |
|||
when (1) { [[[0,0]]] } |
|||
else { new_polys(rank(n-1)) } |
|||
} |
|||
} |
|||
# Generates a textual representation of a Polyomino. |
|||
func text_representation(poly) { |
|||
var table = Hash() |
|||
for x,y in (poly) { table{[x,y]} = '#' } |
|||
var maxx = poly.map(:head).max |
|||
var maxy = poly.map(:tail).max |
|||
(0..maxx).map{|x| (0..maxy).map{|y| table{[x,y]} \\ ' ' }.join } |
|||
} |
|||
say 8.of { rank(_).len } |
|||
var n = (ARGV[0] ? ARGV[0].to_i : 5) |
|||
say ("\nAll free polyominoes of rank %d:" % n) |
|||
rank(n).sort.each{|poly| say text_representation(poly).join("\n")+"\n" }</lang> |
|||
{{out}} |
|||
<pre style="height:250px"> |
|||
[1, 1, 1, 2, 5, 12, 35, 108] |
|||
All free polyominoes of rank 5: |
|||
##### |
|||
#### |
|||
# |
|||
#### |
|||
# |
|||
### |
|||
## |
|||
### |
|||
# # |
|||
### |
|||
# |
|||
# |
|||
### |
|||
# |
|||
# |
|||
### |
|||
## |
|||
## |
|||
## |
|||
# |
|||
## |
|||
## |
|||
# |
|||
## |
|||
# |
|||
## |
|||
# |
|||
### |
|||
# |
|||
</pre> |