Aller au contenu

POO et récursivité⚓︎

Présentation⚓︎

Shikaku est un casse-tête japonais. Le jeu consiste à paver entièrement un grand rectangle avec plusieurs petits, sans chevauchement de ces derniers.

La donnée de départ est constituée :

  1. des dimensions du grand rectangle
  2. des aires des petits rectangles et, pour chacun d'eux, d'une case du grand rectangle que ce petit doit inclure.

Exemple

Ci-dessous, un problème sur un rectangle de \(10\times10\), avec 12 petits rectangles.

ascii

grahique

On retrouve ce puzzle en exercice de programmation chez Codingame : Shikaku-solver.

Nous allons modéliser et résoudre ce problème en utilisant la POO et la récursivité. Dans la présentation qui suit, nous avons utilisé le module ipythonblocks pour visualiser la résolution. Mais l'absence de possibilité d'annotation rend l'affichage perfectible.

Les concepts abordés :

  • Programmation Orientée Objet
  • Récursivité

Principe de résolution⚓︎

Il consiste à résoudre en suivant le principe de retour arrière : on parcourt les cases du grand rectangle, de haut en bas et de gauche à droite et on teste toutes les positions possibles de rectangles autorisés ; on revient en arrière quand on est bloqué. L'algorithme est connu sous le nom de backtracking en anglais.

Souvent dans les puzzles résolus par backtracking on s'intéresse à une solution. La première atteinte convient. Dans le problème donné par Codingame, il s'agit de trouver toutes les solutions. Cela pose le souci de l'explosion combinatoire : il y a trop de configurations à tester.Élaguer cet arbre d'exploration en détectant tôt qu'un début d'exploration va conduire à une impasse est primordial.

Un exemple⚓︎

Voici les premières étapes de la résolution de l'exemple introductif :

Résolution du puzzle test01.txt

