• # 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.