Forum Programmation.autre Avent du Code, jour 12

Post√©¬†par¬† (site web personnel) . Licence CC¬†By‚ÄĎSA.
√Čtiquettes¬†:
4
12
déc.
2022

Suite de l'Avent du Code, jour 12.

Le P√®re No√ęl cherche √† sortir de la gorge de la rivi√®re o√Ļ il est tomb√©, avec l'aide de son ami Dijkstra son communicateur-suisse qui a aussi une fonction de cartographie d'altitude.

  • # En Python

    Post√©¬†par¬† (site web personnel) . √Čvalu√©¬†√†¬†4.

    Ma premi√®re id√©e fonctionnait sur l'exemple mais pas sur les donn√©es r√©elles¬†: parcourir r√©cursivement une matrice de proche en proche en √©vitant simplement les endroits o√Ļ on est d√©j√† pass√©, √ßa atteint vite la limites de longueur de la pile d'appels.

    Du coup, j'ai fait du Dijkstra. Enfin quelque chose inspiré de son algorithme en tout cas. Ça pourrait être fait de façon entièrement itérative, mais ça ne valait pas la peine, ça reste raisonnable en récursif.

    Une fois qu'on a ça, la deuxième partie du puzzle ne pose pas spécialement de problème. Il y a tout de même deux façons de l'implémenter, une bête et méchante (on prend la première solution et on l'applique plusieurs fois), et une un rien plus futée.

    from typing import Iterable, Iterator, List, Optional, Set, Tuple
    
    import numpy as np
    
    
    Coords = Tuple[int, int]
    
    
    class Map:
        def __init__(self, matrix: np.ndarray) -> None:
            self.matrix = matrix
            self.ly, self.lx = matrix.shape
    
        def neighs(self, y: int, x: int) -> Iterator[Coords]:
            """Yield neighbours that are reachable from the given coordinates,
            considering movement rules (no climbing)"""
            for (dx, dy) in ((-1, 0), (1, 0), (0, -1), (0, 1)):
                y_ = y + dy
                x_ = x + dx
                if y_ < 0 or y_ >= self.ly or x_ < 0 or x_ >= self.lx:
                    continue
                if self.matrix[y_, x_] - self.matrix[y, x] <= 1:
                    yield y_, x_
    
        def _distances(self, starts: Iterable[Coords], end: Coords,
                       distances: np.ndarray) -> None:
            """Update distances matrix by computing walking distance from possible
            starts"""
            if starts == []:
                # Nothing left to explore
                return
            nexts = []  # List[Coords]
            for start in starts:
                start_dist = distances[start]
                if start_dist < 0:
                    raise ValueError(
                            'cannot compute distances from uncharted point')
                for neigh in self.neighs(*start):
                    neigh_dist = distances[neigh]
                    if neigh_dist < 0 or start_dist + 1 < neigh_dist:
                        # This point has either never been checked before, or has
                        # been but we have a shorter path to it
                        distances[neigh] = start_dist + 1
                        nexts.append(neigh)
            # Update distances from the points we have just updated
            self._distances(nexts, end, distances)
    
        def min_dist(self, starts: List[Coords], end: Coords) -> int:
            distances = np.full_like(self.matrix, -1)
            """Return the minimal distance to reach end, starting from starts"""
            for start in starts:
                distances[start] = 0
            self._distances(starts, end, distances)
            return distances[end]
    
    
    def import_lines(lines: Iterable[str]) -> Tuple[Map, Coords, Coords]:
        matrix = []  # type: List[List[int]]
        start = None
        end = None
        for y, line in enumerate(lines):
            matrix.append([])
            for x, char in enumerate(line.rstrip()):
                if char == 'S':
                    start = (y, x)
                    height = 0
                elif char == 'E':
                    end = (y, x)
                    height = 25
                else:
                    height = ord(char) - ord('a')
                matrix[-1].append(height)
        if start is None or end is None:
            raise ValueError("no start or end position found")
        return Map(np.array(matrix)), start, end
    
    
    def solve_both(lines: Iterable[str]) -> Tuple[int, int]:
        """Solve part 1 of today's puzzle"""
        map_, start, end = import_lines(lines)
        min1 = map_.min_dist([start], end)
        min2 = map_.min_dist([coords for coords, height  # type: ignore
                              in np.ndenumerate(map_.matrix)
                              if height == 0], end)
        return min1, min2
    • [^] # Re: En Python

      Post√©¬†par¬† . √Čvalu√©¬†√†¬†1.

      Par rapport a la deuxieme partie, pour moi la version bete et mechante ne marchait pas. Le calcul pour chaque point de depart prenait plusieurs minutes, donc il etait obligatoire de 'cacher' les distances a partir de chaque point.

      Excusez l'absence d'accents dans mes commentaires, j'habite en Australie et n'ai pas de clavier francais sous la main.

      • [^] # Re: En Python

        Post√©¬†par¬† . √Čvalu√©¬†√†¬†2.

        Dans mon input, tous les b ne sont que dans la deuxième colonne. Et la première colone ne contient que des a. Comme il faut nécessairement passer par un b, je n'ai testé que des départs depuis la première colonne.

  • # python et lib de graph

    Post√©¬†par¬† . √Čvalu√©¬†√†¬†4.

    J'ai passé plusieurs heures à ne pas comprendre pourquoi je ne trouvais pas la solution. Et puis j'ai compris ; j'ai loupé une phrase cruciale dans l'énoncée : on a le droit de redescendre, bordel !

    J'ai utilise la très précieuse bibliothèque de manipulation de graph en Python, networkx. Mon code ne fait que parser l'input et construire la liste de transitions possibles et présente donc peu d'intérêt. Mais permet au moins de faire une joli nimage du résultat:

    Si vous vous baladez sur Reddit, y en a qui ont fait des représentations de ouf.

    La seconde partie était triviale dans ces conditions et m'a pris moins de deux minutes.

    • [^] # Re: python et lib de graph

      Post√©¬†par¬† (Mastodon) . √Čvalu√©¬†√†¬†2.

      Ah, classe :)
      J'ai rien de joli à montrer ce coup-ci.
      Mais bon, journée présentiel au taf hier, trois heures dans la voiture, 4h en réunions, j'ai à peine eu le temps de bricoler une solution, en ayant réfléchi sur le trajet…

      J'ai fait un parcours de graphe inventé à la volée : je n'ai jamais été fichu de retenir le moindre des algos de parcours que j'ai pu apprendre, alors je suis condamné à réinventer la roue !

      J'ai des cases en entr√©e, je regarde pour chacune d'elles o√Ļ elles peuvent aller (haut, bas, gauche, droite, si la diff√©rence de hauteur est bonne), et si je n'ai pas d√©j√† √©t√© l√† (donc matrice des cases visit√©es avec distance au d√©part dedans).
      Je note l'ensemble des cases nouvellement visitées, et j'itère sur cet ensemble.
      Donc a priori inutile de stocker le score pour le retrouver et calculer la suite comme dans mon code plus bas : il suffit de compter les étapes.

      Instinctivement, je me suis dis que ça pouvait grossir, et donc j'ai décidé de manger le problème par les deux bouts, donc j'explore en montant depuis "S" et en descendant depuis "E".
      Je stocke des scores positifs en montant, et négatifs en descendant.
      Si je rencontre une case visitée depuis l'autre bout (case négative si je monte ou positive si je descends), j'ai fait la liaison.
      En pratique je peux m'arrêter là : si je suis en train de monter c'est étape*2+1, si je suis en train de descendre c'est étape*2+2.
      Dans mon code j'additionne les valeurs absolues : la valeur que j'aurais d√Ľ mettre dans la case, et celle d√©j√† pr√©sente, et j'ai mon r√©sultat.

      Pour l'exercice 2, comme je fournis déjà une liste de case par itération, il suffit de mettre comme liste de démarrage tout les "a" et le "S", vraiment rien à coder, la dernière ligne du programme et basta.

      Ah, et j'ai aligné, je bosse sur un tableau à une dimension, au lieu d'une matrice.
      Et les mouvements possibles ne sont pas (haut, bas, gauche droite) mais (-1, +1, -largeur, +largeur) et un mouvement doit être dans [0, taille[

      Allez, trêve de blabla, code !

      heights = {
          v: (26 if k == 27 else k) or 1
          for k, v in enumerate("SabcdefghijklmnopqrstuvwxyzE")
      }
      input = [line for line in sys.stdin.read().strip().splitlines()]
      w, h = len(input[0]), len(input)
      size = w * h
      moves = [1, -1, w, -w]
      input = "".join(input)
      map = [heights[c] for c in input]
      start = input.index("S")
      end = input.index("E")
      
      
      def test(score, newpos, height, sign):
          """
          False : mouvement impossible
          True : mouvement possible vers case non visitée
          int : mouvement possible vers case visitée, retourne le score de cette case
          """
          if newpos < 0 or newpos >= size:
              return False
          if (sign > 0 and map[newpos] > height + 1)\
             or (sign < 0 and map[newpos] < height - 1):
              return False
          if score[newpos] is None:
              return True
          return score[newpos]
      
      
      def move(score, pos, sign=1):
          height = map[pos]
          visited = []
          solution = False
          for m in moves:
              newpos = pos + m
              t = test(score, newpos, height, sign)
              if not t:  # Movement not allowed
                  continue
              if t is True:  # New tile visited
                  score[newpos] = score[pos] + sign
                  visited.append(newpos)
                  continue
              if t * sign > 0:  # Already visited
                  continue
              # Visited from the other side : solution found !
              visited.append(newpos)
              solution = min(
                  solution or size,
                  1 + sign * score[pos] - sign * score[newpos]
              )
          return visited, solution
      
      
      def main(s1, s2):
          score = [
              0 if (pos in s1 or pos in s2) else None
              for pos in range(size)
          ]
          unfinished = True
          while unfinished:
              v1, v2 = [], []
              for pos in s1:
                  v, solution = move(score, pos, 1)
                  v1 += v
                  if solution:
                      print(score)
                      print(f"Path found in {solution} moves !")
                      unfinished = False
              for pos in s2:
                  v, solution = move(score, pos, -1)
                  v2 += v
                  if solution:
                      print(score)
                      print(f"Path found in {solution} moves !")
                      unfinished = False
              s1, s2 = v1, v2
      
      
      main([start], [end])
      main([pos for pos, height in enumerate(map) if height == 1], [end])
      • Yth.
      • [^] # Re: python et lib de graph

        Post√©¬†par¬† (Mastodon) . √Čvalu√©¬†√†¬†3.

        Pour faire du joli on fait ça :

        class display:
            def __init__(self, input, width, heights):
                self.heights = heights
                self.bgcolors = [[
                    min(255, max(232, heights[c] + 231))
                    for c in line] for line in input]
                self.background = "\n".join(
                    "".join(
                        f"{self.color(c)} "
                        for c in line
                    )
                    for line in self.bgcolors
                )
                self.bgcolors = sum(self.bgcolors, [])
                self.width = width
        
            def color(self, bg=None, fg=None, rgb=None):
                bg = f"\033[48;5;{bg}m" if bg else ""
                fg = f"\033[38;5;{fg}m" if fg else ""
                fg = f"\033[38;2;{rgb[0]};{rgb[1]};{rgb[2]}m" if rgb else fg
                return f"{bg}{fg}"
        
            def cursor(self, row=0, col=0):
                return f"\033[{row};{col}H"
        
            def __call__(self, *visited):
                print(self.cursor(), end='')
                print(self.background)
                for v in visited:
                    print(f"{self.cursor(*divmod(v, self.width))}{self.color(bg=self.bgcolors[v], fg=160)}o")
                time.sleep(.1)
        
        # On ajoute ces deux lignes juste avant la troisième :
        d = display(input, w, heights)
        d()
        input = "".join(input)
        
        # Et enfin en dernière ligne de main():
                d(*v1, *v2)
        
        # Et pour éviter d'avoir les résultats en tout moche au milieu :
        s1 = main([start], [end])
        s2 = main([pos for pos, height in enumerate(map) if height == 1], [end])
        print(d.cursor(row=h+1), end='')
        print("\033[0m", end='')
        print(f"Path found in {s1} moves !")
        print(f"Path found in {s2} moves !")

        Et il faut mettre le terminal en grand, parce que sinon ça va faire très très moche et buggé !
        On a une animation des cases en cours de visite, sur fond de montagne enneigée (dégradé noir en bas, et blanc en haut).

        • Yth.
    • [^] # Re: python et lib de graph

      Post√©¬†par¬† . √Čvalu√©¬†√†¬†3.

      image disparue : 

  • # Sans lib, avec visualisation et deuxi√®me partie non bourrine

    Post√©¬†par¬† (site web personnel) . √Čvalu√©¬†√†¬†2.

    J'ai beaucoup aimé l'exo du jour.

    Comme beaucoup (tout le monde), un petit algo de parcours de graph pour trouver le chemin le plus court.

    J'ai fait une premi√®re version "na√Įve" qui priorisait pas les chemin et donc avan√ßait par "inondation" (D'o√Ļ le nom de fonction flood_map). J'avais un "front" (le point de d√©part au d√©but) et √† chaque passe je calculais un nouveau front (les cases accessibles √† partir du front actuel). D√®s qu'on arrive √† l'arriv√©e, on sait combien il faut d'√©tapes.
    Ça marche très bien, et ça a l'avantage d'être la valeur exacte.

    Et je me suis amuser à faire du A*, et donc explorer une seule case du front (au lieu de toutes) et de choisir la case à privilégier en fonction d'un heuristique.
    C'est beaucoup plus efficace en terme de performance (nb de case étudiées) mais ça ne donne pas forcement le résultat le plus optimal selon l'heuristique utilisé. (Heureusement que j'avais la première version)

    Pour la partie deux, l'astuce c'est de partir de la fin et de s'arrêter dès qu'on trouve une case 'a'. Ça évite de faire du brute force à partant de toutes les cases a.

    Voici la version A* :
    (Vous pouvez le lancer avec votre input pour avoir une petite animation)

    #!/usr/bin/python3
    
    from enum import Enum
    from time import sleep
    from math import sqrt
    import sys
    
    def yield_input():
        import sys
        with open(sys.argv[1]) as f:
            for l in f:
                l = l.strip()
                yield l
    
    class Seen(Enum):
        NONE = 0
        CURRENT = 1
        SEEN = 2
    
    current_color = None
    
    def print_color(color, out):
        global current_color
        if current_color != color:
            current_color = color
            print(color, end="")
        print(out, end="")
    
    class Cell:
        def __init__(self, height, coord):
            self.height = height
            self.coord = coord
            self.seen = Seen.NONE
            self.path_length = 0
            self.previous = None
            self.is_on_the_way = False
    
        # Yield other if we can go there from self
        def yield_check_up(self, other, what=Seen.NONE):
            #print(f"{other.seen} {other.height} {self.height}")
            if other.seen == what and other.height <= self.height + 1:
                other.path_length = self.path_length+1
                other.seen = Seen.CURRENT
                yield other
    
        def yield_check_down(self, other, what=Seen.NONE):
            #print(f"{other.seen} {other.height} {self.height}")
            if other.seen == what and other.height >= self.height - 1:
                other.path_length = self.path_length+1
                other.seen = Seen.CURRENT
                yield other
    
        def print(self):
            global current_color
            if self.seen == Seen.NONE:
                color = "\033[40m"
            elif self.seen == Seen.CURRENT:
                color = "\033[46m"
            else:
                color = "\033[44m"
            if self.is_on_the_way:
                color = "\033[41m"
            char = chr(ord('a')+self.height)
            print_color(color, char)
    
    def move_up(coord):
        return coord[0]-1, coord[1]
    
    def move_down(coord):
        return coord[0]+1, coord[1]
    
    def move_left(coord):
        return coord[0], coord[1]-1
    
    def move_right(coord):
        return coord[0], coord[1]+1
    
    
    class Map:
        def __init__(self):
            self.map = []
            for i, line in enumerate(yield_input()):
                map_line = []
                for j, h in enumerate(line):
                    if h == "S":
                        self.start = (i, j)
                        height = 0
                    elif h == "E":
                        self.end = (i, j)
                        height = 25
                    else:
                        height = ord(h) - ord('a')
                    map_line.append(Cell(height, (i,j)))
                self.map.append(map_line)
                self.nb_lines = len(self.map)
                self.nb_columns = len(self.map[0])
            print(self.nb_lines, self.nb_columns)
    
        def get(self, coord):
            return self.map[coord[0]][coord[1]]
    
        def clear(self):
            for line in self.map:
                for cell in line:
                    cell.seen = Seen.NONE
                    cell.path_length = 0
                    cell.previous = None
                    cell.is_on_the_way = False
    
        # Direction is up or down
        def see_arround(self, cell, direction, what=Seen.NONE):
            attr = f"yield_check_{direction}"
            coord = cell.coord
            if coord[0]> 0:
                yield from getattr(cell, attr)(self.get(move_up(coord)), what)
            if coord[0] < self.nb_lines-1:
                yield from getattr(cell, attr)(self.get(move_down(coord)), what)
            if coord[1] > 0:
                yield from getattr(cell, attr)(self.get(move_left(coord)), what)
            if coord[1] < self.nb_columns-1:
                yield from getattr(cell, attr)(self.get(move_right(coord)), what)
    
        def flood_map(self, start, scoring, check, direction):
            to_see = [self.get(start)]
            round = 0
            while True:
                cell, to_see = to_see[0], to_see[1:]
                if check(cell):
                    return cell, round
                cell.seen = Seen.SEEN
                for next_cell in list(self.see_arround(cell, direction)):
                    next_cell.previous = cell
                    to_see.append(next_cell)
                to_see.sort(key=scoring)
                round += 1
                self.print(round)
    
        def find_a_way_to_summit(self):
            # Scoring is important.
            # A* found quickly A solution, but it may not the best one.
    
            # This scoring is fast but not exact:
            # Result:422, round:1460
            scoring = lambda c: c.path_length + abs(c.coord[0]-self.end[0])**2 + abs(c.coord[1]-self.end[1])**2
    
            # This scoring give more importance to path_length and give the good result
            # Result:412, round:3722
    #        scoring = lambda c: c.path_length + sqrt(abs(c.coord[0]-self.end[0])**2 + abs(c.coord[1]-self.end[1])**2)
            return self.flood_map(self.start, scoring, lambda cell: cell.coord == self.end, "up")
    
        def find_path(self, end):
            current = end
            while current:
                #0print(current.coord)
                current.is_on_the_way = True
                current = current.previous
                self.print(5)
    
        def find_shorter_path_to_summit(self):
            # This scoring is fast but not exact:
            #Result:410, round: 2276
            scoring = lambda c: c.height
    
            # This scoring give more importance to path_length and give the good result
            # Result:402, round:2400
    #        scoring = lambda c: c.path_length + c.height
            return self.flood_map(self.end, scoring, lambda cell: cell.height == 0, "down")
    
        def print(self, round):
            global current_color
            # clear the terminal
            print("\033c", end="")
            current_color = None
            print(round)
            for line in self.map:
                for cell in line:
                    cell.print()
                print()
            sleep(0.005)
    
    
    
    def round1(map):
        cell, nb_round = map.find_a_way_to_summit()
        map.find_path(cell)
        map.print(cell.path_length)
        return cell.path_length, nb_round
    
    def round2(map):
        cell, nb_round = map.find_shorter_path_to_summit()
        map.find_path(cell)
        map.print(cell.path_length)
        return cell.path_length, nb_round
    
    
    def main():
        map = Map()
        result_1 = round1(map)
        map.clear()
        result_2 = round2(map)
        print("Round 1 :", result_1)
        print("Round 2 :", result_2)
        print(map.nb_lines, map.nb_columns)
    
    
    if __name__ == "__main__":
        main()

    Matthieu Gautier|irc:starmad

  • # √Čtoile

    Post√©¬†par¬† (site web personnel) . √Čvalu√©¬†√†¬†4.

    Au fait, vu les visualisations, vous avez √©videmment remarqu√© que loin d'√™tre une gorge de rivi√®re, nous avions plut√īt affaire √† l'√ģle de Numenor une montagne en forme d'√©toile, n'est-ce pas¬†?

    • [^] # Re: √Čtoile

      Post√©¬†par¬† (Mastodon) . √Čvalu√©¬†√†¬†3.

      Jour 12, la Montagne

      Le rendu de mon paysage, en doublant la largeur pour faire moins écrasé.

      Complètement Numénor oui.

      • Yth.
  • # vizu

    Post√©¬†par¬† . √Čvalu√©¬†√†¬†5.

    après la version ascii, la version png, voici la version 3D. ma préférée.

    • [^] # Re: vizu

      Post√©¬†par¬† (Mastodon) . √Čvalu√©¬†√†¬†2.

      J'aime beaucoup :)
      Bravo !

      • Yth.
  • # En retard

    Post√©¬†par¬† . √Čvalu√©¬†√†¬†2.

    J'ai commencé avec beaucoup de retard donc je poste ma solution en retard. Comme je voulais être certains d'avoir le chemin optimal, j'ai fais un parcourt complet.

    Je stocke la carte sous la forme d'une seule chaine de caract√®res et je met √† jour une table position -> distance pour y parvenir, √† chaque it√©ration je repars de toute les nouvelles distances parcourues. C'est tr√®s na√Įf mais tr√®s flexible. Si certains chemin commencent √† avoir des co√Ľts diff√©rents c'est facile √† prendre en compte.

    Je me suis fais avoir du fait que dans l'entrée on a une case S et une case E qui sont pas des altitudes.

    En groovy sans dépendances (que je maitrise pas très bien) ça donne ça :

    Scanner sc = new Scanner(new File('input'))
    
    def width = 0
    String land = ''
    while (sc.hasNextLine()) {
        def line = sc.nextLine()
        width = line.size()
        land += line + '\n'
    }
    
    def target = land.indexOf('E')
    
    land = land.replace('S', 'a').replace('E', 'z')
    
    def pathSize = Integer.MAX_VALUE
    def start = land.indexOf('a', 0)
    while (start >= 0 && start < land.size()) {
        pathSize = Math.min(pathSize, path(start, target, land, width))
        start = land.indexOf('a', start + 1)
    }
    
    println pathSize
    
    def path(int start, int target, String land, int width) {
        Map<Integer, Integer> positions = [(start): 0]
        def updatedPos = [start] as Set
    
        while (!updatedPos.isEmpty()) {
            def posSet = new ArrayList<>(updatedPos)
            updatedPos.clear()
            for (int pos in posSet) {
                int nextStep = positions[pos] + 1
                for (n in next(pos, width, land)) {
                    def old = positions.get(n, Integer.MAX_VALUE)
                    positions[n] = Math.min(old, nextStep)
                    if (old != positions[n]) {
                        updatedPos.add(n)
                    }
                }
            }
        }
    
        return positions.get(target, Integer.MAX_VALUE)
    }
    
    def next(int pos, int width, String land) {
        return [pos - 1, pos + 1, pos - width - 1, pos + width + 1].stream()
                .filter { it >= 0 && it < land.size() }
                .filter { land.charAt(it) <= land.charAt(pos) + 1 && land.charAt(it) >= ('a' as Character) }
                .toList()
    }

    https://linuxfr.org/users/barmic/journaux/y-en-a-marre-de-ce-gros-troll

Suivre le flux des commentaires

Note : les commentaires appartiennent à celles et ceux qui les ont postés. Nous n’en sommes pas responsables.