Hercule Poireau aux vœux de l’ambassadeur

Un petit exercice de programmation

a marqué ce sujet comme résolu.

Hercule Poireau1 est invité aux vœux de nouvelle année par l’ambassadeur de Belgique au Royaume-Uni. Pour faire patienter ses invités avant et pendant le discours, l’ambassadeur fournit à chacun de ses invités un plateau de quinze (trois lignes de cinq) chocolats belges, une invention d’un grand créateur : des rochers en chocolat fourrés à la noisette.

Hercule Poireau se régale d’avance à l’idée de savourer ces délices. Mais, alors qu’il admire les superbes chocolats, une question lui tricote le cervelet : lui qui est féru d’ordre et de méthode, arrivera-t-il à manger ses chocolats, un par un, de façon à ce que le motif (après éventuel arrangement) soit toujours symétrique selon les deux axes ? Devra-t-il rogner sur ses principes et ne se contenter d’une simple et peu satisfaisante symétrie centrale ?

À vous de jouer, chers lecteurs !

Vérifiez si Hercule Poireau pourra satisfaire son envie de chocolat et son besoin pathologique de symétries. Si oui, aidez-le en lui proposant l’intégralité des rangements possibles pour chaque nombre de chocolat restant.

Une fois le discours de l’ambassadeur terminé, Hercule Poireau se pose une autre question : cette histoire de symétrie est-elle possible pour toutes les taille de plateaux de chocolats ?

L’exercice avec un plateau de 5 x 3 est assez léger pour être traité par force brute par n’importe quel ordinateur actuel en un temps négligeable.

Solution pour les symétries XY
Symétries XY pour 15 rochers (1 variante)
●●●●● 
●●●●● 
●●●●● 

Symétries XY pour 14 rochers (1 variante)
●●●●● 
●●○●● 
●●●●● 

Symétries XY pour 13 rochers (3 variantes)
●●○●● ●●●●● ●●●●● 
●●●●● ○●●●○ ●○●○● 
●●○●● ●●●●● ●●●●● 

Symétries XY pour 12 rochers (3 variantes)
●●○●● ●●●●● ●●●●● 
●●○●● ○●○●○ ●○○○● 
●●○●● ●●●●● ●●●●● 

Symétries XY pour 11 rochers (5 variantes)
○●●●○ ●○●○● ●●○●● ●●○●● ●●●●● 
●●●●● ●●●●● ○●●●○ ●○●○● ○○●○○ 
○●●●○ ●○●○● ●●○●● ●●○●● ●●●●● 

Symétries XY pour 10 rochers (5 variantes)
○●●●○ ●○●○● ●●○●● ●●○●● ●●●●● 
●●○●● ●●○●● ○●○●○ ●○○○● ○○○○○ 
○●●●○ ●○●○● ●●○●● ●●○●● ●●●●● 

Symétries XY pour 9 rochers (7 variantes)
○●○●○ ○●●●○ ○●●●○ ●○○○● ●○●○● ●○●○● ●●○●● 
●●●●● ○●●●○ ●○●○● ●●●●● ○●●●○ ●○●○● ○○●○○ 
○●○●○ ○●●●○ ○●●●○ ●○○○● ●○●○● ●○●○● ●●○●● 

Symétries XY pour 8 rochers (7 variantes)
○●○●○ ○●●●○ ○●●●○ ●○○○● ●○●○● ●○●○● ●●○●● 
●●○●● ○●○●○ ●○○○● ●●○●● ○●○●○ ●○○○● ○○○○○ 
○●○●○ ○●●●○ ○●●●○ ●○○○● ●○●○● ●○●○● ●●○●● 

Symétries XY pour 7 rochers (7 variantes)
○○●○○ ○●○●○ ○●○●○ ○●●●○ ●○○○● ●○○○● ●○●○● 
●●●●● ○●●●○ ●○●○● ○○●○○ ○●●●○ ●○●○● ○○●○○ 
○○●○○ ○●○●○ ○●○●○ ○●●●○ ●○○○● ●○○○● ●○●○● 

Symétries XY pour 6 rochers (7 variantes)
○○●○○ ○●○●○ ○●○●○ ○●●●○ ●○○○● ●○○○● ●○●○● 
●●○●● ○●○●○ ●○○○● ○○○○○ ○●○●○ ●○○○● ○○○○○ 
○○●○○ ○●○●○ ○●○●○ ○●●●○ ●○○○● ●○○○● ●○●○● 

