Image UCA logo Prep'isima logo

Antoine Bourdier

PiZZ1

Pikaptcha épisode 1

Introduction

L'objective de ce puzzle est d'aider pikaptcha à cartographier son environnement (un labyrinthe).Le but est de déterminer pour chaque point du labyrinthe son nombre de case adjacentes ou pikaptcha peut se déplacer. En entrée dans le programme, il y a la largeur puis hauteur du labyrinthe. hauteur de fois une chaîne de caractères de longueur largeur contenant une ligne de la grille où 0 est un passage et # est un mur. Voici un exemple d'entrée possible:


        5 3
        00#00#
        0#00#0
        #000#0

On doit donc retrouver en sortie :


        21#21#
        1#23#1
        #132#1

Explication de ma méthode de résolution

J'ai décidé de placer chaque ligne dans une liste nommé grille. Ensuite j'ai séparé chaque élément de ma variable grille dans de nouvelles listes. J'obtiens donc une "matrice" comportant élément de la grille. Avec l'exemple d'entrée grille vaut:

[['0','0','#','0','0','#'],['0','#','0','0','#','0'],['#','0','0','0','#','0']

Ensuite je boucle sur chaque liste de grille, puis sur chaque element de ces listes. Je crée donc une boucle sur chaque élément de la grille. Je rends chaque '0' en entier pour pouvoir les incrémenter puis je teste pour chaque 0 si: l'element adjacent existe (c'est à dire qu'il n'est pas en dehors de la grille pour éviter une erreur du type "out of range"). Puis je teste si l'element est bien un nombre, c'est à dire un passage et non pas un mur. SI tel est le cas alors j'ajoute 1 à l'élément de la grille. Puis après avoir fini sur cet élément je le remets en chaîne de caractère (str) pour avoir plus de faciliter à afficher les lignes. Pour finir j'affiche chaque ligne de grille grâce à la fonction .join()

import sys
      import math
      
      width, height = [int(i) for i in input().split()] # Recuperation des variables largeur et hauteur de la grille
      grille=[]
      for i in range(height):
          grille.append(input())                       # Recuperation de chaque ligne de la grille
      for i in range(height):
          grille[i]=list(grille[i])                   # Chaque element de la grille est dans une liste de la variable grille 
      for i in range(height):                         # Boucle sur chaque liste de la variable grille
          for j in range(width):                      # Boucle sur chaque element de chaque liste de la variable grille
              if grille[i][j]=='0':                   # Chaque 0 est rendu en int
                  grille[i][j]=0                          
                  if i>0 and grille[i-1][j]!='#':         # Test si element du dessus existe et est different de '#'
                      grille[i][j]+=1                             # Si oui alors l'element du dessus est un passage donc on incrémente de 1 car il y a un passage adjacent au dessus
                  if i<height-1 and grille[i+1][j]!='#':      # De la meme facon pour l'element du dessous
                      grille[i][j]+=1
                  if j>0 and grille[i][j-1]!='#':                 # Element à gauche
                      grille[i][j]+=1
                  if j<width-1 and grille[i][j+1]!='#':           # Element à droite
                      grille[i][j]+=1
                  grille[i][j]=str(grille[i][j])                  # Chaque int rendu en str pour l'affichage
      
      for element in (grille):                                # Affichage de chaque ligne
          print("".join(element))

Description d'une solution différente

C'est une solution que je trouve plutôt intéressante car très simple à comprendre et très efficace. Il initialise une variable contenant les directions possibles des cases adjacentes sous forme de couples. Pour chaque element de la grille il boucle sur toutes les directions pour ajouter ou non si les cases adjacentes sont des passages. Il est plus court que le mien et peut-être plus simple à comprendre. Cependant il manque des commentaires pour la comprehension du code notamment à la ligne 12. 

dirs = [(1,0), (-1,0), (0,1), (0,-1)]
      width, height = [int(i) for i in input().split()]
      
      def number_of_adj(i, j, grid):
          global dirs, width, height
          if grid[i][j] == "#":
              return "#"
          else:
              res = 0
              for di, dj in dirs:
                  ii, jj = i + di, j + dj        
                  res += (-1 < ii < height and -1 < jj < width and grid[ii][jj] != "#")
              return res
          
      grid = [list(input()) for _ in range(height)]
      for i in range(height):
          for j in range(width):
              print(number_of_adj(i, j, grid), end = '')
          print()

Apprentissage sur mon code

