Dans le problème du jour, on a des briques, comme au Tetris mais en 3 dimensions.
Chaque brique est composée de plusieurs cubes tous alignés dans une certaine direction (selon la hauteur, la largeur ou la profondeur).
Voici l'exemple
1,0,1~1,2,1
0,0,2~2,0,2
0,2,3~2,2,3
0,0,4~0,2,4
2,0,5~2,2,5
0,1,6~2,1,6
1,1,8~1,1,9
Chaque brique est donnée par les coordonnées x,y,z de ses deux extrémités et séparés par un "~".
La première ligne représente une brique composé de 3 cubes de coordonnées (1, 0, 1), (1, 1, 1), (1, 2, 1) et est orienté dans le sens de la coordonnée y c'est à dire la profondeur.
Le but de la partie 1 est d'abord de simuler la chute de chaque brique sachant il y a un sol à la hauteur 0.
Ensuite, on doit déterminer le nombre de briques qui peuvent être désintégrées.
Une brique peut être désintégrée si aucune autre brique ne tombe si on la retire.
Dans la partie 2, on doit compter, pour chaque brique, le nombre de briques qui vont chuter si on la retire et faire la somme totale.
# Solution en Haskell
Posté par Guillaume.B . Évalué à 1. Dernière modification le 22 décembre 2023 à 11:46.
5ms pour la partie 1 et 15ms pour la partie 2.
Le problème d'aujourd'hui n'est pas très dur conceptuellement mais j'ai un peu galéré à cause de bugs. Heureusement que l'exemple est là pour nous aider contrairement à hier et avant-hier.
Tout d'abord, on va trier les briques selon la coordonnée z. Ca rend les choses plus à traiter.
On va ensuite simuler la chute de chaque pièce par ordre d'apparition, ce qui ne pose pas de problème grâce au tri que l'on vient de faire.
On va ensuite calculer
support
etsupported
.support
est un dictionnaire qui, à une brique i, associe les index des pièces qui la supportent.De même
supported
est un dictionnaire qui, à une brique i, associe les index des pièces supportées par elle.On dira qu'une brique est stable si elle est supportée par au moins deux autres pièces.
Du coup, une pièce peut être désintégrée si les pièces supportées par elle sont toutes stables.
Pour la partie 2, il s'agit pour chaque pièce de faire un parcours en profondeur (en largeur marche aussi) pour simuler la cascade entrainée par la désintégration d'une pièce.
Une pièce chute si les pièces qui la supportent sont soi la pièce qui est désintégrée soit vont chuter.
J'avais écrit une fonction DFS générique qui m'a déjà servie dans plusieurs exemples.
Cette fonction prenait comme paramètre un sommet de départ et une fonction qui a un sommet associe son voisinage, c'est à dire ses sommets successeurs.
Problème: on a besoin ici de connaitre les sommets déjà parcourus (qui correspondent aux briques qui vont être désintégrées) pour calculer le voisinage.
J'ai donc écrit une fonction BFS générique mais qui prend en compte ce paramètre: la fonction de voisinage prend en paramètre un sommet ainsi que l'ensemble des sommets déjà visités.
Voici le code:
[^] # Re: Solution en Haskell
Posté par Guillaume.B . Évalué à 1.
Je viens de me rendre compte que
support
etsupported
pouvaient être des tableaux plutôt que des dictionnaires. Avec quelques autres trucs, je descend à 10ms pour la partie 2.# On fait tomber des trucs, mais on fait pas de Tetris.
Posté par Yth (Mastodon) . Évalué à 2.
C'est le dernier jour où je vais avoir le temps de la faire, la suite ça sera peut-être dans une semaine…
J'ai inventé un algo un peu tordu, assez efficace, rude à piger, donc à débugger.
Déjà les coordonnées sont en 1 dimension :
x+y*10+z*100
, on va simplifier, surtout qu'on ne fait que des mouvements vers le bas, aucun test aux bornes à faire.J'ajoute un bloc de 10x10 en 0 pour poser le bazar.
Une structure de Blocs assez modélisée, une autre pour l'Univers bien plus simple et à la fin un algo tordu.
Et l'exercice 2, prenez peur !
J'ai pas vraiment le temps de remettre au propre, en gros je pars du haut, et je « pose » les blocs les uns sur les autres, en notant ceux qui sont partiellement posés, et où.
Et puis à chaque bloc, j'essaie de simplifier par ceux qui ne sont partiellement posés plus que sur lui.
Et… bah ça marche, en tapant bien sur le code.
Suivre le flux des commentaires
Note : les commentaires appartiennent à celles et ceux qui les ont postés. Nous n’en sommes pas responsables.