Forum Programmation.c Challenge Codingame n°3

Posté par  (site web personnel) . Licence CC By‑SA.
Étiquettes :
5
30
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  . É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  . Évalué à 3.

      Modifier l'énoncé d'un problème n'est pas une solution au problème.

      • [^] # Re: probleme 1

        Posté par  . É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  . Évalué à 1.

    Tu peux détailler ton algo glouton?

    • [^] # Re: Problème 2

      Posté par  (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 :

          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  . Évalué à 1.

        Malin. C'est un problème connu ou tu as trouvé la solution sur le coup ?

        • [^] # Re: Problème 2

          Posté par  (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  . É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  . É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  . É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  (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  . É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  (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  . É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  . É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  (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 ;)

  • # Sujet intéressant.

    Posté par  (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.