Salut à tous,
Pour ceux qui ont participé au challenge Codingame hier, avez-vous trouvé toutes les solutions ? J'ai terminé à 82 % car ma solution au dernier exercice n'était pas du tout optimisée et dépassait 1sec sur les cas non triviaux. Pour ceux qui ont trouvé, pourriez-vous donner votre solution en commentaire ?
Pour mémoire, les 3 problèmes :
coder un mot (chaîne ASCII) en une suite de 0 et d'espaces. 2 blocs par série de bits identiques : un bloc 0 (pour des 0) ou 00 (pour des 1), puis un bloc de zéro de même longueur que la série de bits.
ex : C -> 0100011 -> 0 0 00 0 0 000 00 00
assez facile, en terme d'algorithmeon a une série de jobs à lancer sur une machine avec la date de départ et la durée. Pas de parallélisation possible. Donner le nombre max de jobs que l'on peut exécuter. j'ai trié les jobs par date décroissante, puis j'ai fait un algorithme glouton.
on a un message en morse (chaque lettre a un nombre variable de . et de -, entre 1 et 4) sans les espaces et un dictionnaire. Trouver le nombre d'interprétation possibles du message avec seulement les mots du dictionnaire.
j'ai juste tenté une recherche exhaustive, et ça coinçait sur les gros exemples. Je pense qu'en triant le dictionnaire (en morse), j'aurais pu restreindre le nombre de cas à tester, mais je ne sais pas si ça aurait suffit (et si le tri passait dans le temps machine imparti).
# probleme 1
Posté par Anonyme . Évalué à -1.
tu aurais pu simplifier:
valeur= 0, '0' = un bit (quelque soit sa valeur), ' '=changement de valeur
du coup ton exemple donne: 0 0 000 00
[^] # Re: probleme 1
Posté par Strash . Évalué à 3.
Modifier l'énoncé d'un problème n'est pas une solution au problème.
[^] # Re: probleme 1
Posté par Anonyme . Évalué à 0.
oops, je n'avais pas fait attention: je pensais que ce qui suivait la première phrase était sa solution
# Problème 2
Posté par brendel . Évalué à 1.
Tu peux détailler ton algo glouton?
[^] # Re: Problème 2
Posté par BeberKing (site web personnel) . Évalué à 3. Dernière modification le 30 janvier 2013 à 12:46.
Tu considères les jobs par date décroissante (en partant de la dernière jusqu'à la première). Pour chaque job, tu vérifies si tu peux le lancer en fonction des jobs (postérieurs) déjà lancés. Mon code pas très propre :
Ça marche bien, sauf que dans la vraie vie on sait rarement à l'avance quels seront les futurs jobs.
[^] # Re: Problème 2
Posté par oao . Évalué à 1.
Malin. C'est un problème connu ou tu as trouvé la solution sur le coup ?
[^] # Re: Problème 2
Posté par BeberKing (site web personnel) . Évalué à 1.
Je me souviens qu'il y avait un chapitre sur l'ordonnancement dans mon cours d'algorithmique. Mais ça remonte à quelques années maintenant, donc je ne sais plus si j'avais vu ce problème là exactement ou des variantes. Disons que je n'avais pas la solution en tête en lisant l'énoncé, mais je ne l'ai pas non plus sortie du chapeau…
# Problème 3
Posté par lendemain . Évalué à 1.
Je ne savais pas que le concours duré 5h, sinon j'aurai implémenté quelque chose comme:
Je vais l'écrire en python tout à l'heure.
[^] # Re: Problème 3
Posté par lendemain . Évalué à 2.
j'ai pas testé mais ça devrait ressembler à :
[^] # Re: Problème 3
Posté par totof2000 . Évalué à 2.
On a dit en C
C'est gavant ces pythonneux qui jettent leur déchets partout comme ça !!!
[^] # Re: Problème 3
Posté par BeberKing (site web personnel) . Évalué à 2.
J'ai codé en C, c'est pour ça que j'ai classé le sujet dans Prog.C, mais je ne suis pas sectaire. D'autant plus que coder un arbre en C pour le dictionnaire prendrait quand même du temps.
[^] # Re: Problème 3
Posté par oao . Évalué à 2.
Ma solution est de ne travailler qu'en morse, et récursivement pour n de 1 à la taille L du texte (taille en morse). Pour tout n, nbr[n] est le nombre de possibilités pour faire un texte de taille n du texte. On fixe nbr[0]=1, puis on trouve nbr[n]=somme(nbr[j], j=n-M…n-1), avec M la taille maximale que peut faire un mot, écrit en morse.
La complexité est en O(M*L*log(N)), avec N le nombre de mots dans le dictionnaire. Il faut tester l'existence d'un mot en utilisant des ensembles, pour avoir un test efficace en log(N).
Mon code:
# Je voulais participer, mais...
Posté par liberforce (site web personnel) . Évalué à 2. Dernière modification le 30 janvier 2013 à 13:53.
En fait aucune des boîtes associées ne proposait de choses intéressantes pour moi. Du coup j'ai préféré finir d'écrire mon "résumé" anglais pour essayer de trouver un vrai job. Merci de donner les problèmes, ils n'étaient pas accessibles sur leur site si on arrivait trop tard.
# Python vs Java
Posté par bibitte . Évalué à 5.
Tiens c'est bizarre un code pour un code en python la limite de temps d’exécution est de 6 secondes (python 2.6.6) et pour le Java (java 7) c'est seulement 2.
voir tableau de la FAQ : http://www.codingame.com/cg/#!faq
Java est donc 3 fois plus rapide que python ? (je sais il est gros est bien poilu).
[^] # Re: Python vs Java
Posté par steph1978 . Évalué à 2.
ils ont classé : langages compilés en natif, langage compilés en bytecode avec lancement d'une VM, langage interprétés avec lancement de l'interpréteur.
l'objectif n'est pas la perf mais la complexité algorithmique.
bref, c'est pas hyper trollesque.
# Les debriefing est dispo
Posté par Nicolas Antoniazzi (site web personnel) . Évalué à 2.
Le debriefing du concours est disponible sur le blog de CodinGame, avec des petites stats.
http://blogfr.codingame.com/2013/01/golden-developers.html
Il y a aussi les liens avec les exercices du concours pour les refaire en entrainement
Conclusion : Les développeurs C sont nuls à coté des développeurs Python ;)
[^] # Re: Les debriefing est dispo
Posté par NeoX . Évalué à 2.
sympa leur petit IDE en interface web avec le code, le test et le resultat
# Sujet intéressant.
Posté par Axioplase ıɥs∀ (site web personnel) . Évalué à 1. Dernière modification le 01 février 2013 à 03:42.
J'ai pas joué, mais, c'est sympa. Ça ferait des bonnes questions d'entretiens d'embauche :)
1/ Se résout en écrivant une machine à états finis.
2/ L'algo glouton est la solution la plus simple. Ce problème est décrit en détails dans Introduction to Algorithms, par Cormen et al.
3/ Un exemple classique de programmation dynamique. Si tu avais mis dans un cache les résultats des sous-problèmes déjà calculés à une position donnée la chaîne, tu aurais résolu le problème très vite, à mon avis en quelque millisecondes.
En revanche, ça prend pas cinq heures… une heure devrait suffire.
Suivre le flux des commentaires
Note : les commentaires appartiennent à celles et ceux qui les ont postés. Nous n’en sommes pas responsables.