Forum Programmation.autre exercices donnés au codinggame n°2

Posté par Xavier Faure (site web personnel) le 26 octobre 2012 à 16:10.

Étiquettes :

oct.

2012

Bonjour à tous, j'ai participé hier au codinggame n°2 avec Python. Mon résultat est franchement médiocre (82e, mes algorithmes étaient corrects mais trop lent pour satisfaire les derniers tests) et j'aimerais savoir comment résoudre le troisième problème donné en un temps acceptable (je crois avoir trouvé depuis une solution rapide au n°2).

Si certains sont intéressés je peux donner mes solutions pour les deux premiers problèmes.

PS :
les trois questions :
http://www.codingame.com/challenge2_question1
http://www.codingame.com/challenge2_question2
http://www.codingame.com/challenge2_question3

# Après les journaux bookmark, les questions bookmark

Posté par calandoa le 26 octobre 2012 à 17:29. Évalué à 5.

Ce qui serait pas mal, ça serait plutôt de donner les énoncés… je viens de passer 5 mn à cliquer partout sur ce foutu site sans aucun résultat.
- [^] # Re: Après les journaux bookmark, les questions bookmark
  
  Posté par Xavier Faure (site web personnel) le 26 octobre 2012 à 18:59. Évalué à 2.
  
  C'est exact, c'est pourquoi je viens de donner quelques liens dans mon post initial.
  
  Trust the Python !
# Principe de l'algo

Posté par BeberKing (site web personnel) le 26 octobre 2012 à 18:01. Évalué à 3.

L'idée, c'est de trouver la hauteur y du câble central qui permet de minimiser la somme des distances au câble central. Il se trouve que la médiane permet d'atteindre ce minimum. C'est pas forcément intuitif, mais une fois qu'on sait que c'est la médiane, ça se démontre. Quand il y a 2 médianes (nb pair de valeurs), toutes les valeurs entre ces 2 médianes atteignent le minimum. Et hier une simple recherche sur "minimiser somme des valeurs absolue" m'a permis de trouver que c'était la médiane.

Donc tu calcules la médiane des y, tu calcules la somme |y[i]-median(y)| et tu ajoutes x_max-x_min pour la longueur du câble central.
- [^] # Re: Principe de l'algo
  
  Posté par Xavier Faure (site web personnel) le 26 octobre 2012 à 18:58. Évalué à 1.
  
  Merci de cette réponse très intéressante.
  
  Trust the Python !
- [^] # Re: Principe de l'algo
  
  Posté par BAud (site web personnel) le 26 octobre 2012 à 21:34. Évalué à 3.
  Il se trouve que la médiane permet d'atteindre ce minimum. C'est pas forcément intuitif, mais une fois qu'on sait que c'est la médiane, ça se démontre
  
  ce n'est pas (plus) un truc qu'on voit en 1ère S (bon ok, ya pu de 1ère S…) ?
  - conservation des forces (en vectoriel)
  - conservation du moment des forces (Force*distance…)
  - application géométrique (trait à la règle sur un schéma)
  (bon, je fais ça de mémoire hein).
# magnifique

Posté par chamandier le 27 octobre 2012 à 11:21. Évalué à 3.

…animation illustrant le cycle : je bidouille, je teste, je bidouille.
# Pas bien intéressant...

Posté par arnaudus le 27 octobre 2012 à 20:10. Évalué à 6.
Ça n'engage que moi, mais je trouve que les exercices ne sont pas assez intéressants pour ce type de concours. Leur difficulté principale reste la modélisation du problème et la découverte d'une solution mathématique. Le code, au final, contiendra surtout des entrées sorties, et deux lignes pour l'algorithme.

L'autre problème, c'est que le peu d'algorithmique présente est purement scolaire : trier, prendre le maximum, le minimum, la médiane, etc. Quelqu'un qui a bien révisé peut coder ça sans réfléchir, mais ça n'a vraiment aucun intérêt, puisque dans la vraie vie, on a tout intérêt à utiliser des bibliothèques optimisées et débugguées pour ça. Je pense qu'en 2012, on doit réfléchir autrement sur ce qu'est un programmeur efficace : quelqu'un qui sait utiliser les bons design patterns, les bons outils, les bonnes briques logicielles existantes, etc. Il existe d'excellents exercices d'algorithmique : concevoir une intelligence artificielle pour un jeu, par exemple. Des trucs où il faut être inventif et précis, avoir une bonne intuition sur les contraintes à l'utilisation (identifier tôt les bottlenecks potentiels), etc.

En gros, j'ai l'impression de pouvoir résoudre ces problèmes en 3 lignes avec un langage de haut niveau. Sérieux, en R, la réponse au problème 3 est
```
m <- matrix(scan("")[-1], ncol=2, byrow=TRUE)
print( diff(range(m[,1])) + sum(abs(m[,2]-median(m[,2]))) )
```
Il n'y a rien à coder une fois la solution mathématique trouvée.
- [^] # Re: Pas bien intéressant...
  
  Posté par arnaudus le 28 octobre 2012 à 00:07. Évalué à 2.
  Tiens, pour jouer, voici la solution du 2 en R :
