Forum Programmation.autre Avent du Code, jour 11

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

Étiquettes :

déc.

2022

Suite de l'Avent du Code, jour 11.

Des singes ont volé le contenu de notre sac. Ils jouent à la passe à 10 avec. Pour récupérer le contenu, il faut identifier quel singes ont eu le plus d'items en main.

Un jour où la solution naïve permet de résoudre la partie 1 mais ne passe pas à l'échelle pour la partie 2.

# python, on oublie toute dignité

Posté par steph1978 le 11 décembre 2022 à 13:39. Évalué à 3. Dernière modification le 11 décembre 2022 à 13:39.
Je suis tombé dans le piège de la solution qui ne scale pas en deuxième partie. Pas grave, on s'adapte.

Pour les deux parties, pour éviter un parsing laborieux, j'ai transformé l'input en code. Car à bien y regarder, c'est du code :)

La solution naïve ne scale pas car passé une certaine taille (32bit je crois) l'arithmétique des grands entiers sort du processeur, doit repasser par la mémoire et devient très très lente.

Chez moi c'était très net : les 500 premiers rounds sont fulgurants, moins de 1s, puis chaque round prends presque une seconde. Pour faire les 100000, en admettant avoir assez de RAM, il faudrait donc une grosse heure à 100% de CPU. Je n'ai pas cette patience.

L'astuce pour passer à l'échelle est de limiter la taille des nombres manipulés en appliquant l'arithmétique modulaire. Chaque singe à son diviseur (un nombre premier mais je crois pas que ça joue). Donc au lieu d'avoir l'item sous forme de nombre, on le transforme en une liste de restes de division, un pour chaque singe.

part 1

Je vous épargne le code complet de la première partie qui est en gros celui de la deuxième partie en un peu plus simple.

input
```
from collections import deque
M = [
(
    deque([ 84, 72, 58, 51])
  , lambda old:  old * 3
  , lambda x: 7 if divmod(x,13)[1] else 1
)
# ...
# same for all monkeys
# ...
]
```
part 2

input
```
from collections import deque

PRIMES = (13,2,7,17,5,11,3,19)

def mods(x):
    return [x%i for i in PRIMES]

M = [
[
    deque(mods(x) for x in [ 84, 72, 58, 51])
  , lambda old: [((o%i)*(3%i))%i for (o,i) in zip(old,PRIMES)]
  , lambda x: 7 if x[0] else 1
  ,0
],[
    deque(mods(x) for x in [ 88, 58, 58 ])
  , lambda old: [((o%i)+(8%i))%i for (o,i) in zip(old,PRIMES)]
  , lambda x: 5 if x[1] else 7
  ,0
]# ...
# same for all monkeys
# ...
]
```
main loop
```
import sys
mod = __import__(sys.argv[1])

M = mod.M
for r in range(10*1000):
    print(f"\rround {r+1}",end='')
    for m in M:
        items = m[0]
        m[3] += len(items)
        for _ in range(len(items)):
            i = items.popleft()
            ni = m[1](i) #// 3
            nm = m[2](ni)
            M[nm][0].append(ni)
print()

L=list(sorted(m[3] for m in M))
print(L[-1]*L[-2])
```
- [^] # Re: python, on oublie toute dignité
  
  Posté par GuieA_7 (site web personnel) le 11 décembre 2022 à 13:46. Évalué à 2.
  
  sorted renvoie déjà une liste: https://docs.python.org/3.8/library/functions.html#sorted
  - [^] # Re: python, on oublie toute dignité
    
    Posté par steph1978 le 11 décembre 2022 à 14:11. Évalué à 2. Dernière modification le 11 décembre 2022 à 14:13.
    
    Mince alors, toute une matinée de code à mettre à la benne 😩
    
    Blague à part, merci pour la remarque, je confonds probablement avec map ou reversed qui retournent un itérateur.
    
    J'imagine que pour trier, il faut charger toutes les données, donc pas d'intérêt de retourner un itérateur. Ou alors ne pas chercher d'explication, l'API python n'est pas toujours cohérente.
    - [^] # Re: python, on oublie toute dignité
      
      Posté par GuieA_7 (site web personnel) le 11 décembre 2022 à 21:45. Évalué à 2.
      
      J'imagine que pour trier, il faut charger toutes les données, donc pas d'intérêt de retourner un itérateur.
      
      Oui certainement, ça serait hypocrite de faire croire que la fonction arrive à travailler 'en flux' (sans tout charger) alors que ce n'est pas possible. Et derrière si tu veux un itérateur sur la liste retournée c'est très peu coûteux de te le faire (alors que le contraire est moins vrai).
