Forum Programmation.autre Advent of Code 2023, day 7

Posté par Yth (Mastodon) le 07 décembre 2023 à 10:21. Licence CC By‑SA.

Étiquettes :

déc.

2023

C'est l'aventure, la vraie, notre voyage vers Desert Island, les bords du Nil-dans-les-nuages, croisière tout compris, hôtel de luxe, etc, ben en fait c'est un aller-simple pour les dunes, sous le cagnard torride de cet hiver nuageux, à dos de dromadaire.

Et là, paf, un elfe qui nous demande les morceaux de machine piur réparer la machine à faire des trucs pour que des bidules se passent et qu'on ait enfin de la neige loin d'ici.

Si vous vous demandez quelles parties de quelle machine, z'en êtes au même point que moi.
Comme l'elfe en question a pas l'air plus malin que ses copains, on va jouer au poker, à dos de dromadaire, donc une version spéciale du poker.
Avec des cartes spéciales : 2 à 9, valet, pas-enore-joker, dame, roi, et as, dans l'ordre de puissance.

On a une main de cinq cartes et on compare les figures :
- toutes différentes ;
- une paire ;
- deux paires ;
- brelan ;
- full ;
- carré ;
- carré-à-5-carte-des-tricheurs.
Oui, en fait on joue sans les couleurs, l'elfe doit être dischromatopsique, ou alors le soleil affadi tellement les couleurs qu'on ne les reconnait plus depuis le temps.
Et on mélange les paquets, donc on peut avoir 5 cartes identiques, et on sait bien ce qu'il arrive aux cowboys qui sortent 5 as au poker, ils gagnent un cinquième trou de balle, et rendent visite au croque-mort.

Bref, pas ici apparemment.

Et alors la subtilité, c'est qu'on ne trie pas ses cartes, l'ordre compte quand deux mains sont du même type.
Par exemple A2222 et 99997, deux carrés, un de 2 et l'autre de 9, et bien c'est celui de 2 qui l'emporte parce que la main commence par un As qui est plus balaise que le 9.

Autant dire que c'est un poker pour surchauffés cérébraux, les insolations doivent être communes dans les parages.

Bref, on s'entraîne en triant des mains de pas-tout-à-fait-poker, savoir laquelle est plus forte que l'autre.

Et là, coup de symbale, coup de théatre, ou encore un de ces mauvais joueurs qui ne te donnent pas une règle super spéciale avant de t'avoir mis minable : la carte que j'ai fort (peu) subtilement nommée « pas-enore-joker » est un joker.
Elle ne vaut rien au classement, mais se combine avec n'importe quelle autre carte pour déterminer le type de main, qui va de fait devenir meilleure et être mieux classée.
Ah, bah on comprend mieux comment on peut avoir cinq cartes identiques maintenant !
Parce qu'en y regardant de plus près, dans les mains fournies, on n'a jamais 5 cartes identiques, on aurait donc pu flairer le piège et se douter qu'il y avait un Joker dans la liste des cartes.

Bref, tout ça fait passer le temps, pendant qu'on brûle sous le soleil nuageux du désert dans les airs.

Allez, à vos modélisations :)

Yth.

# Moi, aujourd'hui, je modélise tout propre tout joli !

Posté par Yth (Mastodon) le 07 décembre 2023 à 11:11. Évalué à 2.

Surtout que quand j'ai voulu faire mon malin, j'avais une erreur que je n'ai jamais trouvée, mais qui s'est corrigée d'elle-même en remplaçant des chiffres par des trucs lisibles.
Comme quoi coder propre, contrairement à la rumeur, ben c'est utile même pour soi-même aujourd'hui.

Voilà, avec ça on corrige des bugs, et on supprime plein de commentaires devenus inutiles aussi :

from enum import IntEnum
class HandType(IntEnum):
    HighCard = 1
    OnePair = 2
    TwoPairs = 3
    ThreeOfAKind = 4
    FullHouse = 5
    FourOfAKind = 6
    FiveOfAKind = 7

Comme ça on peut comparer le HandType entre deux mains, et le plus grand est plus fort.
L'autre étape c'est de renommer les cartes pour pouvoir comparer deux mains du même type :

