diff options
-rw-r--r-- | test/files/run/Course-2002-05.check | 39 | ||||
-rw-r--r-- | test/files/run/Course-2002-05.scala | 169 |
2 files changed, 208 insertions, 0 deletions
diff --git a/test/files/run/Course-2002-05.check b/test/files/run/Course-2002-05.check new file mode 100644 index 0000000000..68892dda2e --- /dev/null +++ b/test/files/run/Course-2002-05.check @@ -0,0 +1,39 @@ +(List(),List(1,2,3,4,5,6,7,8)) +(List(1,2,3,4),List(5,6,7,8)) +(List(1,2,3,4,5,6,7,8),List()) + +(List(),List(8,7,6,5,4,3,2,1)) +(List(4,3,2,1),List(8,7,6,5)) +(List(8,7,6,5,4,3,2,1),List()) + +(List(),List(7,2,1,5,4,3,8,6)) +(List(2,1,4,3),List(7,5,8,6)) +(List(7,2,1,5,4,3,8,6),List()) + +List(1,2,3,4,5,6,7,8) + +(List(),List(1,2,3,4,5,6,7,8)) +(List(1,2,3,4),List(5,6,7,8)) +(List(1,2,3,4,5,6,7,8),List()) + +(List(),List(8,7,6,5,4,3,2,1)) +(List(4,3,2,1),List(8,7,6,5)) +(List(8,7,6,5,4,3,2,1),List()) + +(List(),List(7,2,1,5,4,3,8,6)) +(List(2,1,4,3),List(7,5,8,6)) +(List(7,2,1,5,4,3,8,6),List()) + +List(1,2,3,4,5,6,7,8) + +List(List()) +List(List(),List(1)) +List(List(),List(2),List(1),List(1,2)) +List(List(),List(3),List(2),List(2,3),List(1),List(1,3),List(1,2),List(1,2,3)) +List(List(),List(4),List(3),List(3,4),List(2),List(2,4),List(2,3),List(2,3,4),List(1),List(1,4),List(1,3),List(1,3,4),List(1,2),List(1,2,4),List(1,2,3),List(1,2,3,4)) + +queens(1) = List(List((1,1))) +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))) + diff --git a/test/files/run/Course-2002-05.scala b/test/files/run/Course-2002-05.scala new file mode 100644 index 0000000000..9f3304f690 --- /dev/null +++ b/test/files/run/Course-2002-05.scala @@ -0,0 +1,169 @@ +//############################################################################ +// Programmation IV - 2002 - Week 05 +//############################################################################ +// $Id$ + +module 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 = { + System.out.println(partition[int](List(1,2,3,4,5,6,7,8), (x => x < 0))); + System.out.println(partition[int](List(1,2,3,4,5,6,7,8), (x => x < 5))); + System.out.println(partition[int](List(1,2,3,4,5,6,7,8), (x => x < 9))); + System.out.println(); + + System.out.println(partition[int](List(8,7,6,5,4,3,2,1), (x => x < 0))); + System.out.println(partition[int](List(8,7,6,5,4,3,2,1), (x => x < 5))); + System.out.println(partition[int](List(8,7,6,5,4,3,2,1), (x => x < 9))); + System.out.println(); + + System.out.println(partition[int](List(7,2,1,5,4,3,8,6), (x => x < 0))); + System.out.println(partition[int](List(7,2,1,5,4,3,8,6), (x => x < 5))); + System.out.println(partition[int](List(7,2,1,5,4,3,8,6), (x => x < 9))); + System.out.println(); + + System.out.println(quicksort[int]((x,y) => x < y)(List(7,2,1,5,4,3,8,6))); + System.out.println(); + } +} + +//############################################################################ + +module M1 { + def partition[a](xs: List[a], pred: a => boolean): Pair[List[a], List[a]] = { + xs.foldr[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 = { + System.out.println(partition[int](List(1,2,3,4,5,6,7,8), (x => x < 0))); + System.out.println(partition[int](List(1,2,3,4,5,6,7,8), (x => x < 5))); + System.out.println(partition[int](List(1,2,3,4,5,6,7,8), (x => x < 9))); + System.out.println(); + + System.out.println(partition[int](List(8,7,6,5,4,3,2,1), (x => x < 0))); + System.out.println(partition[int](List(8,7,6,5,4,3,2,1), (x => x < 5))); + System.out.println(partition[int](List(8,7,6,5,4,3,2,1), (x => x < 9))); + System.out.println(); + + System.out.println(partition[int](List(7,2,1,5,4,3,8,6), (x => x < 0))); + System.out.println(partition[int](List(7,2,1,5,4,3,8,6), (x => x < 5))); + System.out.println(partition[int](List(7,2,1,5,4,3,8,6), (x => x < 9))); + System.out.println(); + + System.out.println(quicksort[int]((x,y) => x < y)(List(7,2,1,5,4,3,8,6))); + System.out.println(); + } +} + +//############################################################################ + +module 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 = { + System.out.println(powerset(List())); + System.out.println(powerset(List(1))); + System.out.println(powerset(List(1,2))); + System.out.println(powerset(List(1,2,3))); + System.out.println(powerset(List(1,2,3,4))); + System.out.println(); + } +} + +//############################################################################ + +module M3 { + + 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 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 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(); + } +} + +//############################################################################ + +module Test { + def main(args: Array[String]): unit = { + M0.test; + M1.test; + M2.test; + M3.test; + () + } +} + +//############################################################################ |