- [^] # Re: python, on oublie toute dignité
  
  Posté par steph1978 le 11 décembre 2022 à 18:39. Évalué à 2.
  
  En poussant un peu plus la réflexion sur l’arithmétique modulaire, on peut se passer de balader des listes et garder un nombre. Trop tard pour moi :)

# À la chasse aux singes, j'envoie le Python !

Posté par Yth (Mastodon) le 11 décembre 2022 à 18:11. Évalué à 3.

Pour le « truc qui scale pas » de la seconde partie, un bug dans la première partie m'a fait tomber dessus très tôt, et la solution est assez simple.

Un mélange de propre et de hack tout moche pour celui-là, avec un affichage qui montre l'avancement des calculs, ya 9s pour la seconde partie tout de même…

import sys
from collections import deque, OrderedDict
import math
def input():
    operations = {
        "Starting items": "items",
        "Operation": "operation",
        "Test": "test",
        "If true": "true",
        "If false": "false",
    }
    monkey = {}
    for line in sys.stdin:
        if line == "\n":
            yield monkey
            monkey = {}
            continue
        operation, value = line.strip().split(":")
        monkey[operations.get(operation, "monkey")] = (
            value or int(operation.split()[-1]))
    yield monkey

class Monkey:
    relief = 3
    modulo = None
    def __init__(self, monkey, items, operation, test, true, false):
        self.id = monkey
        self.items = deque([int(x) for x in items.split(',')])
        self.operation = operation.split("=", 1)[1]
        self.test = int(test.split()[-1])
        self.true = int(true.split()[-1])
        self.false = int(false.split()[-1])
        self.inspection = 0
    def __call__(self):
        self.inspection += 1
        item = self.items.popleft()
        worry = eval(self.operation.replace("old", str(item))) // self.relief
        if self.modulo:
            worry = worry % self.modulo
        return self.false if worry % self.test else self.true, worry
    def __add__(self, n):
        self.items.append(n)
    def __repr__(self):
        return (
            f"Monkey#{self.id}@{self.inspection}:{self.operation}"
            f" % {self.test} ? {self.true} : {self.false}"
            f" => {list(self.items)}"
        )
    def __bool__(self):
        return len(self.items) != 0
    def __gt__(self, other):
        return self.inspection > other.inspection

def monkey_simulation(
        rounds, input,
        relief=3, modulo=None,
        skiplines=0, show_monkeys=True):
    Monkey.relief = relief
    Monkey.modulo = modulo
    monkeys = OrderedDict(sorted(
        (monkey['monkey'], Monkey(**monkey))
        for monkey in inputmonkeys
    ))
    if show_monkeys:
        print("\033[0;0H", end='')
        print("\n".join([repr(m) for m in monkeys.values()]))
        skiplines += len(monkeys) + 1
    movecursor = f"\033[{skiplines};0H"
    for round in range(rounds):
        print(f"{movecursor}Round #{round}")
        for monkey in monkeys.values():
            while monkey:
                dst, worry = monkey()
                monkeys[dst] + worry
    b1, b2 = [m.inspection for m in sorted(monkeys.values())[-2:]]
    print(f"Monkey business level: {b1*b2}")
    return skiplines + 2, math.prod(monkey.test for monkey in monkeys.values())

