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.