Sujet : Problèmes algorithmiques avancés
Bonjour à tous,
Si vous aimez les problèmes algorithmiques dont il n'est pas possible de trouver la solution optimale en temps fini, n'hésitez pas à faire un tour sur http://primers.xyz ! C'est un site inspiré de la compétition du Google Hash Code où l'objectif est de faire le meilleur score possible sur chaque problème.
ah c'est rigolo ca. C'est des problemes d'algo classiques reformule pour etre plus "sexy". Merci du lien.
Hey, c'est super sympa comme site, merci du partage ! 
Ca a l'air cool !
Qui est chaud pour m'affronter sur l'un des problèmes ? 
Arf je viens de commencer le Agar.IA.
Par contre, on est d'accord que, les instances des problèmes étant des entités finies, rien n'empêche quelqu'un de faire une brute force et de trouver la meilleur solution de cette manière ? Et du coup il a le meilleur score, étant donné que la performance de l'algo entre pas en compte. Je sais que c'est pas l'esprit du site, mais on est bien d'accord ?^^
pour art, en premiere solution ca donne furieusement envie de construire un quadtree et de n'utiliser que fill.
en deuxieme solution tu rajoute une heuristique a chaque noeud qui soit fait le truc du quadtree soit fill toute la zone et clear les pixels qui ne vont pas.
c'est bizarre comme probleme parceque clear n'est pas en carre, mais en pixel...
Pour art optimal,vu que la seule contrainte c'est de faire le minimum d'operations de Fill et de Erase, une solution peut être de faire du backtracking, d'attendre 10 ans et de lui donner la solution optimale à la fin 
Colllax : ==> c'est ce que je dis. Après j'ai pas étudié la complexité précise du problème, si ça se trouve même sur une machine parallèlle l'instance du problème est pas bruteforcable en moins de quelques années ^^
Triple14, compte tenu que ca vient d'un concours de google, j'imagine qu'ils ont penser a se proteger du bruteforce.
NdM: Ca vous dirait de faire un topic par probleme qui vous interesse et de debattre d'algo pour les resoudre?
Ouais, il y a des problemes qui ont l'air interessant. je pense que je regarderai ca d'un peut plus pres quand j'aurais un peu plus de temps. (La semaine prochaine peut etre.)
En plus, j'ai un cluster de GPU sous la main, donc si j'ai envie de bruteforcer des bouts, ca pourrait bien se faire.
Vous savez si il y a une version anglaise du truc?
NdM: J'ai mis le topic dans la liste des topics a ne pas manquer.
En anglais il y a projecteuler.net que la plupart des gens ici connaissent probablement déjà, c'est plus ou moins la même chose mais avec beaucoup plus de problèmes et le côté "mignon" en moins.
Si quelqu'un traite le problem d'art, il pourrait etre interessant d'avoir une visualization de comment l'algo se deroule. une simple visualization des iterations serait suffisante. Quelqu'un motive pour faire ca?
Je veux bien faire celui du coloriage.
Mais après avoir amélioré mon score au Agar.IA 
Avec un bête algo greedy on arrive facilement à 991... mais après c'est plus dur^^
Dans le même style il y a codingame.com
Ca ressemble a des probleme de theorie des codes.
Il y a une famille de descente locale evidente:
1/ "trouve l'interupteur qui si tu le switch change allume le plus de lumiere supplementaire"
2/ "trouve la pair d'interrupteur qui si tu le switch ..."
3/ "trouve le triplet d'interrupteur, ..."
Mais concretement un truc comme ca, ca donne furieusement envie d'essayer des algo genetiques.
Ouais, si on échange les 0 et les 1, je dirais que ça revient à trouver la distance minimale d'un code linéaire..
Sinon avec un bête mélange d'aléatoire et de glouton on tape déjà dans le 140+, même avec des trucs pas rapides en python.
Ptet envisager une approche plus mathématique pour la suite
Ah sinon si vous voulez faire des tests simples avec matlab vous pouvez utiliser gf(truc,2) qui fait que truc est considèré comme élément de GF(2) et donc toutes les opérations seront faites modulo 2
C'est ce qu'a dit godrik
Salut, sympa ce petit concours !
J'en suis à 3546 sur art optimal (gratté par un certain Ismael) avec une méthode assez barbare en deux passes :
- 1ère passe, on parcours tous les pixels à dessiner, un par un, et on regarde la taille max du carré qu'on peut faire à partir de ce pixel (le carré s'étend en +x et +y) donc sans dépasser du dessin. Si le carré est intégralement compris dans un carré précédent on ne le garde pas, ça fait un premier tri.
- 2nde passe, on parcours chaque carré ainsi créée, et on regarde si en le supprimant, les autres carrés comblent sa surface. Si c'est le cas on le supprime, sinon ça veut dire qu'au moins un pixel du carré est "unique" à ce carré.
C'est vraiment loin d'être optimal, il n'y a pas d'analyse c'est fait à la volée. Le résultat change selon le sens ou on parcours les pixels et où on crée les carrés, peut-être qu'Ismael utilise le même genre de truc avec un sens optimisé pour cette image. J'ai quand fait un petit programme pour visualiser la chose : http://dl.free.fr/fE9WcsjBp
J'ai aussi un score sur agar.ia, mais là aussi c'est du bricolage 
Les autres m'inspirent moins... Partagez si vous avez des astuces sur les problèmes.
Super merci à tous pour le feedback !
Bonne idée pour la visualisation des carrés sur Art optimal, j'ai ajouté sur le site une représentation de la solution lorsqu'on en soumet une sur ce problème (et aussi sur Glaces à gogo)
Si vous avez des idées de problèmes ou des suggestions pour le site n'hésitez pas
Ben oui, du coup j'aurais une question, c'était quoi le problème théorique qui était censé être derrière illuminations ? J'ai l'impression qu'il y a eu un petit soucis au moment de le convertir en problème pratique.
Ca ressemble a un probleme de theorie des codes. Compte tenu un code lineaire (genre de haming), construit une entree du probleme qui produit une sortie particuliere.
Pasque je croyais que le but du jeu c'était de trouver des solutions approchées à des problèmes, euh, difficiles au niveau combinatoire.
(c'est quoi l'équivalent français de computationally hard ?)
Je ne sais pas si il y a un vrai equivalent. Quand je parles a des informaticiens, j'utilise "NP-Hard". Et quand je parles a des non-informaticien, j'utilise juste "combinatoire"; un coup de google montre que certains ont l'air d'utiliser "fortement combinatoire".