Forum Programmation.autre Advent of Code 2023, jour 20

• # Les données imposent la méthode

  Posté par Yth (Mastodon) le 20 décembre 2023 à 15:37. Évalué à 3.

  Ici aussi, l'énoncé ne suffit pas à résoudre le problème, les données imposent la méthode.

  Il faut constater qu'à l'instar de l'exemple 2 avec output, le rx de sortie n'existe pas dans les données en entrée, et qu'il est uniquement relié à une boîte à conjonction, l'équivalent du inv du second exemple.
  rx recevra un low pulse ssi inv reçoit des high pulses de partout à la fois.

  Et là on lance des simulations (ou on analyse les données en entrée ?), pour voir quand notre inv reçoit des high pulses, on va constater en environ 13000 itérations qu'on a vu passer 3 high pulses de chacun des 4 sources, et que chacun de ces évènement cycle.

  Chez moi :

  • 3797 HP depuis la 1ère entrée ;
  • 3847 HP depuis la 3è entrée ;
  • 3877 HP depuis la 4è entrée ;
  • 4051 HP depuis la 2è entrée.

  Et ça cycle, donc 1ère entrée en 3797, 7594, 11391, 2è entrée en 4051, 8102, 12153, 3è entrée en 3847, 7694, 11541, 4è entrée en 3877, 7754, 11631.
  4 cycles, et qui commencent tous à 0 en plus, heureux hasard, n'est-ce pas ?

  En analysant les données on doit réaliser qu'on a 4 parcours indépendants, depuis chacune des 4 entrées de notre broadcaster, qui mènent chacun à une entrée de notre boîte inv, donc les cycles sont bien indépendants.
  Par contre, deviner qu'ils commencent à zéro ne me semble pas si évident, même si tout les FlipFlop commencent à off, et les Conjoncteurs à low partout, pourquoi une fois un low reçu à l'arrivée est-ce qu'on retomberait sur l'état initial ?

  Bon, bah le résultat c'est de multiplier les longueurs de cycles entre eux.
  - Parce qu'on a des cycles indépendants.
  - Et qu'ils commencent tous à zéro.

  Le résultat est dans les 256 billions (proche de 4000⁴ ), donc on lance pas la force brute, quelle que soit la qualité de notre modélisation.

  Côté code j'ai pas lourd à montrer, peut-être ma modélisation pour le 1, mignonne, que j'ai un peu pensée en amont pour pouvoir détecter des cycles, donc avec des frozen dataclass. Ça tourne pas trop mal avec 1 millions de cycles en 15 secondes et une RAM constante à 80Mo (c'est PyPy, ya un overhead de RAM de 70Mo, c'est comme ça).
  Le problème réel (4051 cycles) prend moins d'une seconde en CPython, avec 10Mo de RAM.
  L'état des Conjunctions est un binaire avec les bits à 0 ou 1 selon le dernier pulse reçu de chaque entrée, donc les entrées sont ordonnées. Et bien sûr, partout, low c'est 1 ou True, et high c'est 0 ou False, ça simplifie de le prendre comme ça !
  L'état est dans boxes qui ne contient que des frozen dataclasses, donc en pratique quand une boîte change d'état, elle retourne une nouvelle boîte dans le nouvel état, je ne modifie jamais une boîte, ce n'est pas possible, j'en crée des nouvelles selon la situation.
  Cette façon de faire permettrait de comparer deux états global du système.
  On n'a pas à faire ça, donc probablement qu'il vaudrait mieux coder des boîtes dynamiques à états.
  de toute façon le code final est un mélange de trucs fixes et de trucs qui bougent magiquement avec des variables globales, on a vu plus propre (je pense aux statistiques pour le premier problème)...

  data = stdin.read().strip().splitlines()
  FINAL = "ns" # manuellement extrait de mes données
  from dataclasses import dataclass
  from collections import deque
  from functools import cached_property
  messages = deque()
  stats = [0, 0]
  # Modules
  class Module:
   def send(self, src, low): # low if True, high if False
   for dst in self.destination:
   stats[not low] += 1
   messages.append((src, dst, low))
  @dataclass(frozen=True)
  class Broadcaster(Module):
   destination: tuple = tuple()
   def __call__(self, src, name, low):
   self.send(name, low)
   return self
  @dataclass(frozen=True)
  class FlipFlop(Module):
   on: bool = False
   destination: tuple = tuple()
   def __call__(self, src, name, low):
   if not low:
   return self
   self.send(name, self.on) # High if off, low if on
   return FlipFlop(not self.on, self.destination)
  @dataclass(frozen=True)
  class Conjunction(Module):
   src: tuple = tuple()
   destination: tuple = tuple()
   state: int = 0
   def addsrc(self, *src):
   return Conjunction(self.src + src, self.destination, self.state + 2**len(self.src))
   @cached_property
   def full(self):
   return 2 ** len(self.src) - 1 # low pulse for each
   def __call__(self, src, name, low):
   state = self.full if self.state == -1 else self.state
   bit = 2 ** self.src.index(src)
   if low:
   state |= bit
   else:
   state &= self.full - bit
   self.send(name, state == 0)
   return Conjunction(self.src, self.destination, state)
  # data modelisation
  boxes = {}
  conjunctions = set()
  for line in data:
   name, _, *dst = line.replace(",", "").split()
   if name[0] == "b":
   boxes[name] = Broadcaster(tuple(dst))
   elif name[0] == "%":
   boxes[name[1:]] = FlipFlop(False, tuple(dst))
   else:
   boxes[name[1:]] = Conjunction(destination=tuple(dst))
   conjunctions.add(name[1:]) # storing all conjunction names
  # Updating src for conjunctions
  for name, box in boxes.items():
   i = set(box.destination).intersection(conjunctions)
   if i:
   for c in i:
   boxes[c] = boxes[c].addsrc(name)
  # Red Button, DO NOT PUSH !
  button = Broadcaster(("broadcaster",))
  def push():
   button.send("button", True)
   cstate = 0
   while messages:
   src, dst, low = messages.popleft()
   if dst in boxes:
   boxes[dst] = boxes[dst](src, dst, low)
   if dst == FINAL and not low:
   cstate = boxes[FINAL].state
   return cstate
  # Cycling...
  cycles = {}
  for _ in range(5000**4):
   if _ == 1000:
   stats1000 = tuple(stats)
   state = push()
   if state and state not in cycles:
   cycles[state] = _ + 1
   if len(cycles) == len(boxes[FINAL].src):
   break
  # Results
  def mul(i):
   return reduce(lambda x, y: x * y, i)
  ex1 = mul(stats1000)
  ex2 = mul(cycles.values())

  Le coût fixe de PyPy le rend inutile sur le problème réel, je monte de 0,55s à 0,65s, par contre si je cycle 1 million de fois, ça passe de 2min10 à 15s.
  Ça doit être pour ça que je n'ai pas trouvé PyPy si pertinent cette année : l'an dernier je devais être un gros bourrin, cette année je suis tout en finesse (......).

  Bon, c'était mignon, mais toujours un poil agaçant quand l'énoncé ne suffit pas à avoir la résolution, et qu'il faut compter sur des particularités des données.
  Mais bon, si on nous expliquait dès le début qu'il y avait 4 cycles et qu'il fallait les coordonner, l'exercice serait assez trivial...

  • Yth.

  • [^] # Re: Les données imposent la méthode

    Posté par Yth (Mastodon) le 20 décembre 2023 à 15:51. Évalué à 2.

    Ah oui, le deque() permet de faire une FIFO de messages, on les empile à droite, on les dépile à gauche, on a fini quand c'est vide, d'où un code d'itération assez simple dans la fonction push().

    C'était la minute structure de données pas encore vue cette année. Le deque() c'est une list() optimisée pour faire des ajouts/suppressions aux bouts, donc idéal pour des FIFO, LIFO et trucs du genre.

    • Yth.

    • [^] # Re: Les données imposent la méthode

      Posté par Guillaume.B le 20 décembre 2023 à 18:04. Évalué à 1.

      En Haskell, on la structure Seq. C'est des structures immuables permettant d'ajouter ou d'enlever un élément en début ou fin en temps constant. Quand je dis enlever ou ajouter, je veux dire créer une nouvelle séquence en se basant sur l'existante mais sans la modifier.
      Sous le capot, c'est basé sur les finger trees.

      https://en.wikipedia.org/wiki/Finger_tree

