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 !
Commentaires récents