Rapport Pikaptcha

Préambule

Le but de ce rapport est de présenter les solutions aux deux épreuves Pikaptcha.

Le rapport est divisé en deux parties, la première concerne l'épreuve 1 et la seconde l'épreuve 2.

Ma page personnelle est disponible à cette adresse: https://perso.isima.fr/~jugirard3/

> Pikaptcha EP1

Introduction

Pikaptcha s'est retrouvé enfermé dans un labyrinthe et il faut l'aider à en sortir

L'objectif est d'écrire un programme qui retournera pour chaque case de la grille le nombre de passages adjacents.

Pour résoudre le problème on nous fournit un grille qui contient soit:

des 0 qui representent des espaces libres
des # qui representent les murs

On considère qu'il y a au maximum pour chaque case 4 voisins à savoir (droite, gauche, haut, bas). On considère donc que les cases en diagonales ne sont pas des voisins. Voici un exemple de grille:


0000#
#0#00
00#0#

La solution


width, height = [int(i) for i in input().split()]
plateau = []
for i in range(height):
plateau.append(input())
for row in range(height):
    string = ''
    for column in range(width):
        echap = 0
        if plateau[row][column] == '0':
            if row > 0 and plateau[row - 1][column] == '0':
                echap += 1
            if row < height - 1 and plateau[row + 1][column] == '0':
                echap += 1
            if column > 0 and plateau[row][column - 1] == '0':
                echap += 1
            if column < width - 1 and plateau[row][column + 1] == '0':
                echap += 1
            string += str(echap)
        else:
            string += "#"
    print(string)

Explications

On commence par lire la largeur et la hauteur de la grille.

On crée une liste vide plateau qui contiendra la grille sous forme d'une liste de chaîne de caractères. Chaque chaine de caracteres est constituée de "0" ou de "#" représente une ligne du labyrinthe.

On parcourt ensuite la grille ligne par ligne puis dans la ligne colonne par colonne

Si la case est un espace libre on vérifie les cases voisines. Si elles ne sont pas en dehors du plateau et qu'elles sont vides, on incrémente le compteur echap de 1 pour chaque case voisine libre.

Pour chaque colonne de la ligne on ajoute le nombre de cases voisines vides ou le caractère "#" si c'est un mur a la chaîne de caractères

Une fois la ligne entièrement parcourut, affiche la chaîne de caractères qui concatènent les résultats

Les tests

Le code fonctionne correctement et passe tous les tests en moins de 2s comme demandé, voici quelques exemples :

En entrée :


0000#
#0#00
00#0#

En sortie :


1322#
#2#31
12#1#

En entrée :


#00###000
000000000
000##0000

En sortie :


#22###232
244223443
232##2332

La solution de la communauté

Solution de BalazsNagy : https://www.codingame.com/training/easy/detective-pikaptcha-ep1/solution?id=12953085


import sys
import math

# this have to be refactored 

class Passage:
    def __init__(self, x, y):
        self.x = x
        self.y = y    
    
    def count_neighbours(self, passages):
        self.neighbours = len([p for p in passages if self.are_neighbours(p)])
    
    def are_neighbours(self, other):
        return (other.y == self.y and abs(other.x - self.x) == 1) or (other.x == self.x and abs(other.y - self.y) == 1)

width, height = [int(i) for i in input().split()]
passages = []

for y in range(height):
    line = input()
    passages.extend([Passage(x,y) for x, cell in enumerate(line) if cell == '0'])

for passage in passages:
    passage.count_neighbours(passages)

result = [['#' for x in range(width)] for y in range(height)]

for p in passages:
    result[p.y][p.x] = str(p.neighbours)

for row in result:
    print(''.join(row))

J'ai choisi ce code car il utilise une approche avec des classes Python.

En effet les classes apportent de lisibilité au code mais peuvent vite devenir complexes. Ici l'exercice pouvait être resolu sans classe.

On remarque que le code est aussi peut optimiser puisqu'il utilise pas moins de 4 boucles "for" explicite et encore 5 boucles supplémantaires sous forme de compréhension de liste. Le code est donc très peu performant

> Pikaptcha EP2

Introduction