• # Solution en Haskell

  Posté par Guillaume.B le 20 décembre 2023 à 15:39. Évalué à 2.

  Je peux dire que j'ai galéré sur celui là. Tout ça parce que j'ai mal lu l'énoncé.
  Je n'avais pas vu qu'il fallait traiter les gestions de pulsations sous forme de file.
  Je les traitais sous forme de pile et bizarrement ça m'a quand même donné la bonne réponse pour la première partie.

  Pour la deuxième partie, c'est comme pour le jour 8, c'est très compliqué dans le cas général mais facile parce que l'instance a de bonnes propriétés (je n'aime pas trop ce genre de journée).
  Tout d'abord, on remarque que rx a un seul prédécesseur qui est de type Conjonction et que celui a 4 prédécesseurs (que je vais appeler a, b, d) chacun de type Conjonction.
  Ensuite, si on enlève broadcaster, rx et son prédécesseur, on se retrouve avec 4 composantes connexes et donc les pulsations de chacune vont vivre leur vie indépendamment des autres.

  Si, on regarde quand a, b, c ou d envoie une pulsation forte, on remarque que ça forme un cycle sans prépériode et qu'une pulsation forte n'apparait qu'une seule fois durant un cycle.

  Il suffit donc de repérer pour a, b, c et d la première fois qu'il y a une pulsation forte et faire le PPCM entre les différentes valeurs trouvées.

  Pour le code en Haskell, j'utilise une monade State et des Lens, ce qui me permet de simplifier l'écriture.

  data Type = FlipFlop | Conjunction | Broadcaster
  data Module = Module !Type [String]
  type Network = HashMap String Module
  data NState = NState 
   { _ffState :: !(HashMap String Bool) -- the state of flip flap mdoules
   , _from :: !(HashMap String (HashMap String Bool)) -- last signal sent by predecessor
   , _nbLow :: !Int
   , _nbHigh :: !Int
   , _seen :: !(HashMap String Bool)
   }
  makeLenses ''NState
  parser :: Parser Network
  parser = insertRx . Map.fromList <$> module_ `sepEndBy1` eol where
   module_ = do
   t <- type_
   n <- name <* " -> "
   ns <- name `sepBy1` ", "
   pure (n, Module t ns)
   name = some lowerChar
   type_ = FlipFlop <$ "%" <|> Conjunction <$ "&" <|> pure Broadcaster
   insertRx = Map.insert "rx" (Module Broadcaster [])
  sendSignal :: Network -> Seq (String, String, Bool) -> State NState ()
  sendSignal network = \case
   Seq.Empty -> pure ()
   ((name, srcName, pulse) :<| queue') -> do
   if pulse then
   nbHigh += 1
   else do
   nbLow += 1
   seen . ix name .= True
   let Module type_ dests = network Map.! name
   case type_ of
   Broadcaster ->
   sendSignal network $ queue' >< Seq.fromList (map (,name, False) dests)
   FlipFlop ->
   if pulse then 
   sendSignal network queue'
   else do 
   nstate <- get
   let state = _ffState nstate Map.! name 
   ffState . ix name .= not state
   sendSignal network $ queue' >< Seq.fromList (map (,name, not state) dests)
   Conjunction -> do
   from . ix name . ix srcName .= pulse
   nstate <- get
   let signal' = any not $ Map.elems (_from nstate Map.! name)
   sendSignal network $ queue' >< Seq.fromList (map (,name, signal') dests)
  round :: Network -> State NState ()
  round network = do
   seen .= Map.map (const False) network
   sendSignal network $ Seq.singleton ("broadcaster", "$dummy", False)
  initNState :: Network -> NState
  initNState network = NState initFfState initFrom 0 0 initSeen where
   initFfState = Map.map (const False) network
   emptyFrom = Map.map (const Map.empty) network
   edgeList = concat . Map.elems $ Map.mapWithKey go network 
   go u (Module _ vs) = map (u,) vs
   initFrom = foldl' go' emptyFrom edgeList
   go' from_ (u, v) = Map.adjust (Map.insert u False) v from_
   initSeen = Map.map (const False) network
  part1 :: Network -> Int
  part1 network = _nbLow finalState * _nbHigh finalState where
   nstate = initNState network
   finalState = flip execState nstate do
   forM_ [(1::Int)..1000] \_ -> round network
  part2 :: Network -> Integer
  part2 network = foldl' lcm 1 cycles where
   nstate = initNState network
   predRx = head . Map.keys $ _from nstate Map.! "rx"
   predPredRx = Map.keys $ _from nstate Map.! predRx
   nstates = iterate' (execState (round network)) nstate
   cycles = map extractCycle predPredRx
   extractCycle name = head [ idx 
   | (idx, True) <- zip [0..] 
   . map ((Map.! name) . _seen) 
   $ nstates
   ]
  solve :: Text -> IO ()
  solve = aoc parser part1 part2

  • [^] # Re: Solution en Haskell

    Posté par Yth (Mastodon) le 20 décembre 2023 à 15:45. Évalué à 2.

    Ah, oui, c'est vrai ça, le résultat c'est le PPCM des 4 cycles, sauf qu'en l'occurrence ils sont premiers entre eux (enfin, chez moi en tout cas...), encore une propriété cachée dans les données, d'où la multiplication annoncée dans mon message !
    J'ai testé vite fait la multiplication sur le site avant de lancer le PPCM, et ça a fonctionné, donc j'ai complètement oublié qu'il fallait faire ça pour être corrects.

    • Yth.

