Exercice 1 ---------- Axioms of drop: Nil drop n = Nil (d0) xs drop 0 = xs (d1) (x::xs) drop (n+1) = xs drop n (d2) Proof by induction on n of (xs take n) ::: (xs drop n) = xs Base case with n = 0 (xs take 0) ::: (xs drop 0) = xs Nil ::: (xs drop 0) = xs (t1) Nil ::: xs = xs (d1) xs = xs (c0) Inductive case with n = k+1 Hypothesis: (xs take k) ::: (xs drop k) = xs case xs = Nil (Nil take (k+1)) ::: (Nil drop (k+1)) = Nil Nil ::: (Nil drop (k+1)) = Nil (t0) Nil ::: Nil = Nil (d0) Nil = Nil (c0) case xs = y :: ys ((y::ys) take (k+1)) ::: ((y::ys) drop (k+1)) = y :: ys (y :: (ys take (k))) ::: ((y::ys) drop (k+1)) = y :: ys (t2) (y :: (ys take (k))) ::: (ys drop (k)) = y :: ys (d2) y :: ((ys take (k)) ::: (ys drop (k))) = y :: ys (c1) y :: ys = y :: ys (hyp) Q.E.D. Exercice 2 ---------- type Students = List[String] type Hate = List[(String, String)] def bar(sitting: Students, standing: Students, hate: Hate): List[Students] = { def canSit(p1: String, p2: String) = (hate filter ( h => h == (p1, p2) || h == (p2, p1) )).isEmpty if (standing.isEmpty) sitting :: Nil else for (s <- standing if (sitting.isEmpty || canSit(sitting.head, s)); sol <- bar(s :: sitting, standing filter (_ != s), hate) ) yield sol } Exercice 3 ---------- def inBase(b: Int, n: Int) = { def inBase0(ds: List[Int], n: int): List[Int] = if (n == 0) ds else inBase0((n%b)::ds, n/b) inBase0(Nil, n) } def isPal(b: Int, n: Int) = { val r = inBase(b, n) r == r.reverse } def isBinDecPal(n: Int) = isPal(2, n) && isPal(10, n) (0 to 1000000).foldLeft(0){ (sum, x) => if (isBinDecPal(x)) sum + x else sum } Ex3Solution.scala (was in repository) -------------------------------------- object PalindromicProblem extends Application { def convertToBase(a: Int, base: Int) = { def convertTo2Aux(b: Int, res: List[Int]): List[Int] = if (b > 0) convertTo2Aux(b / base, b % base :: res) else res convertTo2Aux(a, List()) } def isPalindromic(n: Int): Boolean = { val to10 = convertToBase(n, 10) val to2 = convertToBase(n, 2) to10 == to10.reverse && to2 == to2.reverse } def sumPalindromicFromTo(start: Int, end: Int) = { ((start until end) filter (isPalindromic(_))) reduceLeft(_ + _) } println("Palindromic sum from 1 to 1000000: " + sumPalindromicFromTo(1, 1000000)) }