Forum Programmation.autre Avent du Code, jour 20

Posté par (Mastodon) . Licence CC By‐SA.
Étiquettes :
2
20
déc.
2022

On est sorti de notre Volcan, et maintenant on cherche les Elfes.
Pour ça on va hacker les données chiffrées dans le transmetteur pour trouver le fameux verger aux fruits étoilés.

Au menu : réordonner une liste cyclique en bougeant les éléments d'une certaine distance, plein de fois, avec des valeurs très grande.
Cyclique = modulo, ici il n'y a pas besoin de faire chauffer le CPU !

Cela dit, vu depuis combien de temps nos lutinelfes de Noël sont restés sans nous pour résoudre leurs problèmes, ça sent le carnage dès qu'on les auras retrouvés...

  • Yth.

  • # Un bug que j'ai résolu sans jamais le trouver.

    Posté par (Mastodon) . Évalué à 3. Dernière modification le 20 décembre 2022 à 11:43.

    J'ai codé ma propre liste chaînée, j'ai été intelligent avec mes modulos, j'ai une réponse sans ultra-optimiser en 4 secondes pour les données de test et les données réelles.

    Et j'ai un bug.
    Tout fonctionne au poil sur les données de test, les deux exercices, et les données réelles, mais pas le second sur données réelles !
    Mauvais résultat.
    Et j'ai beau triturer, je tombe toujours sur le mauvais résultat.

    Alors j'ai recodé un peu différemment mes quelques lignes qui servent à déplacer un nombre dans la liste, je suis persuadé que fonctionnellement c'est identique, et ça fonctionne au super poil avec les données de test.
    Mais je suis malade, ça explique peut-être.
    En tout cas : résultat différent et correct cette fois-ci, avec un code un zest plus propre, mais à peine.

    Sauf que dans le cas où le mouvement est de zéro, modulo, ben j'avais un effet de bord débile, je cassais ma liste...

    Bref, ça aurait dû aller vite, mais pas.

    • Yth.

    • [^] # Re: Un bug que j'ai résolu sans jamais le trouver.

      Posté par (Mastodon) . Évalué à 4. 

      @dataclass(frozen=False)
class Number:
 v: int
 p: int
 n: int
 def __call__(self):
 return self.v, self.p, self.n
 @property
 def next(self):
 return self.problem[self.n]
 @property
 def previous(self):
 return self.problem[self.p]
 @cached_property
 def moves(self):
 return self.value % (len(self.problem) - 1)
 @cached_property
 def value(self):
 return self.v * self.decryptionkey
# Input handling
def numbers(data):
 lastid = len(data) - 1
 yield Number(data[0], lastid, 1)
 for i in range(1, lastid):
 yield Number(data[i], i - 1, i + 1)
 yield Number(data[-1], lastid - 1, 0)
def result(problem):
 number = [x for x in problem if x.v == 0][0]
 for _ in range(1000):
 number = number.next
 n1000 = number.value
 for _ in range(1000):
 number = number.next
 n2000 = number.value
 for _ in range(1000):
 number = number.next
 n3000 = number.value
 r = n1000 + n2000 + n3000
 return r
def decrypt(problem):
 for i, number in enumerate(problem):
 if number.v == 0:
 continue
 # removes number from list
 number.previous.n = number.n
 number.next.p = number.p
 search = number
 for _ in range(number.moves):
 search = search.next
 # search is now the new previous
 number.n = search.n
 number.p = search.next.p
 # Inserting number
 number.next.p = i
 number.previous.n = i
data = [int(x) for x in sys.stdin.read().strip().splitlines()]
# Problème n°1
problem = list(numbers(data))
Number.problem = problem
Number.decryptionkey = 1
decrypt(problem)
print(f"First answer = {result(problem)}")
# Problème n°2
problem = list(numbers(data))
Number.problem = problem
Number.decryptionkey = 811589153
for _ in range(10):
 decrypt(problem)