Le puzzle initial : les cases colorées sont les coordonnées des origines (malheureusement avec BlockGrid on ne peut mettre d'annotations, perdant momentanément les aires des petits rectangles)

grahique

On tente de paver à partir de la case \((0, 0)\)

etape1

On revient en arrière puisque la dernière case de la première ligne ne pouvait être pavée.

etape2

On tente alors le deuxième rectangle à pouvoir atteindre la case \((0, 0)\) : celui de 20 d'aire et dont l'origine est en \((1, 3)\).

etape3

Et la prochaine étape va consister à essayer de paver à partir de la case \((4, 0)\) (voir E4)...

La case \((4, 0)\) est pavée à l'aide d'un rectangle \(3\times 3\) dont l'origine est en \((5, 1)\). Le 1/1 signifie qu'il n'y a pas d'autres possibilités pour ce rectangle de paver la case en question.

etape4

Dans l'absolu, le rectangle d'aire 9, devant inclure l'origine en \((5, 1)\) possède trois autres réalisations possibles :

  • 2 rectangles de largeur 1 et de hauteur 9 commençant respectivement en \((5, 0)\) ou en \((5, 1)\) ;
  • 1 rectangle \(3\times 3\) commençant en \((5, 0)\)

Mais bien sûr aucun de ces 3 rectangle n'inclus la case \((4, 0)\)

On continue encore un peu avec la case \((7, 0)\)

etape5

Attention la prochaine est la case \((4, 3)\), qui est l'origine d'un rectangle, voir E6...

En \((4, 3)\) c'est un rectangle d'aire 8 apparemment :

etape6

Bientôt un retour puisque sur l'étape ci-dessous on constate que la case suivante \((9, 3)\) ne sera pas pavable.

etape7

Le retour...

etape8

On essaie de paver \((6, 3)\) à l'aide d'un autre rectangle...

etape9

La résolution se poursuit, jusqu'à cette première solution...

etape_solution

À chaque solution rencontrée, elle est mémorisée mais l'exploration se poursuit : il nous faut toutes les solutions.

Vocabulaire en vue de la modélisation⚓︎

Rectangle virtuel

Nous appelons rectangle virtuel la donnée d'une case, par ses coordonnées \((x, y)\) et d'une aire entière \(a\). On pourra noter comme un triplet : \((x, y, a)\).

Shikaku puzzle

Un Shikaku puzzle est la donnée d'une largeur et d'une hauteur ainsi qu'un ensemble de rectangles virtuels.

Exemple

L'exemple introductif est le shikaku puzzle n°1 constitué d'un rectangle de \(10\times 10\) et des rectangles virtuels suivants : \((8, 0, 9)\), \((5, 1, 9)\), \((1, 3, 20)\), \((4, 3, 8)\), \((8, 3, 6)\), \(((3, 5, 6)\), \((6, 6, 6)\), \((0, 7, 10)\), \((2, 8, 6)\), \((4, 8, 6)\), \((8, 8, 8)\) et \((6, 9, 6)\) qu'on peut visualiser en ascii :

    0  1  2  3  4  5  6  7  8  9
------------------------------
0 | .  .  .  .  .  .  .  .  9  . | 0
1 | .  .  .  .  .  9  .  .  .  . | 1
2 | .  .  .  .  .  .  .  .  .  . | 2
3 | .  20 .  .  8  .  .  .  6  . | 3
4 | .  .  .  .  .  .  .  .  .  . | 4
5 | .  .  .  6  .  .  6  .  .  . | 5
6 | 10 .  .  .  .  .  .  .  .  . | 6
7 | .  .  .  .  .  .  .  .  .  . | 7
8 | .  .  6  .  6  .  .  .  8  . | 8
9 | .  .  .  .  .  .  6  .  .  . | 9
------------------------------
    0  1  2  3  4  5  6  7  8  9

Origine

On appelle origine les coordonnées d'un rectangle virtuel.

Fichier Shikaku

Les données d'un Shikaku puzzle sont donnés par un fichier texte nommé fichier Shikaku.

Exemple test01.txt

Voici le contenu du fichier Shikaku de l'exemple introductif :

10 10
0 0 0 0 0 0 0 0 9 0
0 0 0 0 0 9 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 20 0 0 8 0 0 0 6 0
0 0 0 0 0 0 0 0 0 0
0 0 0 6 0 0 6 0 0 0
10 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 6 0 6 0 0 0 8 0
0 0 0 0 0 0 6 0 0 0

Rectangle

On appelle rectangle d'un rectangle virtuel \((x_0, y_0, a)\) un rectangle donné par la position en \((x, y)\) de son coin supérieur gauche de sa largeur \(w\) et de la hauteur \(h\) tel que :

  • \((x_0, y_0)\) appartient au rectangle
  • \(w\times h = a\)

On désignera souvent un rectangle par un quadruplet \((x, y, w, h)\).

Exemple

\((0, 0, 9, 1)\) et \((7, 0, 3, 3)\) sont deux rectangles du rectangle virtuel \((8, 0, 9)\).

Rempli

On dira qu'un rectangle virtuel est rempli si un de ses rectangles couvre une partie du grand rectangle du Shikaku puzzle.

Objet VirtualRect⚓︎

★ Question 1

Créer une classe VirtualRect qui possède les propriétés suivantes :

  • shikaku : une référence vers le puzzle Shikaku auquel appartient le rectangle virtuel ;
  • x, y pour les coordonnées de l'origine ;
  • area pour l'aire ;
  • rectangles pour stocker les rectangles de ce virtuel
  • filled un booléen qui reflète la propriété rempli d'un rectangle virtuel.

L'origine et l'aire seront initialisés à la création, par des arguments passés à l'initialiseur d'instance ; de même pour le shikaku.

La propriété rectangles sera un dictionnaire vide pour le moment ; et filled initialisé à False.

Il nous faut maintenant une méthode pour initialiser correctement les rectangles.

Voici comment nous allons procéder :

  1. Décomposer l'entier \(a\) de l'aire du rectangle virtuel en couples \((w, h)\) d'entiers tels que \(w\times h = a\) ;
  2. parcourir chacun des \((w, h)\) de cette décomposition et déterminer les 4 valeurs \(x_m, x_M, y_m, y_M\), les extremum possibles pour les coordonnées \((x, y)\) du coin supérieur gauche d'un rectangle du virtuel considéré
  3. pour chaque rectangle \((x, y, w, h)\) s'il est une concrétisation possible du virtuel, c'est-à-dire s'il y a suffisamment de place (le rectangle reste dans les limites du grand rectangle et ne vient chevaucher aucune origine d'autres rectangles virtuels) alors on met à jour le dictionnaire rectangles pour la clé \((x, y)\) : créer l'ensemble \(\{(w, h)\}\) s'il n'y a pas d'entrée pour cette clé ou ajouter le couple \((w, h)\) à l'ensemble existant.
★★★ Question 2

Implémenter les méthodes suivantes :

  • decompose qui calcule l'ensemble des couples d'entiers \((w, h)\) tels que le produit \(w\times h\) vaut l'aire du rectangle virtuel
  • upper_left qui prend deux valeurs \(w\) et \(h\) en paramètres et calcule le quadruplet \(x_m, x_M, y_m, y_M\)
  • enough_space qui prend 4 paramètres, \(x\), \(y\), \(w\) et \(h\) et qui renvoie la valeur de la méthode du même nom du shikaku
  • init_rectangles pour l'initialisation des rectangles comme décrit.

Objet Shikaku⚓︎

Il nous faut modéliser un Shikaku puzzle caractérisé par :

  • des dimensions (largeur, hauteur)
  • un ensemble de rectangles virtuels

À cela il faudra ajouter :

  • une grille de valeurs : au départ initialisée de 0 sauf aux points origines où l'on trouve les valeurs des aires des rectangles virtuels. Cette grille servira aussi pour l'affichage de la solution comme demandée par Codingame c'est-à-dire avec des lettres de l'alphabet comme motifs de pavage

    Réponse pour l'exemple d'intro 
    1
AAAABBBCCC
AAAABBBCCC
AAAABBBCCC
AAAADDDDEE
AAAADDDDEE
FFGGGHHHEE
FFGGGHHHII
FFJJKKLLII
FFJJKKLLII
FFJJKKLLII

  • une liste des solutions ; chaque solution sera une unique chaine de caractères formée à partir de la grille remplie

    L'unique solution de l'exemple précédent 
    'AAAABBBCCC\nAAAABBBCCC\nAAAABBBCCC\n...\nFFJJKKLLII'
★ Question 3

Créer une classe Shikaku avec les propriétés suivantes :

  • width et height pour les dimensions
  • grid : la grille des valeurs
  • virtuals une liste d'objets VirtualRect comportant les infos initiales des petits rectangles (pour l'instant une liste vide)
  • solutions : la liste des solutions (initialiement vide)