Dans le deuxième exercice, on doit marquer combien de fois on passe sur chaque case en suivant le mur de droite ou de gauche, jusqu'a ce que l'on retourne sur la case de départ.

Le labyrinthe est toujours sous la même forme à savoir une suite de lignes composées de :

0 qui représentent des espaces libres
# qui représentent les murs

La solution


# initialisation des variables
largeur, hauteur = [int(i) for i in input().split()]
plateau = ["#" * (largeur + 2)]
for numeroLigne in range(hauteur):
    ligne = input()
    plateau.append("#" + ligne + "#")
    for caractere in ligne:
        if caractere in "<>^v":
            direction = caractere
            debut = (ligne.index(caractere) + 1, numeroLigne + 1)
            plateau[-1] = plateau[-1].replace(caractere, "0")
plateau.append("#" * (largeur + 2))
murASuivre = input()

solution = []
for ligne_plateau in plateau:
    ligne_solution = []
    for char in ligne_plateau:
        if char == "#":
            ligne_solution.append("#")
        else:
            ligne_solution.append(0)
    solution.append(ligne_solution)


# définition des fonctions de déplacement
def haut(x, y):
    if plateau[y - 1][x] == "#":
        return False, None, None
    return True, (x, y - 1), "^"


def bas(x, y):
    if plateau[y + 1][x] == "#":
        return False, None, None
    return True, (x, y + 1), "v"


def gauche(x, y):
    if plateau[y][x - 1] == "#":
        return False, None, None
    return True, (x - 1, y), "<"


def droite(x, y):
    if plateau[y][x + 1] == "#":
        return False, None, None
    return True, (x + 1, y), ">"


# (direction, murASuivre) : (direction, ...)
choix_direction = {
    # en suivant le mur à gauche
    (">", "L"): (haut, droite, bas, gauche),
    ("v", "L"): (droite, bas, gauche, haut),
    ("<", "L"): (bas, gauche, haut, droite),
    ("^", "L"): (gauche, haut, droite, bas),
    # en suivant le mur à droite
    (">", "R"): (bas, droite, haut, gauche),
    ("v", "R"): (gauche, bas, droite, haut),
    ("<", "R"): (haut, gauche, bas, droite),
    ("^", "R"): (droite, haut, gauche, bas),
}

x, y = debut

while True:

    solution[y][x] += 1
    for fonction in choix_direction[(direction, murASuivre)]:
        possible, coord, new_direction = fonction(x, y)
        if possible:
            x, y = coord
            direction = new_direction
            break
    else:
        # pas de direction possible (encerclé par des murs)
        solution[y][x] = 0
        break

    # si on est revenu au point de départ
    if (x, y) == debut:
        break

solution = solution[1:-1]  # on enlève les bordures
for ligne in solution:
    string = "".join(str(i) for i in ligne[1:-1])  # on enlève les bordures a gauche et a droite
    print(string)

Explications

Signification des variables

largeur et hauteur: Les dimensions du labyrinthe
plateau: Le tableau qui représente le labyrinthe. Chaque élément est une chaîne qui représente une ligne du labyrinthe.
direction: La direction de départ, déterminée à partir de la première occurrence d'un des caractères "<>^v" dans l'une des lignes du labyrinthe.
debut: Les coordonnées du point de départ, déterminées à partir de la position du caractère déterminant la direction.
murASuivre: La direction pour suivre les murs, entrée par l'utilisateur("L" ou "R").
solution: Le tableau qui représente le nombre de passages à chaque emplacement.
choix_direction: Un dictionnaire qui définit la priorité des directions à explorer en fonction de la direction actuelle et du mur à suivre.
x et y: Les coordonnées du point actuel.
possible: Un booléen qui indique si le déplacement est possible.
coord: Les coordonnées du prochain point si le déplacement est possible.
new_direction: La direction dans laquelle le prochain déplacement est effectué si possible.

Algorithme