J'ai trouvé mon code efficace notamment grâce à une bonne utilisation des tests logiques: exemple: "if i>0 and grille[i-1][j]!='#'" si la condition i>0 n'est pas vérifiée la deuxième n'est pas testé et heureusement car sinon il y aurait une erreur de test de type. J'ai appris à écrire l'arbre des conditions pour obtenir le moins de test de conditions.

Pikaptcha épisode 2

Introduction

L'objective de ce puzzle est de compter pour chaque case le nombre de fois que pikaptcha est passée est passée dessus lors de son parcours du labyrinthe. On a en entrée la taille du labyrinthe (largeur et hauteur), le labyrinthe composée de 0 pour une case passage et # pour un mur et enfin comme dernière entrée L ou R pour savoir quel côté du mur pikaptcha doit suivre. En sorti on doit retrouver le labyrinthe avec chaque case passage (0) augmenter du nombre de fois ou pikaptcha est passé dessus. Voici un exemple d'entrée possible: 


      5 3
      >000#
      #0#00
      00#0#
      L

On doit donc obtenir en sortie:


      1322#
      #2#31
      12#1#

Explication de ma méthode de résolution

Synopsis

Pour réaliser ce puzzle. Je vais utiliser la flèche ,ainsi que son positionnement et je ferais parcourir cette flèche tant que je ne suis pas revenu au point de départ. Lors de son parcours je pourrais incrèmenter chaque passage

Explication détaillée

J'initialise une fonction mur_autour qui prend en argument la taille de ma grille (height et width) et qui renvoie cette grille entourée de # representant des murs. Ensuite j'initialise la fonction position_depart qui prend en argument la hauteur et la largeur de ma grille et qui me renvoie la position de la flèche au départ et son orientation. A l'emplacement de la flèche la valeur 0 est mise. J'initialise ensuite deux fonctions similaires gauche et droite qui prenne en argument la grille,height,width,i,j,fleche avec i et j la position de la fleche et fleche son orientation. Ces fonctions me permettent d'obtenir la position suivante de ma fleche ainsi que son orientation. Dans le programme principal il y a d'abord la récuperation de la taille du labyrinthe te le labyrinthe. Le labyrinthe en liste à deux dimensions. Ensuite j'appelle la fonction mur_autour pour entourer cette liste de mur pour pouvoir plus simplement la manipuler. Ensuite j'incrémente de deux height et width car la taille de la grille a augmenter de deux de hauteur et deux de largeur. Je récupère ensuite dans la variable side quel côté pikaptcha va suivre. Je recupère un 3-uplet contenant la position de départ de la flèche et son orientation. Ceci est contenu dans la variable i_j_fleche_depart. Ensuite je teste quel côtés pikaptcha va suivre puis je calcule la position de la flèche suivante et son orientation grâce aux fonctions gauche et droite selon side. J'incrémente de 1 le passage sur lequel est la fleche. Puis je boucle jusqu'à que ma fleche soit à la position départ ou la fleche soit à la position (0,0) c'est à dire que la flèche est bloqué et ne peut aller nul part. Je réitère le processus de flèche suivante ainsi de suite jusqu'a sortir de la boucle. Une fois la boucle terminée je souhaite aficher chaque ligne de la grille. Pour cela je boucle sur chaque element à l'interieur de mes murs ajoutée. J'affiche ensuite chaque ligne sous forme de chaîne de caractères. 