• # Pas d'exemple

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

  À noter que les exemples fournis en première partie ne s'appliquaient pas à la deuxième partie, et que cette dernière ne fournissait aucun exemple utilisable. J'ai trouvé ça vache.

  • [^] # Re: Pas d'exemple

    Posté par Ysabeau 🧶 (site web personnel, Mastodon) le 20 décembre 2023 à 17:17. Évalué à 3.

    Y'a moyen de voir ce que fait le code au fait ? Le code ça ne me dit rien.

    Je n’ai aucun avis sur systemd

    • [^] # Re: Pas d'exemple

      Posté par Yth (Mastodon) le 21 décembre 2023 à 22:44. Évalué à 3.

      C'est pas hyper simple à représenter, mais je vais essayer.

      button
      ↓
      broadcaster
      │ 
      ├→hd → lt → rh → gx → xf → tg → ks → tc → qz → rl → pf → pr
      │ │↑ ↑ ↓ ↑ ↑ ↓ ↑ ↑ ↓ ↓ ↓ ↓
      │ │╰───┌─────────────────────────────────────────────────┐ ┌──┐
      │ ╰───→│ nl │→│cq│──╮
      │ └─────────────────────────────────────────────────┘ └──┘ │
      │ │
      ├→zj → kn → xn → gf → gv → vr → qb → hq → nx → bs → rd → vs │
      │ │↑ ↓ ↓ ↑ ↑ ↑ ↑ ↑ ↓ ↓ ↓ ↓ ↓
      │ │╰───┌─────────────────────────────────────────────────┐ ┌──┐ ┌──┐
      │ ╰───→│ pb │→│vp│→│ │
      │ └─────────────────────────────────────────────────┘ └──┘ │ │
      │ │ │
      ├→sq → vh → qc → gp → cp → jt → kb → hj → cf → jg → pd → mt │ns│→rx
      │ │↑ ↓ ↑ ↑ ↓ ↑ ↓ ↓ ↓ ↓ ↓ ↓ │ │
      │ │╰───┌─────────────────────────────────────────────────┐ ┌──┐ │ │
      │ ╰───→│ rr │→│rv│→│ │
      │ └─────────────────────────────────────────────────┘ └──┘ └──┘
      │ ↑
      └→jz → ht → jv → zs → dq → jc → xv → dx → fq → xz → zp → mm │
       │↑ ↑ ↓ ↑ ↓ ↑ ↓ ↓ ↑ ↓ ↓ ↓ │
       │╰───┌─────────────────────────────────────────────────┐ ┌──┐ │
       ╰───→│ dj │→│dc│──╯
       └─────────────────────────────────────────────────┘ └──┘

      On va dire qu'un « low pulse » est un 1, et un « high pulse » un 0.
      C'est plus simple pour comprendre.

      Le button envoie un 1 quand on appuie dessus.
      Le broadcaster transmet ce qu'il a reçu à toutes ses destinations.

      Les noms simples, en deux lettres, sans cadre, sont des alternateurs, s'ils reçoivent un 1, ils envoient une fois un 1, et une fois un 0. Mais s'ils reçoivent 0 ils bougent pas.
      À l'état initial ils enverront un 0 au premier 1 reçu.
      Donc notre broadcaster étant relié à des alternateurs, au repos il ne se passe rien, mais quand on appuie sur le gros bouton rouge, il active les quatre alternateurs devant lui.

      Les noms dans les cadres sont des boîtes de remise à zéro, en gros.
      Au début elles sont configurées sur 1 à toutes leurs entrées, mais c'est mis à jour dès qu'elles reçoivent un truc.
      Si toutes leurs entrées sont à 0, alors elles envoient un 1 à toutes leurs sorties ! Sinon, c'est un 0, qui sera ignoré par tous les alternateurs connectés. D'où le nom de boîte de remise à zéro, ça ne va envoyer 1 aux alternateurs que quand ça reçoit du 0 de partout à la fois !

      Quand ça arrive, les boîtes à droites reçoivent un 1 et donc envoient un 0, sinon elles reçoivent un 0 et envoie un 1.
      Avec une seule entrée, ce sont des inverseurs.

      Donc quand nos grosses boîtes s'activent et réussissent à envoyer un 1, le signal est inversé en 0 vers la boîte finale.
      Si toutes les quatre grosses boîtes envoient un 1 en même temps, alors la boîte finale reçoit quatre 0.
      À ce moment là elle va envoyer un 1 vers rx, qui est notre module de sortie et qui n'attends que ça !

      Franchement, une fois représenté comme ça, le problème il est hyper clair hein ?
      Faut trouver le moment où chacune des grosses boîte s'active.

      Là, on a grosso-modo tous fait une simulation : on part de l'état initial, chaque alternateur va envoyer un 0, et les grosses boîtes sont sur 1 dans toutes leurs entrées, et on appuie sur le gros bouton rouge, jusqu'à ce que les boîtes s'activent.

      Là on note quand c'est arrivé.
      Typiquement on va continuer pour voir quand ça va se produire à nouveau, pour chaque boîte, et essayer de déduire un schéma.
      Ici c'est facile, en fait, dès la première fois que ça s'active, on a fait un cycle et c'est retour à l'état initial, en fait pas tout à fait, mais au moins ça boucle sur la même durée.
      On a donc 4 cycles, il ne reste plus qu'à les coordonner, savoir quand est-ce qu'ils vont s'activer tous ensemble.
      Et le plus petit multiple commun aux quatre valeurs mesurées est notre réponse.

      Maintenant en poussant l'analyse.
      Notre série par exemple de la première boîte, consiste en 12 alternateurs, tous éteints donc prêts à envoyer 0.
      On va noter ça 000000000000.
      La boîte n'enverra absolument rien tant qu'on ne l'aura pas activée (enfin, elle envoie des 0 qui sont ignorés par les alternateurs).
      Si on appuie, le premier va s'allumer, et envoyer 0, qui va être ignoré, on est donc dans cette situation :
      100000000000.
      Au second coup, notre premier alternateur va s'éteindre, repasser à 0, mais aura envoyé un 1 à droite, sur le second, qui va s'allumer et envoyer 0 qui sera ignoré.
      01000000000
      Au 3ème coup, on rallume le premier, rien d'autre ne bouge : 110000000000.
      4 : 0010000000
      5 : 1010000000
      6 : 0110000000
      7 : 1110000000
      Ok peut continuer la simulation, mais il apparaît comme évident qu'on est en train de compter. On a exactement la représentation binaire, mais de gauche à droite, des numéros des étapes.

      Là on va regarder notre boîte nl, et constater qu'elle va s'activer dès qu'elle reçoit 0 en même temps de la part de hd, rh, tg, qz, rl, pf et pr, ce qui va arriver quand il vont tous s'être allumés (passer de 0 à 1) comme dernière action.
      Ça arrive dès qu'on a 1 sur chacun d'entre eux, et 0 sur les autres, c'est la première fois où ça va se produire et c'est cette configuration : 101001001111 qu'on retourne en 111100100101 pour avoir le chiffre binaire 3877, qu'on retrouve bien dans mes résultats plus haut.
      Pour les autres, on va simplement lire 111000001111 soit 3847, 110010111111 soit 4051, et enfin 101010110111 soit 3797.

      Diantre c'est juste.
      Là nos nombres sont premiers entre eux, donc le PPCM vaut la multiplication des 4 soit... beaucoup.

      Mais bref, voilà le problème entièrement décortiqué, et finalement une lecture directe des chiffre à trouver, sans aucun calcul, sans besoin d'ordinateur, sauf pour le PPCM (c'est un peu misérable à la main avec des chiffres aussi gros quand même).

      Merci de ta question Ysabeau, je n'aurais pas poussé autant sinon :)

      Pour continuer un petit peu, sur notre exemple 1.
      On active sur 101001001111 mais à ce moment là notre boîte ne se contente pas d'envoyer un 1 vers la sortie, elle envoie aussi un 1 vers tous nos 0 !
      En effet, tous les alternateurs qui n'envoient pas vers la boîte, reçoivent de la boîte.
      Ils sont éteints, ils vont donc s'allumer, envoyer des 0 qui seront ignorés et passer tous à 1 : 111111111111 = 4095.
      Sauf que le tout premier reçoit lui aussi un 1, exactement comme si on avait appuyé sur le bouton une fois tout passé à 1 !
      C'est hd, et il est bien en dernier de la liste des alternateurs activés par nl. On lui envoie un 1 qui va faire s'éteindre tous les alternateurs en chaîne, puisqu'ils envoient un 1 en s'éteignant. Ils vont donc tous avoir envoyé un 1 vers la boîte (ceux qui sont connectés) qui verra bien son état retourner à celui d'origine.
      D'où la boucle et le cycle qui recommence exactement à zéro, on est effectivement retourné précisément à l'état initial.
      On a compté de 0 à 3877, et au moment d'arriver à 3877, on a une remise à 0 avec un signal envoyé vers la sortie.

      • Yth.

      • [^] # Re: Pas d'exemple

        Posté par Ysabeau 🧶 (site web personnel, Mastodon) le 22 décembre 2023 à 13:55. Évalué à 3.

        Merci pour les explications (et je comprend qu'il n'y à rien à voir en fait).

        Je n’ai aucun avis sur systemd

        • [^] # Re: Pas d'exemple

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

          Ah non, on manipule des chiffres ou des lettres, réunis en ensembles, en listes, en dictionnaires.
          Parfois on peut représenter ce qu'il se passe, parfois pas trop.
          Et on doit faire gaffe à pas trop demander de calculs à la machine, sinon ça peut prendre des mois.

          • Yth.

