«

»

Mar 27 2013

CodinGame de mars

Hier, j’ai participé au concours CodinGame de mars. J’ai trouvé les exercices très simples par rapport à la version précédente. Cette fois, pas besoin de se prendre la tête pour trouver comment faire l’algorithme, pas besoin de se demander comment diminuer la complexité de ma récursion pour réussir à passer dans les critères de temps ou de mémoire. Ici, en lisant les premières lignes d’énoncé, je voyait déjà le code dans ma tête… Un peu décevant. Mais bon, vous allez voir que ça ne m’a pas empêché de me planter ;-).

Vous pouvez consulter les énoncés et mon code ici

Exercice 1

Le premier exercices est très simple, il faut calculer une suite.

1
2
3
4
5
6
5
1 5
1 1 1 5
3 1 1 5
1 3 2 1 1 5
1 1 1 3 1 2 2 1 1 5

Une ligne est donc composée des couples comportant le décompte des nombres similaires consécutifs et le nombre en question. Le programme, doit calculer la ligne N quand on lui donne la première ligne R et N.

J’ai décidé de ne pas me prendre la tête et de calculer séquentiellement toutes les itérations de la suite pour arriver à la ligne demandée. Il doit surement y avoir un moyen de déduire la ligne directement sans faire toutes les autres, mais bon vu les contraintes très larges et les plages de valeurs proposées, ça ne valait pas le coup. Voici mon 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
import sys

n = int(raw_input())
l = int(raw_input())
s = [ n ]
for i in xrange(l - 1):
    c = 0
    a = s[0]
    s2 = []
    for j in s:
        if a == j:
            c += 1
        elif c > 0:
            s2.append(c)
            s2.append(a)
            c = 1
        a = j
    if c > 0:
        s2.append(c)
        s2.append(a)

    s = s2

print ' '.join(['%d' % i for i in s])

Mon code à passé tous les tests avec succès. J’ai mis 16 minutes pour l’écrire.

Exercice 2

Pour l’exercice suivant, le programme doit prendre en entré un fichier structuré mais non formaté et le formater.

En lisant l’énoncé, on pense tout de suite qu’il faut écrire un parser. Mais en regardant de plus près, comme on veut juste formater, on peut simplement imprimer le code formaté au fur et à mesure que l’on avance dans la lecture du fichier, sans devoir construire une représentation du fichier complète en mémoire. Je suis donc parti sur l’écriture d’une petite machine à états.

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
import sys, re

r = re.compile('\d')

n = int(raw_input())
s = ''
for i in range(n):
    s += raw_input() + '\n'



BLOCK = 1
STRING = 2
INT = 3

state = [BLOCK]
indent = ''
i = 0
accumulator = None
statement = ''
while i < len(s):
    #print s[i], state
    if state[-1] == BLOCK:
        if s[i] == '(':
            if statement:
                print indent + statement
                statement = ''
            print indent + '('
            indent += '    '
            state.append(BLOCK)
        elif s[i] == ')':
            # print last statement
            if statement:
                print indent + statement
                statement = ''
            del state[-1]
            indent = indent [: -4]
            statement = ')'
        elif s[i] == '=':
            statement += '='
        elif s[i] == ';':
            # print last statement
            print indent + statement + ';'
            statement = ''
        elif s[i] == "'":
            state.append(STRING)
            accumulator = ''
        elif s[i:i+4] == 'null':
            i += 3
            statement = 'null'
        elif s[i:i+4] == 'true':
            i += 3
            statement = 'true'
        elif s[i:i+5] == 'false':
            i += 4
            statement = 'false'
        elif r.match(s[i]):
            state.append(INT)
            accumulator = s[i]
        else:
            # junk
            pass
    elif state[-1] == STRING:
        if s[i] == "'":
            statement += "'" + accumulator + "'"
            del state[-1]
        else:
            accumulator += s[i]
    elif state[-1] == INT:
        if r.match(s[i]):
            accumulator += s[i]
        else:
            statement += accumulator
            del state[-1]
            i -= 1
    i += 1

print statement

Après quelques petits tests, j’ai soumis mon code au bout de 52 minutes. Malheureusement, j’ai fait une petite erreur. Je n’ai pas testé le cas où j’ai une CLE_VALEUR composée avec un true, false ou null. Dans ce cas, j’écrase la variable statement au lieu de concaténer… En gros il manque un + devant les = des lignes 50, 53 et 56 ! Du coup, mon code rate deux tests.

J’obtiens donc 95% de réussite en 1h08, ce qui me classe en 95e place… Si je n’avais pas fait cette étourderie, j’aurai été 8e… C’est con ! 😉

Bon, dès que j’ai retrouvé mes codes de ma participation au coding game de janvier, je fais faire un petit article. Là, les exercices étaient beaucoup plus intéressant !

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="">