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))
}