print(f"Final answer = {result(problem)}")

      • [^] # Re: Un bug que j'ai résolu sans jamais le trouver.

        Posté par . Évalué à 3.

        Pour moi, pas de modelisation en classes aujourd'hui.
        Le truc qui m'a pris du temps c'est de realiser qu'il y avait plusieurs fois les memes valeurs dans les donnees reelles. J'ai resolu ca au plus vite en stockant une liste de tuples (valeur, rang d'apparition de cette valeur).

        is_part_2 = True
original_sequence = []
with open("2022/input_files/day20") as f:
 for data in f:
 n = int(data.rstrip()) * (811589153 if is_part_2 else 1)
 c = [x[0] for x in original_sequence].count(n)
 original_sequence.append((n, c))
sequence = original_sequence.copy()
for _ in range(10 if is_part_2 else 1):
 for n, occurence in original_sequence:
 old_index = sequence.index((n, occurence))
 new_index = (old_index + n) % (len(sequence) - 1)
 if new_index == 0:
 new_index = len(sequence) - 1
 sequence.insert(new_index, sequence.pop(old_index))
i0 = sequence.index((0, 0))
a = (i0 + 1000) % len(sequence)
b = (i0 + 2000) % len(sequence)
c = (i0 + 3000) % len(sequence)
print(f"{sequence[a][0]+sequence[b][0]+sequence[c][0]=}")

        Excusez l'absence d'accents dans mes commentaires, j'habite en Australie et n'ai pas de clavier francais sous la main.

        • [^] # Re: Un bug que j'ai résolu sans jamais le trouver.

          Posté par . Évalué à 4.

          J'oubliais de dire, sans liste chainee, avec une liste python toute bete, ca prend une demi-seconde avec les donnees reelles.

          Excusez l'absence d'accents dans mes commentaires, j'habite en Australie et n'ai pas de clavier francais sous la main.

          • [^] # Re: Un bug que j'ai résolu sans jamais le trouver.

            Posté par (Mastodon) . Évalué à 4. Dernière modification le 20 décembre 2022 à 15:02.

            C'est tellement plus intelligent que ce que j'ai fait, je suis jaloux !
            Je ne pensais pas que les listes seraient assez performantes, j'aurais dû essayer.

            Bravo !

            Tu peux pas faire ça plutôt ?

             for id, data in enumerate(f):
 n = int(data.rstrip()) * (811589153 if is_part_2 else 1)
 original_sequence.append((id, c))

            Tu t'en fous du nombre d'occurrence, ce que tu veux c'est que chaque élément de la liste soit unique.

            • Yth.

            • [^] # Re: Un bug que j'ai résolu sans jamais le trouver.

              Posté par . Évalué à 2.

              Tout-a-fait! C'est plus efficace comme tu le proposes et ca marche pareil.

              Excusez l'absence d'accents dans mes commentaires, j'habite en Australie et n'ai pas de clavier francais sous la main.

              • [^] # Re: Un bug que j'ai résolu sans jamais le trouver.

                Posté par (Mastodon) . Évalué à 2. Dernière modification le 20 décembre 2022 à 15:18.

                Faut aussi que 0 reste (0, 0), pour le retrouver à la fin.
                Mais ça gagne 35% de temps :)

                Bravo, j'admire la simplicité !

                • Yth, je note list.index() c'est pas pourri en vrai, peut-être si on a des listes de millions d'éléments, mais là c'est 5000, c'est petit.

        • [^] # Re: Un bug que j'ai résolu sans jamais le trouver.

          Posté par (site web personnel) . Évalué à 4.

          Joli, du coup j'ai honte de montrer ma solution avec liste chaînée maison. Mais je la montre quand même, allez :

          from __future__ import annotations
import io
from typing import Iterable, Iterator, Optional
class Chain:
 def __init__(self, *elts: Element) -> None:
 self._len = len(elts)
 self.first = elts[0]
 last = elts[-1]
 prev: Optional[Element] = None
 for elt in elts:
 if prev is not None:
 prev.attach(elt)
 prev = elt
 last.attach(self.first)
 def __len__(self):
 return self._len
 def __getitem__(self, index: int) -> Element:
 index = index % len(self)
 current = self.first
 for _ in range(index):
 current = current.next
 return current
 def get_elt(self, base_elt: Element, index: int) -> Element:
 index = index % len(self)
 current = base_elt
 for _ in range(index):
 current = current.next
 return current
 def __iter__(self) -> Iterator[Element]:
 current = self.first
 for _ in range(self._len):
 yield current
 current = current.next
 def extract(self, index: int) -> Element:
 elt = self[index]
 elt.detach()
 self._len -= 1
 return elt
 def extract_elt(self, elt: Element) -> None:
 # WARNING: not checking that elt is part of self
 elt.detach()
 self._len -= 1
 def insert(self, index: int, elt: Element) -> None:
 prev = self[index]
 next_ = prev.next
 # Attach (prev and elt) and (elt and next_)
 prev.attach(elt)
 elt.attach(next_)
 self._len += 1
 def insert_elt(self, base: Element,
 shift: int, elt: Element) -> None:
 # WARNING: not checking that elt is part of self
 shift %= self._len
 prev = base
 for _ in range(shift):
 prev = prev.next
 next_ = prev.next
 # Attach (prev and elt) and (elt and next_)
 prev.attach(elt)
 elt.attach(next_)
 self._len += 1
 def __str__(self):
 result = io.StringIO()
 result.write('(')
 for elt in self:
 result.write('{}, '.format(elt.value))
 result.write(')')
 return result.getvalue()