Symétries XY pour 5 rochers (5 variantes)
○○○○○ ○○●○○ ○○●○○ ○●○●○ ●○○○● 
●●●●● ○●●●○ ●○●○● ○○●○○ ○○●○○ 
○○○○○ ○○●○○ ○○●○○ ○●○●○ ●○○○● 

Symétries XY pour 4 rochers (5 variantes)
○○○○○ ○○●○○ ○○●○○ ○●○●○ ●○○○● 
●●○●● ○●○●○ ●○○○● ○○○○○ ○○○○○ 
○○○○○ ○○●○○ ○○●○○ ○●○●○ ●○○○● 

Symétries XY pour 3 rochers (3 variantes)
○○○○○ ○○○○○ ○○●○○ 
○●●●○ ●○●○● ○○●○○ 
○○○○○ ○○○○○ ○○●○○ 

Symétries XY pour 2 rochers (3 variantes)
○○○○○ ○○○○○ ○○●○○ 
○●○●○ ●○○○● ○○○○○ 
○○○○○ ○○○○○ ○○●○○ 

Symétries XY pour 1 rochers (1 variante)
○○○○○ 
○○●○○ 
○○○○○ 

Symétries XY pour 0 rochers (1 variante)
○○○○○ 
○○○○○ 
○○○○○
Solution pour les symétries centrales
Symétries centrales pour 15 rochers (1 variante)
●●●●● 
●●●●● 
●●●●● 

Symétries centrales pour 14 rochers (1 variante)
●●●●● 
●●○●● 
●●●●● 

Symétries centrales pour 13 rochers (7 variantes)
○●●●● ●○●●● ●●○●● ●●●○● ●●●●○ ●●●●● ●●●●● 
●●●●● ●●●●● ●●●●● ●●●●● ●●●●● ○●●●○ ●○●○● 
●●●●○ ●●●○● ●●○●● ●○●●● ○●●●● ●●●●● ●●●●● 

Symétries centrales pour 12 rochers (7 variantes)
○●●●● ●○●●● ●●○●● ●●●○● ●●●●○ ●●●●● ●●●●● 
●●○●● ●●○●● ●●○●● ●●○●● ●●○●● ○●○●○ ●○○○● 
●●●●○ ●●●○● ●●○●● ●○●●● ○●●●● ●●●●● ●●●●● 

Symétries centrales pour 11 rochers (21 variantes)
○○●●● ○●○●● ○●●○● ○●●●○ ○●●●● ○●●●● ●○○●● ●○●○● ●○●●○ ●○●●● ●○●●● ●●○○● ●●○●○ ●●○●● ●●○●● ●●●○○ ●●●○● ●●●○● ●●●●○ ●●●●○ ●●●●● 
●●●●● ●●●●● ●●●●● ●●●●● ○●●●○ ●○●○● ●●●●● ●●●●● ●●●●● ○●●●○ ●○●○● ●●●●● ●●●●● ○●●●○ ●○●○● ●●●●● ○●●●○ ●○●○● ○●●●○ ●○●○● ○○●○○ 
●●●○○ ●●○●○ ●○●●○ ○●●●○ ●●●●○ ●●●●○ ●●○○● ●○●○● ○●●○● ●●●○● ●●●○● ●○○●● ○●○●● ●●○●● ●●○●● ○○●●● ●○●●● ●○●●● ○●●●● ○●●●● ●●●●● 

Symétries centrales pour 10 rochers (21 variantes)
○○●●● ○●○●● ○●●○● ○●●●○ ○●●●● ○●●●● ●○○●● ●○●○● ●○●●○ ●○●●● ●○●●● ●●○○● ●●○●○ ●●○●● ●●○●● ●●●○○ ●●●○● ●●●○● ●●●●○ ●●●●○ ●●●●● 
●●○●● ●●○●● ●●○●● ●●○●● ○●○●○ ●○○○● ●●○●● ●●○●● ●●○●● ○●○●○ ●○○○● ●●○●● ●●○●● ○●○●○ ●○○○● ●●○●● ○●○●○ ●○○○● ○●○●○ ●○○○● ○○○○○ 
●●●○○ ●●○●○ ●○●●○ ○●●●○ ●●●●○ ●●●●○ ●●○○● ●○●○● ○●●○● ●●●○● ●●●○● ●○○●● ○●○●● ●●○●● ●●○●● ○○●●● ●○●●● ●○●●● ○●●●● ○●●●● ●●●●● 

