Free polyominoes enumeration: Difference between revisions
Content added Content deleted
(Added Kotlin) |
(add Scala code) |
||
Line 822: | Line 822: | ||
(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|Scala}}== |
|||
Translation of [[Free_polyominoes_enumeration#Haskell|Haskell]] via [[Free_polyominoes_enumeration#D|D]] |
|||
{{works with|Scala|2.12}} |
|||
<lang Scala>object Free { |
|||
type Point = (Int, Int) |
|||
type Polyomino = List[Point] |
|||
def rotate90(p: Point): Point = (p._2, -p._1) |
|||
def rotate180(p: Point): Point = (-p._1, -p._2) |
|||
def rotate270(p: Point): Point = (-p._2, p._1) |
|||
def reflect(p: Point): Point = (-p._1, p._2) |
|||
def minima(polyomino: Polyomino): Point = { |
|||
polyomino.reduce((a,b) => (Math.min(a._1, b._1), Math.min(a._2, b._2))) |
|||
} |
|||
def translateToOrigin(polyomino: Polyomino): Polyomino = { |
|||
val m = minima(polyomino) |
|||
polyomino.map(p => (p._1 - m._1, p._2 - m._2)) |
|||
} |
|||
def rotationsAndReflections(polyomino: Polyomino): List[Polyomino] = { |
|||
val refPol = polyomino.map(reflect) |
|||
List( |
|||
polyomino, |
|||
polyomino.map(rotate90), |
|||
polyomino.map(rotate180), |
|||
polyomino.map(rotate270), |
|||
refPol, |
|||
refPol.map(rotate90), // === pol |
|||
refPol.map(rotate180), |
|||
refPol.map(rotate270), |
|||
) |
|||
} |
|||
def canonical(polyomino: Polyomino): Polyomino = { |
|||
import Ordering.Implicits._ |
|||
val rot = rotationsAndReflections(polyomino) |
|||
val rot1 = rot.map(translateToOrigin) |
|||
val rot2 = rot1.map(poly => poly.sorted) |
|||
val rots = rot1.take(1).sorted |
|||
val rot3 = rot2.min |
|||
rotationsAndReflections(polyomino) |
|||
.map(translateToOrigin) |
|||
.map(poly => poly.sorted).min |
|||
} |
|||
def contiguous(p: Point): List[Point] = List( |
|||
(p._1 - 1, p._2), |
|||
(p._1 + 1, p._2), |
|||
(p._1, p._2 - 1), |
|||
(p._1, p._2 + 1), |
|||
) |
|||
def newPoints(polyomino: Polyomino): List[Point] = { |
|||
polyomino.flatMap(contiguous).filterNot(polyomino.contains(_)).distinct |
|||
} |
|||
def newPolyominos(polyomino: Polyomino): List[Polyomino] = { |
|||
newPoints(polyomino).map(p => canonical(p :: polyomino)).distinct |
|||
} |
|||
val monomino: Polyomino = List((0, 0)) |
|||
val monominos: List[Polyomino] = List(monomino) |
|||
def rank(n: Int): List[Polyomino] = { |
|||
require(n >= 0) |
|||
n match { |
|||
case 0 => Nil |
|||
case 1 => monominos |
|||
case _ => rank(n - 1).flatMap(newPolyominos).distinct |
|||
} |
|||
} |
|||
}</lang> |
|||
<pre>(0,0) (0,1) (1,1) (1,2) (2,1) |
|||
(0,0) (0,1) (0,2) (1,0) (1,1) |
|||
(0,0) (0,1) (0,2) (0,3) (1,1) |
|||
(0,1) (1,0) (1,1) (1,2) (2,1) |
|||
(0,0) (0,1) (0,2) (1,1) (2,1) |
|||
(0,0) (0,1) (1,1) (1,2) (2,2) |
|||
(0,0) (0,1) (0,2) (1,2) (1,3) |
|||
(0,0) (0,1) (1,1) (2,1) (2,2) |
|||
(0,0) (0,1) (0,2) (1,0) (1,2) |
|||
(0,0) (0,1) (0,2) (0,3) (1,0) |
|||
(0,0) (0,1) (0,2) (1,0) (2,0) |
|||
(0,0) (0,1) (0,2) (0,3) (0,4)</pre> |
|||
=={{header|Kotlin}}== |
=={{header|Kotlin}}== |