Les puzzles seront donnés comme dans Codingame : un fichier texte contenant sur la première ligne la largeur et la hauteur du grand rectangle, puis le grand rectangle sous la forme de lignes et de colonnes de 0 sauf aux emplacements des rectangles virtuels : on y trouve les aires.

Fichier texte de l'exemple

Le puzzle de l'introduction est modélisé par le fichier texte test_01.txt ci-dessous :

test01.txt
10 10
0 0 0 0 0 0 0 0 9 0
0 0 0 0 0 9 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 20 0 0 8 0 0 0 6 0
0 0 0 0 0 0 0 0 0 0
0 0 0 6 0 0 6 0 0 0
10 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 6 0 6 0 0 0 8 0
0 0 0 0 0 0 6 0 0 0
★★ Question 4

Créer une méthode load qui prend un nom de fichier en paramètre et utilise les infos pour initialiser un Shikaku puzzle.

Ainsi on aura :

>>> puzzle = Shikaku()
>>> puzzle.load('test_01.txt')
>>> puzzle.grid
[[0, 0, 0, 0, 0, 0, 0, 0, 9, 0],
[0, 0, 0, 0, 0, 9, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 20, 0, 0, 8, 0, 0, 0, 6, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 6, 0, 0, 6, 0, 0, 0],
[10, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 6, 0, 6, 0, 0, 0, 8, 0],
[0, 0, 0, 0, 0, 0, 6, 0, 0, 0]]

La méthode doit aussi mettre à jour la liste virtuals

Quelques petites méthodes utiles⚓︎

★★ Question 5

  1. Coder une méthode empty qui prend en paramètre les coordonnées \(x\) et \(y\) d'une case et qui renvoie True si et seulement si la case correspondante dans la grille est vide.

  2. En utilisant la méthode empty ; coder une méthode enough_space qui prend 6 paramètres : les infos d'un rectangle soit \(x\) et \(y\) les coordonnées du coin supérieur gauche, \(w\) et \(h\) les dimensions ainsi que \(x_o\) et \(y_o\) une orgine de rectangle virtuel. La fonction renvoie True si la grille est entièrement vide sur l'emprise du rectangle sauf au niveau de la case \((x_o, y_o)\).