data = sys.stdin.read().strip().splitlines()
hands1 = (
    Hand(a.translate(str.maketrans("TJQKA", "abcde")), int(b))
    for line in data
    for a, b in [line.split()]
)

Et pour l'exercice 2, on initialise les données (hands2) tout pareil sauf qu'on fait : str.maketrans("TJQKA", "a0cde") comme ça le Joker a une valeur plus petite que les autres cartes lors de la comparaison. Et en plus on va pouvoir bosser avec la même classe Hand, et compter les Jokers, donc les "0", et comme il n'y en a pas dans les données transformées pour l'exercice 1, ça va fonctionner pour les deux !

Maintenant notre classe Hand peut être initialisée avec les données : hand et bid, et on la décore pour pouvoir ordonner directement une liste de mains. Le cached_property permet de s'assurer qu'on ne recalculera jamais deux fois le score d'une main lors de l'exécution (an pratique ça divise le temps d'exécution par 2 environ, ça aurait pu être bien pire…). On utilise une frozen dataclass parce qu'on ne modifie pas une main, là aussi c'est de l'optimisation qui peut s'avérer déterminante en cas de problème vraiment gros.

from functools import total_ordering, cached_property
from dataclasses import dataclass
@dataclass(frozen=True)
@total_ordering
class Hand:
    hand: str = ""
    bid: int = 0
    @cached_property
    def score(self):
        return some magic
    def __lt__(self, other):
        return (self.hand < other.hand) if self.score == other.score else (self.score < other.score)
    def __eq__(self, other):
        return False

Ouaip, on simplifie en disant que deux mains sont toujours différentes, à toutes fins utiles, ça va plus vite, hein ?
Parce qu'on suppose, vu l'exercice, que toutes les mains fournies sont différentes, sinon le calcul final donnera un résultat différent (sauf si elles ont le même « bid », auquel cas osef).
De plus cut -d\ -f1 < 07.input | sort -u | wc -l; wc -l 07.input nous retourne 1000 lignes pour chaque, on a donc bien des mains uniques dans les données en entrée.
En pratique on ne gagne rien, avec la cached_property sur le score, de toute façon on va calculer le score une seule fois par main, et ça coûte pas lourd comme comparaisons. Mais là aussi c'est lié finalement à la toute petite quantité de données.

Bref, il ne nous reste plus qu'à résoudre, avec la fonction sorted() qui va faire tout le boulot à notre place, magique !

ex1 = sum((i + 1) * hand.bid for i, hand in enumerate(sorted(hands1)))
ex2 = sum((i + 1) * hand.bid for i, hand in enumerate(sorted(hands2)))

Et enfin, voilà le code de la méthode Hand.score, là où on se rend compte que tous les magiciens ont leur « trucs ». Je ne sais pas si j'aurais pu faire plus « intelligent », mais c'est assez clair je pense.

    @cached_property
    def score(self):
        cards = set(self.hand)  # all kind of cards in hand
        nb = len(cards)  # number of different cards, including jokers
        jokers = self.hand.count("0")  # number of jokers in hand
        if nb == 5:  # abcde, abcd*
            return HandType.OnePair if jokers else HandType.HighCard
        if nb == 4:  # aabcd, aabc*, **abc
            return HandType.ThreeOfAKind if jokers else HandType.OnePair
        if nb == 3:  # aaabc, aabbc, aaab*, aabb*, aa**c, ***bc
            cards.discard("0")  # Jokers are already counted
            card = cards.pop()  # draw a non-joker card
            c = self.hand.count(card)
            if c == 2:  # aabbc, aabb*, aa**c
                return [HandType.TwoPairs, HandType.FullHouse, HandType.FourOfAKind][jokers]
            if c == 3:  # aaabc, aaab*
                return HandType.FourOfAKind if jokers else HandType.ThreeOfAKind
            # non-joker card U is unique: aaabU, aabbU, aaaU*, aa**U, ***bU
            card = cards.pop()
            if self.hand.count(card) == 2:  # aabbU, aa**U
                return HandType.FourOfAKind if jokers else HandType.TwoPairs
            # aaabU, aaaU*, ***bU
            return HandType.FourOfAKind if jokers else HandType.ThreeOfAKind
        if nb == 2:  # aaa**, ***aa, aaaa*, ****a
            if jokers:  # whatever, jokers makes it Five of a kind
                return HandType.FiveOfAKind
            card = cards.pop()
            if self.hand.count(card) in (2, 3):  # aaabb
                return HandType.FullHouse
            # aaaab
            return HandType.FourOfAKind
        return HandType.FiveOfAKind

Et voilà :)
Et une fois n'est pas coutume : PyPy est largement moins efficace que Python là-dessus, on passe de 70 à 370 millisecondes, même avec les 150ms de démarrage de PyPy, c'est amplement trois fois moins bon pour l'exécution en elle-même.
Dans tous les cas : pas de quoi faire chauffer la pièce à coups de CPU.

