Forum Programmation.autre Advent of Code 2023, day 8

• # Encore des maths, du Python et de la POO

  Posté par alberic89 🐧 le 08 décembre 2023 à 21:02. Évalué à 1.

  

  Ma solution aurait pu être mieux optimisée pour la lisibilité et la redondance, mais elle fonctionne. Je définis une classe pour les nœuds, surcharge quelques opérateurs, prétraite quelques données, et trouve le ppcm en utilisant le module math de Python.

  #!/bin/python3
  
  from math import lcm
  
  class Nodon:
      def __init__(self,name,left,right):
          self.name = name
          self.right = right
          self.left = left
  
      def __repr__(self):
          return self.name
  
      def __eq__(self,stringnode):
          if self.name == stringnode:
              return True
          return False
  
      def endswith(self,letter):
          if self.name[2] == letter:
              return True
          return False
  
      def go(self,direction):
          if direction == "R":
              return self.right
          if direction == "L":
              return self.left
          raise ValueError
  
  
  def parse_node(puzzle):
      direction = puzzle[0]
      nodes = []
      for line in puzzle[1:]:
          if line == "":
              continue
          nodes.append(Nodon(line[:3],line[7:10],line[12:15]))
      return direction, nodes
  
  def run(direction, nodes):
      now = nodes[nodes.index("AAA")]
      nb = 0
      while now != "ZZZ":
          for d in direction:
              now = now.go(d)
              nb += 1
              if now == "ZZZ":
                  break
      return nb
  
  def nodesendswith(nodes, l):
      for n in nodes:
          if n.endswith(l) == False:
              return False
      return True
  
  def beforerun(nodes):
      for n in nodes:
          n.right = nodes[nodes.index(n.right)]
          n.left = nodes[nodes.index(n.left)]
      return nodes
  
  def runboth(direction, nodes):
      now = []
      for n in nodes:
          if n.endswith("A"):
              now.append(n)
      nb = 0
      ends = []
      while len(now) != 0:
          for d in direction:
              nb += 1
              for i in range(len(now)):
                  now[i] = now[i].go(d)
                  if now[i].endswith("Z"):
                      ends.append(nb)
                      now[i] = None
              for i in range(now.count(None)):
                  now.remove(None)
              if len(now) == 0:
                  break
      return lcm(*ends)
  
  def solve1(puzzle,testing=False):
      s=0
      d, nodes = parse_node(puzzle)
      s = run(d, tuple(beforerun(nodes)))
      if testing:
          print(s)
      return s
  
  def solve2(puzzle,testing=False):
      s = 0
      d, nodes = parse_node(puzzle)
      s = runboth(d, tuple(beforerun(nodes)))
      if testing:
          print(s)
      return s
  
  test1 = """RL
  
  AAA = (BBB, CCC)
  BBB = (DDD, EEE)
  CCC = (ZZZ, GGG)
  DDD = (DDD, DDD)
  EEE = (EEE, EEE)
  GGG = (GGG, GGG)
  ZZZ = (ZZZ, ZZZ)
  """
  result1 = 2
  test2 = """LR
  
  11A = (11B, XXX)
  11B = (XXX, 11Z)
  11Z = (11B, XXX)
  22A = (22B, XXX)
  22B = (22C, 22C)
  22C = (22Z, 22Z)
  22Z = (22B, 22B)
  XXX = (XXX, XXX)
  """
  result2 = 6
  
  # for cli invocation
  
  def solve(short=False,one=True,two=True):
  
      s1, s2 = False , False
  
      if one:
          print("----Part 1----")
          if short == False:
              if solve1(test1.split("\n"),testing=True) != result1:
                  print("Not working.")
                  return False
              else :
                  print("Maybe working?")
          with open("input.txt",'r') as file:
              lines = file.read().split("\n")
              s1 = solve1(lines)
              print(s1)
  
      if two:
          print("----Part 2----")
          if short == False:
              if solve2(test2.split("\n"),testing=True) != result2:
                  print("Not working.")
                  return False
              else :
                  print("Maybe working?")
          with open("input.txt",'r') as file:
              lines = file.read().split("\n")
              s2 = solve2(lines)
              print(s2)
  
      return s1, s2
  
  if __name__ == "__main__":
  
      from sys import argv
  
      s = False
      one = True
      two = True
  
      if len(argv) >= 2:
  
          if "-s" in argv or "--summary" in argv or "--short" in argv:
              s = True
          if "1" in argv:
              two = False
              one = True
          elif "2" in argv:
              one = False
              two = True
          if "2" in argv:
              two = True
  
      solve(short=s,one=one,two=two)

  L'informatique n'est pas une science exacte, on n'est jamais à l'abri d'un succès

