Coder-Studio - Forums

Kirua · 25-10-2007 17:05:32

Calvin, c'est difficile justement de juger si c'est "d?j? pas mal" ou pas. Je ne dis pas que ce n'est pas "pas mal", juste qu'on ne sait rien dire sans avoir vrmnt analys? le probl?me et fait ses propres essais.

Calvin1602 · 25-10-2007 21:22:20

ben avec une m?thode brute-force la 72?me pi?ce change ? peu pr?s toutes les 10 min. Et l? 92% de 16? , ben >> 72 .

Puzzles.Ao · 19-11-2007 13:53:41

92% veut dire que (256/100)*92 = 235 pieces ont ?t? mise sur le plateau, effectivement rien ne dit que la solution est bonne, mais c'est deja mieux que de plac? difficilement 100 pi?ces a la main. De plus le resultat est rapidement atteignable.

Pour exemple : Indice 1 -> 24 grilles en 1 heure. (6x6) c'est petit, mais la formule marche... Maintenant on mixant, chance, technique, chance, chance, et mise a jour du projet, chance peut ?tre que ...

Voila ++ (dsl pour la r?ponse tardive).
40 clients pour l'instant, et 1 seul qui a fait des remarques, donc ... les gens a l'air satisfait ... mais encore beaucoup de bug, et une version DS qui se pr?pare. Bientot +++

http://puzzles.ao.free.fr

Dernière modification par Puzzles.Ao (26-11-2007 13:54:19)

Aquanum · 08-01-2008 22:03:41

Hop remontage de topic les gens !!!

Je suis tomb? sur le site d'eternity par hasard. Je n'avais pas particip? ? cette discussion quand on en avait parl? sur coder-studio. Mais l? maintenant ?a m'int?resse bien. Non pas pour l'argent et pour la solution, je m'en fiche, quelqu'un aura trouv? avant nous...

Mais pour le d?fi, m?me si on trouve une solution qu'apr?s d?cembre 2008 ?a serait la classe 006_grin

Et pis on sait jamais ptetre qu'avec de la chance xD mouarf...

Bon alors j'ai r?fl?chi ? un programme ?videmment, je sais que ?a existe d?j?, mais je m'en fiche, je veux le programmer moi m?me ou y participer. Ce programme serait mis en r?seau sur plein de PC en m?me temps, et tournerait en fond de tache sur chaque PC volontaire. "Si on gagne", j'y crois pas trop, on divise par autant d'utilisateurs.

Bon, je tiens ? pr?ciser, je m'en fous de l'argent, pour moi c'est plus de l'ordre du d?fi, m?me si on y arrive qu'apr?s 013_chuffed mouahah

Donc moi je serais pour tenter la bruteforce avec des astuces permettant de faire r?duire consid?rablement les possibilit?s. Donc se cr?er un pseudo algo r?fl?chi alli? ? la bruteforce de testage de toutes les combinaisons. Il y a 20 000 solutions possibles, si on tape au hasard les pi?ces, y a moyen d'avoir ? un moment de la chance. Et je table l? dessus, il doit y avoir ce genre de logiciels qui tournent en ce moment. On a pas moins de chance de trouver m?me si on s'y prend bien apr?s eux.

Rah je je regrette de plus ?tre ? EDF avec le supercalculateur ? 4000 processeurs... 013_chuffed ...

Bon m?me si c'est vou? ? l'?chec, je pense qu'on pourrait essayer tous ensemble de r?fl?chir ? un truc qui marche. Et on lance le truc en r?seau, le tout communiquant sur un serveur qui centralise les infos et indique ce qui a d?j? ?t? fait.

Le point qui m'emb?te c'est le moyen de stockage des combinaisons d?j? r?alis?es... ?a va prendre ze place...

Enfin voilou, moi je suis motiv? pour relever le d?fi, quite ? pas trouver, on se sera creus? la t?te et on aura lanc? notre mouvement geek 001_smile

Coder-Studio TEAM

Aquanum · 08-01-2008 22:10:27

