Discussion :

[millie]

Bonjour,

Pour ce sixième défi proposé par SpiceGuid, l'équipe de developpez.com vous propose un challenge assez court qui peut laisser place à l'optimisation.

Challenge :



Il s'agit d'écrire une fonction (s: string) → string qui renvoie un palindrome p tel que:

• s contient p
• s ne contient aucun palindrome qui soit strictement plus long que p

On rappelle qu'un palindrome est une chaîne de caractère dont l'ordre de lettre est identique, selon que la lise par la gauche ou par la droite.
Formellement, une chaîne s est un palindrome si et seulement si :
Pour tout i de 0 à taille(s)-1, s[i] = s[taille(s)-1-i]

Les règles

Il n'y a pas de règle particulière (évidemment, il faut que la solution proposée fonctionne). Vous pouvez proposer des solutions aussi bien dans des langages fonctionnels (caml, haskell, scheme, lisp...) qu'impératif. Le public pourra ainsi juger du code suivant divers critères :

• la maintenabilité
• la simplicité
• le fait qu'il soit optimisé

Le public pourra également juger les différences entre une solution fonctionnelle et une solution impérative. Il lui sera ainsi plus facile de voir, pour un même problème, les différences entre divers paradigmes.

Pour répondre, il vous suffit de poster à la suite.

A vos claviers
de votre participation.

__________________________
Sujet proposé par SpiceGuid

[Jedai]

J'avais une petite solution en Haskell, qui utilise un zipper de liste. Je me suis concocté mon propre zipper mais on peut aussi trouver des implémentations sur Hackage :
MyListZipper.hs :

Code Haskell :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
module MyListZipper (LZ(), toZipper
                    , forward, backward
                    , (<|), (|>)
                    , start, end
                    , next, prev) where
 
data LZ a = LZ [a] [a]
 
toZipper xs = LZ [] xs
 
forward, backward :: LZ a -> LZ a
forward z@(LZ xs []) = z
forward (LZ xs (y:ys)) = LZ (y:xs) ys
backward z@(LZ [] ys) = z
backward (LZ (x:xs) ys) = LZ xs (x:ys)
 
(<|) :: a -> LZ a -> LZ a
y <| (LZ xs ys) = LZ xs (y:ys)
(|>) :: LZ a -> a -> LZ a
(LZ xs ys) |> x = LZ (x:xs) ys
 
start, end :: LZ a -> Bool
start (LZ xs _) = null xs
end (LZ _ ys) = null ys
 
next, prev :: LZ a -> (a, LZ a)
next (LZ xs (y:ys)) = (y, LZ xs ys)
prev (LZ (x:xs) ys) = (x, LZ xs ys)

Et le code principal :

Code Haskell :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
module Main () where
import Data.List
import Control.Arrow
import MyListZipper
 
data Pal a = Pal [a] [a]
 
expand (Pal beg seed) = beg ++ seed ++ reverse beg
 
grow :: (Eq a) => Pal a -> LZ a -> Pal a
grow pal@(Pal beg seed) z 
    | start z || end z || p /= n = pal
    | otherwise                  = grow (Pal (p:beg) seed) z'
    where (p, temp) = prev z
          (n, z')   = next temp
 
seeds :: (Eq a) => [a] -> [(Pal a, LZ a)]
seeds = zSeeds . toZipper 
 
zSeeds :: (Eq a) => LZ a -> [(Pal a, LZ a)]
zSeeds z | end z     = []
         | otherwise = (pal, z') : zSeeds z''
         where
           (n, temp)      = next z
           (pal, z', z'') = findSeed [n] temp (forward z)
 
findSeed :: (Eq a) => [a] -> LZ a -> LZ a -> (Pal a, LZ a, LZ a)
findSeed s@(x:_) z w
    | end z || n /= x  = (Pal [] s, z, w)
    | otherwise        = findSeed (n:s) z' (forward w)
    where (n, z') = next z
 
longest = foldl' max (0,"") . map ((length &&& id) . expand . uncurry grow) . seeds
 
main = print . longest =<< getContents

L'idée est simple : on commence par isoler les séquences de lettres identiques dans s, puis on essaie de faire "grossir" ces séquences par les deux côtés tant que cela reste un palindrome, enfin on récupère le palindrome le plus long.

--
Jedaï

[djo.mos]

Salut,
Une solution impérative (code en Java) :
L'idée est parcourir les lettres de la chaine, en recherchant la lettre courante dans le reste de la chaine. Si on en trouve, on teste si la sous-chaine qui commence à la lettre courante jusqu'à la lettre trouvée est palindrome.

Code java :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
package defi6;
 
public class Defi6 {
 
	private boolean isPalindrome(char[] a, int i, int j) {
		int l = j - i;
		for (int x = i; x <= i + l / 2; x++) {
			if (a[x] != a[j - (x - i)]) {
				return false;
			}
		}
		return true;
	}
 
	private String extractPalyndrome(String s) {
		char[] a = s.toCharArray();
		String candidate = null;
		for (int i = 0; i < a.length; i++) {
			for (int j = i; j < a.length; j++) {
				if (a[j] == a[i] && isPalindrome(a, i, j)) {
					String pal = s.substring(i, j + 1);
					if (candidate == null
							|| pal.length() > candidate.length()) {
						candidate = pal;
					}
				}
			}
		}
		return candidate;
	}
 
	public static void main(String[] args) {
		System.out.println(new Defi6().extractPalyndrome("abbbccacc"));
	}
 
}

[Philou67430]

J'espère avoir bien compris qu'il faut réaliser une fonction qui retourne le plus long palindrome d'une chaine de caractère.

La fonction est réalisée en perl, et est basée sur les expressions régulières :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
sub palindrome {
  return [sort { length $b <=> length $a } $_[0] =~ /((.+).?(??{ reverse "$2" }))/gx]->[0];
}

Exemple d'utilisation en uniligne :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
$ perl -e '$aa = "tooiuertreuioot toot azertyuioppoiuytreza";sub palindrome { return [sort { length $b <=> length $a } $aa =~ /((.+
).?(??{ reverse "$2" }))/gx]->[0] } print palindrome($aa)'

Attention cependant, l'opérateur (??{ ... }) des expressions régulières de perl est considéré comme expérimental (version 5.10), mais il est diablement efficace ici.
L'extraction des palindromes est réalisée grâce à la regexp :
/((.+).?(??{ reverse "$2" }))/gx
à savoir un certain nombre de caractère (le plus possible), suivi éventuellement d'un caractère quelconque, suivi de la première partie déjà trouvée, mais à l'envers.
On extrait de cet expression deux chaines : le palindrome et la première partie du palindrome. La palindrome est toujours plus long que la première partie.
Ensuite, on trie le résultat par longue décroissante, et on prends le premier élément de cette liste.

[Jedai]

La solution que j'ai donné en premier lieu a une très bonne complexité/efficacité, mais ce n'est évidemment pas le plus simple qu'on puisse faire en Haskell, dans la même optique que la solution Perl, on peut avoir :

Code Haskell :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
isPalindrome s = s == reverse s
allSubstrings = concatMap (init . tails) . inits
longest = maximumBy (comparing length) . filter isPalindrome . allSubstrings

Complexité absolument horrible bien sûr... (ça reste plus rapide que la solution Perl, même en interprété)
La solution de djo.mos est meilleure de ce point de vue mais tout de même plus complexe que ma première solution Haskell.

--
Jedaï

[Philou67430]

Sauf erreur, Jedaï, je crois que ta fonction isPalindrome ne récupère pas les palindromes de taille impaire.