Yth.

[^] # Re: Moi, aujourd'hui, je modélise tout propre tout joli !

Posté par 🚲 Tanguy Ortolo (site web personnel) le 07 décembre 2023 à 12:03. Évalué à 3.

Je découvre cached_property, merci !

[^] # Re: Moi, aujourd'hui, je modélise tout propre tout joli !

Posté par barmic 🦦 le 10 décembre 2023 à 18:57. Évalué à 2.

Et enfin, voilà le code de la méthode Hand.score, là où on se rend compte que tous les magiciens ont leur « trucs ». Je ne sais pas si j'aurais pu faire plus « intelligent », mais c'est assez clair je pense.

Personnellement je l'ai pris en compte pendant de calcul du jocker :

fn hand_type_jocker(hand: &String) -> u8 {
    let mut counters = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0];
    for c in hand.chars().into_iter() {
        let i = CARDS_JOCKER.find(c).unwrap();
        counters[i] += 1;
    }
    let mut values = (0, 0);
    for i in 1..counters.len() {
        if counters[i] > values.0 {
            values = (counters[i], values.0);
        } else if counters[i] > values.1 {
            values = (values.0, counters[i]);
        }
    }
    let jocker = counters[0];
    values = (values.0 + jocker, values.1);
    match values {
        (5, _) => 6,
        (4, _) => 5,
        (3, 2) => 4,
        (3, _) => 3,
        (2, 2) => 2,
        (2, _) => 1,
        _ => 0,
    }
}

J'augmente la plus grand nombre de carte identique par le nombre de jocker.

https://linuxfr.org/users/barmic/journaux/y-en-a-marre-de-ce-gros-troll

# T means 10

Posté par 🚲 Tanguy Ortolo (site web personnel) le 07 décembre 2023 à 12:02. Évalué à 4.
Petite subtilité sémantique, les cartes disponibles sont 23456789TJQK, ce qui signifie :
- deux
- trois
- quatre
- …
- neuf
- dix (T pour ten, soit 10)
- valet (J pour jack)
- dame (Q pour queen)
- roi (K pour king)
La raison d'utiliser la lettre T pour le dix vient de la nécessité de l'écrire en un seul caractère. 10, ça fait deux caractères…
- [^] # Re: T means 10
  
  Posté par Yth (Mastodon) le 07 décembre 2023 à 12:18. Évalué à 2.
  Et A pour As aussi, au bout.
  - Y.
- [^] # Re: T means 10
  
  Posté par mac__ le 07 décembre 2023 à 13:09. Évalué à 1.
  
  Il est d'ailleurs probablement malin de ré-écrire les nom des cartes dans la chaîne de caractères qui correspond à une main, pour faciliter le tri en utilisant l'ordre lexicographique quand on a besoin de comparer des mains qui sont ex-aequo…
  
  Pour ma part, j'ai fait (pour la partie 1):
  
  A -> E
  K -> D
  Q -> C
  J -> B
  T -> A
  
  De même, il est aussi malin de trier les mains - ça rend le repérage des combinaisons trivial avec quelques regexp bien placées (il y a juste une subtilité pour le Full qui peut être XXXYY ou XXYYY)
# Besoin d'énumérations ordonnées

Posté par 🚲 Tanguy Ortolo (site web personnel) le 07 décembre 2023 à 14:18. Évalué à 3.
Comme j'aime bien modéliser, c'est un sujet où j'utilise naturellement des énumérations. Pour les cartes, comme pour les types de mains.
```
class Card(Enum):
    ONE   = '1'
    TWO   = '2'
    THREE = '3'
    …
    TEN   = 'T'
    JACK  = 'J'
    QUEEN = 'Q'
    KING  = 'K'
```
L'avantage en donnant aux cartes la valeur correspondant au caractère qui les représente, c'est que ça permet de les parser très facilement :
```
card = Card('A')
```
Le problème, c'est que je veux comparer les cartes. Et des énumérations, eh bien ça ne se compare pas. Pas sans implémenter au moins une fonction de comparaison. Et ça, c'est… pénible.

