«

»

Avr 01 2013

CodinGame de Janvier

J’ai participé au CodinGame de Janvier. Contrairement à ceux de Mars, le niveau des exercices était vraiment sympa… Voici mes résultats, je m’en suis mieux sorti qu’au mois de mars avec une 29e place, 79% de réussite en 2h30 (sur 5h).

Je vais parler du 3e exercice. L’objectif était d’analyser des messages écrits en morse, mais sans séparateur entre les mots. Il fallait trouver le nombre de combinaisons de mots possible qui pourrait donner ce message. Le programme prenant en entrée le message, ainsi que la liste des mots possibles.

Première tentative

J’ai décidé de procéder récursivement. Je commence déjà par convertir tous les mots de mon dictionnaires en morse.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
import sys
codex = {
    'A': '.-', 'B': '-...', 'C': '-.-.', 'D': '-..', 'E': '.',
    'F': '..-.', 'G': '--.', 'H': '....', 'I': '..', 'J': '.---',
    'K': '-.-', 'L': '.-..', 'M': '--', 'N': '-.', 'O': '---',
    'P': '.--.', 'Q': '--.-', 'R': '.-.', 'S': '...', 'T': '-',
    'U': '..-', 'V': '...-', 'W': '.--', 'X': '-..-', 'Y': '-.--', 'Z': '--..',
}
def encode(m):
    return ''.join([codex[i] for i in m])

morse = raw_input()
n = int(raw_input())

mots = []
for i in range(n):
    m = raw_input()
    mots.append(encode(m))

Ma fonction récursive commence par comparer le début de ma chaine avec tous les mots. Si une occurrence est trouvée, je rappel la fonction avec le reste de la chaine. La fonction retourne le nombre de possibilités trouvées. Ma condition de fin de récursivité est quand la chaine à traduire est vide.

Voici le code :

1
2
3
4
5
6
7
8
9
10
def _try(s):
    if not s:
        return 1
    c = 0
    for m in mots:
        if m == s[:len(m)]:
            c += _try(s[len(m):])
    return c

print _try(morse)

Première optimisation

Le problème avec les fonctions récursives, c’est souvent le temps d’exécution. Ici, c’était juste désastreux. La première optimisation que je vois, c’est dans ma boucle qui test les mots. J’ai décidé d’essayer de ne couper ma chaine qu’une seule fois pour chaque longueur de mot. Puis d’essayer de trouver cette chaine dans un dictionnaire. J’ai parier sur le fait que la recherche dans un dictionnaire est très optimisé.

Je change donc ma routine de génération du dictionnaire :

1
2
3
4
5
6
7
8
lmots = 0
mots = {}
for i in range(n):
    m = raw_input()
    m2 = encode(m)
    if len(m2) > lmots:
        lmots = len(m2)
    mots[m2] = m

Et ma routine de recherche :

1
2
3
4
5
6
7
8
9
def _try(s):
    if not s:
        return 1
    c = 0
    for i in range(min(lmots, len(s))):
        m = s[:i+1]
        if mots.has_key(m):
            c += _try(s[i+1:])
    return c

Ainsi, dans la boucle qui est dans la fonction de recherche, je passe d’une boucle qui fait la longueur des mots de mon dictionnaire, à une boucle dont la longueur est égale au mot le plus long de mon dictionnaire. Sur un gros dictionnaire, ça peut faire une sacré économie. Mais ce n’est pas encore vraiment ça. En particulier le test 4 met une éternité… Comme j’en avais un peu marre, c’est le code que j’ai soumis au bout de 52 minutes.

Le bug

Mais je me suis planté. J’avais introduit un bug en utilisant un dictionnaire. Le bug est pourtant évident, c’est même le sujet de l’épreuve. Une suite de . et – en morse peut correspondre à plusieurs suites de lettres différentes. Et en créant mon dictionnaire, comme j’utilise le code morse comme clé, si plusieurs mots dans le dictionnaire donne la même clé, je n’enregistre que le dernier de ces mots. J’oublie donc des mots, et donc, des solutions.

Pour corriger ça, je décide donc de stocker le nombre de mots possibles pour chaque clé.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
lmots = 0
mots = {}
for j in range(n):
    m = encode(raw_input())
    lmots = max(len(m), lmots)
    mots[m] = mots.get(m, 0) + 1

def _try(s):
    if not s:
        return 1
    c = 0
    for i in range(min(lmots, len(s))):
        m = s[:i+1]
        if mots.has_key(m):
            c += mots[m] * _try(s[i+1:])
    return c

Le bug est corrigé, mais l’exécution est toujours terriblement lente !

Dernière optimisation

Il y a une optimisation évidente. On appel _try sur le reste de la chaine. Si par hasard, en trouvant un autre début de mot, on se retrouve avec la même fin de chaine, il n’y a aucun intérêt à recalculer toute la chaine. Vous l’avez compris, je parle ici de faire du cache !

Voici mon implémentation :

1
2
3
4
5
6
7
8
9
10
11
12
13
cache = {}
def _try(s):
    if len(s) in cache:
        return cache[len(s)]
    if not s:
        return 1
    c = 0
    for i in range(min(lmots, len(s))):
        m = s[:i+1]
        if mots.has_key(m):
            c += len(mots[m]) * _try(s[i+1:])
    cache[len(s)] = c
    return c

Et voilà ! Avec cette petite optimisation, j’arrive à exécuter le test 4 en moins d’une demi seconde. Contrat rempli, 100% des tests passent !

Laisser un commentaire

Votre adresse de messagerie ne sera pas publiée. Les champs obligatoires sont indiqués avec *

Vous pouvez utiliser ces balises et attributs HTML : <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code class="" title="" data-url=""> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong> <pre class="" title="" data-url=""> <span class="" title="" data-url="">