path: root/test-nsc/files/run/Course-2002-05.scala

//############################################################################
// 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;
    ()
  }
}

//############################################################################