rofl, ce truc est vraiment impossible, mais ?a va ?tre fun xD

pissendlove · 08-01-2008 22:39:02

Ba moi je suis plutot pour, on peut toujours essayer, on a rien a perdre. En plus j'ai les deux puzzles test, ?a sera un bon moyen de voir l'efficassit? des programmes.

Apres, on va devoir faire un bon brainstorming pour trouver la fa?on de bruteforce qui pourait etre le plus efficasse.

Aquanum · 08-01-2008 22:58:44

Au fait ... correction sur le nombre de possibilit?..., il faut prendre en compte l'orientation des pi?ces. Y a un facteur 4 quelque part... Ce n'est pas que 256! Ensuite il faut prendre en compte les associations de pi?ces possibles. Du coup le calcul me semble bien plus complexe.

Globalement ?a rajoute pas mal de combinaisons 028_nugget et je me demande si c'est pas tout simplement de la perte de temps de bosser sur une telle ?nigme. Vous ne connaitriez pas d'autres ?nigmes avec moins de combinaisons possibles? Parce qu'? part faire perdre du temps, ?a ne va pas apporter grand chose. J'?tais aps mal emball? ? premi?re vue, j'ai regard? un peu partout des analyses du probl?me et je pense pas pouvoir rivaliser avec des gens qui g?rent 100000 fois plus que moi.

Je me demande si simplement nous ne pourrions pas ? la limite inventer notre propre ?nigme et essayer de la r?soudre 001_smile Ca serait d?j? plus int?ressant, parce que l?, si on veut vraiment bien bosser dessus il faut acheter le jeu, et 50? c'est cher...

Il doit bien y avoir des trucs funs ? calculer nan? J'ai envie de faire mumuse sur un calculateur en r?seau. Bosser un peu de code r?seau ?a me plairait bien.

Bref, je pense que j'ai plus ? perdre ? essayer de trouver la solution que de ne rien faire xD

Donc je vais chercher d'autres ?nigmes ou m'en cr?er une 013_chuffed , ou bien trouver un gros truc ? calculer. Il doit bien y avoir des projets ? mener o? le r?sultat au final est ? la hauteur du temps pass? ? chercher 001_smile

Kirua · 09-01-2008 01:15:09