import sys
      import math
      
      def mur_autour(grille,height,width):                            # Fonction permettant d'ajouter des murs tout autour de la grille 
          for p in range(height):                                     # Boucle pour ajouter un # au début et un autre à la fin de la ligne
              grille[p].insert(0,"#")
              grille[p].append("#")
          grille.insert(0,[])
          grille.append([])
          for k in range(width+2):                                    # Boucle pour ajouter une ligne de # au début et à la fin de la grille
              grille[0].append("#")
              grille[-1].append("#")
          return grille 
           
      def position_depart(height,width,grille):                       # Fonction permettant d'obtenir la position i,j du point de départ de la flèche
          for i in range(height):
              for j in range(width):
                  if grille[i][j]!=0 and grille[i][j]!='#':
                      fleche=grille[i][j]
                      grille[i][j]=0
                      return (i,j,fleche)                             # Retourne i,j et l'orientation de la fleche
          return (0,0,'>')                                            # Si pas de flèche alors la fonction retourne (0,0,'>') pour éviter des erreurs lors de l'execution  
                                                   # Retourne la grille modifié
      
      def gauche(grille,height,width,i,j,fleche):                     # Fonction permettant d'obtenir la position suivante de la flèche et son orientation en suivant le mur de gauche
          if fleche=='>':
              if type(grille[i-1][j])==int:
                  return (i-1,j,"^")
              elif type(grille[i][j+1])==int:
                  return (i,j+1,">")
              elif type(grille[i+1][j])==int:
                  return (i+1,j,"v")
              elif type(grille[i][j-1])==int:
                  return (i,j-1,"<")
              else:
                  return (0,0,">")                                    # Au cas ou la flèche de départ est entourée de #
          elif fleche=="^":
              if type(grille[i][j-1])==int:
                  return(i,j-1,"<")
              elif type(grille[i-1][j])==int:
                  return(i-1,j,"^")
              elif type(grille[i][j+1])==int:
                  return(i,j+1,">")
              elif type(grille[i+1][j])==int:
                  return(i+1,j,"v")
              else:
                  return (0,0,">")
          elif fleche=="<":
              if type(grille[i+1][j])==int:
                  return(i+1,j,"v")
              elif type(grille[i][j-1])==int:
                  return(i,j-1,"<")
              elif type(grille[i-1][j])==int:
                  return(i-1,j,"^")
              elif type(grille[i][j+1])==int:
                  return(i,j+1,">")
              else:
                  return (0,0,">")
          else:
              if type(grille[i][j+1])==int:
                  return(i,j+1,">")
              elif type(grille[i+1][j])==int:
                  return(i+1,j,"v")
              elif type(grille[i][j-1])==int:
                  return(i,j-1,"<")
              elif type(grille[i-1][j])==int:
                  return(i-1,j,"^")
              else:
                  return (0,0,">")
                  
      def droite(grille,height,width,i,j,fleche):                     # Fonction permettant d'obtenir la position suivante de la flèche et son orientation en suivant le mur de droit
          if fleche=='>':
              if type(grille[i+1][j])==int:
                  return (i+1,j,"v")
              elif type(grille[i][j+1])==int:
                  return (i,j+1,">")
              elif type(grille[i-1][j])==int:
                  return (i-1,j,"^")
              elif type(grille[i][j-1])==int:
                  return (i,j-1,"<")
              else:
                  return (0,0,">")
          elif fleche=="^":
              if type(grille[i][j+1])==int:
                  return(i,j+1,">")
              elif type(grille[i-1][j])==int:
                  return(i-1,j,"^")
              elif type(grille[i][j-1])==int:
                  return(i,j-1,"<")        
              elif type(grille[i+1][j])==int:
                  return(i+1,j,"v")
              else:
                  return (0,0,">")
          elif fleche=="<":
              if type(grille[i-1][j])==int:
                  return(i-1,j,"^")
              elif type(grille[i][j-1])==int:
                  return(i,j-1,"<")
              elif type(grille[i+1][j])==int:
                  return(i+1,j,"v")
              elif type(grille[i][j+1])==int:
                  return(i,j+1,">")
              else:
                  return (0,0,">")
          else:
              if type(grille[i][j-1])==int:
                  return(i,j-1,"<")
              elif type(grille[i+1][j])==int:
                  return(i+1,j,"v")
              elif type(grille[i][j+1])==int:
                  return(i,j+1,">")
              elif type(grille[i-1][j])==int:
                  return(i-1,j,"^")
              else:
                  return (0,0,">")
      
      width, height = [int(i) for i in input().split()]               # Recuperation des variables de largeur et hauteur de la grille
      grille=[]
      for i in range(height):
          grille.append(input())                                      # Recuperation de chaque ligne de la grille
      for i in range(height):
          grille[i]=list(grille[i])                                   # Mise en "matrice" de la grille
      for i in range(height):
          for j in range(width):
              if grille[i][j]=='0':
                  grille[i][j]=0                                      # Chaque passage de grille est mis à 0 pour pouvoir l'incrémenter
      grille=mur_autour(grille,height,width)                          # La grille est maintenant entourée de mur
      height+=2
      width+=2                                                        # La hauteur et largeur ont donc augmenter de deux
      side = input()                                                  # Recuperation du mur que pikaptcha va suivre
      i_j_fleche_depart=position_depart(height,width,grille)          # Recuperation de la position de depart de la fleche ainsi que son orientation
      if side=='L':
          i_j_fleche=gauche(grille,height,width,i_j_fleche_depart[0],i_j_fleche_depart[1],i_j_fleche_depart[2])   # Position suivante de la fleche et son orientation
          if type(grille[i_j_fleche[0]][i_j_fleche[1]])==int:                                                     # Test si on essaye d'incrementer un entier et pas '#'
                  grille[i_j_fleche[0]][i_j_fleche[1]]+=1
          while (i_j_fleche[0]!=i_j_fleche_depart[0] or i_j_fleche[1]!=i_j_fleche_depart[1]) and i_j_fleche!=(0,0,i_j_fleche[2]):         # Tant que la flèche n'est pas au point de départ ou flèche en position(0,0,'*') qui signifie que la flèche est entourée de #
              i_j_fleche=gauche(grille,height,width,i_j_fleche[0],i_j_fleche[1],i_j_fleche[2])                                            # Position suivante de la flèche
              if type(grille[i_j_fleche[0]][i_j_fleche[1]])==int:
                  grille[i_j_fleche[0]][i_j_fleche[1]]+=1
      else:
          i_j_fleche=droite(grille,height,width,i_j_fleche_depart[0],i_j_fleche_depart[1],i_j_fleche_depart[2])                           # De la meme facon pour suivre le mur Droit
          if type(grille[i_j_fleche[0]][i_j_fleche[1]])==int:
                  grille[i_j_fleche[0]][i_j_fleche[1]]+=1
          while (i_j_fleche[0]!=i_j_fleche_depart[0] or i_j_fleche[1]!=i_j_fleche_depart[1]) and i_j_fleche!=(0,0,i_j_fleche[2]):
              i_j_fleche=droite(grille,height,width,i_j_fleche[0],i_j_fleche[1],i_j_fleche[2])
              if type(grille[i_j_fleche[0]][i_j_fleche[1]])==int:
                  grille[i_j_fleche[0]][i_j_fleche[1]]+=1
      
      for i in range(1,height-1):                                      # Affichage de chaque ligne de la grille
          chaine=""
          for j in range(1,width-1):
              chaine+=str(grille[i][j])
          print(chaine)

