Free polyominoes enumeration: Difference between revisions
Added Kotlin
m (→{{header|Java}}: small changes) |
(Added Kotlin) |
||
Line 822:
(0,0) (0,1) (0,2) (1,0) (2,0)
(0,0) (0,1) (0,2) (0,3) (0,4)</pre>
=={{header|Kotlin}}==
{{trans|Python}}
<lang scala>// version 1.1.51
class Point(val x: Int, val y: Int) : Comparable<Point> {
fun rotate90() = Point( this.y, -this.x)
fun rotate180() = Point(-this.x, -this.y)
fun rotate270() = Point(-this.y, this.x)
fun reflect() = Point(-this.x, this.y)
override fun equals(other: Any?): Boolean {
if (other == null || other !is Point) return false
return this.x == other.x && this.y == other.y
}
override fun compareTo(other: Point) =
if (this == other ) 0
else if (this.x < other.x || (this.x == other.x && this.y < other.y)) -1
else 1
override fun toString() = "($x, $y)"
}
typealias Polyomino = List<Point>
// Finds the min x and y coordinates of a Polyomino.
val Polyomino.minima get() = Pair(this.minBy { it.x }!!.x, this.minBy { it.y }!!.y)
fun Polyomino.translateToOrigin(): Polyomino {
val (minX, minY) = this.minima
return this.map { Point(it.x - minX, it.y - minY) }.sorted()
}
// All the plane symmetries of a rectangular region.
val Polyomino.rotationsAndReflections get() =
listOf(
this,
this.map { it.rotate90() },
this.map { it.rotate180() },
this.map { it.rotate270() },
this.map { it.reflect() },
this.map { it.rotate90().reflect() },
this.map { it.rotate180().reflect() },
this.map { it.rotate270().reflect() }
)
val Polyomino.canonical get() =
this.rotationsAndReflections.map { it.translateToOrigin() }.minBy { it.toString() }!!
// All four points in Von Neumann neighborhood
val Point.contiguous get() =
listOf(Point(x - 1, y), Point(x + 1, y), Point(x, y - 1), Point(x, y + 1))
// Finds all distinct points that can be added to a Polyomino.
val Polyomino.newPoints get() = this.flatMap { it.contiguous }.filter { it !in this }.distinct()
val Polyomino.newPolys get() = this.newPoints.map { (this + it).canonical }
val monomino = listOf(Point(0, 0))
val monominoes = listOf(monomino)
// Generates polyominoes of rank n recursively.
fun rank(n: Int): List<Polyomino> = when {
n < 0 -> throw IllegalArgumentException("n cannot be negative")
n == 0 -> emptyList<Polyomino>()
n == 1 -> monominoes
else -> rank(n - 1).flatMap { it.newPolys }
.distinctBy { it.toString() }
.sortedBy { it.toString() }
}
fun main(args: Array<String>) {
val n = 5
println("All free polyominoes of rank $n:\n")
for (poly in rank(n)) {
for (pt in poly) print("$pt ")
println()
}
val k = 10
println("\nNumber of free polyominoes of ranks 1 to $k:")
for (i in 1..k) print("${rank(i).size} ")
println()
}</lang>
{{out}}
<pre>
All free polyominoes of rank 5:
(0, 0) (0, 1) (0, 2) (0, 3) (0, 4)
(0, 0) (0, 1) (0, 2) (0, 3) (1, 0)
(0, 0) (0, 1) (0, 2) (0, 3) (1, 1)
(0, 0) (0, 1) (0, 2) (1, 0) (1, 1)
(0, 0) (0, 1) (0, 2) (1, 0) (1, 2)
(0, 0) (0, 1) (0, 2) (1, 0) (2, 0)
(0, 0) (0, 1) (0, 2) (1, 1) (2, 1)
(0, 0) (0, 1) (0, 2) (1, 2) (1, 3)
(0, 0) (0, 1) (1, 1) (1, 2) (2, 1)
(0, 0) (0, 1) (1, 1) (1, 2) (2, 2)
(0, 0) (0, 1) (1, 1) (2, 1) (2, 2)
(0, 1) (1, 0) (1, 1) (1, 2) (2, 1)
Number of free polyominoes of ranks 1 to 10:
1 1 2 5 12 35 108 369 1285 4655
</pre>
=={{header|Python}}==
| |||