Forum Programmation.autre Avent du Code, jour 23

Posté par Yth (Mastodon) le 23 décembre 2022 à 13:03. Licence CC By‑SA.

Étiquettes :

déc.

2022

On a enfin retrouvé nos Lutinelfes !
Dans le verger magique aux fruits étoilés.
Super !

Sauf que quand on a déréglé le Volcan pour survivre et sauver les éléphants, en ouvrant les valves de vapeur, ben… On a déréglé le volcan, donc là il n'est pas en éruption.
Oups…
Les fruits vont pas bien pousser !

Les Elfes vont malgré tout planter leurs arbustes dans les cendres volcaniques, et pour ça s'éparpiller gaiement jusqu'à être bien isolés les uns des autres.

Pour ça ils tournent en rond, et n'avancent que si la voie est vraiment bien libre dans une direction.

On s'arrête quand les elfes sont contents et ne bougent plus.

Youpi !

Yth.

# Mes conseils...

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

Ne pas modifier un set() pendant qu'on itère ce même set().

Vérifier notre index d'itération, des fois qu'il indique la dernière itération a avoir vue des changements plutôt que la première itération où personne n'a bougé.

Après 3h à traquer un bug pourri (j'ai vraiment le cerveau en rade), une simple simulation avec une jolie modélisation fonctionne sans lourdeur, pas de données extraordinaires ni de surcharge CPU ici, juste de la méthode, des intersections d'ensembles, et une jolie image.

Titre de l'image

for elf in elves:
    if elf.choice in ok:
        elves.remove(elf)
        elves.add(elf.choice)

Hein que c'est pourrave et qu'on voit pas vite les effets du bidule quand ça fonctionne sur deux rounds de validation ?
Bref : for elf in elves.copy() pour faire vite.
Ou mieux :

move = {elf for elf in elves if elf.choice in ok}
moveto = {elf.choice for elf in move}
elves.difference_update(move)
elves.update(moveto)

Yth.

[^] # Re: Mes conseils...

Posté par Yth (Mastodon) le 23 décembre 2022 à 13:33. Évalué à 2. Dernière modification le 23 décembre 2022 à 13:34.

@dataclass(frozen=True)
class Direction:  # Sur-modélisation de la direction
    d: int
    @classmethod
    def init(cls):
        cls.N = Direction(0)
        cls.S = Direction(1)
        cls.W = Direction(2)
        cls.E = Direction(3)
        return [cls.N, cls.S, cls.W, cls.E]
    @classmethod
    @cache
    def get(cls, d):
        return cls.init()[d % 4]
    @cached_property
    def next(self):
        return Direction.get(self.d + 1)
    def __str__(self):
        return "NSWE"[self.d]

class Elf(tuple):  # Modélisation failsafe d'une position d'elfe.
    @cached_property
    def col(self):
        return self[0]
    @cached_property
    def row(self):
        return self[1]
    @cached_property
    def enw(self):
        return Elf((self.col - 1, self.row - 1))
    @cached_property
    def en(self):
        return Elf((self.col, self.row - 1))
    @cached_property
    def ene(self):
        return Elf((self.col + 1, self.row - 1))
    @cached_property
    def ew(self):
        return Elf((self.col - 1, self.row))
    @cached_property
    def ee(self):
        return Elf((self.col + 1, self.row))
    @cached_property
    def esw(self):
        return Elf((self.col - 1, self.row + 1))
    @cached_property
    def es(self):
        return Elf((self.col, self.row + 1))
    @cached_property
    def ese(self):
        return Elf((self.col + 1, self.row + 1))
    @cached_property
    def around(self):
        return {self.enw, self.en, self.ene, self.ew, self.ee, self.esw, self.es, self.ese}
    @cached_property
    def N(self):
        return {self.enw, self.en, self.ene}
    @cached_property
    def S(self):
        return {self.esw, self.es, self.ese}
    @cached_property
    def W(self):
        return {self.enw, self.ew, self.esw}
    @cached_property
    def E(self):
        return {self.ene, self.ee, self.ese}
    def look(self, d):
        return [self.N, self.S, self.W, self.E][d.d]
    def go(self, d):
        return [self.en, self.es, self.ew, self.ee][d.d]
    def choose(self, direction, elves):
        for _ in range(4):
            if self.look(direction).isdisjoint(elves):
                return self.go(direction)
            direction = direction.next

def inputs(data):
    return {
        Elf((col, row))
        for row, r in enumerate(data.splitlines())
        for col, c in enumerate(r)
        if c == "#"
    }


def dimension(elves):
    return (
        min(e.col for e in elves),
        max(e.col for e in elves),
        min(e.row for e in elves),
        max(e.row for e in elves),
    )


def iteration(elves, direction, debug=False):
    considering = set()
    blocked = set()
    for elf in elves:
        if elf.around.isdisjoint(elves):
            elf.choice = None
            continue
        elf.choice = elf.choose(direction, elves)
        if not elf.choice:
            continue
        if elf.choice in considering:
            blocked.add(elf.choice)
            elf.choice = None
        else:
            considering.add(elf.choice)
    considering.difference_update(blocked)
    move = {elf for elf in elves if elf.choice in considering}
    moveto = {elf.choice for elf in move}
    elves.difference_update(move)
    elves.update(moveto)
    return len(considering)

Direction.init()
direction = Direction.N
elves = inputs(sys.stdin.read())
round = 0
while iteration(elves, direction):
    round += 1
    direction = direction.next
    if round == 10:
        c0, c1, r0, r1 = dimension(elves)
        print(f"Empty Spaces at Round 10 = {(c1 - c0 + 1) * (r1 - r0 + 1) - len(elves)}")
print(f"Ended at round {round+1}")

Simple, propre, impossible de se planter, tout est clair, tout est sur-validé. Et ça fonctionne.
Mon bug c'est parce que j'avais fait une boucle pour afficher du debug.
Sinon j'aurais pas fait de boucle, et utiliser des set.difference/update comme dans le code présenté…
Pfff…

Ah, oui, partir sur une classe dérivée de tuple pour les Elfes, c'est évidemment pour pouvoir utiliser les fonctions d'ensemble, très simples et efficaces, sans avoir à coder quoi que ce soit de compliqué, ou réinventer la roue !

Yth.

[^] # Re: Mes conseils...

Posté par Yth (Mastodon) le 23 décembre 2022 à 15:14. Évalué à 2.
Et une autre image pour valider visuellement les résultats de test, avec la solution finale du test au round 20.
- Yth.

[^] # Re: Mes conseils...

Posté par Yth (Mastodon) le 23 décembre 2022 à 15:20. Évalué à 2.
Et les données initiales qui donnent le résultat vu plus haut après 881 itérations !
- Yth.
- [^] # Re: Mes conseils...
  
  Posté par alkino le 23 décembre 2022 à 16:09. Évalué à 2.
  
  Chanceux, j'étais à 992 secondes !
  - [^] # Re: Mes conseils...
    
    Posté par Eric P. le 24 décembre 2022 à 01:14. Évalué à 1. Dernière modification le 24 décembre 2022 à 01:14.
    
    889 rounds pour moi.
    Et mon programme prend moins de 2s.
    Il n'est pas tres different des votres, mais je stocke les coordonnees des Elfs dans un dictionary a la place d'un set, car la plupart des acces se font a key connue. Je me suis dit qu'un acces par key serait plus rapide qu'un 'in' sur un set qui parcourerait le set.
    Ce qui est en fait faux, d'apres https://wiki.python.org/moin/TimeComplexity
    Le set etant implemente comme un hash table, en moyenne un in dans un set est en O(1).
    
    Cela dit mon implementation etant presque instantanee je n'ai rien eu a faire pour la partie 2.
    
    Excusez l'absence d'accents dans mes commentaires, j'habite en Australie et n'ai pas de clavier francais sous la main.

# ready, set, python

Posté par steph1978 le 23 décembre 2022 à 18:14. Évalué à 4. Dernière modification le 23 décembre 2022 à 18:15.

Pas si difficile aujourd'hui mais j'ai butté sur à peut prêt toutes les instructions
- ah si un elf peut bouger partout alors il ne bouge pas ?!
- ah les directions changent a chaque tour ?!
- mais qu'est ce qu'il se passe au bord ?
- ah la grille est infinie ?!

Ce dernier point m'a contraint à changer ma conception : d'une matrice à un set. Moins sympa pour débuguer mais nécessaire quand on ne connaît pas les limites du jeu. Finalement un code plus simple car pas de gestion de dépassement, et utilisation des fonctions de set (appartenance, union, différences) et des list comprehension un peu partout. Et accessoirement beaucoup plus rapide : 1025 round en 8s pour le tout.

python, 60 loc

import sys

E = set()  # elves
for y,l in enumerate(sys.stdin.read().splitlines()):
    for x,c in enumerate(l):
        if c == '#':
            E.add((y,x))

def can(y,x):
    can1 = (y-1,x-1) not in E
    can2 = (y-1,x) not in E
    can3 = (y-1,x+1) not in E
    can4 = (y,x+1) not in E
    can5 = (y+1,x+1) not in E
    can6 = (y+1,x) not in E
    can7 = (y+1,x-1) not in E
    can8 = (y,x-1) not in E
    return [can1,can2,can3,can4,can5,can6,can7,can8]

def canN(y,x,can1,can2,can3,can4,can5,can6,can7,can8):
    if can1 and can2 and can3:
        return (y-1,x)
def canS(y,x,can1,can2,can3,can4,can5,can6,can7,can8):
    if can5 and can6 and can7:
        return (y+1,x)
def canW(y,x,can1,can2,can3,can4,can5,can6,can7,can8):
    if can7 and can8 and can1:
        return (y,x-1)
def canE(y,x,can1,can2,can3,can4,can5,can6,can7,can8):
    if can3 and can4 and can5:
        return (y,x+1)

from collections import deque
dirs = deque([canN,canS,canW,canE])
for r in range(int(sys.argv[1])):
    P = dict()
    for e in E:  # each elve
        (y,x) = e
        moves = [ d(y,x,*can(y,x)) for d in dirs ]
        if all(m is not None for m in moves):
            continue
        if all(m is None for m in moves):
            continue
        p = next(filter(lambda m: m is not None, moves))
        if p not in P: # can move
            P[p] = (y,x)
        else: # occupied, invalidate move
            P[p] = None
    moved = { v for k,v in P.items() if v is not None }
    newpos = { k for k,v in P.items() if v is not None }
    if r+1 == 10:
        minx = min(x for (x,_) in E)
        maxx = max(x for (x,_) in E)
        miny = min(y for (_,y) in E)
        maxy = max(y for (_,y) in E)
        print((maxx-minx+1) * (maxy-miny+1)  - len(E))
    if len(newpos) == 0:
        print(f"no move after {r+1}")
        break
    E = (E - moved) | newpos
    dirs.rotate(-1)

[^] # Re: ready, set, python

Posté par steph1978 le 23 décembre 2022 à 23:05. Évalué à 5.

En image

J'arrive pas à comprendre en partant de l'input et de règles pourquoi ça se propage pas uniformément mais privilégie la direction en bas à droite.

# Dans l'ensemble, c'est plus simple que l'an dernier

Posté par syj le 24 décembre 2022 à 00:16. Évalué à 2.

Dans l'ensemble, ils sont tous beaucoup plus simple que l'an dernier.

Environ 1h40 après 12h de voiture + ma crève qui ne me lâche pas, on va dire que çà aurait pu être pire.

Dans l'ensemble , il n'y a rien de compliqué aujourd'hui. Il faut juste conserver à l'esprit toutes les petites règles qui ne sont pas flag en gras dans la description.

Résultat, j'ai perdu 30min à comprendre que quand il n'y a pas d'Elf autour. Il ne bouge pas.

La deuxième partie, elle ne rajoute rien de dur, je m'attendais à une règle genre distance, ou un truc qui faisait exploser la volumétrie.

Mais non rien, j'ai juste lancé mon programme pas du tout optimisé en me disant il va falloir que je trouve une opti.
Je n'ai pas eu le temps de finir d'écrire la première opti que j'avais déjà la solution.

1min20 pour 1014 round

Suivre le flux des commentaires

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