Forum Programmation.autre Avent du Code, jour 13

Posté par steph1978 le 13 décembre 2022 à 12:25. Licence CC By‑SA.

Étiquettes :

déc.

2022

Suite de l'Avent du Code, jour 13.

Encore des problèmes de communications, les paquets arrivent dans le désordre. Heureusement le protocole de communication permet de les ré-ordonner. Au boulot !

# En Pypthon

Posté par 🚲 Tanguy Ortolo (site web personnel) le 13 décembre 2022 à 13:16. Évalué à 5.

Pour la définition de aoc.group_lines(lines: str), cf. hier

from __future__ import annotations

import itertools

from typing import Iterable, Iterator, List, Optional, Tuple, Union

import aoc


class Element:
    def __init__(self, value: Union[List[Element], int]):
        self.value = value

    def __lt__(self, other: Element) -> bool:
        if isinstance(self.value, int) and isinstance(other.value, int):
            return self.value < other.value
        if isinstance(self.value, list) and isinstance(other.value, list):
            for self_elt, other_elt in zip(self.value, other.value):
                if self_elt < other_elt:
                    return True
                if other_elt < self_elt:
                    return False
            # Ran out of elements on one of the lists
            return len(self.value) < len(other.value)
        if isinstance(self.value, int):
            return Element([self]) < other
        if isinstance(other.value, int):
            return self < Element([other])
        assert False  # should not happen: we covered all cases

    def __eq__(self, other: object) -> bool:
        if not isinstance(other, Element):
            return NotImplemented
        if isinstance(self.value, int) and isinstance(other.value, int):
            return self.value == other.value
        if isinstance(self.value, list) and isinstance(other.value, list):
            return (len(self.value) == len(other.value)
                    and all(self_elt == other_elt for self_elt, other_elt
                            in zip(self.value, other.value)))
        if isinstance(self.value, int):
            return Element([self]) == other
        if isinstance(other.value, int):
            return self == Element([other])
        assert False  # should not happen: we covered all cases

    def __str__(self) -> str:
        if isinstance(self.value, int):
            return str(self.value)
        elif isinstance(self.value, list):
            return '[{}]'.format(
                    ','.join(str(element) for element in self.value))
        assert False  # should not happen: we covered all cases


def import_element(chars: Iterable[str]) -> Element:
    element: Optional[Element] = None
    lists: List[List[Element]] = []  # List[List[Element]]
    current_list: Optional[List[Element]] = None
    current_int: Optional[int] = None
    for char in chars:
        if char == '[':
            if current_int is not None:
                raise ValueError("unexpected beginning of list")
            if current_list is not None:
                lists.append(current_list)
            current_list = []
        elif char == ']':
            if current_list is None:
                raise ValueError("unexpected end of list")
            # If we were parsing an int, add it before closing current list
            if current_int is not None:
                current_list.append(Element(current_int))
                current_int = None
            if lists:
                # We are closing a sub-list
                prev_list = lists.pop()
                prev_list.append(Element(current_list))
                current_list = prev_list
            else:
                # We are closing the top-level list
                element = Element(current_list)
                current_list = None
        elif char.isdecimal():
            value = int(char)
            if current_int is None:
                current_int = value
            else:
                current_int = 10 * current_int + value
                continue
        elif char == ',':
            if current_list is None:
                raise ValueError("unexpected separator")
            if current_int is not None:
                current_list.append(Element(current_int))
                current_int = None
        elif char == '\n':
            pass
        else:
            raise ValueError("unexpected character")
    if element is None:
        raise ValueError("nothing to parse")
    return element


def import_pairs(lines: Iterable[str]) -> Iterator[Tuple[Element, Element]]:
    for group in aoc.group_lines(lines):
        elements = [import_element(line) for line in group]
        if len(elements) != 2:
            raise ValueError("unexpected group length")
        yield (elements[0], elements[1])


def import_elements(lines: Iterable[str]) -> Iterator[Element]:
    for line in lines:
        if line and line != '\n':
            yield import_element(line)


def solve1(lines: Iterable[str]) -> int:
    """Solve part 1 of today's puzzle"""
    pairs = import_pairs(lines)
    return sum(i + 1 for i, (elt1, elt2) in enumerate(pairs) if elt1 < elt2)


def solve2(lines: Iterable[str]) -> int:
    """Solve part 2 of today's puzzle"""
    elements: Iterable[Element] = import_elements(lines)
    div1 = import_element("[[2]]")
    div2 = import_element("[[6]]")
    elements = sorted(itertools.chain(elements, (div1, div2)))
    key = 1
    for i, element in enumerate(elements):
        if element == div1 or element == div2:
            key *= i + 1
    return key

[^] # Re: En Pypthon

Posté par Yth (Mastodon) le 13 décembre 2022 à 14:48. Évalué à 2.
Ah, j'avoue, j'ai même pas imaginé deux secondes faire un vrai parsing des données :)
- Yth.
[^] # Re: En Pypthon

Posté par GuieA_7 (site web personnel) le 13 décembre 2022 à 15:00. Évalué à 2.

Un gentil contributeur cette année m'a fait découvrir qu'à partir du moment où on utilise from __future__ import annotations, on peut déjà remplacer Union[List[Element], int] par list[Element] | int par exemple (testé sur Python 3.7 et suivant).