• # Enfin...

  Posté par syj le 24 décembre 2023 à 00:55. Évalué à 1.

  J'ai enfin ma solution pour le jour 20.
  1) J'ai exploré plusieurs solutions comme laisser mon PC calculé à l'aveugle pendant 1j de travail. Je chauffe en partie à l'électrique. Donc, cela ne me coutait pas de laisser mon PC cramer des Watt :).
  2) J’ai tenté de simplifier les cycles des flip-flop sans grand succès. Car je pensais que les conjuctions serait beaucoup plus complexe avec leurs multiples false, true qu’elles crachent
  3) Via récursivité de trouver une méthode pour factoriser les circuits. Je n’ai pas vu la solution suivante toute suite, car ma fonction recursive allé jusqu’au flip / flop. Mais au final,c’était trop complexe pour trouver une simplification évidente.
  4) Finalement, j’ai tenté juste de regarder les cycles des trues sur les 4 conjonctions qui sont avant RX { "hz", "pv", "qh", "xm" }
  Et là, c’était évident. J’avais des cycles réguliers pour ces 4 conjonctions. Il ne me reste plus qu’à trouver quand elles sont à true toutes les 4 en même temps. Ce qui revient à trouver le PPCM des 4 cycles.
  J’ai demandé à chatgpt de me fournir le calcul d’un PPCM (çà se reconnait au style).
  En prenant, le problème dans le bon sens, j’aurai pu le résoudre en 1h partie 1 et partie 2.... J’ai mis encore bien 5h cumulé.

  public class Aoc2023s20v3 { 
   public record Message(String sourceName, boolean hight, Component component) { 
   }
   // Hard coded main conjunction
   protected static final String[] CHECK_MAIN_RX_CONJUNCTION = new String[] {
   "hz", "pv", "qh", "xm"
   };
   // Function to find the GCD (Greatest Common Divisor) of two numbers
   private static long findGCD(long a, long b) {
   while (b != 0) {
   long temp = b;
   b = a % b;
   a = temp;
   }
   return a;
   }
   // Function to find the LCM (Lowest Common Multiple) of two numbers
   private static long findLCM(long a, long b) {
   return (a * b) / findGCD(a, b);
   }
   // Function to find the LCM of an array of numbers
   public static long findLCMOfArray(Long[] numbers) {
   if (numbers.length == 0) {
   throw new IllegalArgumentException("Array should not be empty");
   }
   long lcm = numbers[0];
   for (int i = 1; i < numbers.length; i++) {
   lcm = findLCM(lcm, numbers[i]);
   }
   return lcm;
   }
   public static abstract class Component {
   String name;
   String[] targetNames = new String[0] ;
   public Map<String, Message> getMessageHight = new HashMap<>();
   public Map<String, Message> getMessageLow = new HashMap<>();
   private Message[] sendTrue;
   private Message[] sendFalse;
   public HashMap<Long, List<Boolean>> signalHistory = new LinkedHashMap<>();
   public Component(String name) {
   this.name = name;
   }
   public void registerInput(String name) {
   }
   public void clear() {
   }
   public void process(Circuit circuit, Message message) {
   }
   public final void send(Circuit circuit, boolean sendSignalHight) { 
   Message[] toSend;
   if(sendSignalHight) {
   if(sendTrue == null) {
   sendTrue = Arrays.stream(targetNames).map(target -> new Message(this.name, sendSignalHight, circuit.elementsByName.get(target))).toArray(k-> new Message[k]);
   }
   toSend = sendTrue;
   } else {
   if(sendFalse == null) {
   sendFalse = Arrays.stream(targetNames).map(target -> new Message(this.name, sendSignalHight, circuit.elementsByName.get(target))).toArray(k-> new Message[k]);
   }
   toSend = sendFalse;
   }
   if(this instanceof Conjuction && sendSignalHight)
   signalHistory.computeIfAbsent((long)circuit.circuitIndex, (k)->new ArrayList<Boolean>()).add(sendSignalHight);
   ArrayDeque<Message> messages = circuit.messages; 
   for (Message target : toSend) { 
   messages.add(target);
   } 
   }
   public String expr(Circuit circuit) {
   return this.name;
   }
   }
   public static class FlipFlop extends Component {
   boolean state;
   public FlipFlop(String name) {
   super(name);
   }
   @Override
   public void clear() {
   state = false;
   }
   @Override
   public void process(Circuit circuit, Message message) {
   if (message.hight) {
   // do nothing
   return;
   }
   this.state = !state;
   send(circuit, this.state);
   }
   @Override
   public String toString() {
   return "FlipFlop [state=" + state + ", name=" + name + ", targetNames=" + targetNames + "]";
   }
   public String expr(Circuit circuit) {
   return "%" + this.name;
   }
   }
   public static class Conjuction extends Component {
   private long state= 0;
   private long allUp = 0;
   private Map<String, Long> inputMask = new HashMap<>();
   private Map<String, Long> notInputMask = new HashMap<>();
   public Conjuction(String name) {
   super(name);
   }
   @Override
   public void registerInput(String name) {
   int nextId = inputMask.size();
   long mask = 1L << nextId;
   inputMask.put(name, mask);
   notInputMask.put(name, ~mask);
   allUp = (1L << (nextId+1))-1;
   }
   @Override
   public void process(Circuit circuit, Message message) {
   if(message.hight) {
   long mask = inputMask.get(message.sourceName);
   state = state | mask;
   } else {
   long notMask = notInputMask.get(message.sourceName);
   state = state & notMask;
   }
   var notAllTrue = state != allUp;
   send(circuit, notAllTrue); 
   }
   @Override
   public String toString() {
   return "Conjuction [name=" + name + ", targetNames=" + targetNames + "]";
   }
   public String expr(Circuit circuit) {
   return "/*" + this.name + "*/(" + this.inputMask.keySet().stream().map(n->circuit.elementsByName.get(n).expr(circuit)).collect(Collectors.joining(" & ")) + ") \n";
   }
   }
   public static class Output extends Component {
   private long countHight;
   private long countSmall;
   public Output(String name) {
   super(name);
   }
   @Override
   public void clear() {
   this.countHight = 0;
   this.countSmall = 0;
   }
   @Override
   public void process(Circuit circuit, Message message) {
   if (message.hight)
   countHight++;
   else
   countSmall++;
   }
   @Override
   public String toString() {
   return "Output [countHight=" + countHight + ", countSmall=" + countSmall + ", name=" + name
   + ", targetNames=" + targetNames + "]";
   }
   }
   public static class Circuit {
   Map<String, Component> elementsByName = new HashMap<>();
   String[] broadcastList = new String[0]; 
   ArrayDeque<Message> messages = new ArrayDeque<>();
   long countHight;
   long countLow;
   long circuitIndex = 0;
   void parse(Scanner in) {
   while (in.hasNext()) {
   String row = in.nextLine();
   String[] part = row.split("->");
   String typeName = part[0].trim();
   String[] targetNames = Arrays.stream(part[1].trim().split(",")).map(String::trim).toArray(k ->new String[k]);
   if ("broadcaster".equals(typeName)) {
   broadcastList = targetNames;
   } else if (typeName.startsWith("%")) {
   FlipFlop flipFlop = new FlipFlop(typeName.substring(1));
   flipFlop.targetNames = targetNames;
   elementsByName.put(flipFlop.name, flipFlop);
   } else if (typeName.startsWith("&")) {
   Conjuction c = new Conjuction(typeName.substring(1));
   c.targetNames = targetNames;
   elementsByName.put(c.name, c);
   }
   }
   elementsByName.put("output", new Output("output"));
   elementsByName.put("rx", new Output("rx"));
   for (Component source : elementsByName.values()) {
   for (String target : source.targetNames) {
   Component rx= elementsByName.get(target);
   if(rx != null) {
   rx.registerInput(source.name);
   }
   }
   }
   for (String target : broadcastList) {
   elementsByName.get(target).registerInput("broadcast");
   }
   }
   public long experienceToFindWhereRxIsUp(long count) {
   messages.clear();
   elementsByName.values().forEach(Component::clear);
   countHight = 0;
   countLow = 0;
   long s = System.currentTimeMillis();
   int x=0;
   while(true) {
   circuitIndex = x;
   countLow++;
   for (String initial : broadcastList) {
   messages.add(new Message("broadcast", false, elementsByName.get(initial)));
   }
   processMessages(); 
   if(x > count) {
   System.out.println("seek " + x + " " + (System.currentTimeMillis() -s) + "ms");
   s = System.currentTimeMillis();
   return tryToFindLcmInMainConjuction();
   }
   x++;
   }
   }
   private long tryToFindLcmInMainConjuction() { 
   List<Long> toComputeLcm = new ArrayList<>();
   for(String name: CHECK_MAIN_RX_CONJUNCTION) {
   Component c= elementsByName.get(name);
   System.out.println(c.name + " => " + c.signalHistory.keySet());
   Long previous = null;
   Long previousDiff= null;
   for(Long l: c.signalHistory.keySet()) {
   if(previous !=null) {
   long diff= l-previous;
   System.out.print((l-previous) + ",");
   if(previousDiff != null) {
   if(diff == previousDiff) {
   toComputeLcm.add(diff);
   } else {
   System.out.println("Can't compute LCM");
   }
   }
   previousDiff = diff;
   }
   previous = l;
   }
   System.out.println();
   }
   return findLCMOfArray(toComputeLcm.toArray(new Long[toComputeLcm.size()]));
   }
   private void processMessages() {
   while (!messages.isEmpty()) {
   Message message = messages.pollFirst();
   if(message.hight) {
   countHight++;
   } else {
   countLow++;
   }
   message.component.process(this, message);
   }
   }
   }
   public static void main(String[] args) {
   try (Scanner in = new Scanner(Aoc2023s18v2.class.getResourceAsStream("res/t20.txt"))) {
   Circuit circuit = new Circuit();
   circuit.parse(in);
   long result = circuit.experienceToFindWhereRxIsUp(20000);
   System.out.println(result);
   }
   }
  }

Suivre le flux des commentaires

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