Symétries centrales pour 9 rochers (35 variantes)
○○○●● ○○●○● ○○●●○ ○○●●● ○○●●● ○●○○● ○●○●○ ○●○●● ○●○●● ○●●○○ ○●●○● ○●●○● ○●●●○ ○●●●○ ○●●●● ●○○○● ●○○●○ ●○○●● ●○○●● ●○●○○ ●○●○● ●○●○● ●○●●○ ●○●●○ ●○●●● ●●○○○ ●●○○● ●●○○● ●●○●○ ●●○●○ ●●○●● ●●●○○ ●●●○○ ●●●○● ●●●●○ 
●●●●● ●●●●● ●●●●● ○●●●○ ●○●○● ●●●●● ●●●●● ○●●●○ ●○●○● ●●●●● ○●●●○ ●○●○● ○●●●○ ●○●○● ○○●○○ ●●●●● ●●●●● ○●●●○ ●○●○● ●●●●● ○●●●○ ●○●○● ○●●●○ ●○●○● ○○●○○ ●●●●● ○●●●○ ●○●○● ○●●●○ ●○●○● ○○●○○ ○●●●○ ●○●○● ○○●○○ ○○●○○ 
●●○○○ ●○●○○ ○●●○○ ●●●○○ ●●●○○ ●○○●○ ○●○●○ ●●○●○ ●●○●○ ○○●●○ ●○●●○ ●○●●○ ○●●●○ ○●●●○ ●●●●○ ●○○○● ○●○○● ●●○○● ●●○○● ○○●○● ●○●○● ●○●○● ○●●○● ○●●○● ●●●○● ○○○●● ●○○●● ●○○●● ○●○●● ○●○●● ●●○●● ○○●●● ○○●●● ●○●●● ○●●●● 

Symétries centrales pour 8 rochers (35 variantes)
○○○●● ○○●○● ○○●●○ ○○●●● ○○●●● ○●○○● ○●○●○ ○●○●● ○●○●● ○●●○○ ○●●○● ○●●○● ○●●●○ ○●●●○ ○●●●● ●○○○● ●○○●○ ●○○●● ●○○●● ●○●○○ ●○●○● ●○●○● ●○●●○ ●○●●○ ●○●●● ●●○○○ ●●○○● ●●○○● ●●○●○ ●●○●○ ●●○●● ●●●○○ ●●●○○ ●●●○● ●●●●○ 
●●○●● ●●○●● ●●○●● ○●○●○ ●○○○● ●●○●● ●●○●● ○●○●○ ●○○○● ●●○●● ○●○●○ ●○○○● ○●○●○ ●○○○● ○○○○○ ●●○●● ●●○●● ○●○●○ ●○○○● ●●○●● ○●○●○ ●○○○● ○●○●○ ●○○○● ○○○○○ ●●○●● ○●○●○ ●○○○● ○●○●○ ●○○○● ○○○○○ ○●○●○ ●○○○● ○○○○○ ○○○○○ 
●●○○○ ●○●○○ ○●●○○ ●●●○○ ●●●○○ ●○○●○ ○●○●○ ●●○●○ ●●○●○ ○○●●○ ●○●●○ ●○●●○ ○●●●○ ○●●●○ ●●●●○ ●○○○● ○●○○● ●●○○● ●●○○● ○○●○● ●○●○● ●○●○● ○●●○● ○●●○● ●●●○● ○○○●● ●○○●● ●○○●● ○●○●● ○●○●● ●●○●● ○○●●● ○○●●● ●○●●● ○●●●● 

Symétries centrales pour 7 rochers (35 variantes)
○○○○● ○○○●○ ○○○●● ○○○●● ○○●○○ ○○●○● ○○●○● ○○●●○ ○○●●○ ○○●●● ○●○○○ ○●○○● ○●○○● ○●○●○ ○●○●○ ○●○●● ○●●○○ ○●●○○ ○●●○● ○●●●○ ●○○○○ ●○○○● ●○○○● ●○○●○ ●○○●○ ●○○●● ●○●○○ ●○●○○ ●○●○● ●○●●○ ●●○○○ ●●○○○ ●●○○● ●●○●○ ●●●○○ 
●●●●● ●●●●● ○●●●○ ●○●○● ●●●●● ○●●●○ ●○●○● ○●●●○ ●○●○● ○○●○○ ●●●●● ○●●●○ ●○●○● ○●●●○ ●○●○● ○○●○○ ○●●●○ ●○●○● ○○●○○ ○○●○○ ●●●●● ○●●●○ ●○●○● ○●●●○ ●○●○● ○○●○○ ○●●●○ ●○●○● ○○●○○ ○○●○○ ○●●●○ ●○●○● ○○●○○ ○○●○○ ○○●○○ 
●○○○○ ○●○○○ ●●○○○ ●●○○○ ○○●○○ ●○●○○ ●○●○○ ○●●○○ ○●●○○ ●●●○○ ○○○●○ ●○○●○ ●○○●○ ○●○●○ ○●○●○ ●●○●○ ○○●●○ ○○●●○ ●○●●○ ○●●●○ ○○○○● ●○○○● ●○○○● ○●○○● ○●○○● ●●○○● ○○●○● ○○●○● ●○●○● ○●●○● ○○○●● ○○○●● ●○○●● ○●○●● ○○●●● 

