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.