Forum Programmation.autre Advent of Code, jour 13

• # Pas bien compliqué… en reformulant

  Posté par 🚲 Tanguy Ortolo (site web personnel) le 13 décembre 2023 à 10:44. Évalué à 3.

  

  La première partie ne pose aucune difficulté particulière. Pour la seconde, l'énoncé suggère presque une implémentation directe : essayer de changer les points, un par un, et chercher à chaque fois si on trouve une réflexion. Inutile de dire que ça risque de prendre un peu trop de temps.

  En reformulant le problème, on peut trouver une solution plus intelligente : on ne cherche plus une réflexion parfaite mais une réflexion avec exactement une erreur. Voilà, vous avez l'algorithme, je vous laisse. :-)

  • [^] # Re: Pas bien compliqué… en reformulant

    Posté par Yth (Mastodon) le 13 décembre 2023 à 11:29. Évalué à 2.

    

    Je me suis pris la tête à cause d'une erreur de raisonnement et du fait que je n'ai rien modélisé.
    J'avais un algo qui détectait de très bons candidats à la presque-symétrie, en fait j'avais 103 candidats sur 100.
    Et pour ces 3 là je dois fouiller un peu plus loin pour valider la presque symétrie, et là, si j'avais fait une classe Pattern avec les données dedans, je serais allé bien plus vite.

    En fait, sur le principe (mais pas tellement sur la résolution dans mon cas, j'ai été lent), on voit tout de suite un truc dans les données, et ça suggère des idées.

    Bref, si j'avais pris le temps de faire quelque chose de propre, je serais allé plus vite :)

    • Yth.

  • [^] # Re: Pas bien compliqué… en reformulant

    Posté par mac le 13 décembre 2023 à 11:42. Évalué à 1.

    

    La solution en flippant les points un par un ne prend pas tellement de temps que ça, les tableaux à manipuler sont de taille assez modeste…

    Je m'en sors à moins de 2 secondes en Python chez moi.

  • [^] # Re: Pas bien compliqué… en reformulant

    Posté par 🚲 Tanguy Ortolo (site web personnel) le 13 décembre 2023 à 11:57. Évalué à 3.

    

    Allez, voici le code :

    from collections.abc import Iterable
    from typing import Optional, Self
    
    from enum import Enum
    import io
    
    import aoc
    
    
    Coords = tuple[int, int]
    
    
    class Terrain(Enum):
        ASH = '.'
        ROCK = '#'
    
        def __str__(self) -> str:
            if self is self.ASH:
                return ' '
            if self is self.ROCK:
                return '▒'
            raise ValueError('invalid terrain value')
    
    
    class Pattern:
        def __init__(self, array: Iterable[Iterable[Terrain]]):
            self.matrix = list(list(line) for line in array)
            self.ly = len(self.matrix)
            self.lx = len(self.matrix[0])
    
        @classmethod
        def import_lines(cls, lines: Iterable[str]) -> Self:
            return cls((Terrain(char) for char in line.rstrip()) for line in lines)
    
        def __getitem__(self, coords: Coords) -> Terrain:
            y, x = coords
            return self.matrix[y][x]
    
        def __str__(self) -> str:
            s = io.StringIO()
            for line in self.matrix:
                for terrain in line:
                    s.write(str(terrain))
                s.write('\n')
            return s.getvalue()
    
        def y_reflection_errors(self, y: int) -> int:
            """Count the number of errors in a horizontal reflection between y - 1
            and y. Return 0, 1 or 2 (meaning many)."""
            errors = 0
            for i in range(min(y, self.ly - y)):
                y1 = y - 1 - i
                y2 = y + i
                for x in range(self.lx):
                    errors += self[y1, x] != self[y2, x]
                    if errors >= 2:
                        return errors
            return errors
    
        def x_reflection_errors(self, x: int) -> int:
            """Count the number of errors in a vertical reflection between x - 1
            and x. Return 0, 1 or 2 (meaning many)."""
            errors = 0
            for i in range(min(x, self.lx - x)):
                x1 = x - 1 - i
                x2 = x + i
                for y in range(self.ly):
                    errors += self[y, x1] != self[y, x2]
                    if errors >= 2:
                        return errors
            return errors
    
        def y_reflection1(self) -> Optional[int]:
            for y in range(1, self.ly):
                if self.y_reflection_errors(y) == 0:
                    return y
            return None
    
        def x_reflection1(self) -> Optional[int]:
            for x in range(1, self.lx):
                if self.x_reflection_errors(x) == 0:
                    return x
            return None
    
        def y_reflection2(self) -> Optional[int]:
            for y in range(1, self.ly):
                if self.y_reflection_errors(y) == 1:
                    return y
            return None
    
        def x_reflection2(self) -> Optional[int]:
            for x in range(1, self.lx):
                if self.x_reflection_errors(x) == 1:
                    return x
            return None
    
    
    def part1(lines: aoc.Data) -> int:
        """Solve puzzle part 1: determine the sum of perfect reflection columns and
        100× that of perfect reflection lines."""
        total = 0
        for i, group in enumerate(aoc.group_lines(lines)):
            pattern = Pattern.import_lines(group)
            if (x := pattern.x_reflection1()) is not None:
                total += x
            elif (y := pattern.y_reflection1()) is not None:
                total += 100 * y
            else:
                raise ValueError('pattern without reflection‽')
        return total
    
    
    def part2(lines: aoc.Data) -> int:
        """Solve puzzle part 1: determine the sum of imperfect reflection columns
        and 100× that of imperfect reflection lines."""
        total = 0
        for i, group in enumerate(aoc.group_lines(lines)):
            pattern = Pattern.import_lines(group)
            if (x := pattern.x_reflection2()) is not None:
                total += x
            elif (y := pattern.y_reflection2()) is not None:
                total += 100 * y
            else:
                raise ValueError('pattern without reflection‽')
        return total

  • [^] # Re: Pas bien compliqué… en reformulant

    Posté par vicnet le 14 décembre 2023 à 13:15. Évalué à 1.

    

    Salut,

    Oui, il suffit de s'arrêter à la première solution qui donne une valeur différente!

    J'avoue que cet advent m'a demander du temps car j'ai eu du mal à comprendre l'énoncé de la 1re partie et encore plus de la 2e…
    Est-ce qu'on fait une symétrie en supprimant les colonnes que à gauche ou les 2. Bref, en relisant j'ai compris qu'on souhaitait une symétrie avec des lignes/colonnes imaginaires !

    Et pour le 2e, mon algo ne voyait pas toutes les symétries d'un même pb, il ne prenait que la 1er qui était généralement celle calculée au 1er coup !
    J'ai eu du mal à trouver pourquoi je n'avais pas bonne valeur au final.

• # Solution en Haskell

  Posté par Guillaume.B le 13 décembre 2023 à 12:05. Évalué à 2.

  

  Voici ma solution en Haskell.
  Pas vraiment de difficulté, j'ai factorisé le code pour résoudre les deux parties de la même manière.
  Pour les connaisseurs d'Haskell, le test isSymetry est lazy et s'arrête dès qu'il a détecté au moins une différence pour la partie 1 et deux différences pour la partie 2.
  700 microsecondes pour chacune des parties.

  module AOC2023.Day13 (solve) where
  import           AOC.Prelude
  import           AOC (aoc)
  import qualified Data.Vector as V
  import           Data.Vector ((!))
  import           AOC.Parser (Parser, sepEndBy1, some, eol)
  
  data Tile = Ash | Rock deriving (Eq)
  type Grid = [[Tile]]
  
  parser :: Parser [Grid]
  parser = (some tile `sepEndBy1` eol) `sepEndBy1` eol where
      tile = Ash <$ "." <|> Rock <$ "#"
  
  isSymetry :: ([Bool] -> Bool) -> Vector [Tile] -> Int -> Bool
  isSymetry check v x = check difference where
      difference = filter id $ zipWith (/=) list1 list2
      list1 = concatMap (v!) range
      list2 = concatMap (\i -> v ! (2 * x - i - 1)) range
      n = V.length v
      range = if 2 * x < n then [0..x-1] else [x..n-1]
  
  solveFor :: ([Bool] -> Bool) -> [Grid] -> Int
  solveFor check = sum . map score where
      score grid = (100*) <$> symetry grid <|> symetry (transpose grid) ?: 0  
      symetry grid = find (isSymetry check vgrid) [1..n-1] where
          vgrid = V.fromList grid
          n = V.length vgrid
  
  isSingleton :: [a] -> Bool
  isSingleton [_] = True
  isSingleton _ = False
  
  solve :: Text -> IO ()
  solve = aoc parser (solveFor null) (solveFor isSingleton)

• # En binaire et en puissances de 2

  Posté par Yth (Mastodon) le 13 décembre 2023 à 16:08. Évalué à 2.

  

  Je vois deux types de caractères, je pense binaire.
  Transformer les lignes en nombre, ça permet des comparaisons d'entiers plutôt que de chaînes : ça me plaît.

  Alors voilà une partie 1 assez rapide, faut surtout (surtout) bien mesurer ses indices de listes, ses ranges, etc.

  D'abord les données, on va retourner une liste de nombres horizontaux et la même chose en vertical, les . sont des 0 et les # des 1.

  def patterns():
    _h, _v = [], []
    for line in stdin.read().strip().splitlines() + [""]:
      if line:
        line = line.translate(str.maketrans(".#", "01"))
        _h.append(int(line, 2))
        _v.append(list(line))
        continue
      _v = [int("".join(col), 2) for col in zip(*_v)]
      yield _h, _v
      _h, _v = [], []
  
  data = list(patterns())

  Ensuite j'ai deux fonctions de calcul de symétries, différentes pour les deux exercices, ça se factorisait assez mal chez moi.

  def symetry(search):
    for axe in range(len(search) - 1, 0, -1):
      size = min(axe, len(search) - axe)
      for a, b in zip(search[axe - size:axe], search[axe + size - 1:axe - 1:-1]):
        if a != b:
          break
      else:
        yield axe
  
  ex1 = sum(
    sum(list(symetry(h))) * 100 + sum(list(symetry(v)))
    for h, v in data
  )

  L'exercice 2 est un peu plus complexe, puisque je n'ai plus vraiment accès aux données d'origine, je n'ai plus que mes nombres :

  POWEROF2 = {2**i for i in range(20)}
  def almost_symetry(search):
    for axe in range(len(search) - 1, 0, -1):
      size = min(axe, len(search) - axe)
      diffs = [
        (a, b)
        for a, b in zip(search[axe - size:axe], search[axe + size - 1:axe - 1:-1])
        if a != b
      ]
      # looking for exactly one different line
      if len(diffs) != 1:
        continue
      # And one difference between the two lines
      a, b = diffs[0]
      diff = abs(a - b) * 2
      if diff in POWEROF2 and (a & diff) == (b & diff):
        yield axe
  
  ex2 = sum(
    sum(list(almost_symetry(h))) * 100 + sum(list(almost_symetry(v)))
    for h, v in data
  )

  La réflexion est simple : si deux lignes diffèrent d'un seul élément, alors leur représentation binaire diffère d'un seul bit, donc leur différence est une puissance de 2. Les puzzles ne dépassent pas 17x17, donc avec mon ensemble qui va jusque 2²⁰ je suis suffisamment large.

  Par contre c'est une condition nécessaire, mais pas suffisante. Presque, en tout cas avec les données de test on ne trouve pas l'erreur.
  Ben oui, si deux lignes diffèrent sur deux cases côte à côte, une à 1 d'un côté et l'autre de l'autre, la différence fait 2ⁿ⁺¹ - 2ⁿ = 2^n, qui est puissance de 2.
  En regardant bien, pour une différence de 2ⁿ on a forcément le bit n différent, mais si le bit n+1 est identique alors les deux nombres sont identiques (sinon on peut même en avoir plein : 32-16-8=8 !).

  Bref, encore une fois je veux faire vite, je teste une idée sans même la valider dans ma tête, c'est faux et je me demande pourquoi.

  Mais voilà, finalement on a un truc assez simple, trivialement rapide (0,3s on tombe jamais vraiment en dessous de ça en démarrant un interpréteur python), donc pas trop chercher à optimiser, on ne saurait pas vraiment si on y gagne ou pas.

  Par contre côté lisibilité c'est mort, il faut réfléchir à tout ce que ces indices, ces parcours à l'envers ou pas, etc, signifient vraiment, pour comprendre quoi que ce soit.

  • Yth.

  • [^] # Re: En binaire et en puissances de 2

    Posté par barmic 🦦 le 18 décembre 2023 à 09:16. Évalué à 2.

    

    Tu t'es pris la tête je trouve pour la comparaison en binaire.

    J'ai fais un xor et j'ai vérifié s'il donnait une puissance de 2

    let c = a_data ^ b_data;
    return (c & (c - 1)) == 0;

    Il y a 2 subtilités :

    • le test répond oui pour 0
    • on accepte qu'une seule différence sur la map

    Du coup j'ai une condition

    if c == 0 {
        return 0;
    } else if (c & (c - 1)) == 0 {
        return 1;
    } else {
        return 2;
    }

    La spécifictité de ce code fais que ma partie 1 et ma partie 2 sont assez distinct, mais je suis à ~500µs.

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

    • [^] # Re: En binaire et en puissances de 2

      Posté par Yth (Mastodon) le 22 décembre 2023 à 22:48. Évalué à 2.

      

      Pertinent, je n'ai pas révisé mon opération logiques depuis un moment, je n'ai plus les réflexes…

      Je vais me rafraîchir ça.

      • Yth.

Suivre le flux des commentaires

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