[Algorithmie] Les chans IRC

[InstinctHack]

io,

un nouveau challenge de programmation que m'as proposer bofh.

y'a un problème sympa qui serait de déterminer combien de chans il faut former, pour que tous les gens qui s'entendent bien aient au moins un chan en commun, et que les gens qui s'entendent pas aient aucun chan en commun

en pièce jointe, vous trouverez un fichier de données.
sur la première ligne, la liste des pseudos (oui, très classe comme pseudo )
sur les suivantes une liste de couple qui représente des animosités entre deux pseudos.

mon résultat :
langage : PHP
nombre : 30
temps : 4m45.973s

bon courage !

[Wabouz]

Moi qui pensait faire ça avec une feuille et un crayon ^^

[b0fh]

PS: il faut évidemment minimiser le nombre de chans.

Le format de sortie n'est pas précisé, mais une ligne par chan avec la liste des pseudos membres, ça me parait raisonnable !

Deuxième détail: en pratique, on ne ferait pas de chans de deux personnes, on dirait qu'ils causent simplement en privé, mais pour ce problème, considérons les privés comme des petits chans. Ou autrement dit, on cherche a minimiser le nombre total de chans + de privés.

Un exemple d'exécution:

Input:

Code :

1 2 3 4
1 2
1 3

Signifie que 1 et 2 ne s'aiment pas, et que 1 et 3 ne s'aiment pas, et la solution est:

Code :

1 4
2 3 4

soit 2 chans; on voit qu'en effet, 1 et 2 ne sont jamais dans le même chan, 1 et 3 ne sont jamais dans le même chan, et toutes les autres paires possibles [(1,4), (2,3), (2,4), (3,4)] existent dans au moins un chan.

[Wabouz]

ça soulève un point pour la résolution de l'exo. À partir de combien de personnes dans le chan on considère que c'en est un?...

[notfound]

Bin 3 en tout ! cf. le post de b0fh.
2 personnes sur un chan pourrait-être considéré comme n'en étant pas un, mais plutôt comme étant un private. Mais je crois pas qu'il faille se soucier de ça.

[InstinctHack]

voilà mon résultat qui montre qu'une amélioration est sûrement possible

Code :

0 1 3 6 8 22 24 28 30 40 43 53 60 61 62 120 138 183 199 216 403 444 449 492  
2 4 5 7 9 15 21 23 25 27 33 45 55 85 107 113 148 173 178 273 307 317 342 432 459
10 12 13 14 17 18 26 32 41 44 46 47 48 49 63 64 116 265 352 353 414 466
11 16 20 29 31 35 36 54 66 68 72 77 89 102 131 132 166 174 208 228 313 327 330 461 494
19 37 39 51 65 75 80 81 82 86 90 91 136 137 158 175 177 218 231 347 423
34 38 42 52 56 57 59 67 94 100 109 111 112 134 163 181 190 198 207 251 259 379
50 70 71 73 78 79 83 88 92 101 110 115 127 129 160 196 274 315 350 365 481 485
58 69 74 84 95 97 108 123 146 153 171 180 182 185 206 219 220 249 270 289 306 401
76 87 93 96 104 114 121 122 124 135 143 149 164 187 188 250 256 272 322 336 349 416 427 462
98 99 103 105 106 119 128 142 145 157 165 167 186 191 193 210 246 285 286 340 374
117 118 130 139 140 141 152 155 169 170 172 200 225 232 236 242 300 366 421 447 477
125 133 147 150 151 162 176 179 197 213 214 238 262 269 292 294 348 375 393 407
126 156 159 201 202 204 209 230 235 237 244 257 261 266 271 312 338 439 460
144 154 161 189 194 203 211 212 226 227 247 263 279 316 356 370 391 398 433
168 184 192 205 217 222 223 234 245 248 254 295 360 373 389 410
195 215 221 229 233 240 241 252 280 284 291 308 335 359 394 418 468 473 476
224 239 243 253 267 276 290 293 297 331 339 346 367 371 395 400 422 429 469
255 258 260 264 268 283 302 303 310 329 333 341 361 368 369 420 446 451 463
275 281 282 288 296 299 301 304 343 345 382 388 479 487
277 278 298 318 323 325 326 334 354 355 358 363 383 384 402 413 417 478
287 305 311 314 321 328 351 376 377 381 399 425 428 430 457 480
309 319 320 324 337 344 380 396 412 419 437 474
332 362 364 372 392 405 411 431 434 436 441 464 472 484
357 378 385 386 390 397 404 406 408 426 471
387 415 424 443 448 454 475 483 489 490 496
409 435 440 442 445 458 497 499
438 450 452 465 482 486 491
453 455 456 495
467 488 493
470 498

Et oui, le code génére des "groupes" jamais le numéro 0 ne parleras avec 498, pourtant ils se détestent pas.
(pour les perf de temps, je crois que je peux pas mal descendre mais avec une augmentation de la mérmoire utilisée)

Allez, à vous :p

edit : et FUCK j'ai un private entre 470 et 498

edit2 : je confirme je viens de passer de 4m45.973s à 1.752s pour le même résultat