Description d'une solution différente

C'est une solution que je trouve joli car il n'y a que 40 ligne. Il utilise les directions de mouvemenet possible, il y donc moins de test. Les fonctions sont faciles à comprendre. Il fait parcourir sa flèche sur sa liste a deux dimensions.

directions = {'<':(-1, 0), '>':(1, 0), '^':(0, -1), 'v':(0, 1)}
    
    def next_direction(d, clockwise):
        dd = [1, -1][clockwise]
        dirs_ccw = '>^<v'
        return dirs_ccw[((dirs_ccw.find(d) + dd) + len(dirs_ccw))%len(dirs_ccw)]
    
    def wall_direction(d, side): return next_direction(d, side == 'R')
    
    def rotate_direction(d, side): return next_direction(d, side == 'L')
    
    def move(x, y, d):
        dx, dy = directions[d]
        return (x + dx, y + dy)
    
    def can_move(map, x, y, d):
        global width, height
        x, y = move(x, y, d)
        return x >= 0 and y >= 0 and x < width and y < height and map[y][x] != '#'
    
    width, height = map(int, input().split())
    map = [list(input()) for y in range(height)]
    side = input()
    
    origin = ()
    for y in range(height):
        for x in range(width):
            if map[y][x] in directions:
                origin = (x, y)
                break
        if origin: break
    
    x, y = origin
    d = map[y][x]
    map[y][x] = '0'
    
    stuck = False
    while True:
        wd = wall_direction(d, side)
        new_d = d
        if can_move(map, x, y, wd): # check wall on the side
            new_d = wd
        else:
            rotations = 4 # max rotations to detect blocked situation
            while not can_move(map, x, y, new_d) and rotations: # rotate if wall in front
                new_d = rotate_direction(new_d, side)
                rotations -= 1
            stuck = rotations == 0
        if stuck: break
        map[y][x] = str(int(map[y][x]) + 1)
        d = new_d
        x, y = move(x, y, d)
        if (x, y) == origin: break
        
    for i in map: print(*i, sep='')

Apprentissage sur mon code

L'utilisation de couple pour donner les directions aurait pu éviter un grand nombre de test dans les fonctions gauche et droite. L'utilisaion de sous fonction aurait pu être utile pour éviter que les fonctions gauche et droite sois trop longue. (Cela aurait pu m'éviter des erreurs lors de certaines éxecution car fautes humaines). Mon programme principale est peut-être difficile à comprendre car nom de variable trop longue. Cependant j'ai bien utilisée des fonctions qui permettent une meilleure compréhension du code.