S-99: P06, P07

Je continue la résolution des 99 problèmes en Scala. Au fur et à mesure que j’avance dans la résolutions de ces problèmes je me rends compte je fais beaucoup usage du pattern matching. Et cet épisode ne fait pas exception à la règle!

Le problème P06: Vérifier si une liste est un palindrome

C’est par là si vous voulez en savoir davantage sur le palindrome. Exemple

scala> isPalindrome(List(1, 2, 3, 2, 1))
res0: Boolean = true

La solution à P06

Je suis rapidement arrivé à la solution suivante consistant à comparer la liste avec son inverse. J’ai ensuite cherché d’autres plus “efficace” mais je ne suis pas arrivé à trouver une solution plus “fonctionnelle” à mon goût.

def isPalindrome[T](xs: List[T]) = xs.reverse == xs

Le test de la solution

import org.specs2.mutable._

class P06Spec extends Specification {
  "P06.isPalindrome(xs)" should {
    "return true" in {
      P06.isPalindrome(List()) must_== true
    }

    "return true" in {
      P06.isPalindrome(List(1)) must_== true
    }

    "return true" in {
      P06.isPalindrome(List(60, 60)) must_== true
    }

    "return true" in {
      P06.isPalindrome(List(3, 2, 1, 2, 3)) must_== true
    }
  }
}

Le problème P07: Mettre à plat une liste de listes

Il s’agit de mettre à plat une liste dont les constituants peuvent être des listes à leur tour. *C’est pour le fun que nous écrivons cette fonction mais pas une nécessité car l’API des listes fournit une méthode permettant de mettre à plat une liste. *Exemple:

scala> flatten(List(List(1, 1), 2, List(3, List(5, 8))))
res0: List[Any] = List(1, 1, 2, 3, 5, 8)

La solution à P07

La solution utilise le pattern matching et la récursivité à fond!

  def flatten(xs: List[Any]): List[Any] = {
    xs match {
      case head :: tail => (head, tail) match {
        case (h: List[Any], t) => flatten(h) ++ flatten(t)
        case (h: Any, t) => h :: flatten(t)
      }
      case x => x
    }
  }

Le test de la solution

import org.specs2.mutable._

object P07Spec extends Specification {
  "P07.flatten(xs)" should {
    "return Nil" in {
      P07.flatten(Nil) must_== Nil
    }

    "return List(1)" in {
      P07.flatten(List(1)) must_== List(1)
    }

    "return List(1, 2)" in {
      P07.flatten(List(1, List(2))) must_== List(1, 2)
    }

    "return List(1, 2, 3, 4)" in {
      P07.flatten(List(1, List(2, 3), 4)) must_== List(1, 2, 3, 4)
    }

    "return List(1, 2, 3, 4, 5, 7, 8)" in {
      P07.flatten(List(1, List(2, 3), 4, List(5, List(6, List(7, 8))))) must_== List(1, 2, 3, 4, 5, 6, 7, 8)
    }
  }
}

Fin du voyage mes amis! A bientôt pour un autre épisode ;-)