```
s <- scan("stdin")[-1]
m <- which(s==min(s))
cat(min(s)-max(s[1:m[length(m)]]),"\n")
```
  Encore une fois, il n'y a même pas d'algorithme : on a une entrée, un calcul hyper simple, et une sortie. La seule difficulté de l'exercice, c'est la modélisation du problème, et éventuellement savoir coder min() et max() si le langage n'offre pas des fonctions aussi simples.
  
  Bref, je confirme que les problèmes sont bien trop ennuyeux à mon goût.
  - [^] # Re: Pas bien intéressant...
    
    Posté par brendel le 29 octobre 2012 à 16:05. Évalué à 3.
    
    Et pour la 1? R est pas bien adapté je pense :) (Je connais quasiment pas R, donc je dit peut être n'importe quoi)
    - [^] # Re: Pas bien intéressant...
      
      Posté par arnaudus le 29 octobre 2012 à 18:43. Évalué à 2.
      
      Si c'est tout à fait possible (peut-être 4 lignes), mais j'ai eu la flemme :-)
  - [^] # Re: Pas bien intéressant...
    
    Posté par brendel le 29 octobre 2012 à 16:38. Évalué à 2.
    
    Heu ta question 2 me semble fausse, si je ne fais pas d'erreur : il se peut que la plus grande distance ne concerne pas le minimum de la séquence.
    Par exemple, sur la séquence "2 -8 89 -1", ta réponse retourne -10, alors qu'il faut retourner -90.
    - [^] # Re: Pas bien intéressant...
      
      Posté par arnaudus le 29 octobre 2012 à 18:57. Évalué à 2.
      Tu as raison, mais mon code a passé les 5 tests proposés sur le site, je n'ai pas cherché plus loin. Du coup, mon argument "c'est trop simple" tombe à l'eau, non? :-) Bon, ce n'est pas si compliqué que ça, il faut appliquer la recherche entre le début et le dernier minimum, et entre le premier maximum et la fin, et prendre la plus grande différence.
      
      s <- scan("stdin")[-1] lastmin <- min(s)-max(s[1:rev(which(s==min(s)))[1]]) firstmax <- min(s[which(s==max(s))[1]:length(s)])-max(s) cat(min(lastmin, firstmax),"\n")
      - [^] # Re: Pas bien intéressant...
        
        Posté par brendel le 29 octobre 2012 à 19:21. Évalué à 1.
        
        Oui, mais comme tu dis c'est un peu plus compliqué, il faut rappeler qu'il n'y a que 3 heures pour les 3 questions. Bon, comme toi j'aurais préféré plus de temps/moins de questions, mais des plus intéressantes (enfin, si j'avais participé, je n'était pas dispo jeudi à 18h).
        
        Sinon c'est joli d'écrire ça en 4 lignes mais il y a plus efficace : on peut faire ça en une passe, ton programme en fait 7, si je compte bien (allez, 5 si R est assez bon pour ne pas exécuter les 2 min(s) et les 2 max(s), mais sans dire que s est non mutable, c'est pas forcement évident).
        
        Bon après, je pense qu'il suffit d'être en O(n) pour passer les tests…
        
        [^] # Re: Pas bien intéressant...
        
        Posté par arnaudus le 29 octobre 2012 à 19:43. Évalué à 2.
        
        c'est joli d'écrire ça en 4 lignes mais il y a plus efficace
        
        Certes, on peut écrire ça en assembleur aussi… Je ne suis pas certain que les consignes étaient spécialement claires. Apparemment, la lisibilité était évaluée sur des critères peu convainquants, et je n'ai pas lu de remarques sur le contexte. Typiquement, le code le plus efficace devra tenir compte des contraintes (exécuter rarement sur des gros jeux de données, exécuter des milliers de fois sur des vecteurs de taille 10, etc) qui peuvent rendre toute tentative d'optimisation a priori totalement contre-productive.
        
        si R est assez bon pour ne pas exécuter les 2 min(s)
        
        Ça me parait très peu probable. R est un langage de script, il exécute les instructions les unes après les autres. Par contre, je ne suis pas convaincu que le stockage du contenu des min et des max soit plus rapide que le double appel à la fonction : c'est complètement empirique.
        
        [^] # Re: Pas bien intéressant...
        
        Posté par brendel le 29 octobre 2012 à 19:59. Évalué à 2. Dernière modification le 29 octobre 2012 à 20:00.
        
        Certes, on peut écrire ça en assembleur aussi…
        
        Je parle pas du langage, mais d'écrire un algo qui ne lit qu'une fois les données. Certes ici l'important est de trouver un algo en O(n), mais bon c'est pas très élégant exécuter pleins de fonctions à la suite sur la séquence quand la parcourir une fois suffit :) Ici ça aurait pas un vrai impact sur l'efficacité je pense.
        
        Apparemment, la lisibilité était évaluée sur des critères peu convainquants, et je n'ai pas lu de remarques sur le contexte.
        
        C'est LE gros point noir du concours : on avait aucune idée de comment on était évalué. Au final les candidats sont classés d'abord par pourcentage de tests passés, ensuite par le temps total à coder les 3 questions (et donc ici un langage de haut niveau qui permet d'écrire les réponses en 4 ligne est très avantageux :p). Un test passé c'est résultat correct et respect des contraintes de temps et mémoire.
        
        Par contre, je ne suis pas convaincu que le stockage du contenu des min et des max soit plus rapide que le double appel à la fonction : c'est complètement empirique.
        
        Pas trop compris : quand tu écris min(s), ça veut dire exécuter la fonction et stocker le résultat dans un variable anonyme. Lire cette variable plutôt que ré-exécuter min(s) et donc stocker le même résultat dans une autre variable anonyme me semble forcement plus rapide
        
        [^] # Re: Pas bien intéressant...
        
        Posté par arnaudus le 29 octobre 2012 à 23:24. Évalué à 2.
        
        c'est pas très élégant exécuter pleins de fonctions à la suite sur la séquence quand la parcourir une fois suffit
        
        Ah, je pense que c'est un problème de culture et de définition de l'«élégance» :-) Classiquement, quand on utilise un langage de haut niveau, on est moins exigeant sur la performance brute. Je n'ai pas de culture algorithmique, et à mes yeux, quelque chose comme "amplitude <- max(x) - min(x)" est beaucoup plus élégant qu'une boucle qui ne fait qu'une passe : quelque part, on touche presque au langage naturel.
        
        L'autre truc, c'est que quand on a un langage non compilé, on ne peut que deviner la manière dont les opérations sont optimisées, mais en faisant les tests, on peut avoir des surprises :
        
        x <- rnorm(10000000) > system.time(max(x)-min(x)) user system elapsed 0.128 0.000 0.132 > system.time(diff(range(x))) user system elapsed 0.160 0.044 0.212
        
        Visiblement, dans ce cas, il vaut mieux faire deux passes qu'une seule (je ne sais pas pourquoi, ça vient peut-être de l'implémentation en C des fonctions correspondantes).
      - [^] # Re: Pas bien intéressant...
        
        Posté par arnaudus le 29 octobre 2012 à 19:30. Évalué à 2. Dernière modification le 29 octobre 2012 à 22:42.
        
        Je m'auto-réponds encore une fois (rien que pour le plaisir de voir les geekscottes), il y a beaucoup plus simple (mais en O(n²))! . Je ne sais pas si la lisibilité et la concision étaient privilégiées sur l'efficacité.
        
        s <- scan("stdin")[-1] cat(min(sapply(1:length(s), FUN=function(x) { min(s[x:length(s)]-s[x])})))
      - [^] # Re: Pas bien intéressant...
        
        Posté par brendel le 30 octobre 2012 à 18:33. Évalué à 2.
        
        Tiens, cette réponse est aussi fausse : ça ne marche pas avec 3 1 27 5 30 29 :)
        
        [^] # Re: Pas bien intéressant...
        
        Posté par brendel le 30 octobre 2012 à 19:30. Évalué à 2. Dernière modification le 30 octobre 2012 à 19:31.
        
        Mon code en C qui marche avec les séquences précédentes (et leurs tests):
        
        int main() { int n1 = -1; unsigned int n2 = 2e31+1; int pot_n1 = -1, distance_max = 1; int n; scanf("%d", &n); int x; for(int i=0; i<n; i++) { scanf("%d",&x); if(x > n1 && x > pot_n1) pot_n1 = x; else if(x < n2) { n2 = x; distance_max = n2 - n1; } if(x-pot_n1 < distance_max) { n1 = pot_n1; pot_n1 = -1; n2 = x; distance_max = n2-n1; } } if(n2>n1) printf("0\n"); else printf("%d\n",distance_max); return 0; }
        
        [^] # Re: Pas bien intéressant...
        
        Posté par arnaudus le 30 octobre 2012 à 22:14. Évalué à 2. Dernière modification le 30 octobre 2012 à 22:17.
        
        Eh mon code de 2 lignes fonctionne, lui :-) Par contre, je ne vois pas l'intérêt de fournir 5 tests qui ne font pas le tour des possibilités. Ça veut dire qu'un algo faux peut avoir tous les points?
        
        En tout cas, ça confirme bien mon idée de départ, le problème est bien de trouver la solution mathématique à l'exercice, pas de l'implémenter.
        
        [^] # Re: Pas bien intéressant...
        
        Posté par brendel le 30 octobre 2012 à 22:21. Évalué à 1. Dernière modification le 30 octobre 2012 à 22:23.
        
        Ton code en deux ligne est en O( n² ), ça m'étonnerais qu'il passe les tests avec des gros jeux de données. Les tests fournis sont à titre d'exemples, les tests utilisés pour ton score final ne sont pas publics, et on espère bien plus fourni.
        
        En tout cas, ça confirme bien mon idée de départ, le problème est bien de trouver la solution mathématique à l'exercice, pas de l'implémenter.
        
        Ici il s'agit de trouver un algo et de l’implémenter… C'est claire que c'est un concours d'algorithme plus que de programmation :)

Suivre le flux des commentaires

Note : les commentaires appartiennent à celles et ceux qui les ont postés. Nous n’en sommes pas responsables.