Symétries centrales pour 6 rochers (35 variantes)
○○○○● ○○○●○ ○○○●● ○○○●● ○○●○○ ○○●○● ○○●○● ○○●●○ ○○●●○ ○○●●● ○●○○○ ○●○○● ○●○○● ○●○●○ ○●○●○ ○●○●● ○●●○○ ○●●○○ ○●●○● ○●●●○ ●○○○○ ●○○○● ●○○○● ●○○●○ ●○○●○ ●○○●● ●○●○○ ●○●○○ ●○●○● ●○●●○ ●●○○○ ●●○○○ ●●○○● ●●○●○ ●●●○○ 
●●○●● ●●○●● ○●○●○ ●○○○● ●●○●● ○●○●○ ●○○○● ○●○●○ ●○○○● ○○○○○ ●●○●● ○●○●○ ●○○○● ○●○●○ ●○○○● ○○○○○ ○●○●○ ●○○○● ○○○○○ ○○○○○ ●●○●● ○●○●○ ●○○○● ○●○●○ ●○○○● ○○○○○ ○●○●○ ●○○○● ○○○○○ ○○○○○ ○●○●○ ●○○○● ○○○○○ ○○○○○ ○○○○○ 
●○○○○ ○●○○○ ●●○○○ ●●○○○ ○○●○○ ●○●○○ ●○●○○ ○●●○○ ○●●○○ ●●●○○ ○○○●○ ●○○●○ ●○○●○ ○●○●○ ○●○●○ ●●○●○ ○○●●○ ○○●●○ ●○●●○ ○●●●○ ○○○○● ●○○○● ●○○○● ○●○○● ○●○○● ●●○○● ○○●○● ○○●○● ●○●○● ○●●○● ○○○●● ○○○●● ●○○●● ○●○●● ○○●●● 

Symétries centrales pour 5 rochers (21 variantes)
○○○○○ ○○○○● ○○○○● ○○○●○ ○○○●○ ○○○●● ○○●○○ ○○●○○ ○○●○● ○○●●○ ○●○○○ ○●○○○ ○●○○● ○●○●○ ○●●○○ ●○○○○ ●○○○○ ●○○○● ●○○●○ ●○●○○ ●●○○○ 
●●●●● ○●●●○ ●○●○● ○●●●○ ●○●○● ○○●○○ ○●●●○ ●○●○● ○○●○○ ○○●○○ ○●●●○ ●○●○● ○○●○○ ○○●○○ ○○●○○ ○●●●○ ●○●○● ○○●○○ ○○●○○ ○○●○○ ○○●○○ 
○○○○○ ●○○○○ ●○○○○ ○●○○○ ○●○○○ ●●○○○ ○○●○○ ○○●○○ ●○●○○ ○●●○○ ○○○●○ ○○○●○ ●○○●○ ○●○●○ ○○●●○ ○○○○● ○○○○● ●○○○● ○●○○● ○○●○● ○○○●● 

Symétries centrales pour 4 rochers (21 variantes)
○○○○○ ○○○○● ○○○○● ○○○●○ ○○○●○ ○○○●● ○○●○○ ○○●○○ ○○●○● ○○●●○ ○●○○○ ○●○○○ ○●○○● ○●○●○ ○●●○○ ●○○○○ ●○○○○ ●○○○● ●○○●○ ●○●○○ ●●○○○ 
●●○●● ○●○●○ ●○○○● ○●○●○ ●○○○● ○○○○○ ○●○●○ ●○○○● ○○○○○ ○○○○○ ○●○●○ ●○○○● ○○○○○ ○○○○○ ○○○○○ ○●○●○ ●○○○● ○○○○○ ○○○○○ ○○○○○ ○○○○○ 
○○○○○ ●○○○○ ●○○○○ ○●○○○ ○●○○○ ●●○○○ ○○●○○ ○○●○○ ●○●○○ ○●●○○ ○○○●○ ○○○●○ ●○○●○ ○●○●○ ○○●●○ ○○○○● ○○○○● ●○○○● ○●○○● ○○●○● ○○○●● 

