summaryrefslogtreecommitdiff
path: root/test/pending/shootout/meteor.scala-2.scala
diff options
context:
space:
mode:
Diffstat (limited to 'test/pending/shootout/meteor.scala-2.scala')
-rw-r--r--test/pending/shootout/meteor.scala-2.scala496
1 files changed, 0 insertions, 496 deletions
diff --git a/test/pending/shootout/meteor.scala-2.scala b/test/pending/shootout/meteor.scala-2.scala
deleted file mode 100644
index 2b42c19260..0000000000
--- a/test/pending/shootout/meteor.scala-2.scala
+++ /dev/null
@@ -1,496 +0,0 @@
-/* The Computer Language Shootout
- http://shootout.alioth.debian.org/
- contributed by Isaac Gouy
-*/
-
-// This is an un-optimised example implementation
-// classes BoardCell and PieceCell have Array
-
-
-import scala.collection.mutable._
-
-object meteor {
- def main(args: Array[String]) = {
- val solver = new Solver( Integer.parseInt(args(0)) )
- solver.findSolutions
- solver.printSolutions
- }
-}
-
-
-
-
-// Solver.scala
-// import scala.collection.mutable._
-
-final class Solver (n: Int) {
- private var countdown = n
- private var first: String = _
- private var last: String = _
-
- private val board = new Board()
-
- val pieces = Array(
- new Piece(0), new Piece(1), new Piece(2), new Piece(3), new Piece(4),
- new Piece(5), new Piece(6), new Piece(7), new Piece(8), new Piece(9) )
-
- val unplaced = new BitSet(pieces.length)
-
- { unplaced ++= (0 until pieces.length) }
-
-
- def findSolutions(): Unit = {
- if (countdown == 0) return
-
- if (unplaced.size > 0){
- val emptyCellIndex = board.firstEmptyCellIndex
-
- for (k <- Iterator.range(0,pieces.length)){
- if (unplaced.contains(k)){
- unplaced -= k
-
- for (i <- Iterator.range(0,Piece.orientations)){
- val piece = pieces(k).nextOrientation
-
- for (j <- Iterator.range(0,Piece.size)){
- if (board.add(j,emptyCellIndex,piece)) {
-
- if (!shouldPrune) findSolutions
-
- board.remove(piece)
- }
- }
- }
- unplaced += k
- }
- }
- }
- else {
- puzzleSolved
- }
- }
-
- private def puzzleSolved() = {
- val b = board.asString
- if (first == null){
- first = b; last = b
- } else {
- if (b < first){ first = b } else { if (b > last){ last = b } }
- }
- countdown = countdown - 1
- }
-
- private def shouldPrune() = {
- board.unmark
- !board.cells.forall(c => c.contiguousEmptyCells % Piece.size == 0)
- }
-
-
- def printSolutions() = {
-
- def printBoard(s: String) = {
- var indent = false
- var i = 0
- while (i < s.length){
- if (indent) Console.print(' ')
- for (j <- Iterator.range(0,Board.cols)){
- Console.print(s.charAt(i)); Console.print(' ')
- i = i + 1
- }
- Console.print('\n')
- indent = !indent
- }
- Console.print('\n')
- }
-
- Console.print(n + " solutions found\n\n")
- printBoard(first)
- printBoard(last)
- }
-
-/*
- def printPieces() =
- for (i <- Iterator.range(0,Board.pieces)) pieces(i).print
-*/
-
-}
-
-
-
-
-// Board.scala
-// import scala.collection.mutable._
-
-object Board {
- val cols = 5
- val rows = 10
- val size = rows * cols
-}
-
-final class Board {
- val cells = boardCells()
-
- val cellsPieceWillFill = new Array[BoardCell](Piece.size)
- var cellCount = 0
-
- def unmark() = for (c <- cells) c.unmark
-
- def asString() =
- new String( cells map(
- c => if (c.piece == null) '-'.toByte
- else (c.piece.number + 48).toByte ))
-
- def firstEmptyCellIndex() = cells.findIndexOf(c => c.isEmpty)
-
-
- def add(pieceIndex: Int, boardIndex: Int, p: Piece) = {
- cellCount = 0
- p.unmark
-
- find( p.cells(pieceIndex), cells(boardIndex))
-
- val boardHasSpace = cellCount == Piece.size &&
- cellsPieceWillFill.forall(c => c.isEmpty)
-
- if (boardHasSpace) cellsPieceWillFill.foreach(c => c.piece = p)
-
- boardHasSpace
- }
-
- def remove(piece: Piece) = for (c <- cells; if c.piece == piece) c.empty
-
-
- private def find(p: PieceCell, b: BoardCell): Unit = {
- if (p != null && !p.marked && b != null){
- cellsPieceWillFill(cellCount) = b
- cellCount = cellCount + 1
- p.mark
- for (i <- Iterator.range(0,Cell.sides)) find(p.next(i), b.next(i))
- }
- }
-
-
- private def boardCells() = {
- val a = for (i <- Array.range(0,Board.size)) yield new BoardCell(i)
- val m = (Board.size / Board.cols) - 1
-
- for (i <- Iterator.range(0,a.length)){
- val row = i / Board.cols
- val isFirst = i % Board.cols == 0
- val isLast = (i+1) % Board.cols == 0
- val c = a(i)
-
- if (row % 2 == 1) {
- if (!isLast) c.next(Cell.NE) = a(i-(Board.cols-1))
- c.next(Cell.NW) = a(i-Board.cols)
- if (row != m) {
- if (!isLast) c.next(Cell.SE) = a(i+(Board.cols+1))
- c.next(Cell.SW) = a(i+Board.cols)
- }
- } else {
- if (row != 0) {
- if (!isFirst) c.next(Cell.NW) = a(i-(Board.cols+1))
- c.next(Cell.NE) = a(i-Board.cols)
- }
- if (row != m) {
- if (!isFirst) c.next(Cell.SW) = a(i+(Board.cols-1))
- c.next(Cell.SE) = a(i+Board.cols)
- }
- }
- if (!isFirst) c.next(Cell.W) = a(i-1)
- if (!isLast) c.next(Cell.E) = a(i+1)
- }
- a
- }
-
-
-/*
-// Printing all the board cells and their neighbours
-// helps check that they are connected properly
-
- def printBoardCellsAndNeighbours() = {
- Console.println("cell\tNW NE W E SW SE")
- for (i <- Iterator.range(0,Board.size)){
- Console.print(i + "\t")
- for (j <- Iterator.range(0,Cell.sides)){
- val c = cells(i).next(j)
- if (c == null)
- Console.print("-- ")
- else
- Console.printf("{0,number,00} ")(c.number)
- }
- Console.println("")
- }
- Console.println("")
- }
-*/
-
-}
-
-
-
-
-// Piece.scala
-
-object Piece {
- val size = 5
- val rotations = Cell.sides
- val flips = 2
- val orientations = rotations * flips
-}
-
-final class Piece(_number: Int) {
- val number = _number
- val cells = for (i <- Array.range(0,Piece.size)) yield new PieceCell()
-
- {
- number match {
- case 0 => make0
- case 1 => make1
- case 2 => make2
- case 3 => make3
- case 4 => make4
- case 5 => make5
- case 6 => make6
- case 7 => make7
- case 8 => make8
- case 9 => make9
- }
- }
-
- def flip() = for (c <- cells) c.flip
- def rotate() = for (c <- cells) c.rotate
- def unmark() = for (c <- cells) c.unmark
-
-
- private var orientation = 0
-
- def nextOrientation() = {
- if (orientation == Piece.orientations) orientation = 0
- if (orientation % Piece.rotations == 0) flip else rotate
- orientation = orientation + 1
- this
- }
-
-
- private def make0() = {
- cells(0).next(Cell.E) = cells(1)
- cells(1).next(Cell.W) = cells(0)
- cells(1).next(Cell.E) = cells(2)
- cells(2).next(Cell.W) = cells(1)
- cells(2).next(Cell.E) = cells(3)
- cells(3).next(Cell.W) = cells(2)
- cells(3).next(Cell.SE) = cells(4)
- cells(4).next(Cell.NW) = cells(3)
- }
-
- private def make1() = {
- cells(0).next(Cell.SE) = cells(1)
- cells(1).next(Cell.NW) = cells(0)
- cells(1).next(Cell.SW) = cells(2)
- cells(2).next(Cell.NE) = cells(1)
- cells(2).next(Cell.W) = cells(3)
- cells(3).next(Cell.E) = cells(2)
- cells(3).next(Cell.SW) = cells(4)
- cells(4).next(Cell.NE) = cells(3)
- }
-
- private def make2() = {
- cells(0).next(Cell.W) = cells(1)
- cells(1).next(Cell.E) = cells(0)
- cells(1).next(Cell.SW) = cells(2)
- cells(2).next(Cell.NE) = cells(1)
- cells(2).next(Cell.SE) = cells(3)
- cells(3).next(Cell.NW) = cells(2)
- cells(3).next(Cell.SE) = cells(4)
- cells(4).next(Cell.NW) = cells(3)
- }
-
- private def make3() = {
- cells(0).next(Cell.SW) = cells(1)
- cells(1).next(Cell.NE) = cells(0)
- cells(1).next(Cell.W) = cells(2)
- cells(2).next(Cell.E) = cells(1)
- cells(1).next(Cell.SW) = cells(3)
- cells(3).next(Cell.NE) = cells(1)
- cells(2).next(Cell.SE) = cells(3)
- cells(3).next(Cell.NW) = cells(2)
- cells(3).next(Cell.SE) = cells(4)
- cells(4).next(Cell.NW) = cells(3)
- }
-
- private def make4() = {
- cells(0).next(Cell.SE) = cells(1)
- cells(1).next(Cell.NW) = cells(0)
- cells(1).next(Cell.SW) = cells(2)
- cells(2).next(Cell.NE) = cells(1)
- cells(1).next(Cell.E) = cells(3)
- cells(3).next(Cell.W) = cells(1)
- cells(3).next(Cell.SE) = cells(4)
- cells(4).next(Cell.NW) = cells(3)
- }
-
- private def make5() = {
- cells(0).next(Cell.SW) = cells(1)
- cells(1).next(Cell.NE) = cells(0)
- cells(0).next(Cell.SE) = cells(2)
- cells(2).next(Cell.NW) = cells(0)
- cells(1).next(Cell.SE) = cells(3)
- cells(3).next(Cell.NW) = cells(1)
- cells(2).next(Cell.SW) = cells(3)
- cells(3).next(Cell.NE) = cells(2)
- cells(3).next(Cell.SW) = cells(4)
- cells(4).next(Cell.NE) = cells(3)
- }
-
- private def make6() = {
- cells(0).next(Cell.SW) = cells(1)
- cells(1).next(Cell.NE) = cells(0)
- cells(2).next(Cell.SE) = cells(1)
- cells(1).next(Cell.NW) = cells(2)
- cells(1).next(Cell.SE) = cells(3)
- cells(3).next(Cell.NW) = cells(1)
- cells(3).next(Cell.SW) = cells(4)
- cells(4).next(Cell.NE) = cells(3)
- }
-
- private def make7() = {
- cells(0).next(Cell.SE) = cells(1)
- cells(1).next(Cell.NW) = cells(0)
- cells(0).next(Cell.SW) = cells(2)
- cells(2).next(Cell.NE) = cells(0)
- cells(2).next(Cell.SW) = cells(3)
- cells(3).next(Cell.NE) = cells(2)
- cells(3).next(Cell.SE) = cells(4)
- cells(4).next(Cell.NW) = cells(3)
- }
-
- private def make8() = {
- cells(0).next(Cell.E) = cells(1)
- cells(1).next(Cell.W) = cells(0)
- cells(1).next(Cell.E) = cells(2)
- cells(2).next(Cell.W) = cells(1)
- cells(2).next(Cell.NE) = cells(3)
- cells(3).next(Cell.SW) = cells(2)
- cells(3).next(Cell.E) = cells(4)
- cells(4).next(Cell.W) = cells(3)
- }
-
- private def make9() = {
- cells(0).next(Cell.E) = cells(1)
- cells(1).next(Cell.W) = cells(0)
- cells(1).next(Cell.E) = cells(2)
- cells(2).next(Cell.W) = cells(1)
- cells(2).next(Cell.NE) = cells(3)
- cells(3).next(Cell.SW) = cells(2)
- cells(2).next(Cell.E) = cells(4)
- cells(4).next(Cell.W) = cells(2)
- cells(4).next(Cell.NW) = cells(3)
- cells(3).next(Cell.SE) = cells(4)
- }
-
-/*
- def print() = {
- Console.println("Piece # " + number)
- Console.println("cell\tNW NE W E SW SE")
- for (i <- Iterator.range(0,Piece.size)){
- Console.print(i + "\t")
- for (j <- Iterator.range(0,Cell.sides)){
- val c = cells(i).next(j)
- if (c == null)
- Console.print("-- ")
- else
- for (k <- Iterator.range(0,Piece.size)){
- if (cells(k) == c) Console.printf(" {0,number,0} ")(k)
- }
- }
- Console.println("")
- }
- Console.println("")
- }
-*/
-
-}
-
-
-
-
-// Cell.scala
-
-object Cell {
- val NW = 0; val NE = 1
- val W = 2; val E = 3
- val SW = 4; val SE = 5
-
- val sides = 6
-}
-
-abstract class Cell {
- var marked = false
-
- def mark() = marked = true
- def unmark() = marked = false
-}
-
-
-
-
-// BoardCell.scala
-
-final class BoardCell(_number: Int) extends Cell {
- val next = new Array[BoardCell](Cell.sides)
- val number = _number
- var piece: Piece = _
-
- def isEmpty() = piece == null
- def empty() = piece = null
-
- def contiguousEmptyCells(): Int = {
- if (!marked && isEmpty){
- mark
- var count = 1
-
- for (neighbour <- next)
- if (neighbour != null && neighbour.isEmpty)
- count = count + neighbour.contiguousEmptyCells
-
- count } else { 0 }
- }
-}
-
-
-
-
-// PieceCell.scala
-
-final class PieceCell extends Cell {
- val next = new Array[PieceCell](Cell.sides)
-
- def flip = {
- var swap = next(Cell.NE)
- next(Cell.NE) = next(Cell.NW)
- next(Cell.NW) = swap
-
- swap = next(Cell.E)
- next(Cell.E) = next(Cell.W)
- next(Cell.W) = swap
-
- swap = next(Cell.SE)
- next(Cell.SE) = next(Cell.SW)
- next(Cell.SW) = swap
- }
-
- def rotate = {
- var swap = next(Cell.E)
- next(Cell.E) = next(Cell.NE)
- next(Cell.NE) = next(Cell.NW)
- next(Cell.NW) = next(Cell.W)
- next(Cell.W) = next(Cell.SW)
- next(Cell.SW) = next(Cell.SE)
- next(Cell.SE) = swap
- }
-}
-
-
-
-
generated by cgit v1.2.3 (git 2.39.1) at 2024-05-03 20:09:08 +0000