Défi algorithmique

[Reldan]

Des amateurs de casse tête informatique dans l'assistance ?
Je dois implémenter un algo un peu touchy sur ALN.
Voici un modélisation du problème :

Nous avons 3 types de boites (A, B, C) et 5 types de formes (rond, triangle, carré, rectangle, losange).
Soit un ensemble composé de n'importe quelles combinaison de boites et de formes.
L'algorithme doit déterminer si on peut ranger toutes les formes dans les boites.

Avec les contraintes suivantes :
Une boite A peut contenir 2 ronds + 1 parmi (triangle, carré, rectangle, losange)
Une boite B peut contenir 4 ronds + 1 triangle + 1 (carré ou rectangle) + 1 losange
Une boite C peut contenir 2 ronds + 2 différents parmi (triangle, carré, rectangle, losange)

Exemple 1 : 2 boites B, 1 Boite C , 1 carré, 2 rectangles, 3 losanges
Exemple 2 : 2 boites A, 1 boites B, 2 Boite C , 8 ronds, 4 carrés, 1 rectangle, 3 losanges

J'ai fait ma version ça a l'air d'être ok mais si l'un de vous veux essayer, je me suis dit que le défi était suffisamment intéressant pour être partagé ;-)

ps : les plus attentifs reconnaîtront les règles (une partie seulement) de validation de liste pour un certain jeu de figurine.

Des trucs dans https://fr.wikipedia.org/wiki/Probl%C3%A...in_packing ?

[Reldan]

Oui mais là, par rapport au bin packing en générale, on se fiche d'optimiser, on veux juste savoir si ça rentre. La fonction retourne juste un booléen, pas une architecture.
Ça simplifie beaucoup le problème.

[Gandahar]

Personnellement, je n'ai pas compris quelles sont tes variables en entrée et quel résultat tu veux obtenir en sortie.
Tu cherches à obtenir un nombre optimisé de boites A, B, C à partir de formes 1 à 5 ?
Ou le contraire ?
Ou autre chose ?

Les 3 règles de gestions sont-elles exhaustives, à savoir que tu ne peux pas faire "2 ronds = 1 carré" par exemple ?

(Nb : j'ignore à quelles règles de jeu tu fais références mais ça n'a aucune importance pour créer un algorithme)

[Reldan]

En entré j'ai une liste de boites et de formes (n'importe quel nombre de n'importe quel type).
Ex : 2 boites B, 1 boite C , 1 carré, 2 rectangles, 3 losanges

En sortie j'ai un booléen : true si l'ensemble des formes peut être contenu dans l'ensemble des boites.

Oui les règles sont exhaustives.

[Gandahar]

J'ai un algorithme qui fonctionne sous Excel avec quelques manips manuelles.
Tu as un exemple vraiment compliqué à faire passer ?
Dans les 2 exemples du début, La réponse à l'exemple 1 est false et celle de l'exemple 2 est true

S'il fonctionne complètement, il sera facile de le transformer en programme.
Cependant, je ne programme qu'en langage C.


[Edit 1]
Ca y est, j'ai inclus une fonction C répondant à ton besoin dans l'un de mes programmes existant.
Je suis prêt à la tester avec n'importe quel jeu d'essai.

Je pourrais t'envoyer le code source de la fonction, elle n'est pas compliquée et tu pourras la traduire dans n'importe quel autre langage.
[/Edit]


[Edit 2]
C'est envoyé.
[/Edit]

Moi j'ai true sur la question 1 :
Boite C : losange + carré : ok
2 Boite B : losange + rectangle x2 : ok
total : 3 losange, 1 carré, 2 rectangles.

En algo je suis parti sur somme de chaque capacité max, puis somme carré +rectangle en capacité max, puis somme carré + rectangle + losange + triangle en capacité max.
Si tout est ok, alors ok.

2A et C sont équivalent (sauf sur le rond).

La façon "propre" serait de remplir les emplacements "faciles" (les ronds). Si c'est ok, on passe à triangle/losange. Si c'est ok, on compte les emplacements restants / la demande en carré /rectangle.

[Reldan]

@petitgars
Non 2A et C ne sont pas pareil du tout car dans le C il faut 2 différents parmi....
@gandahar
Non les 2 exemples sont true.

Bon les ronds, on s'est fout, aucune difficulté.
Le problème vient d'un blocage potentiel sur les autres selon l'ordre dans lequel on commence à remplir.

En fait moi j'ai trié les formes par quantité. Et commencé par ranger les formes que j'avais le plus.
En commençant par les boites les plus "bloquantes" : C puis B puis A.
Du coup mon algo fonctionne sur tout les cas bloquants que j'ai pu identifier mais sans être sûr qu'il fonctionnera toujours


rappel:
Une boite A peut contenir 2 ronds + 1 parmi (triangle, carré, rectangle, losange)
Une boite B peut contenir 4 ronds + 1 triangle + 1 (carré ou rectangle) + 1 losange
Une boite C peut contenir 2 ronds + 2 différents parmi (triangle, carré, rectangle, losange)

Exemple 1 :
-2 boites B, 1 Boite C
- 1 carré, 2 rectangles, 3 losanges

si je commence à mettre 1 carré et 1 rectangle dans la C , je ne pourrais pas mettre les 3 losanges
en commençant par ranger 1 losange dans la C ça passe

Exemple 2 :
- 2 boites A, 1 boites B, 2 Boite C
- 8 ronds, 4 carrés, 1 rectangle, 3 losanges
Si je commence à ranger mes rectangles et losanges dans les boites A et B , pareil plus de place pour les carrés
En commençant par 2 carrés dans les 2 boites C ça passe.

Du coup c c’est un pb uniquement si tu as un nombre impair de boites c
Pour bloquer ton algo il faudrait un cas ou ranger le plus de forme est pénalisant. J’aurais tendance à dire que ton algo couvre tous les cas.

Pour le tester j’utiliserai « a + b + c » (avec compo au max). S’il est true sur ce cas il le sera sur des variantes, non ?

[Reldan]

Non pour les boîtes C c'est pas une question d'impair. On ne peux pas mettre 3 triangles dans 2 boîtes c.

Oui tu dois avoir raison pour la vérification, remplir au max en favorisant 1 forme ou 2.