class Element:
 def __init__(self, value: int) -> None:
 self.value = value
 self.prev = self
 self.next = self
 def attach(self, other: Element) -> None:
 self.next = other
 other.prev = self
 def detach(self) -> None:
 prev = self.prev
 next_ = self.next
 # Detach self
 self.prev = self
 self.next_ = self
 # Attach prev and next_
 prev.attach(next_)
def solve1(lines: Iterable[str]) -> int:
 """Solve part 1 of today's puzzle"""
 elts = [Element(int(line)) for line in lines]
 seq = Chain(*elts)
 zero: Optional[elt] = None
 for elt in elts:
 if zero is None and elt.value == 0:
 zero = elt
 prev = elt.prev
 seq.extract_elt(elt)
 seq.insert_elt(prev, elt.value, elt)
 if zero is None:
 raise ValueError("invalid input without a zero value")
 return (seq.get_elt(zero, 1000).value
 + seq.get_elt(zero, 2000).value
 + seq.get_elt(zero, 3000).value)
def solve2(lines: Iterable[str]) -> int:
 """Solve part 2 of today's puzzle"""
 key = 811589153
 elts = [Element(key * int(line)) for line in lines]
 seq = Chain(*elts)
 zero: Optional[elt] = None
 for _ in range(10):
 for elt in elts:
 if zero is None and elt.value == 0:
 zero = elt
 prev = elt.prev
 seq.extract_elt(elt)
 seq.insert_elt(prev, elt.value, elt)
 if zero is None:
 raise ValueError("invalid input without a zero value")
 return (seq.get_elt(zero, 1000).value
 + seq.get_elt(zero, 2000).value
 + seq.get_elt(zero, 3000).value)

          À noter que c'est pas mal plus lent qu'avec des listes Python en fait... :-(

          • [^] # Re: Un bug que j'ai résolu sans jamais le trouver.

            Posté par (Mastodon) . Évalué à 2.

            C'est clair, on fait de belles modélisations, alors que la solution d'Éric cartonne tout.

            Possible que la liste chaînée devienne plus performante si on a des millions d'éléments, mais à 5000, on se fait laminer.

            • Yth.

  • # il était vraiment null celui-ci

    Posté par . Évalué à 2.

    J'ai pris le problème du mauvais sens, il m'a fallut plus de 3h pour comprendre qu'il ne fallait pas appliquer la transformation 3000 fois pour avoir la réponse.

    J'ai réecris 3 ou 4 fois mon code. J'ai commencé par un tableau avec des modulos au final, j'ai terminé par une liste doublement chainés comme quasiment tout le monde.

    J'ai remis une bonne 1h30 pour caler le modulo pour éviter d'appliquer les millions de déplacement.

    Bref, un très mauvaise journée. En plus, vous êtes plein à y être arrivé avant moins résultat.
    Je n'ai plus aucun espoir de rafler la seconde place.

    • [^] # Re: il était vraiment null celui-ci

      Posté par . Évalué à 3.

      Il faut voir le verre a moitie plein, si je regarde le leaderboard plus personne ne peut te rattraper et ta place sur le podium est garantie!

      On est encore 8 actifs dans le leaderboard, donc en gros si j'ai bien compris les regles, on peut tu peux gagner au maximum 7 points par jour sur les autres, et il ne reste que 4 jours.

      Excusez l'absence d'accents dans mes commentaires, j'habite en Australie et n'ai pas de clavier francais sous la main.

Suivre le flux des commentaires

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