#!/usr/bin/env python
# coding: utf-8

# # Anacycliques
# 
# Trouver tous les anacycliques dans une liste de mots (issue de lexique.org par exemple). Les palindromes sont des cas particuliers d'anacycliques.  
# Ex : 'été' est un palidrome  
# 'vu' et 'uv', 'tort' et 'trot' sont des anacycliques
# 

# Tester si deux mots sont des anacycliques est très simple en Python. Pour cela on peut utiliser les slices avec le troisième argument pour le pas.  
# `word[::-1]` : un pas de `-1` permet d'inverser la chaîne de caractères.

# In[ ]:


def is_anacyclique(word1, word2):
    """
    Returns True if the given words are palindromes
    False if not
    """
    if word1 == word2[::-1]:
        return True
    else:
        return False


# In[ ]:


is_anacyclique("tort", "trot")


# In[19]:


words = []
with open('lexique381.ortho', 'r') as f:
    for line in f:
        line = line.rstrip()
        if len(line) != 1:
            words.append(line)
print("Nb de mots : {}".format(len(words)))


# Tester l'appartenance d'un élément à une liste de 142641 éléments est couteux en temps de traitement.  
# Le test d'appartenance d'un élément à une liste est de complexité 0(n) (voir [TimeComplexity](https://wiki.python.org/moin/TimeComplexity) sur le wiki Python).  
# Ici comme la liste est déjà pas mal grande et que l'opération est répétée n fois, le temps de traitement est rhédibitoire.

# Puisqu'on aime se compliquer la vie on peut essayer de réduite la taille de la liste en se limitant aux mots de même taille. Les anacycliques sont forcément de même taille.

# In[ ]:


def words_by_length(words):
    """
    Receives a list of words sorted by length, returns a list of words for each length
    """
    for length in range(len(words[0]), len(words[-1]) + 1):
        yield [word for word in words if len(word) == length]


# In[ ]:


res = set()
sorted_words = sorted(words, key = lambda x:len(x))
for words_n in words_by_length(sorted_words):
    for word in words_n:
        acyclique = word[::-1]
        if acyclique in words_n:
            res.add(tuple([word, acyclique]))
        
for match in sorted(res):
    print(match)


# Malgré le découpage du lexique en mots de même taille et l'utilisation des générateurs, le temps de traitement reste important.  
# Essayons avec un dictionnaire.

# In[12]:


from collections import defaultdict
words_d = defaultdict()
with open('lexique381.ortho', 'r') as f:
    for line in f:
        line = line.rstrip()
        if len(line) != 1:
            words_d[line] = ""
print("Nb de mots : {}".format(len(words_d.keys())))


# On a une différence de taille d'avec la liste parce que le dictionnaire supprime les doublons (125627 contre 142641). Mais ça ne change pas vraiment l'ordre du volume des données.

# In[15]:


res = set()
for word in words_d.keys():
    acyclique = word[::-1]
    if acyclique in words:
        res.add(tuple([word, acyclique]))
        
for match in sorted(res)[:20]:
    print(match)


# Là c'est tout de suite BEAUCOUP plus rapide <small>(supprimez `[:20]` pour avoir tous les résultats)</small>. Mais pourquoi ?  
# Parce que le test d'appartenance pour un dictionnaire est estimé à O(1) en moyenne (O(n) dans le pire des cas).  
# idem pour les ensembles (`set`)

# In[16]:


words_s = set()
with open('lexique381.ortho', 'r') as f:
    for line in f:
        line = line.rstrip()
        if len(line) != 1:
            words_s.add(line)
print("Nb de mots : {}".format(len(words_s)))


# In[17]:


res = set()
for word in words_s:
    acyclique = word[::-1]
    if acyclique in words:
        res.add(tuple([word, acyclique]))
        
for match in sorted(res)[:20]:
    print(match)


# Allez on va s'amuser à mesurer ça :

# In[25]:


get_ipython().run_line_magic('time', '"palindrome" in words')
get_ipython().run_line_magic('time', '"palindrome" in words_d')
get_ipython().run_line_magic('time', '"palindrome" in words_s')


# Si vous êtes intéressés par l'implémentation des dictionnaires vous pourrez lire l'article suivant : [Python dictionary implementation] (http://www.laurentluce.com/posts/python-dictionary-implementation/)

# In[ ]: