Résultats du TI-Concours 2017

[noelnadal]

Il y a un peu moins de trois semaines s'achevait la sixième édition du TI-Concours.

À présent, voici (enfin) les résultats !

Petit résumé du concours

Le samedi 25 mars dernier, trois sujets ont été publiés. Chacun d'entre eux portait sur un thème différent (jeu, algorithmique, optimisation), et il fallait en faire au moins deux sur trois en 30 jours.

Peu avant la fin, le concours a été prolongé d'une semaine. Au final, nous avons reçu six participations valides, plus une septième qui n'a pas été retenue car ne comportant qu'un seul programme. Pour rappel, l'an dernier il y avait eu 7 participations dans cette catégorie, mais il était beaucoup plus facile d'obtenir une participation valide, étant donné qu'il suffisait de traiter une des 7 (courtes) questions. Ainsi, on peut estimer que les sujets ont eu plus de succès cette année, d'autant plus que je n'ai personnellement pas reçu de critique négative vis-à-vis de ces derniers, si ce n'est qu'ils étaient plus difficiles que d'habitude.

Les six participants ont traité exactement deux sujets : quatre ont fait le premier, six le deuxième, deux le troisième.

Résultats de l'épreuve 1

L'épreuve 1 consistait en la réalisation d'un jeu. Le joueur devait incarner STV, un super-héros de Bourg-la-Reine TI-Planet venu sauver le monde de l'invasion des technolapins. En fait, derrière ce scénario apocalyptique se cachait en fait un jeu de mémoire, qui devait être codé par les participants, tout en gardant le thème de départ.

Globalement, tous les programmes respectaient les consignes. La différence s'est faite sur des critères tels que l'originalité, l'esthétisme, la fluidité, la prise en main...

1) mgeorger (87)
2) Wistaro (79)
3) m@thieu41 (77)
4) cheuble (69)

mgeorger remporte donc un autocollant TI-Planet pour cette première place dans l'épreuve 1.

Résultats de l'épreuve 2

L'épreuve 2 proposait le problème d'algorithmique suivant : TI-Bot organise un tournoi entre les membres de TI-Planet pour déterminer qui fait les meilleures blagues sur le tchat. Chaque spectateur est intéressé par les matches (en un contre un) dont le niveau attendu est compris dans un certain intervalle. Comment déterminer pour chaque spectateur le nombre de matches différents possibles susceptibles de l'intéresser ?

Il y a eu quelques dégâts sur cette épreuve. Seuls trois participants sur 6 sont parvenus à passer tous les tests, les trois autres ayant codé un programme qui provoque (plus ou moins souvent) des erreurs de mémoire. Chose assez regrettable, personne n'est parvenu à trouver l'astuce géniale, qui permettait d'obtenir un algorithme assez rapide.

1) Ruadh (100)
2) Wistaro (63.13)
3) Dark_Coco (53.33)
4) m@thieu41 (36.87)
5) mgeorger (8.67)
6) cheuble (7.33)

Désolé grosged, je n'ai pas fait tourner ton programme, mais à la lecture du code il passait tous les tests aussi.

Bravo donc à Ruadh, dont la solution battait largement les autres en termes de vitesse d'exécution, même s'il ne m'a pas battu ( ). Il remporte un autocollant TI-Planet grâce à cette première place.

Résultats de l'épreuve 3

L'épreuve 3 demandait aux participants d'aider notre cher rédacteur Alvoko, réputé pour dessiner des oeuvres d'une qualité remarquable. Surchargé de commande à cause de sa notoriété, le but était de déterminer à qui et où envoyer des colis, afin de maximiser son bénéfice.

Malheureusement, cette épreuve fut un échec pour les deux participants qui s'y sont essayés. En effet, les deux programmes provoquaient des erreurs sur la quasi-totalité des tests.

1) Ruadh (8)
2) Dark_Coco (5)

Malgré tout, Ruadh est bien premier une nouvelle fois, et remporte donc un autre autocollant TI-Planet.

Résultats finaux

Cette année, comme tous les sujets n'étaient pas obligatoires, il avait été décidé dès le début que les scores seraient harmonisés, afin que des participants qui auraient traité un sujet plus difficile ne soient pas pénalisés. Il est clair que ce n'est pas la solution miracle, et vous pouvez si vous le souhaitez donner votre avis sur la pertinence d'un tel choix. On pourra, ou non, continuer ainsi pour des éditions ultérieures.

Une autre chose : cette année, il n'y avait plus de finale. Regrettez-vous cette disparition ? Ou une seule "manche" comme cette année convient ? N'hésitez pas à faire part de vos remarques (constructives).

Toujours est-il que le classement final de cette édition du TI-Concours 2017 est le suivant.

Première place : Ruadh

Deuxième place : Wistaro

Troisième place : mgeorger

Quatrième place : m@thieu41

Cinquième place : Dark_Coco

Sixième place : cheuble

Show/Hide spoilerAfficher/Masquer le spoiler

Félicitations à Ruadh, qui remporte donc pour la deuxième fois le TI-Concours !
Il peut dès à présent contacter les administrateurs de TI-Planet pour réclamer le lot de son choix (descendre un peu pour la liste des lots). L'autre lot ira à Wistaro, deuxième du TI-Concours 2017.

Pour rappel, tous le monde ayant obtenu un score strictement positif, les six participants reçoivent un compte premium TI-Planet.

Merci à tous pour votre participation, et, je l'espère, à l'année prochaine !

[grosged]

sincères félicitations !

[critor]

Félicitations aux gagnants, ainsi qu'à tous les participants !

[Wistaro]

Bravo à tous le monde!

Je veux bien connaître ton astuce miracle noelnadal

Honnêtement, j'étais loin d'imaginer avoir cette place.
Sur le sujet 2, je trouvais mon algo lent, et les autres (Ruadh, Mathieu....) me parlait de leur solution qui semblait beaucoup plus rapide que la mienne...
Désolé donc noelnadal d'avoir été peut-être un peu énervant vers la fin, j'étais quasi-certain de finir dans les derniers à cette épreuve, et donc au classement global...

[Ruadh]

Félicitations à tous les participants !

[noelnadal]

Alors l'astuce géniale, je vais vous en parler un petit peu.
Je précise que c'est une astuce qui rend l'algorithme asymptotiquement plus rapide, et donc, dans certains cas, l'algorithme de Ruadh par exemple fait l'affaire, notamment lorsque L1 prend des valeurs assez grandes.

Considérons la liste L4 (par exemple), définie comme suit : L4(i) est le nombre de participants dont le niveau est (i-1). On met (i-1) au lieu de i pour ne pas oublier les gens qui sont au niveau 0. À noter qu'une liste ne contient qu'au plus 999 éléments, donc il fallait typiquement en utiliser une deuxième pour stocker ce qui débordait.

En fait, on va considérer cette liste L4 comme un polynôme P(X) = L4(1) + L4(2)X + L4(3)X^2 + ... + L4(M)X^(M-1), avec M = dim(L4). Maintenant, si on calcule P(X) * P(X), puis que, pour chaque indice 1≤i≤M, on retranche L4(i)*L4(i) - (L4(i)*(L4(i)-1))/2 (qu'on peut simplifier, mais c'est pour que vous compreniez après) au coefficient 2i du polynôme résultant, alors, vous remarquerez que chaque coefficient j du résultat est égal au nombre de matches possibles de niveau j.

Ensuite, pour que le programme soit réellement efficace, il fallait multiplier le polynôme par lui-même de manière rapide. On pouvait par exemple utiliser l'algorithme de Karatsuba (https://fr.wikipedia.org/wiki/Algorithme_de_Karatsuba), ou, si vous êtes courageux, l'algorithme utilisant la Transformée de Fourier Rapide, en plus efficace asymptotiquement, mais assez compliqué à comprendre et à coder. Dans les deux cas, il fallait implémenter un algorithme récursif en TI-Basic (e)z80, ce qui n'est pas si facile que ça...

Après, on pouvait utiliser la technique des sommes partielles pour répondre à chaque spectateur en temps constant.

À noter que je n'ai pas eu le courage d'implémenter la méthode avec la Transformée de Fourier Rapide. Je ne suis même pas sûr qu'elle ait un meilleur score, vu qu'il faut en théorie atteindre des valeurs de N assez élevées pour que ça ait un intérêt.

Notez aussi que pour stocker le polynôme résultant, il faut utiliser au moins deux listes, ce qui complique l'implémentation. Mais bon, vous aviez presque 37 jours, et aussi, on pouvait utiliser des matrices...

[Wistaro]

Je pas sûr d'avoir bien compris ton algo..
Quel rapport entre la FFT et la multiplication rapide de polynômes..?

[noelnadal]

Je pas sûr d'avoir bien compris ton algo..
Quel rapport entre la FFT et la multiplication rapide de polynômes..?

Il existe un algorithme quasi-linéaire en temps de multiplication de polynôme utilisant la FFT.

[m@thieu41]

Bravo à tout le monde !

Considérons la liste L4 (par exemple), définie comme suit : L4(i) est le nombre de participants dont le niveau est (i-1). On met (i-1) au lieu de i pour ne pas oublier les gens qui sont au niveau 0. À noter qu'une liste ne contient qu'au plus 999 éléments, donc il fallait typiquement en utiliser une deuxième pour stocker ce qui débordait.

En fait, on va considérer cette liste L4 comme un polynôme P(X) = L4(1) + L4(2)X + L4(3)X^2 + ... + L4(M)X^(M-1), avec M = dim(L4). Maintenant, si on calcule P(X) * P(X), puis que, pour chaque indice 1≤i≤M, on retranche L4(i)*L4(i) - (L4(i)*(L4(i)-1))/2 (qu'on peut simplifier, mais c'est pour que vous compreniez après) au coefficient 2i du polynôme résultant, alors, vous remarquerez que chaque coefficient j du résultat est égal au nombre de matches possibles de niveau j.

Du coup pour stocker P², il faut 4 listes

C'est assez ressemblant à ce que j'ai fait (j'ai essayé de faire un segment tree (avec des matrices pour les dépassements de mémoire... beurk)), sauf que tu gagnes du temps sur la génération, moi sur la récupération des valeurs.


Argh des erreurs mémoire ? Quand ça ?


Quelle était la stratégie des autres ?

[noelnadal]

Concrètement la taille de ta matrice [A] dépendait de max(L1), et pour des valeurs élevées, ça me faisait une erreur mémoire. Typiquement, pour max(L1) = 1337, t'avais une matrice de taille 55*98, un truc comme ça...

La plupart des gens ont opté pour une approche naïve, plus ou moins bien implémentée, qui consistait à regarder pour chaque match distinct et chaque requête s'il fallait incrémenter le résultat ou pas. Ça mettait pas mal de temps à tourner, il faut le dire...