diff options
Diffstat (limited to 'test-nsc/files/run/Course-2002-05.scala')
-rw-r--r-- | test-nsc/files/run/Course-2002-05.scala | 215 |
1 files changed, 0 insertions, 215 deletions
diff --git a/test-nsc/files/run/Course-2002-05.scala b/test-nsc/files/run/Course-2002-05.scala deleted file mode 100644 index c761f88f5d..0000000000 --- a/test-nsc/files/run/Course-2002-05.scala +++ /dev/null @@ -1,215 +0,0 @@ -//############################################################################ -// Programmation IV - 2002 - Week 05 -//############################################################################ -// $Id$ - -object M0 { - def partition[a](xs: List[a], pred: a => boolean): Pair[List[a], List[a]] = { - if (xs.isEmpty) - Pair(List(),List()) - else { - val tailPartition = partition(xs.tail, pred); - if (pred(xs.head)) - Pair(xs.head :: tailPartition._1, tailPartition._2) - else - Pair(tailPartition._1, xs.head :: tailPartition._2) - } - } - - def quicksort[a] (less : (a,a) => boolean) (xs : List[a]) : List[a] = { - if (xs.isEmpty) - xs - else { - val pivot = xs.head; - val sub = partition(xs.tail, (elem : a => less(elem, pivot))); - quicksort(less)(sub._1) ::: List(pivot) ::: quicksort(less)(sub._2) - } - } - - def test = { - Console.println(partition[int](List(1,2,3,4,5,6,7,8), (x => x < 0))); - Console.println(partition[int](List(1,2,3,4,5,6,7,8), (x => x < 5))); - Console.println(partition[int](List(1,2,3,4,5,6,7,8), (x => x < 9))); - Console.println; - - Console.println(partition[int](List(8,7,6,5,4,3,2,1), (x => x < 0))); - Console.println(partition[int](List(8,7,6,5,4,3,2,1), (x => x < 5))); - Console.println(partition[int](List(8,7,6,5,4,3,2,1), (x => x < 9))); - Console.println; - - Console.println(partition[int](List(7,2,1,5,4,3,8,6), (x => x < 0))); - Console.println(partition[int](List(7,2,1,5,4,3,8,6), (x => x < 5))); - Console.println(partition[int](List(7,2,1,5,4,3,8,6), (x => x < 9))); - Console.println; - - Console.println(quicksort[int]((x,y) => x < y)(List(7,2,1,5,4,3,8,6))); - Console.println; - } -} - -//############################################################################ - -object M1 { - def partition[a](xs: List[a], pred: a => boolean): Pair[List[a], List[a]] = { - xs.foldRight[Pair[List[a], List[a]]](Pair(List(), List())) { - (x, p) => if (pred (x)) Pair(x :: p._1, p._2) else Pair(p._1, x :: p._2) - } - } - - def quicksort[a] (less : (a,a) => boolean) (xs : List[a]) : List[a] = { - if (xs.isEmpty) - xs - else { - val pivot = xs.head; - val sub = partition(xs.tail, (elem : a => less(elem, pivot))); - quicksort(less)(sub._1) ::: List(pivot) ::: quicksort(less)(sub._2) - } - } - - def test = { - Console.println(partition[int](List(1,2,3,4,5,6,7,8), (x => x < 0))); - Console.println(partition[int](List(1,2,3,4,5,6,7,8), (x => x < 5))); - Console.println(partition[int](List(1,2,3,4,5,6,7,8), (x => x < 9))); - Console.println; - - Console.println(partition[int](List(8,7,6,5,4,3,2,1), (x => x < 0))); - Console.println(partition[int](List(8,7,6,5,4,3,2,1), (x => x < 5))); - Console.println(partition[int](List(8,7,6,5,4,3,2,1), (x => x < 9))); - Console.println; - - Console.println(partition[int](List(7,2,1,5,4,3,8,6), (x => x < 0))); - Console.println(partition[int](List(7,2,1,5,4,3,8,6), (x => x < 5))); - Console.println(partition[int](List(7,2,1,5,4,3,8,6), (x => x < 9))); - Console.println; - - Console.println(quicksort[int]((x,y) => x < y)(List(7,2,1,5,4,3,8,6))); - Console.println; - } -} - -//############################################################################ - -object M2 { - - def powerset[a] (s : List[a]) : List[List[a]] = { - if (s.isEmpty) - List(List()) - else { - val x = s.head; - val withoutX = powerset(s.tail); - withoutX ::: withoutX.map(s1 : List[a] => x::s1) - } - } - - def test = { - Console.println(powerset(List())); - Console.println(powerset(List(1))); - Console.println(powerset(List(1,2))); - Console.println(powerset(List(1,2,3))); - Console.println(powerset(List(1,2,3,4))); - Console.println; - } -} - -//############################################################################ - -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] = { - def placeQueens(row: int): List[Placement] = { - if (row == 0) - List(List()) - else { - def isSafe(column: int, placement: Placement): boolean = - placement forall { - pos => (pos._2 != column && - abs(pos._2 - column) != row - pos._1) - } - - def adjoinRow(placement: Placement): List[Placement] = - range(1, n) - .filter (column => isSafe(column, placement)) - .map (column => Pair(row, column) :: placement); - - placeQueens(row - 1) flatMap adjoinRow - } - } - placeQueens(n) - } - - def test = { - Console.println("queens(1) = " + queens(1)); - Console.println("queens(2) = " + queens(2)); - Console.println("queens(3) = " + queens(3)); - Console.println("queens(4) = " + queens(4)); - Console.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); - - 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 = { - Console.println("queens(1) = " + queens(1)); - Console.println("queens(2) = " + queens(2)); - Console.println("queens(3) = " + queens(3)); - Console.println("queens(4) = " + queens(4)); - Console.println; - } -} - -//############################################################################ - -object Test { - def main(args: Array[String]): unit = { - M0.test; - M1.test; - M2.test; - M3.test; - M4.test; - () - } -} - -//############################################################################ |