Forum Programmation.c Challenge Codingame n°3

Posté par BeberKing (site web personnel) le 30 janvier 2013 à 10:48. Licence CC By‑SA.

Étiquettes :

jan.

2013

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'algorithme
on 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 le 30 janvier 2013 à 11:07. É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 le 30 janvier 2013 à 11:12. Évalué à 3.
  
  Modifier l'énoncé d'un problème n'est pas une solution au problème.
  - [^] # Re: probleme 1
    
    Posté par Anonyme le 30 janvier 2013 à 11:22. É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 le 30 janvier 2013 à 11:25. Évalué à 1.

Tu peux détailler ton algo glouton?
- [^] # Re: Problème 2
  
  Posté par BeberKing (site web personnel) le 30 janvier 2013 à 11:42. É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 :
```
    struct job
    {
       int j,d;
    };

    static int compare (void const *a, void const *b)
    {
       struct job const *pa = a;
       struct job const *pb = b;
       return pb->j - pa->j;
    }

    int main()
    {
        int n;
        scanf("%d", &n);
        struct job jobs[100000];

        for (int i = 0; i < n; i++)
            scanf("%d %d",&jobs[i].j,&jobs[i].d);
        qsort (jobs, n, sizeof *jobs, compare);

        int x=2000000, total=0;
        for (int i = 0; i < n; i++) {
            if (jobs[i].j+jobs[i].d<=x){
                ++total;
                x=jobs[i].j;
            }
        }
        printf("%d",total);
        return 0;
    }
```
  Ç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 le 30 janvier 2013 à 23:22. É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) le 31 janvier 2013 à 09:38. É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 le 30 janvier 2013 à 12:35. Évalué à 1.

Je ne savais pas que le concours duré 5h, sinon j'aurai implémenté quelque chose comme:

convertir les mots du vocabulaire en morse.
inserré ces mots en morse dans une sorte d'arbre binaire, qui lorsqu'on lui donne un le message en morse, retourne la liste des mots qui corresponde.
a partir de la liste des mots qui corresponde faire une fonction récursive qui recommence le processus précédent avec le message en morse tronqué d'un des mots précédent correspondant, répéter le processus jusqua ce que plus de correspondances ne soit trouvé ou que le message ait été entiérement tronqué.

Je vais l'écrire en python tout à l'heure.

[^] # Re: Problème 3

Posté par lendemain le 30 janvier 2013 à 14:17. Évalué à 2.

j'ai pas testé mais ça devrait ressembler à :

import sys

morse = raw_input()
voc = []

for i in xrange(int(raw_input())):
    voc.append(raw_input())

dict = {"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": "--.."}


struct = [[], []];

def insert_in_struct(v):
    curr_struct = struct
    for i in list(v):
        if i == ".":
            if curr_struct[0] == []:
                curr_struct[0] = [[], []]
            curr_struct = curr_struct[0]
        else:
            if curr_struct[1] == []:
                curr_struct[1] = [[], []]
            curr_struct = curr_struct[1]
    curr_struct.append(v)

# insert_in_struct("..--.")
# insert_in_struct("..--..-")
# insert_in_struct("..--.-")

# insert_in_struct("--.-")
# insert_in_struct("--...")

# a quoi resemble la structure de donnée
# [[[[], [[], [[[[], [[], [], '..--..-']], [[], [], '..--.-'], '..--.'], []]]], []], [[], [[[[[], [], '--...'], []], [[], [], '--.-']], []]]]

def possible_words(msg):
    curr_struct = struct
    res = []
    for i in list(msg):
        if len(curr_struct) > 2:
            res += curr_struct[2:]
        if curr_struct == []:
            return res
        if i == ".":
            curr_struct = curr_struct[0]
        else:
            curr_struct = curr_struct[1]
    return res

# print possible_words("..--..--")
# avec les valeurs précédentes ['..--.', '..--..-']


def to_morse(l):
    return dict[l.upper()]

for i in voc:
    insert_in_struct("".join(map(to_morse, list(i))))


def decode(morse,nb):
    if morse == "":
        return [nb]
    a = possible_words(morse)
    if a == []:
        return [0]
    a = map(lambda x: morse[len(x):])
    r = []
    for i in a:
        r += decode(i, nb + 1)
    return r

print max(decode(morse,0))

[^] # Re: Problème 3

Posté par totof2000 le 30 janvier 2013 à 15:40. É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) le 30 janvier 2013 à 15:51. É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 le 30 janvier 2013 à 23:23. É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:

import sys

morse = { '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': '--..',
}

l = sys.stdin.readline()[:-1]
n = int(sys.stdin.readline()[:-1])
words = []
for _ in xrange(n):
    words.append(sys.stdin.readline()[:-1])

mwords = ["".join(morse[c] for c in w) for w in words]
M=max(len(mw) for mw in mwords)
smwords = set(mwords)

nbr = [0 for _ in xrange(len(l)+1)]
nbr[0] = 1
for i in xrange(1,len(nbr)):
    for j in xrange(i-M,i-1):
        if j>=0 and l[j: i] in smwords: 
            nbr[i] += nbr[j]

print nbr[-1]

# Je voulais participer, mais...

Posté par liberforce (site web personnel) le 30 janvier 2013 à 13:53. É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 le 30 janvier 2013 à 14:57. É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 le 13 février 2013 à 15:35. É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) le 31 janvier 2013 à 23:26. É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 le 01 février 2013 à 13:43. É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) le 01 février 2013 à 03:41. É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.