On initialise les variables avec les valeurs qui nous sont données.
On crée la liste plateau qui représente le labyrinthe. On ajoute au plateau des murs artificiels en ajoutant des "#" à ses bord. Cela évitera pas la suite de devoir vérifier si nous sommes au bord du plateau.
On parcourt les entrées ligne par ligne et on les ajoute au plateau. Pour chaque ligne on vérifie si un des caractères suivants n'est pas présent "<>^v", ce qui signifierait que nous avons trouvé le point de départ. Si c'est le cas, on initialise les variables direction et debut avec les valeurs correspondantes.
On crée la liste solution qui représente le nombre de passages à chaque emplacement. On initialise chaque emplacement à 0 si il n'y a pas de mur, et à "#" si il y a un mur.
On définit les fonctions de déplacement haut, bas, gauche et droite. Ces fonctions vérifient si le déplacement est possible, et si c'est le cas, renvoient True, les coordonnées du prochain point et la direction dans laquelle le prochain déplacement est effectué.
On définit le dictionnaire choix_direction qui définit la priorité des directions à explorer en fonction de la direction actuelle et du mur à suivre.
On initialise les variables x et y avec les coordonnées du point de départ.
On boucle tant que le point de départ n'est pas atteint.
On incrémente le nombre de passages à l'emplacement actuel.
On parcourt les directions prioritaires en fonction de la direction actuelle et du mur a suivre.
Si le déplacement est possible, on met à jour les variables x, y et direction avec les valeurs renvoyées par la fonction de déplacement.
Si aucun déplacement n'est possible, on remet le nombre de passages à l'emplacement actuel à 0 et on sort de la boucle. Cela signifie que nous sommes encerclés par des murs.
Si nous sommes revenus au point de départ, on sort de la boucle.

Les Tests

Le code fonctionne correctement et passe tous les tests en moins de 2s comme demandé, voici quelques exemples :

En entrée :


0000#
#0#00
00#0#

En sortie :


1322#
#2#31
12#1#

La solution de la communauté

Solution de nicola : https://www.codingame.com/training/easy/detective-pikaptcha-ep2/solution?id=12245062


w,h=map(int,input().split())
p=[]
for i in range(h):
    p.append(input())
    D=set(p[-1])&{"<",">","v","^"}
    if D:
        d=D.pop()
        P=(i,p[-1].index(d))
        p[-1]=p[-1].replace(d,"0")
c=input()
init=P
d={">":(0,1),"<":(0,-1),"v":(1,0),"^":(-1,0)}[d]
mouv={"R":{(0,1): ((1,0), (0,1), (-1,0),(0,-1)),
           (0,-1):((-1,0),(0,-1),(1,0), (0,1)),
           (1,0): ((0,-1),(1,0), (0,1), (-1,0)),
           (-1,0):((0,1), (-1,0),(0,-1),(1,0))},
      "L":{(0,1): ((-1,0),(0,1), (1,0), (0,-1)),
           (0,-1):((1,0), (0,-1),(-1,0),(0,1)),
           (1,0): ((0,1), (1,0), (0,-1),(-1,0)),
           (-1,0):((0,-1),(-1,0),(0,1), (1,0))}}[c]

while True:
    for m in mouv[d]:
        x,y=P[0]+m[0],P[1]+m[1]
        if not 0<=x<\h:
            continue
        if not 0<=y<\w:
            continue
        if p[x][y]=="#":
            continue
        d=m
        P=(x,y)
        p[x]=p[x][:y]+str(int(p[x][y])+1)+p[x][y+1:]
        break
    else:
        break
    if P==init:
        break

print("\n".join(p))

J'ai choisi ce code car il me semble être particulierement efficace. En effet le code utlise des Set à la place de liste pour augmenter la vitesse de recherche. De plus le code a une complexité plutôt faible cas il utlise peux de boucle et remplace les conditions par un dictionnaire

Cependant, plusieurs points pourraient être améliorés :

Le code peut être rendu plus lisible en utilisant des noms de variables plus significatifs et plus longs.
Le dictionnaire mouv pourrait être réarrangé pour une meilleure lisibilité
Il faudrait ajouter quelques commentaires pour diriger le relecteur

Rapport Pikaptcha Eps 1 & 2

Par Jules GIRARD - Prep'Isima - Janvier 2023

Préambule

> Pikaptcha EP1

Introduction

La solution

Explications

Les tests

La solution de la communauté

> Pikaptcha EP2

Introduction

La solution

Explications

Signification des variables

Algorithme

Les Tests

La solution de la communauté