Je rêve donc d'une solution propre pour définir une classé énumérée dont les membres se comparent, simplement avec leur ordre de définition.
- [^] # Re: Besoin d'énumérations ordonnées
  
  Posté par 🚲 Tanguy Ortolo (site web personnel) le 07 décembre 2023 à 14:29. Évalué à 3.
  
  https://blog.yossarian.net/2020/03/02/Totally-ordered-enums-in-python-with-ordered_enum
  https://stackoverflow.com/questions/42369749/use-definition-order-of-enum-as-natural-order
- [^] # Re: Besoin d'énumérations ordonnées
  
  Posté par Yth (Mastodon) le 07 décembre 2023 à 15:24. Évalué à 2. Dernière modification le 07 décembre 2023 à 15:27.
  Une idée :
```
from enum import Enum
from functools import total_ordering

@total_ordering
class Card(Enum):
    JOKER = '*'
    ONE   = '1'
    TWO   = '2'
    THREE = '3'
    FOUR  = '4'
    FIVE  = '5'
    SIX   = '6'
    SEVEN = '7'
    EIGHT = '8'
    NINE  = '9'
    TEN   = 'T'
    JACK  = 'J'
    QUEEN = 'Q'
    KING  = 'K'
    ACE   = 'A'
    def __lt__(self, other):
        return self.weight < other.weight
    def __eq__(self, other):
        return self.weight == other.weight

for i, card in enumerate(Card):
    card.weight = i

>>> Card('A') > Card('7')
True
>>> Card('J') > Card('K')
False
>>> a = [Card(x) for x in "A2222"]
>>> b = [Card(x) for x in "99997"]
>>> a > b
True
```
  Un peu du hack puisque la définition même de la classe est bancale, et qu'il faut modifier après initialisation et avant utilisation, mais ça fonctionne.
  - Yth.
  - [^] # Re: Besoin d'énumérations ordonnées
    
    Posté par Yth (Mastodon) le 07 décembre 2023 à 15:52. Évalué à 2.
    Et en rajoutant deux lignes tu peux les utiliser dans des Set, ou en clé de dictionnaires etc :
```
  def __hash__(self):
    return self.weight
```
    Avec ça je n'ai quasiment rien à changer dans mon algorithme pour utiliser cette classe à la place des caractères "23456789abcdef" comme je l'ai fait dans ma solution.
    
    J'aime bien l'élégance de la chose, et le côté vraiment lisible, zéro hack dans le reste du code.
    Bon, par contre je n'ai besoin que de Card.JOKER de façon explicite.
    Il faut juste faire un line.replace(Card.JACK.value, Card.JOKER.value pour la seconde partie de l'exercice, à la place des a.translate(str.maketrans("TJQKA", "a0cde")), c'est plus joli.
    
    Je perd un poil en perfs par contre : 85ms au lieu de 70ms.
    Je suppose que c'est au niveau de la comparaison d'un tuple de Card par rapport à celle de deux str dans mon code initial.
    Pas très sûr, mais c'est dommage…
    - Yth.
    - [^] # Re: Besoin d'énumérations ordonnées
      
      Posté par 🚲 Tanguy Ortolo (site web personnel) le 07 décembre 2023 à 17:11. Évalué à 3.
      
      Une énumération n'est pas nativement utilisable dans des ensembles ou en clef de dictionnaire ???
      - [^] # Re: Besoin d'énumérations ordonnées
        
        Posté par Yth (Mastodon) le 07 décembre 2023 à 17:34. Évalué à 2.
        
        Ah non, ma faute, en fait il ne faut pas redéfinir __eq__(), si on le fait alors ça fait sauter le hash (enfin, disons que ça casse quelque chose quelque part) et on ne peut plus l'utiliser dans les set(), mais on n'a pas besoin de surcharger cette méthode : elle fonctionne très bien nativement.
        
        Donc on définit uniquement __lt__() avec le @total_ordering, et on est bon :)
        
        Yth.