# python, en trichant

Posté par steph1978 le 13 décembre 2022 à 13:21. Évalué à 4.

Je galérais à organiser ma comparaison de paquets, et j'ai eu un indice d'utiliser un comparateur. Je suis reparti là dessus et ça fonctionne.

import sys

P = [ tuple(map(eval, p.split("\n"))) for p in sys.stdin.read().split("\n\n") ]

def C(l,r):
    T = (type(l),type(r))
    if T == (int,int):
        if l<r: return -1
        return l>r # 0 or 1
    if T == (int,list):
        return C([l],r)
    if T == (list,int):
        return C(l,[r])
    # list,list
    for q in zip(l,r):
        c = C(*q)
        if c: return c
    return C(len(l),len(r))

# part 1
S = 0
for i,p in enumerate(P):
    if C(*p) <= 0:
        S += i+1
print(S)

# part 2
from functools import cmp_to_key
Q = [ q for (l,r) in P for q in [l,r] ]
Q.append([[2]])
Q.append([[6]])
Q.sort(key=cmp_to_key(C))
print((Q.index([[2]])+1)*(Q.index([[6]])+1))

[^] # Re: python, en trichant

Posté par 🚲 Tanguy Ortolo (site web personnel) le 13 décembre 2022 à 13:30. Évalué à 6.
On peut tricher en moins craignos. Un indice :
```
$ file 13.in
13.in: JSON data
```
- [^] # Re: python, en trichant
  
  Posté par steph1978 le 13 décembre 2022 à 15:31. Évalué à 2. Dernière modification le 13 décembre 2022 à 15:33.
  
  Tu veux dire à la place du eval. Oui clairement, c'est moins craignos.
  
  À la première lecture je pensais que tu voulais résoudre le problème en javascript 😓. Je veux dire juste en comparant les deux listes avec un <. J'ai tenté, ça marche presque 😛. Mais non en fait, les règles de comparaisons ne sont pas les mêmes.
  - [^] # Re: python, en trichant
    
    Posté par Yth (Mastodon) le 13 décembre 2022 à 15:50. Évalué à 3.
    Ouais, j'ai essayé de faire un hack pour remplacer les chiffres seuls par des listes de chiffres, et après faire un json.loads() et juste comparer, en bricolant quelques trucs du genre on arrive à faire tourner les données de démo.
    
    Pour faire court, c'est le premier exercice du calendrier où je n'ai pas fourni la bonne réponse du premier coup…
    
    Après j'ai été moins « malin », et j'ai réussi…
    - Yth.

[^] # Re: python, en trichant

Posté par Yth (Mastodon) le 13 décembre 2022 à 14:46. Évalué à 2.

J'ai un code équivalent, avec un peu plus de modélisation, mais sinon, c'est algorithmiquement identique :

import sys
import json
from functools import total_ordering


@total_ordering
class packet:
    def __init__(self, data):
        self.data = data

    def compare(self, a, b):
        if type(a) == type(b) == int:
            if a == b:
                return None
            return a < b
        if type(a) == int:
            a = [a]
        if type(b) == int:
            b = [b]
        for i, j in zip(a, b):
            c = self.compare(i, j)
            if c is not None:
                return c
        else:
            return self.compare(len(a), len(b))
        return None

    def __lt__(self, other):
        return self.compare(self.data, other.data) is True

    def __eq__(self, other):
        return self.compare(self.data, other.data) is None


def input():
    x = None
    for line in sys.stdin:
        if line == "\n":
            x = None
        elif x is not None:
            yield x, packet(json.loads(line))
        else:
            x = packet(json.loads(line))


score = 0
all_packets = []
for id, (a, b) in enumerate(input()):
    all_packets += [a, b]
    if a <= b:
        score += id + 1
print(f"Pairs in the right order : {score}")
decoder = [packet([[2]]), packet([[6]])]
s = sorted(all_packets + decoder)
print(f"Decoder Key = {(s.index(decoder[0])+1) * (s.index(decoder[1])+1)}")

Je n'ai pas songé à split("\n\n"), ça fait que j'ai une première partie qui bosse en flux, mais comme pour la seconde il faut trier, on est obligé d'avoir toutes les données chargées, change rien.
Et ma fonction de comparaison est très centrée sur l'exercice : a < b c'est True, a > b c'est False et a == b c'est None, ergo on poursuit. C'est plus propre de faire -1/0/1.

Yth.

[^] # Re: python, en trichant

Posté par Yth (Mastodon) le 13 décembre 2022 à 15:06. Évalué à 2.

On peut faire un truc rigolo sur la partie travail, on garde packet et input() identiques, et on reste sur du générateur/itérateur jusqu'à la fin avec le sort :

def analyse(decoder):
    score = 0
    for id, (a, b) in enumerate(input()):
        yield a
        yield b
        if a <= b:
            score += id + 1
    print(f"Pairs in the right order : {score}")
    for d in decoder:
        yield d


decoder = [packet([[2]]), packet([[6]])]
s = sorted(analyse(decoder))
print(f"Decoder Key = {(s.index(decoder[0])+1) * (s.index(decoder[1])+1)}")

Yth, pour le fun…

Suivre le flux des commentaires

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