inputmonkeys = [line for line in input()]
skiplines, modulo = monkey_simulation(20, inputmonkeys)
print(f"Global modulo = {modulo}")
monkey_simulation(10000, inputmonkeys, 1, modulo, skiplines+1, False)

L'idée pour la seconde passe c'est que tout peut se passer au modulo du produit de tous les modulos. Même au PGCM de tous les modulos des différents singes, mais le produit suffit, on a des nombres suffisamment petits pour que ça roule vite et bien.

Donc la première passe retourne ce produit des modulos, qui est nourri à la seconde passe, en modifiant la classe de base avant instanciation des nouveaux singes.
Joli hack bien crade quoi :)

Après on a quelques bidouilles d'affichage pour lister les singes et faire défiler le n° de round, et ainsi voir l'avancement des calculs.

Et bien sûr, le cœur du problème avec un bon gros eval sur l'opération à effectuer, sinon c'pas drôle !

Yth.

[^] # Re: À la chasse aux singes, j'envoie le Python !

Posté par 🚲 Tanguy Ortolo (site web personnel) le 11 décembre 2022 à 21:07. Évalué à 4.

Je n'ai pas encore résolu le problème de ce jour, dimanche c'est famille, mais ça va venir. 🙂

En lisant l'énoncé, tout de même, je m'étais dit que ça devait faire des nombres qui monteraient bien vite. En y réfléchissant, je pense que j'aurais tout seul pensé à travailler modulo leur PGCD.

Pour le code d'opération, l'eval vient tout de suite en tête bien sûr, mais ça me donne quand même quelques boutons, d'écrire du code qui a l'air d'un trou de sécurité. Réflexe professionnel je pense. À suivre, je dois toujours coder ça de toute façon.
- [^] # Re: À la chasse aux singes, j'envoie le Python !
  
  Posté par 🚲 Tanguy Ortolo (site web personnel) le 12 décembre 2022 à 08:04. Évalué à 3.
  
  Euh, modulo leur PPCM évidemment !
- [^] # Re: À la chasse aux singes, j'envoie le Python !
  
  Posté par Yth (Mastodon) le 12 décembre 2022 à 13:54. Évalué à 2.
  Ah oui, j'ai sorti l'eval avec réticence, mais c'est tellement adapté à ce cas précis…
  
  Professionnellement il faudrait salement valider la chaîne, et probablement qu'un parseur aurait été la solution, pour ne pas faire d'eval.
  - Yth, PGPM, PPCD, rhaaa, c'pareil quoi, le lecteur aura corrigé de lui-même !
[^] # Re: À la chasse aux singes, j'envoie le Python !

Posté par GuieA_7 (site web personnel) le 11 décembre 2022 à 22:36. Évalué à 4.

À noter que str.join() prend juste un itérable, et donc "\n".join([repr(m) for m in monkeys.values()]) peut s'écrire plus simplement "\n".join(repr(m) for m in monkeys.values()).
Même remarque avec deque().

# En Python, avec un parseur d'opération

Posté par 🚲 Tanguy Ortolo (site web personnel) le 12 décembre 2022 à 14:33. Évalué à 4.

from __future__ import annotations

import itertools
import math
import re

from typing import Callable, Iterable, Iterator, List, Tuple


class Test:
    def __init__(self, div: int, rcpt1: int, rcpt2: int):
        self.div = div
        self.rcpt1 = rcpt1
        self.rcpt2 = rcpt2

    def __call__(self, n: int):
        if n % self.div == 0:
            return self.rcpt1
        else:
            return self.rcpt2