Symétries centrales pour 3 rochers (7 variantes)
○○○○○ ○○○○○ ○○○○● ○○○●○ ○○●○○ ○●○○○ ●○○○○ 
○●●●○ ●○●○● ○○●○○ ○○●○○ ○○●○○ ○○●○○ ○○●○○ 
○○○○○ ○○○○○ ●○○○○ ○●○○○ ○○●○○ ○○○●○ ○○○○● 

Symétries centrales pour 2 rochers (7 variantes)
○○○○○ ○○○○○ ○○○○● ○○○●○ ○○●○○ ○●○○○ ●○○○○ 
○●○●○ ●○○○● ○○○○○ ○○○○○ ○○○○○ ○○○○○ ○○○○○ 
○○○○○ ○○○○○ ●○○○○ ○●○○○ ○○●○○ ○○○●○ ○○○○● 

Symétries centrales pour 1 rochers (1 variante)
○○○○○ 
○○●○○ 
○○○○○ 

Symétries centrales pour 0 rochers (1 variante)
○○○○○ 
○○○○○ 
○○○○○

Variante beaucoup plus difficile pour les plus motivés d’entre vous :

Quelles sont les positions des chocolats Hercule Poireau doit manger, et quels sont les déplacements qu’il doit effectuer, dans le but de minimiser les déplacements pour obtenir des motifs symétriques ?

  1. Toute coïncidence avec un personnage d’Agatha Christie ne serait que purement fortuite.↩
+3 -0

J’ai comme l’impression qu’il y a encore des symmétries à exploiter. Le problème a une symmétrie D2 (EDIT: pas forcément, voir plus bas). C’est généralisable a tout plateau de chocolat pour lequels le nombre de ligne n’est pas égal au nombre de colonne, et je me demande si il n’y a du coup pas moyen d’avoir une formule qui énumère le nombre de possibilités. Par contre, si le nombre de ligne est égal au nombre de colonne, on tombe dans le groupe D4, avec plus de symmétries (et de possibilités <3 ). EDIT: non, voir plus bas :)

+0 -0

Une fois le discours de l’ambassadeur terminé, Hercule Poireau se pose une autre question : cette histoire de symétrie est-elle possible pour toutes les taille de plateaux de chocolats ?

Je me pose une question, 15 chocolats rochers en une soirée, ce n’est pas un peu beaucoup ? Tu as publié le code quelque part que tu as utilisé ?

+0 -0

C’est généralisable a tout plateau de chocolat pour lequels le nombre de ligne n’est pas égal au nombre de colonne, et je me demande si il n’y a du coup pas moyen d’avoir une formule qui énumère le nombre de possibilités

pierre_24

Je me posais la question aussi, mais c’est très loin au-delà de mes compétences en maths.

Est-ce qu’il y a un algo plus malin que de la force brute, ou bien l’idée est surtout de programmer cette force brute ?

philippemilink

C’est un atelier-exercice-jeu, tu fais ce que tu veux en fonction de ton intérêt et de ton niveau :)

Sur un 5 x 3, de toutes façons même avec une force brute mal programmée, ça passera, il n’y a que 32768 plateaux possibles. Sur un plateau plus grand, disons 8 x 8, ça deviendra indispensable d’être plus subtil pour arriver au bout du problème.

Je me pose une question, 15 chocolats rochers en une soirée, ce n’est pas un peu beaucoup ?

Renault

Il faut être gourmand, oui.

Tu as publié le code quelque part que tu as utilisé ?

Renault

Non, volontairement. D’une part parce que je ne veux pas donner d’exemple dès la parution de l’atelier ; d’autre part car c’est une bête force brute codée de façon très sale juste pour avoir un exemple de solution, et je voulais tenter un truc un peu plus subtil (et générique) avant de le publier.

+0 -0

Bonjour,

Il doit y avoir un truc que je ne comprends pas dans l’énoncé. Dès le moment où on prend un chocolat qui n’est pas au milieu, la symétrie est cassée dans un sens ou dans un autre, non ? Donc il faut forcément en prendre deux à la fois donc pas un par un ?

Merci pour l’éclaircissement…

+0 -0

Mes deux cents (je met en caché pour ceux qui veulent chercher de leur côté):

Un peu de réflexion

Une fois que tu as pris un chocolat tu peux en déplacer d’autres pour rendre le motif symétrique.

SpaceFox