Hmm, me dis qu'il vaut quand m?me mieux faire un calcul de proba avant de lancer un bruteforce, et puis ... si la proba est de l'ordre du lotto (mais ? mon avis, c'est pire 013_chuffed ), ben se r?signer 003_wink .

Quant au stockage des combis, a priori, elles sont d?nombrables (?a, c'est clair ), et donc possiblement "num?rotables": peut-?tre qu'il y a moyen de g?n?rer les combinaisons n1 ? n2 de fa?on "bien d?finie", auquel cas, le serveur central g?re les bornes qu'il envoie aux PC calculateurs, et il n'y a rien ? sauvegarder. Si on poursuivait la chose (mais ?a me para?t vain, sans en avoir fait l'analyse en tout cas), ce serait quelque chose ? explorer.

Calvin1602 · 09-01-2008 01:34:43

Un truc genre :
t'as N PCs dispos.
Tu prends le 1er qui passe, tu commences ? parcourir ton graphe en largeur d'abord. D?s que t'as une liste de longueur N, tu envoies le parcours d?j? effectu? ? chacun des N PCs ...

Kirua · 09-01-2008 11:08:07

Hmm, pas vraiment, parce que ?a n?cessiterait quand m?me de g?n?rer toutes les combis sur le PC serveur. Je pensais plut?t ? chercher une fonction du style:

f : N -> N^16xN^16

avec N les naturels, et N^16xN^16 l'espace des combinaisons. Si c'est possible d'avoir une bijection comme ?a (et c'est pas n?cessaire de calculer l'inverse de la fonction hmm!), c'est super cool 001_smile .

Calvin1602 · 09-01-2008 12:32:26

par TOUTES les combis, seulement N. Le serveur parcourt l'arbre des solutions jusqu'? une profondeur de log2(N) seulement, ?a doit ?tre tr?s rapide m?me pour un grand N ( genre 100 ... perso j'ai pas 100 PCs sous la main ... quoique, un ssh sur tous les PCs du d?partement ... 006_grin )

Par contre je vois pas ? quoi pourra bien te servir ta fonction ? et qui plus est, il y a un *4 qui se perd ( l'orientation ).

Kirua · 09-01-2008 18:05:29

okok

N^16xN^16x{0, 1, 2, 3}

013_chuffed

Mais honn?tement, tu vois pas l'int?r?t? Pourtant, point de vue m?moire, c'est gigantesque! Tu dois pas stocker les combis test?es! Juste maintenir un compteur!

Aquanum · 09-01-2008 18:56:06

Statistiquement, n'a t-on pas plus de chances de tomber sur une solution au hasard que de faire progressivement par incr?mentation de compteur?

L'inconv?nient de faire au hasard c'est le stockage des infos et la comparaison pour savoir si ?a existe d?j? :s

Calvin1602 · 09-01-2008 19:14:40

ahh, ok. en gros t'incr?mentes un compteur de 0 ? un nombre gigantesque, ? a chaque fois tu retestes l'int?gralit? de la map ?
Franchement je pr?f?re me payer un arbre. Au moins il n'y a que 4 tests ? faire dans chaque branche, pas 16*16*4.

Aquanum · 09-01-2008 19:51:32

Moi j'?tais pour tenter u? chaque combinaison de mani?re al?atoire et de stocker les 256*4 informations... aoutch ... nan j'ai rien dit, c'est tar? comme id?e.

Au bout de 1 milliard de combinaisons test?es on a d?j? stock? 256*4*10^9=1T?raoctets de donn?es xD ahah ... stupide.

Alors pour 256! combinaisons (on arrondi)... ?a ferait 8,7840540195107087781794024620158e+518 octets de stock?s ... mouahahah soit
8,7840540195107087781794024620158e+509 disque durs de 1 milliard de T?raoctets !

Yeah ? la one again!

Faut que j'invente un SGBD pour g?rer un truc comme ?a.

Ah tiens, regardons la consommation en ?lectricit?. Un disque dur consomme 50 W. Supposons qu'un disque dur de 1 milliard de To consomme un peu plus. On va ?tre gentil on va mettre 1 MW.

Bon alors je continue mon calcul.

8,784054019510708778179402462015e+480 ann?e d'utilisation de la puissance du soleil... Hum je vais trouver mieux.

8,784054019510708778179402462015e+445 fois la masse totale ?nerg?tique de l'univers. Merde je vais manquer de courant...

Moi je vous dit, c'est un putain de rack ? disque durs qu'il nous faut!

On va y arriver!

Kirua · 10-01-2008 17:54:49

015_tongue

ceci dit, aqua, tu t'es plant? dans ton calcul je pense: un milliard de terraoctets, c'est 10^18 octets -> ?a fait "que" 8.8e500 disques durs de 1e9 To 003_wink

Aquanum · 10-01-2008 19:56:53

Oup oui en effet j'ai oubli? de remultiplier par les 10^9 octets du DD.

Ceci dit... on peut dire que c'est n?gligeable ?a rajoute juste 9 puissances xD

C'est tellement ?norme qu'on ne peut m?me plus se repr?senter l'?chelle.
De dire, pour faire fonctionner mon disque dur j'ai besoin de la puissance du soleil pendant un an, ?a parle!!!

Alors que de dire pour faire marcher mon bazar j'ai besoin de 10^500 fois l'?nergie totale de l'univers... ?a parle plus tellement c'est ?norme xD

Kirua · 10-01-2008 21:11:05

Un truc utile pour ?a, c'est de se rappeler les ordres de grandeur du nombre de secondes ?coul?es depuis le big bang pour les complexit?s temporelles et le nombre d'atomes dans l'univers pour les complexit?s spatiales. On se calme vite 013_chuffed . De m?moire, ?a doit ?tre genre 10^17 et 10^80, quelque chose du style.

Armine · 11-01-2008 17:36:01

Mais ca vaut peut etre le coup 006_grin

patemino · 11-01-2008 18:51:05

Sans compter qu'il faut inventer un nouveau syst?me d'adressage je pense... et puis les puces et les bus qui vont avec...

libjch · 28-11-2008 21:39:02

YopYop les gens
Dans le cadre d'un cours d'IA, on doit faire un prog qui essaye de r?soudre ce truc.
Les r?gles sont simples :

Il fait tourner le prog pendant 20min sur une machine(quadcore toussa).Et regarde le nombre de pi?ces qui ne vont pas (2 bord de couleurs diff?rentes) et fait un classement.

On fait comme on veux, avec ce que l'on veut.
Tout les TP ont ?t? fait en python, mais la, on pensait le faire dans un langage plus rapide et qui g?re le multicoeur.

On a aussi quelques notions en Comet, qui a l'air bien optimis? pour ce genre de probl?me, mais on a du mal a l'utiliser, quelqu'un a d?j? essay? ? ?a vaut la peine de d?couvrir plus en profondeur ?

Donc, petit brainstorming, si quelqu'un a des suggestions a ce niveau.
Sinon pour l'algo: on y a pas encore beaucoup r?fl?chit, mais on a pens? faire une recherche tabu, en partant de plusieurs solution initiales.

Dernière modification par libjch (28-11-2008 21:42:16)

Calvin1602 · 29-11-2008 12:34:53

Dans le genre de langage rapide et qui g?re la parall?lisation en natif, pour moi ya Ada et Erlang.
Apr?s Erlang je sais pas si c'est super utilis? ... Yaura ptet plus de doc sur Ada. sais pas.

N'emp?che c'est ouf que vous ayez ?a comme sujet 001_smile

pissendlove · 10-12-2008 14:07:06

libjch, Il y a d?j? pas mal de temps que tu as post? ce message mais si tu veux t'entra?ner sur des plus petits puzzle, je peux te passer une photo des 2 puzzle interm?diaires plus petit et beaucoup plus r?alisable que le grand.

libjch · 10-12-2008 15:43:57

On a des instances de test (m?me beaucoup) ?a ira 003_wink

Pour l'instant une Tabu-Search qui tourne 2 min arrive a avoir un jeu ou il ne reste environ 64 bords mal plac?s... (il y a 16*16*4=1024 bords de pi?ces au total) donc ca marche assez bien, mais le probl?me c'est que m?me en laissant tourner 1h en plus, on arrive pas en dessous des 60...

Coder-Studio - Forums

#51 25-10-2007 17:05:32

Re: Eternity II

#52 25-10-2007 21:22:20

Re: Eternity II

#53 19-11-2007 13:53:41

Re: Eternity II

#54 08-01-2008 22:03:41

Re: Eternity II

#55 08-01-2008 22:10:27

Re: Eternity II

#56 08-01-2008 22:39:02

Re: Eternity II

#57 08-01-2008 22:58:44

Re: Eternity II

#58 09-01-2008 01:15:09

Re: Eternity II

#59 09-01-2008 01:34:43

Re: Eternity II

#60 09-01-2008 11:08:07

Re: Eternity II

#61 09-01-2008 12:32:26

Re: Eternity II

#62 09-01-2008 18:05:29

Re: Eternity II

#63 09-01-2008 18:56:06

Re: Eternity II

#64 09-01-2008 19:14:40

Re: Eternity II

#65 09-01-2008 19:51:32

Re: Eternity II

#66 10-01-2008 17:54:49

Re: Eternity II

#67 10-01-2008 19:56:53

Re: Eternity II

#68 10-01-2008 21:11:05

Re: Eternity II

#69 11-01-2008 17:36:01

Re: Eternity II

#70 11-01-2008 18:51:05

Re: Eternity II

#71 28-11-2008 21:39:02

Re: Eternity II

#72 29-11-2008 12:34:53

Re: Eternity II

#73 10-12-2008 14:07:06

Re: Eternity II

#74 10-12-2008 15:43:57

Re: Eternity II

Pied de page des forums