• # sans PPCM, t'est cuit

  Posté par steph1978 le 09 décembre 2023 à 09:19. Évalué à 1.

  

  J'ai bien brûlé du CPU avant de comprendre qu'il fallait pas tout faire tourner en même temps mais juste calculer le nombre d'étapes de chaque fantôme puis de prendre leur PPCM.

  En 20 lignes de python:

  import sys
  from itertools import cycle
  from math import lcm
  
  I, _, *P = [l for l in sys.stdin.read().splitlines()]
  # BCN = (HFN, KFC)
  # 0123456789012345678
  P = {l[0:3]:(l[7:10],l[12:15]) for l in P}
  
  G = [p for p in P.keys() if p[2] == 'A']
  R = []
  for g in G:
      C = g
      N = 0
      for i in cycle(I):
          if C[2] == 'Z':
              break
          C = P[C][i == 'R']
          N += 1
      R.append(N)
  print(lcm(*R))

  • [^] # Re: sans PPCM, t'est cuit

    Posté par Yth (Mastodon) le 10 décembre 2023 à 14:41. Évalué à 2.

    

    Mon algo final est un peu bâtard, parce qu'il part sur un truc plus générique selon les données de l'énoncé et s'arrête un peu sèchement grâce à ce qu'on « découvre » dans les données :

    Au passage j'ai découvert itertools.cycle, très pratique, au début j'avais réimplémenté la me^me chose avec un générateur.

    import sys
    import re
    import math
    from dataclasses import dataclass
    from itertools import cycle
    
    program, _, *data = sys.stdin.read()).strip().splitlines()
    program = [int(x == "R") for x in program]
    
    @dataclass
    class Node:
      name: str
      left: str = None
      right: str = None
      start: bool = False
      end: bool = False
      def __bool__(self):
        return self.end
      def __getitem__(self, key):
        return self.right if key else self.left
    
    places = {x[0]: Node(*x) for line in data for x in [re.findall("[A-Z]{3}", line)] if x}
    for place in places.values():
      place.left = places[place.left]
      place.right = places[place.right]
      place.start = place.name[2] == "A"
      place.end = place.name[2] == "Z"
    
    def run(position, prog):
      _endpos = None
      _endtime = 0
      _nb = 0
      for direction in cycle(prog):
        position = position[direction]
        _nb += 1
        if position:
          if _endpos:
            break
          _endpos = position.name
          _endtime = _nb
      return _endpos, _endtime, _nb
    
    # Exercice 1
    endpos, ex1, loop = run(places["AAA"], program)
    
    # Exercice 2
    loops = []
    for place in places.values():
      if place.start:
        endpos, loopstart, loopend = run(place, program)
        loop = loopend - loopstart
        loops.append(loop)
        print(f"From {place.name} to {endpos}, loop={loopstart}+{loop}={loopend}")
    
    ex2 = math.lcm(*loops)

    Les affichages de la boucle de l'exercice 2 donnent chez moi :

    From VNA to KTZ, loop=15871+15871=31742
    From AAA to ZZZ, loop=21251+21251=42502
    From DPA to GGZ, loop=16409+16409=32818
    From JPA to MCZ, loop=11567+11567=23134
    From DBA to TPZ, loop=18023+18023=36046
    From QJA to FTZ, loop=14257+14257=28514
    

    On voit très clairement les deux cycles de même longueur, dès le début.
    C'est à partir de cet affichage là qu'on saute la résolution générique pour se contenter de calculer le PPCM et finir le problème.

    • Yth.

Suivre le flux des commentaires

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