En fait, c’est plus que "tu peux": tu dois faire un déplacement (mais un seul suffit). En effet, on peut remarquer que pour un nombre de chocolat mangé impair, le chocolat du centre doit systématiquement être mangé … Tandis que c’est systématiquement l’inverse pour un nombre pair de chocolat mangé. Le corrolaire marrant de ça, c’est que notre Hercules est bien embêté si le nombre de chocolat sur une ligne ou une colonne est pair, parce que dans ce cas, il n’existe pas de solutions symmétriques pour un nombre impair de chocolat(s) mangé(s) :(

Tout viens du fait qu’un chocolat a une ou plusieurs positions identiques par symmétrie. Ainsi, si je considère la symmétrie centrale, le chocolat dans le coin tout en haut à gauche va de pair avec celui dans le coin tout en bas à droite: si l’un est mangé, l’autre doit être mangé, et donc je les enlève par paire. C’est encore pire avec la symmétrie XY, puisque le même chocolat est équivalent par symmétrie à ceux dans tout les autres coins. Heureusement pour ton problème, le chocolat au centre n’a pour équivalent que lui même, ce qui te sauve pour les nombres impairs de chocolat mangés.

Je suis en train de réfléchir à exploiter ça pour proposer une solution un peu plus opti' (mais pas de beaucoup) que le bruteforce. Pour que ça soit marrant, il faut que je trouve une métrique pour les déplacements de chocolat à minimiser :pirate:

Et pour les matheux (ou les curieux) qui passeraient par là:

Encore un peu de théorie des groupes !

Il s’agit bel et bien de jouer avec des groupe de symmétrie en deux dimensions. Ainsi, dans sa première solution, Spacefox énumère en fait tout les plateaux à nn chocolats mangés qui appartiennent au groupe D2D_2, tandis qu’il énumère les plateaux appartenant à C2C_2 (en effet, il s’agit plus d’une rotation de 180° que d’une "symmétrie centrale", mais ça marche aussi) dans la seconde. Vu que C2⊂D2C_2 \subset D_2, les plateaux appartenant à D2D_2 sont aussi valides pour C2C_2.

Au début, je croyais que les plateaux ou le nombre de ligne est égal au nombre de colonne pouvaient présenter plus de symmétrie (en l’occurence D4D_4). Problème, dans ce cas, un chocolat mangé a systématiquement 4 positions équivalentes par symmétrie (sauf, pour un nombre de ligne et de colonne de chocolat impaires, la position centrale). Du coup, il n’est possible d’avoir des plateaux appartenant à la symmétrie D4D_4 que pour 4n4n (et éventuellement 4n+14n+1) chocolats mangés, donc on ne peut pas satisfaire à l’énoncé.

Reste donc à trouver un moyen malin d’énoncer les plateaux appartenant à D2D_2 ou C2C_2 :pirate:

+0 -0

Bonjour,

Exercice interessant, j’ai pondu un algo que je pense améliorable (mais je n’ai pas plus de temps à y passer dessus aujourd’hui), mais reste tout de même plus efficace qu’un brute force pour le moment.

L’idée étant la suivante.

Mon tableau de chocolat qui mesure NxM peut être réduit en transposant celui-ci dans un repère orthonormé, et en s’intéressant uniquement à X>=0 et Y>=0.

En image ça donne quelque chose comme la figure ci-dessous.

Avant
Avant
Après
Après

On constate que les symétries XY se font soit par 1, soit par 2, soit par 4. Partant de là, le problème se résume à distribuer un ensemble groupes sur une dimension. Naïvement je tri mon tableau pour distribuer en priorité les grand groupe (ce que j’appelle l’algo des plus grosses pierres, mais je suppose qu’il y a un vrai nom que je ne connais pas :lol: ).

De ce que j’ai compris en modélisant l’exercice il est techniquement possible de générer de très gros tableau du moment ou il y a de la place en mémoire et du moment ou N et M sont impairs.

Mon code en python donne ça.

from itertools import product


class Point:
    def __init__(self, x, y):
        self.x = x
        self.y = y

    def count_sym_xy(self):
        if self.x == 0 and self.y == 0:
            return 1
        elif self.x == 0 or self.y == 0:
            return 2
        else:
            return 4

    def __str__(self):
        return "({0}/{1})".format(self.x, self.y)

    def __repr__(self):
        return str(self)

    def __eq__(self, other):
        if isinstance(other, Point):
            return self.x == other.x and self.y == other.y
        return False

    def symetric_eq(self, other):
        if isinstance(other, Point):
            return abs(self.x) == abs(other.x) and abs(self.y) == abs(other.y)
        return False


def get_possible_symmetric_in_N(value, points):
    natural_set = filter(lambda p: p.x >= 0 and p.y >= 0, points)
    return list(filter(lambda p: p.count_sym_xy() == value, natural_set))


def get_bound(v):
    return range(int(((v + 1) / 2) * -1) + 1, int((v + 1) / 2))


def generate_list_of_points_on_board(x, y):
    range_x = get_bound(x)
    range_y = get_bound(y)

    return [Point(i, j) for i, j in product(range_x, range_y)]


def display_points(x, y, points, eat_points):
    range_x = get_bound(x)
    range_y = get_bound(y)

    for i in range_y:
        for j in range_x:
            for p in points:
                if p.y == i and p.x == j:
                    if p in eat_points:
                        print('X', end='')
                    else:
                        print('0', end='')
        print()


def generate_step(x, y, points):
    count_maximum_steps = x * y
    possible_symmetric_1_point = get_possible_symmetric_in_N(1, points)
    possible_symmetric_2_point = get_possible_symmetric_in_N(2, points)
    possible_symmetric_4_point = get_possible_symmetric_in_N(4, points)

    for step in range(count_maximum_steps):
        print(f"Symétrie pour {str(step + 1)} chocolat(s) mangé(s)")
        symmetrical_possibilities = select_list_of_possibilities(
            possible_symmetric_1_point,
            possible_symmetric_2_point,
            possible_symmetric_4_point,
            step + 1)
        display_points(x, y, points, get_eating_points(points, symmetrical_possibilities))
        print()


def select_list_of_possibilities(point_1, point_2, point_4, step):
    total = 0
    list_possibilities = []
    return_list = []

    for points in [point_4, point_2, point_1]:
        for i in range(len(points)):
            list_possibilities.append(points[0].count_sym_xy())
    for item in list_possibilities:
        if item + total == step:
            return_list.append(item)
            return return_list
        elif item + total < step:
            return_list.append(item)
            total += item
    return return_list


def get_eating_points(points, symmetrical_possibilities):
    positive_points = list(filter(lambda p: p.x >= 0 and p.y >= 0, points.copy()))
    negative_points = list(filter(lambda p: p.x < 0 or p.y < 0, points.copy()))
    result = []
    for symmetrical_possibility in symmetrical_possibilities:
        for ind, p in enumerate(positive_points):
            if p.count_sym_xy() == symmetrical_possibility:
                added_point = positive_points.pop(ind)
                result.append(added_point)
                for other_add_point in negative_points:
                    if added_point.symetric_eq(other_add_point):
                        result.append(other_add_point)
                break
    return result


def display_steps(x, y):
    pts = generate_list_of_points_on_board(x=x, y=y)
    generate_step(x=x, y=y, points=pts)


if __name__ == '__main__':
    display_steps(x=5, y=3)

Le résultat donne ceci.

Symétrie pour 1 chocolat(s) mangé(s)
00000
00X00
00000

Symétrie pour 2 chocolat(s) mangé(s)
00X00
00000
00X00

Symétrie pour 3 chocolat(s) mangé(s)
00X00
00X00
00X00

Symétrie pour 4 chocolat(s) mangé(s)
0X0X0
00000
0X0X0

Symétrie pour 5 chocolat(s) mangé(s)
0X0X0
00X00
0X0X0

Symétrie pour 6 chocolat(s) mangé(s)
0XXX0
00000
0XXX0

Symétrie pour 7 chocolat(s) mangé(s)
0XXX0
00X00
0XXX0

Symétrie pour 8 chocolat(s) mangé(s)
XX0XX
00000
XX0XX

Symétrie pour 9 chocolat(s) mangé(s)
XX0XX
00X00
XX0XX

Symétrie pour 10 chocolat(s) mangé(s)
XXXXX
00000
XXXXX

Symétrie pour 11 chocolat(s) mangé(s)
XXXXX
00X00
XXXXX

Symétrie pour 12 chocolat(s) mangé(s)
XXXXX
0X0X0
XXXXX

Symétrie pour 13 chocolat(s) mangé(s)
XXXXX
0XXX0
XXXXX

Symétrie pour 14 chocolat(s) mangé(s)
XXXXX
XX0XX
XXXXX

Symétrie pour 15 chocolat(s) mangé(s)
XXXXX
XXXXX
XXXXX

Pour info, je n’ai pas tenté d’optimisation de déplacement des chocolats entre chaque chocolats mangé, mais ça doit aussi pouvoir se faire en gardant en mémoire la disposition précédente (ce que je ne fais pas dans ma version).

+0 -0

Une fois que tu as pris un chocolat tu peux en déplacer d’autres pour rendre le motif symétrique.

Ah, voilà ce qui me manquait, merci !

Du coup voilà ma théorie artisanale… J’essaierai peut-être de coder un truc plus tard. JE suis plutôt bon ou pas vraiment ? Je n’ai pas encore lu les solutions et les autres propositions.

Par convention, je numérote les chocolats de 1 à 3 en ligne et de A à E en colonnes.

Pour le premier chocolat, on n’a pas le choix, on est obligé de prendre celui du milieu (C2)

Pour le deuxième chocolat, si on veut garder les symétries horizontales et verticales, en fait, on n’a seulement 3 possibilités: A2, B2 et C1. Ensuite on doit déplacer le symétrique de celui qu’on a pris au centre (C2). On a 3 motifs possibles à ce stade, avec des trous en A2+E2, B2+D2 ou C1+C3.

Pour le troisième chocolat, on est de nouveau obligé de prendre celui du milieu, et ça sera de nouveau le cas à chaque nombre impair.

Pour le quatrième chocolat ça devient intéressant:

  • Soit on prend de nouveau sur les axes (2 possibilités parmi A2, B2 et C1 qu’on n’a pas déjà pris), suivi d’un déplacement au centre
  • Soit alors on chamboule tout et on attaque soit le coin, soit le bord. Ca fait 2 possibilités: A1 ou B1, puis on déplace les trois symétriques correspondants vers les trois actuellement auparavant vides.

Si je compte bien, ça donne 5 motifs possibles au total. A1+A3+E1+E3, B1+B3+D1+D3, A2+B2+D2+E2, A2+C1+C3+E2, B2+C1+C3+D2

A 6 chocolats, je compte 7 motifs possibles en tout:

  • Soit on a vidé les axes (A2+B2+C1+C3+D2+E2)
  • Soit on a pris les coins et deux chocolats dans les axes (3 possibilités)
  • Soit on a pris les bords et deux chocolats dans les axes (3 possibilités)

A partir de x>=8 chocolats, logiquement, on a le même nombre de motifs possibles qu’à 15 -x chocolats, car il suffit d’inverser les motifs déjà trouvés.

J’ai pas envie ni le temps de me lancer dans un truc plus général pour le moment, mais mon intuition est qu’on ne peut conserver une symétrie dans les deux axes uniquement si on a un nombre de lignes et de colonnes impairs. Le nombre de motifs possibles doit dépendre 1/du nombre de chocolats sur les axes et 2/du nombre de chocolats en-dehors des axes et à partir de là, c’est des arrangements pour les dénombrer.

Pour ce qui est du minimum de déplacements, je dirais:

  1. 0 (on prend le centre)
  2. 1 (axe -> centre)
  3. 0 (on prend le centre)
  4. 3 (coins/bords -> axes et centre; on peut temporiser et ne faire qu’un déplacement à cette étape, mais on devra du coup en faire 3 au sixième chocolat, donc ça revient au même)
  5. 0
  6. 1 (axe -> centre)
  7. 0
  8. 3
  9. 0
  10. 1
  11. 0
  12. 3
  13. 0
  14. 1
  15. 0

Soit un total de 13 déplacements

+0 -0

Bonjour,

En fait on peut se contenter de 11 déplacements, j’ai dit une bêtise hier soir. Je ne crois pas qu’on puisse faire mieux par contre.

Situation de départ
#####
#####
#####

Premier chocolat
#####
##0##
#####

Deuxième chocolat
##0##
#####
##0##
=> 1 déplacement

Troisième chocolat
##0##
##0##
##0##

Quatrième chocolat
##0##
#0#0#
##0##
=> 1 déplacement, 2 au total

Cinquième chocolat
##0##
#000#
##0##

Sixième chocolat
##0##
00#00
##0##
=> 1 déplacement, 3 au total

Septième chocolat
##0##
00000
##0##

Huitième chocolat
0#0#0
0###0
0#0#0
=> 3 déplacements (pas le choix!), 6 au total

Neuvième chocolat
0#0#0
0#0#0
0#0#0

Dixième chocolat
0#0#0
00#00
0#0#0
=> 1 déplacement, 7 au total

Onzième chocolat
0#0#0
00000
0#0#0

Douzième chocolat
00000
0###0
00000
=> 3 déplacements (là non plus on ne peut pas faire autrement), 10 au total

Treizième chocolat
00000
0#0#0
00000

Quatorzième chocolat
00000
00#00
00000
=> 1 déplacement, 11 au total

Situation finale
00000
00000
00000
=> 11 déplacements au total
+0 -0
Connectez-vous pour pouvoir poster un message.
Connexion

Pas encore membre ?

Créez un compte en une minute pour profiter pleinement de toutes les fonctionnalités de Zeste de Savoir. Ici, tout est gratuit et sans publicité.
Créer un compte