# Python

Posté par alberic89 🐧 le 07 décembre 2023 à 20:32. Évalué à 1.

C'est très très très louche : on est un jour impair et la difficulté est raisonnable. Nous sommes trahis.
POur aujourd'hui, j'ai défini deux classes Hand et HandJoker très semblables et qui ont certains opérateurs surchargés pour pouvoir utiliser la fonction sorted().
Après les avoir triés dans des listes par catégories, ont les tris et on récupère le score.

#!/bin/python3

cardlist = {
    "A" : 14,
    "K" : 13,
    "Q" : 12,
    "J" : 11,
    "T" : 10,
}

cardlistjoker = {
    "A" : 14,
    "K" : 13,
    "Q" : 12,
    "J" : 1,
    "T" : 10,
}

class Hand:
    def __init__(self, cardstring, points, cardlist):
        self.points = points
        self.cards = []
        for i in cardstring:
            if i in cardlist.keys():
                self.cards.append(cardlist[i])
            else:
                self.cards.append(int(i))
        self.computecat()

    def computecat(self):
        r = {}
        for i in range(2,15):
            r.update({i:self.cards.count(i)})
        if 5 in r.values():
            self.cat = 0
        elif 4 in r.values():
            self.cat = 1
        elif 3 in r.values() and 2 in r.values():
            self.cat = 2
        elif 3 in r.values():
            self.cat = 3
        elif 2 in r.values() and list(r.values()).count(2) == 2:
            self.cat = 4
        elif 2 in r.values():
            self.cat = 5
        else:
            self.cat = 6

    def __lt__(self, otherhand): # self > otherhand
        for i, c in enumerate(self.cards):
            if c > otherhand.cards[i]:
                return True
            elif c < otherhand.cards[i]:
                return False
        raise ValueError

    def __gt__(self, otherhand): # self < otherhand
        for i, c in enumerate(self.cards):
            if c < otherhand.cards[i]:
                return True
            elif c > otherhand.cards[i]:
                return False
        raise ValueError

class HandJoker(Hand):

    def computecat(self):
        r = {}
        j = self.cards.count(1)
        for i in range(2,15):
            r.update({i:self.cards.count(i)})
        if (5 in r.values()) or (4 in r.values() and j == 1) or (3 in r.values() and j == 2) or (2 in r.values() and j == 3) or (j >= 4):
            self.cat = 0
        elif (4 in r.values()) or (3 in r.values() and j == 1) or (2 in r.values() and j == 2) or (j == 3):
            self.cat = 1
        elif (3 in r.values() and 2 in r.values()) or (2 in r.values() and list(r.values()).count(2) == 2 and j == 1):
            self.cat = 2
        elif (3 in r.values()) or (2 in r.values() and j == 1) or (j == 2):
            self.cat = 3
        elif (2 in r.values()) and (list(r.values()).count(2) == 2):
            self.cat = 4
        elif (2 in r.values()) or (j == 1):
            self.cat = 5
        else:
            self.cat = 6


def parse_hand(puzzle,joker=False):
    hands = []
    for h in puzzle:
        if h == "":
            continue
        if joker:
            hands.append(HandJoker(h.split()[0], int(h.split()[1]),cardlistjoker))
        else:
            hands.append(Hand(h.split()[0], int(h.split()[1]), cardlist))
    return hands

def classify(hands):
    rhands =[[],[],[],[],[],[],[],]
    for h in hands:
        rhands[h.cat].append(h)
    hands = []
    for c in rhands:
        for h in sorted(c):
            hands.append(h)
    return hands


def solve1(puzzle,testing=False):
    s=0
    hands = classify(parse_hand(puzzle))
    hands.reverse()
    for i, h in enumerate(hands):
        s+= (i+1)*h.points
    if testing:
        print(s)
    return s

def solve2(puzzle,testing=False):
    s = 0
    hands = classify(parse_hand(puzzle,joker=True))
    hands.reverse()
    for i, h in enumerate(hands):
        s+= (i+1)*h.points
    if testing:
        print(s)
    return s

test1 = """32T3K 765
T55J5 684
KK677 28
KTJJT 220
QQQJA 483
"""
result1 = 6440
test2 = test1
result2 = 5905

# 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

Suivre le flux des commentaires

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