diff options
author | paltherr <paltherr@epfl.ch> | 2003-07-18 11:17:08 +0000 |
---|---|---|
committer | paltherr <paltherr@epfl.ch> | 2003-07-18 11:17:08 +0000 |
commit | 5f77ce3a39f276eea29df1b09926553364d80e1d (patch) | |
tree | fb35a381874e7bc20950af7437fe068e08d25c45 | |
parent | 5a64e1706c57b41a8b4199387efd081d6aabaf08 (diff) | |
download | scala-5f77ce3a39f276eea29df1b09926553364d80e1d.tar.gz scala-5f77ce3a39f276eea29df1b09926553364d80e1d.tar.bz2 scala-5f77ce3a39f276eea29df1b09926553364d80e1d.zip |
- Merged queens into Course-2002-05
-rw-r--r-- | test/files/run/Course-2002-05.check | 5 | ||||
-rw-r--r-- | test/files/run/Course-2002-05.scala | 50 | ||||
-rw-r--r-- | test/files/run/queens.check | 4 | ||||
-rw-r--r-- | test/files/run/queens.scala | 49 |
4 files changed, 53 insertions, 55 deletions
diff --git a/test/files/run/Course-2002-05.check b/test/files/run/Course-2002-05.check index 68892dda2e..aa73638bcb 100644 --- a/test/files/run/Course-2002-05.check +++ b/test/files/run/Course-2002-05.check @@ -37,3 +37,8 @@ queens(2) = List() queens(3) = List() queens(4) = List(List((4,3),(3,1),(2,4),(1,2)),List((4,2),(3,4),(2,1),(1,3))) +queens(1) = List(List(1)) +queens(2) = List() +queens(3) = List() +queens(4) = List(List(3,1,4,2),List(2,4,1,3)) + diff --git a/test/files/run/Course-2002-05.scala b/test/files/run/Course-2002-05.scala index 2d8a146624..46b4acc349 100644 --- a/test/files/run/Course-2002-05.scala +++ b/test/files/run/Course-2002-05.scala @@ -115,6 +115,12 @@ object M2 { object M3 { + def abs(x: int) = if (x < 0) 0 - x else x; + + def range(lo: Int, hi: Int): List[Int] = + if (lo > hi) List() + else lo :: range(lo + 1, hi); + type Placement = List[Pair[int,int]]; def queens(n: int): List[Placement] = { @@ -139,11 +145,50 @@ object M3 { placeQueens(n) } - def range(lo: int, hi: int): List[int] = + def test = { + System.out.println("queens(1) = " + queens(1)); + System.out.println("queens(2) = " + queens(2)); + System.out.println("queens(3) = " + queens(3)); + System.out.println("queens(4) = " + queens(4)); + System.out.println(); + } +} + +//############################################################################ + +object M4 { + + def abs(x: int) = if (x < 0) 0 - x else x; + + def range(lo: Int, hi: Int): List[Int] = if (lo > hi) List() else lo :: range(lo + 1, hi); - def abs(x: int) = if (x < 0) 0 - x else x; + type Placement = List[Int]; + + def queens(n: Int): List[Placement] = { + val columns = range(1, n); + def placeQueens(row: Int): List[Placement] = { + if (row == 0) + List(List()) + else { + def isSafe(col: Int, p: Placement, delta: Int): Boolean = + p.isEmpty || + (col != p.head && + abs(col - p.head) != delta && + isSafe(col, p.tail, delta + 1)); + + for ( + val placement <- placeQueens(row - 1); + val col <- columns; + isSafe(col, placement, 1) + ) yield { + col :: placement + } + } + } + placeQueens(n); + } def test = { System.out.println("queens(1) = " + queens(1)); @@ -162,6 +207,7 @@ object Test { M1.test; M2.test; M3.test; + M4.test; () } } diff --git a/test/files/run/queens.check b/test/files/run/queens.check deleted file mode 100644 index 8187f196b8..0000000000 --- a/test/files/run/queens.check +++ /dev/null @@ -1,4 +0,0 @@ -Solutions to 1 queens: List(List(1)) -Solutions to 2 queens: List() -Solutions to 3 queens: List() -Solutions to 4 queens: List(List(3,1,4,2),List(2,4,1,3)) diff --git a/test/files/run/queens.scala b/test/files/run/queens.scala deleted file mode 100644 index ba812f5971..0000000000 --- a/test/files/run/queens.scala +++ /dev/null @@ -1,49 +0,0 @@ -// $Id$ - -object M0 { - type Placement = List[Int]; - - def range(lo: Int, hi: Int): List[Int] = - if (lo > hi) List() - else lo :: range(lo + 1, hi); - - def abs(x: Int) = if (x < 0) 0 - x else x; - - def queens(n: Int): List[Placement] = { - val columns = range(1, n); - def placeQueens(row: Int): List[Placement] = { - if (row == 0) - List(List()) - else { - def isSafe(col: Int, p: Placement, delta: Int): Boolean = - p.isEmpty || - (col != p.head && - abs(col - p.head) != delta && - isSafe(col, p.tail, delta + 1)); - - for ( - val placement <- placeQueens(row - 1); - val col <- columns; - isSafe(col, placement, 1) - ) yield { - col :: placement - } - } - } - placeQueens(n); - } - - def test = { - System.out.println("Solutions to 1 queens: " + queens(1)); - System.out.println("Solutions to 2 queens: " + queens(2)); - System.out.println("Solutions to 3 queens: " + queens(3)); - System.out.println("Solutions to 4 queens: " + queens(4)); - } -} - -object Test { - def main(args: Array[String]): Unit = { - M0.test; - () - } -} |