Défi N°6 : Les palindromes

[JeitEmgie]

premier essai :

Code :

1
2
3
4
5
6
time palindrome.rb < /usr/share/dict/words  > /dev/null

real	0m23.213s
user	0m23.189s
sys	0m0.022s

Code :

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
#!/usr/bin/env ruby

while s = gets
	r=s.reverse
	l=s.length

	palindromes=Array.new

	i=0
	while i<l-1 && palindromes.empty?
		j = 0
		while j<=i
			s1=s[j,l-i]
			r1=r[i-j,l-i]
			if s1 == r1
				palindromes << s1
			end
			j += 1
		end
		i += 1
	end
	if !palindromes.empty?
		puts "Largest palindromes in #{s}"
		palindromes.each do |p|
			puts "\t#{p}"
		end
		puts "------------"
	end
end

exemple de sortie :

Code :

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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
Largest palindromes found in aa
        aa
------------
Largest palindromes found in aal
        aa
------------
Largest palindromes found in aalii
        aa
        ii
------------
Largest palindromes found in aam
        aa
------------
Largest palindromes found in aardvark
        aa
------------
Largest palindromes found in aardwolf
        aa
------------
Largest palindromes found in Aaronitic
        iti
------------
Largest palindromes found in aba
        aba
------------
Largest palindromes found in Ababdeh
        bab
------------
Largest palindromes found in Ababua
        bab
------------
Largest palindromes found in abac
        aba
------------
Largest palindromes found in abaca
        aba
        aca
------------
Largest palindromes found in abacate
        aba
        aca
------------
Largest palindromes found in abacay
        aba
        aca
------------
Largest palindromes found in abacinate
        aba
------------
Largest palindromes found in abacination
        aba
------------
Largest palindromes found in abaciscus
        aba
------------
…
Largest palindromes found in computation
	tat
------------
Largest palindromes found in computational
	tat
------------
Largest palindromes found in computative
	tat
------------
Largest palindromes found in computativeness
	tat
	ene
------------
Largest palindromes found in computus
	utu
------------
Largest palindromes found in Comsomol
	omo
------------
Largest palindromes found in comurmurer
	rer
------------
…
Largest palindromes found in forrue
	rr
------------
Largest palindromes found in forsakenness
	enne
------------
Largest palindromes found in forsooth
	oo
------------
…
Largest palindromes found in navarchy
	ava
------------
Largest palindromes found in Navarrese
	ava
	ese
------------
Largest palindromes found in Navarrian
	ava
------------
Largest palindromes found in naveled
	ele
------------
…
Largest palindromes found in premillenarianism
	ll
------------
Largest palindromes found in premillennial
	ll
	nn
------------
Largest palindromes found in premillennialism
	ll
	nn
------------
Largest palindromes found in premillennialist
	ll
	nn
…
Largest palindromes found in zymome
	mom
------------
Largest palindromes found in zymometer
	mom
	ete
------------
Largest palindromes found in zymomin
	mom
------------
Largest palindromes found in zymosimeter
	ete
------------
Largest palindromes found in zymosis
	sis
------------
Largest palindromes found in zymotically
	ll
------------
Largest palindromes found in zymotoxic
	oto
------------
Largest palindromes found in Zyryan
	yry
------------
Largest palindromes found in Zyzzogeton
	zz
------------

le même palindrome apparaissant à différents endroits sera sorti plusieurs fois…
si l'on veut une seule sortie : remplacer l'Array "palindromes" par un Hash…

pour info, la même version compilée en C :

Code :

1
2
3
4
5
6
time ./palindrome < /usr/share/dict/words > /dev/null

real	0m0.605s
user	0m0.596s
sys	0m0.006s

si l'on veut les palindromes >= à une taille minimum c'est le "l-1" du "while i<l-1 && palindromes.empty?" qu'il faut paramétrer en "l - (longueur minimale désirée - 1)"

si on ne stocke pas les résultats, mais qu'on les sort directement (tjs la version en C)

Code :

1
2
3
4
5
6
time ./palindrome < /usr/share/dict/words > /dev/null

real	0m0.378s
user	0m0.268s
sys	0m0.014s

[fcharton]

Une expression J qui donne la liste des plus longs palindromes

Code :

1
2
3
4
((#~((=>./)@:(#@>)))@:(#~((-:|.)@>))@:~.@:,@:({\~(1+i.@:#)))

(#~((=>./)@:(#@>)))(#~((-:|.)@>))~.,({\~(1+i.@:#)) 'esope reste ici et se repose'
'te ici et'

Petite explication:
si y est la chaine qu'on étudie

1+i.#y
est la suite 1 2 3 ... #y (#y : longueur de la chaine)
n {/ y
génère toutes les sous chaines de longueur n de y
1+i.#y {/ y
génère un tableau de toutes les sous chaines de y

({\~(1+i.@: #)) est l'expression fermée correspondante

, met ce tableau "en ligne", et ~. en élimine les doublons
~.,({\~(1+i.@: #))
est la liste de toutes les sous chaines uniques

(-: |.) renvoie 1 si la chaine est un palindrome, 0 sinon
(#~((-: |.)@ >))
sélectionne les palindromes de la liste précédente

(#@>) compte les lettres de chaque palindrome
>./ donne le maximum d'une suite
(=>./)@: (#@>) renvoie 1 si la longueur est égale à la longueur maximale rencontrée dans la suite

(#~((=>./)@: (#@>))) sélectionne les palindromes maximaux

Francois