★★ Question 6
  1. Ajouter à la classe Shikaku une méthode empty_coords qui renvoie un itérateur sur les couples \((x, y)\) des cases vides. Un itérateur s'obtient par exemple comme une contruction de liste en compréhension : 
    def ma_methode(self, ...):
    return (f(elt) for elt in something if constraint(elt))
  2. Ajouter une méthode unfilled_areas qui renvoie un itérateur des rectangles virtuels non remplis.
★★ Question 7
  1. Ajouter une constante LABELS qui est la chaine de caractères suivantes : 
    ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz
  2. Ajouter la méthode fill qui pren en paramètres un rectangle c'est-à-dire quatre paramètres \(x\), \(y\), \(w\), \(h\) et un indice \(i\) et qui remplit la grille du shikaku avec la lettre de l'alphabet à l'indice \(i\)
  3. Ajouter la méthode unfill qui remet des 0 partout sauf à l'emplacement original du rectangle virtuel où il faut remettre la valeur de l'aire

La résolution : la méthode solve⚓︎

★★★ Question 8

La résolution se fait par la méthode solve qui suit le principe décrit au début de cette page. Cette méthode prend en paramètre les coordonnées \(x\) et \(y\) de la première case en haut à gauche non encore remplie et un indice de lettre :

def solve(self, x, y, letter_id):
    if # une solution a été atteinte:
        # ajouter à solutions la version str de grid
    elif # la case x, y est déja remplie:
        # passer à la case suivante et faire un appel récursif
    else:
        # Parcourir les virtual_rect de virtuals qui ont 
        # la case (x, y) parmi les coins supérieurs gauche possible
            # parcourir les rectangles qui ont assez de place
                # - remplir la grille avec ce rectangle
                # - chercher la case suivante 
                # - faire l'appel récursif sur solve avec letter_id + 1
                # - défaire le dernier remplissage

Implémenter la méthode solve.

★★ Question 9

Ajouter une méthode answer qui trie les solutions puis affiche le nombre de solutions et la première.

Tests et explosion combinatoire⚓︎

Effectuer un test avec le puzzle 1 et vérifier que vous obtenez la bonne réponse :

1
AAAABBBCCC
AAAABBBCCC
AAAABBBCCC
AAAADDDDEE
AAAADDDDEE
FFGGGHHHEE
FFGGGHHHII
FFJJKKLLII
FFJJKKLLII
FFJJKKLLII

Normalement, le code produit devrait permettre de passer les tests dans codingame.

Néanmoins, il est possible d'améliorer les temps d'exécution. En effet, certains rectangles virtuels n'ont qu'un rectangle possible et il est donc inutile d'aller tester pour d'autres rectangles virtuels des rectangles qui viendraient empiéter sur l'emplacement réservé.

Le rectangle virtuel de 20

Par exemple, on constate sur cette vue que le rectangle virtuel de 20 ci-dessous n'a que cet emplacement de possible :

rect20

Il est donc inutile par exemple d'explorer les configurations qui commencent par :

rect9

Sur l'exemple 3, dont voici le fichier initial :

Test 3 
20 20
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 8 0
0 0 0 0 0 0 0 0 0 0 0 0 65 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 8 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 15 0 0 0 0 0
18 0 0 0 0 0 0 0 0 9 0 0 0 6 0 0 0 0 0 6
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 6 0 0
0 0 0 0 0 0 0 8 0 0 0 0 0 0 0 6 8 0 0 0
10 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 8 0 6 0 0 8 0 0 6 0 0 0 0 0 0
8 0 0 0 0 0 0 0 0 0 0 6 0 0 0 6 0 0 0 8
0 0 0 0 0 0 0 0 0 0 0 6 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 6 0 0 6 0 0 0 6 0 0 0 12 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 16 0 0 10 0 0 0 0 0 6 0 0 0 0 0 0 0
9 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 6 0 0 0 0 0 8 0 0 0 0
0 0 0 0 0 9 0 9 0 0 0 0 0 6 0 0 8 0 8 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 6 0
0 0 0 0 0 0 26 0 0 0 0 0 0 8 0 0 0 0 0 0

Voici les rectangles obligatoires :

test3

Dès lors l'exploration pour trouver les 32 solutions passe de 44405 configurations explorées à 10933.

Retour en haut de la page