class Monkey:
    def __init__(self, number: int, items: List[int], op: Callable[[int], int], test: Test) -> None:
        self.number = number
        self.items = items
        self.op = op
        self.test = test
        self.activity = 0

    _re_monkey = re.compile(r'^Monkey (\d+):?\n?$')
    _re_items = re.compile(r'^\s*Starting items: (.*)\n?$')
    _re_op = re.compile(r'^\s*Operation: (.*)\n?$')
    _re_test = re.compile(r'^\s*Test: divisible by (\d+)\n?$')
    _re_true = re.compile(r'^\s*If true: throw to monkey (\d+)\n?$')
    _re_false = re.compile(r'^\s*If false: throw to monkey (\d+)\n?$')

    @classmethod
    def import_lines(class_, lines: Iterable[str]) -> Monkey:
        lines = iter(lines)
        number = int(class_._re_monkey.match(next(lines)).group(1))
        items = [int(word) for word in class_._re_items.match(next(lines)).group(1).split(', ')]
        op = import_op(class_._re_op.match(next(lines)).group(1))
        div = int(class_._re_test.match(next(lines)).group(1))
        rcpt1 = int(class_._re_true.match(next(lines)).group(1))
        rcpt2 = int(class_._re_false.match(next(lines)).group(1))
        test = Test(div, rcpt1, rcpt2)
        return class_(number, items, op, test)


def group_key() -> Callable[[str], int]:
    key = 0
    def aux(line: str):
        nonlocal key
        if line.rstrip() == '':
            key += 1
        return key
    return aux


def group_lines(lines: Iterable[str]) -> Iterable[Iterable[str]]:
    for _, group in itertools.groupby(lines, group_key()):
        yield (line for line in group if line.rstrip() != "")


_re_op_unary = re.compile("^new = old ([+*]) (\d+)$")
_re_op_binary = re.compile("^new = old ([+*]) old$")
def import_op(line: str) -> Callable[[int], int]:
    if (m := _re_op_unary.match(line)) is not None:
        arg = int(m.group(2))
        if m.group(1) == '+':
            return lambda old: old + arg
        if m.group(1) == '*':
            return lambda old: old * arg
        raise ValueError("unrecognized operator")
    if (m := _re_op_binary.match(line)) is not None:
        if m.group(1) == '+':
            return lambda old: 2 * old
        if m.group(1) == '*':
            return lambda old: old ** 2
        raise ValueError("unrecognized operator")
    raise ValueError("unrecognized operation arity")


class Game:
    def __init__(self, monkeys: dict[int, Monkey]) -> None:
        self.monkeys = monkeys

    def round(self) -> None:
        for monkey in self.monkeys.values():
            for item in monkey.items:
                item = monkey.op(item)
                item //= 3
                rcpt = monkey.test(item)
                monkey.activity += 1
                self.monkeys[rcpt].items.append(item)
            monkey.items = []

    @classmethod
    def import_lines(class_, lines: Iterable[str]) -> Game:
        monkeys = {}
        for group in group_lines(lines):
            monkey = Monkey.import_lines(group)
            monkeys[monkey.number] = monkey
        return class_(monkeys)

    def business(self) -> int:
        activity = sorted(monkey.activity for monkey in self.monkeys.values())
        return activity[-1] * activity[-2]


class Game2(Game):
    def __init__(self, *args, **kwargs) -> None:
        super().__init__(*args, **kwargs)
        self.div = math.lcm(*(monkey.test.div for monkey in self.monkeys.values()))

    def round(self) -> None:
        for monkey in self.monkeys.values():
            for item in monkey.items:
                item = monkey.op(item) % self.div
                rcpt = monkey.test(item)
                monkey.activity += 1
                self.monkeys[rcpt].items.append(item)
            monkey.items = []


def solve1(lines: Iterable[str]) -> int:
    """Solve part 1 of today's puzzle"""
    game = Game.import_lines(lines)
    for _ in range(20):
        game.round()
    return game.business()


def solve2(lines: Iterable[str]) -> int:
    """Solve part 2 of today's puzzle"""
    game = Game2.import_lines(lines)
    for _ in range(10000):
        game.round()
    return game.business()

Suivre le flux des commentaires

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

part 1

input

part 2

input

main loop