Forum Programmation.autre Advent of Code, jour 15

Posté par Yth (Mastodon) le 15 décembre 2023 à 09:38. Licence CC By‑SA.

Étiquettes :

déc.

2023

Remettre la production de lave en route

D'accord, j'ai été un peu rapide dans mon interprétation d'hier, on avait simplement focalisé la lumière du soleil vers le chambre de fusion.
Là il faut calibrer les lentilles de focalisation pour condenser les rayons au maximum et faire, enfin, fondre la roche.

Première étape : courir après un renne qui a piqué une page du manuel.

Pour ça on va calculer une sorte de hash d'une série d'instructions du type :

rn=1,cm-,qp=3,cm=2,qp-,pc=4,ot=9,ab=5,pc-,pc=6,ot=7

Pour chaque instruction, par exemple rn=1 le hash est une formule quelconque : on prend la valeur ASCII de chaque caractère, multipliée par 17, congrue à 256, et on ajoute la suivante, on multiplie par 17, on congrue à 256, etc.
En C ça doit donner:

unsigned char hash = 0
for i=0; i<strlen(step); i++):
  hash = (hash + step[i]) * 17

Voilà, on additionne tout ça (mais dans un int ce coup-ci), et hop, 1320.
Dès qu'on crie "1320 !" au renne, il s'arrête et nous rend la page volée.
Enfin… Il faut faire ça avec un jeu de données à peine plus grand, il y a 4000 instructions.

Seconde étape, réaligner les focales, focaliser les alignements, converger, etc.

Donc on a 256 boîte, totalement optimisé pour les codeurs C, et on va suivre les instructions, pour placer, ou modifier, des lentilles dans chaque boîte.
On ne fait pas de réorganisation complexe, on remplace une lentille avec un label identique, ou on l'ajoute au bout, ou alors on retire une lentille avec un label donné.

Le HASH du label donne la boîte où on va travailler, donc un label correspond toujours à une boîte, c'est bien rangé.

Et puis après on calcule une somme de contrôle pour valider qu'on a bien mis les lentilles au bon endroit.

Bilan, c'est presque un exercice de jour 1, ou 2, aucune optimisation, aucune réflexion, on applique bêtement les opérations, et le plus fort est celui qui se lève à 6h du matin !

Yth.

# En express aujourd'hui

Posté par Yth (Mastodon) le 15 décembre 2023 à 09:46. Évalué à 2.
```
from sys import stdin
from collections import OrderedDict
def HASH(step):
  r = 0
  for x in step:
    r = ((r + ord(x)) * 17) % 256
  return r

sequence = stdin.read()).strip().split(",")
ex1 = sum(HASH(step) for step in sequence)
boxes = [OrderedDict() for _ in range(256)]
for step in sequence:
  if step[-1] == "-":
    label = step[:-1]
    boxes[HASH(label)].pop(label, 0)
  else:
    label = step[:-2]
    boxes[HASH(label)][label] = int(step[-1])
ex2 = sum(
  (i + 1) * (j + 1) * lens
  for i, box in enumerate(boxes)
  for j, lens in enumerate(box.values())
)
```
Si le problème était vraiment très grand, on pourrait mettre un cache sur la fonction HASH, puisqu'on va pas mal tourner avec les mêmes HASH.
Là, bof, ça fait peut-être passer de 0,04+-0,005 à 0,03+-0,005 secondes, autant dire que le CPU a refroidi pendant le traitement.
- Yth, à la rigueur, si j'avais eu ce problème demain, vu que je vais devoir coder sur mon téléphone, en marchant, j'aurais pas été déçu, mais là…
- [^] # Re: En express aujourd'hui
  
  Posté par steph1978 le 16 décembre 2023 à 00:09. Évalué à 2.
  
  Tu m'évites un copier-coller :) Aux noms des variables près, j'ai exactement le même code.
  
  Reposant aujourd'hui :)

# Solution en Haskell

Posté par Guillaume.B le 15 décembre 2023 à 10:55. Évalué à 2.

Problème très simple aujourd'hui. Aucune subtilité algorithmique ou autre astuce à avoir.
Juste un petit détail, j'ai pensé à utiliser, pour représenter les boites, des hashmaps avec pour clé des strings (les labels) et pour valeur des ints (les longueurs focales).
Petit problème, les HashMap de la librairie containers ne préservent pas l'ordre d'insertion, cet ordre étant nécessaire pour calculer le "focusingPower".
J'ai donc utilisé des HashMaps d'une librairie tierce qui, elles, préservent l'ordre d'insertion.
250 microseconds pour la partie 1 et 600 microseconds pour la partie 2.
Je pense que ce serait plus performant si j'utilisais des structures de données mutables mais ce serait moins joli.

data Operation = Remove | Insert !Int
data Step = Step !String !Operation
type Box = HMap.InsOrdHashMap String Int
type Boxes = IntMap Box

stepToString :: Step -> String
stepToString (Step str Remove) = str ++ "-"
stepToString (Step str (Insert n)) = str ++ "=" ++ show n

parser :: Parser [Step]
parser = step `sepEndBy1` "," where
    step = Step <$> some lowerChar <*> operation
    operation = Remove <$ "-" <|> Insert <$> ("=" *> decimal)

hash :: String -> Int
hash = foldl' go 0 where
    go acc ch = (acc + ord ch) * 17 `mod` 256

part1 :: [Step] -> Int
part1 = sum . map (hash . stepToString)

hashmapStep :: Boxes -> Step -> Boxes
hashmapStep boxes (Step label instr) = case instr of
    Remove -> IntMap.adjust (HMap.delete label) k boxes 
    Insert len -> IntMap.adjust (HMap.insert label len) k boxes
    where k = hash label

focusingPower :: Boxes -> Int
focusingPower boxes = sum [ (i+1) * j * len 
                          | (i, box) <- IntMap.toList boxes
                          , (j, (_, len)) <- zip [1..] (HMap.toList box)
                          ]
part2 :: [Step] -> Int
part2 = focusingPower . foldl' hashmapStep initialBoxes where
    initialBoxes = IntMap.fromList (zip [0..] (replicate 256 HMap.empty))

solve :: Text -> IO ()
solve = aoc parser part1 part2

[^] # Re: Solution en Haskell

Posté par Yth (Mastodon) le 15 décembre 2023 à 12:25. Évalué à 2.
En python3 récent (je sais plus trop quelle version, mais c'est pas si récent en vrai), les dict() conservent l'ordre des données.
Donc j'aurais pu utiliser le dict() standard.
J'ai opté pour l'OrderedDict parce que l'énoncé est assez confus, j'avais cru que quand on remplaçait une lentille, elle repassait devant, et l'OrderedDict a une fonction move_to_end pour pile poil ça.
Alors que pas du tout en vrai, c'est vraiment hyper simple et sans subtilité.

Bref, dans mon code on remplace OrderedDict par dict et ça fonctionne pareil.

C'est vraiment le seul point qui m'a un poil ralenti : la lecture, et mauvaise compréhension, de l'énoncé.
- Yth.

# Pourquoi des dictionnaires ?

Posté par 🚲 Tanguy Ortolo (site web personnel) le 15 décembre 2023 à 13:09. Évalué à 2. Dernière modification le 15 décembre 2023 à 13:10.

Pourquoi utilisez-vous des dictionnaires plutôt qu'un tableau ? On a 256 boîtes, indexées par un entier de 0 à 255, ça semble naturel de représenter ça par un tableau de 256 boîtes non ?

Mon code :

from enum import Enum
from dataclasses import dataclass
import io
import re

from typing import Optional, Self

import aoc


def hash_(s: bytes) -> int:
    value = 0
    for b in s:
        value += b
        value *= 17
        value %= 256
    return value


@dataclass(frozen=True)
class Lens:
    focal: int
    label: bytes

    def __str__(self) -> str:
        return '%s %d' % (self.label.decode(), self.focal)


class Operation(Enum):
    REM = '-'
    PUT = '='


class Instruction:
    def __init__(self, label: bytes, op: Operation, arg: Optional[int] = None):
        self.label = label
        self.box = hash_(label)
        self.op = op
        self.arg = arg

    pattern = re.compile('^(.+)([=-])(.*)$')

    @classmethod
    def import_word(cls, word: str) -> Self:
        if (m := cls.pattern.match(word)) is not None:
            label = m[1].encode('ascii')
            op = Operation(m[2])
            arg = None
            if (s := m[3]) != '':
                arg = int(s)
            return cls(label, op, arg)
        raise ValueError('cannot parse instruction')


class Box:
    def __init__(self) -> None:
        self.lenses: list[Lens] = []

    def remove(self, label: bytes) -> None:
        for i, lens in enumerate(self.lenses):
            if lens.label == label:
                del self.lenses[i]
                return

    def put(self, new_lens: Lens):
        for i, lens in enumerate(self.lenses):
            if lens.label == new_lens.label:
                self.lenses[i] = new_lens
                return
        self.lenses.append(new_lens)

    def is_empty(self) -> bool:
        return len(self.lenses) == 0

    def __str__(self) -> str:
        return ' '.join("[%s]" % str(lens) for lens in self.lenses)



class Machine:
    def __init__(self) -> None:
        self.boxes: tuple[Box] = tuple(Box() for _ in range(256))  # type: ignore

    def __str__(self) -> str:
        s = io.StringIO()
        for i, box in enumerate(self.boxes):
            if not box.is_empty():
                s.write('Box %d: %s\n' % (i, str(box)))
        return s.getvalue()

    def apply(self, instruction: Instruction) -> None:
        box = self.boxes[instruction.box]
        if instruction.op is Operation.REM:
            box.remove(instruction.label)
            return
        if instruction.op is Operation.PUT and instruction.arg is not None:
                lens = Lens(instruction.arg, instruction.label)
                box.put(lens)
                return
        raise ValueError("invalid instruction")

    def power(self) -> int:
        total = 0
        for box_number, box in enumerate(self.boxes):
            for lens_number, lens in enumerate(box.lenses):
                total += (box_number + 1) * (lens_number + 1) * lens.focal
        return total



def part1(lines: aoc.Data) -> int:
    """Solve puzzle part 1: determine the sum of hash value of all instructions"""
    total = 0
    for line in lines:
        for part in line.rstrip().split(','):
            h = hash_(part.encode('ascii'))
            total += hash_(part.encode('ascii'))
    return total


def part2(lines: aoc.Data) -> int:
    """Solve puzzle part 2: determine the sum of staff"""
    instructions = (Instruction.import_word(part) for line in lines for part in line.rstrip().split(','))
    machine = Machine()
    for instruction in instructions:
        machine.apply(instruction)
    return machine.power()

[^] # Re: Pourquoi des dictionnaires ?

Posté par Yth (Mastodon) le 15 décembre 2023 à 14:22. Évalué à 3.
Le dictionnaire est utilisé à l'intérieur des boîtes, pour ne pas réinventer tes méthodes Box.remove() ou Box.put().

Je range les lentilles dans un dictionnaire, mais les boîte sont dans une liste : boxes = [{} for _ in range(256)], ou boxes = [OrderedDict() for _ in range(256)] si on veut utiliser ça, mais ça revient au même.
Dans chaque boîte j'ai un dictionnaire {label: lens}
- Yth.
[^] # Re: Pourquoi des dictionnaires ?

Posté par steph1978 le 16 décembre 2023 à 00:10. Évalué à 2. Dernière modification le 16 décembre 2023 à 00:10.

Pour économiser 40 lignes de code ?

# Pas si vite

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

D'accord, j'ai été un peu rapide dans mon interprétation d'hier, on avait simplement focalisé la lumière du soleil vers le chambre de fusion.

Oui, justement, j'ai comme l'impression que ce n'est pas parce qu'on a remis en service la production de lave que les forges de l'île du métal vont se remettre en marche toutes seules et que les lutins arriveront à produire des pièces de rechange sans aide. Et même alors quelque chose me dit que même avec des pièces de rechange toutes neuves, les lutins de l'île du désert vont avoir besoin de notre aide pour réparer leurs machines et pour collecter du sable. Sur l'île de l'île, on risque aussi d'avoir besoin d'assistance pour relancer la filtration de l'eau et l'envoyer sur l'île de la neige. Quand à l'île de la neige, je pense que la machine à neige ne va pas recevoir directement cette eau, et que les lutins ont sûrement fini par oublier comment cette machine.

Si les lutins savaient se débrouiller tout seuls, ça se saurait depuis le temps. Et là, on vient de relancer un processus vachement de pure ingénierie lutinesque donc vachement complexe et instable. On n'est pas encore sortis de l'auberge.

# Python, un peu poussif

Posté par alberic89 🐧 le 15 décembre 2023 à 19:45. Évalué à 1.

Ce problème aurait dû être simple. Mais sinon ce ne serait pas un problème.

J'ai mis bien du temps à comprendre que je ne pouvais construire une liste vide de 256 listes vides juste avec [[],]*256 car alors toutes les listes sont liées, et la modification d'une seule entraine la modification de toutes les autres. Sigh. Moi qui espérais pouvoir rattraper mon léger retard, c'est mal parti, et ce n'est pas ce week-end que ça va s'arranger.

Un code néanmoins simple, et je l'espère facile à comprendre :

#!/bin/python3

def asciiHash(word):
    r = 0
    for l in word:
        r = ((r + ord(l)) * 17) % 256
    return r

def getPower(box):
    r = 0
    for i,b in enumerate(box):
        for index,lens in enumerate(b):
            r += lens[1]*(index+1)*(i+1)
    return r

def getEmptyList(nb):
    return [[] for _ in range(nb)]

def focusingPower(sequence):
    box = getEmptyList(256)
    for s in sequence:
        if s[-1] == "-":
            for index, lens in enumerate(box[asciiHash(s[:-1])]):
                if lens[0] == s[:-1]:
                    box[asciiHash(s[:-1])].remove(lens)
                    break
        else:
            c = False
            for index, lens in enumerate(box[asciiHash(s.split("=")[0])]):
                if lens[0] == s.split("=")[0]:
                    box[asciiHash(s.split("=")[0])][index] = (s.split("=")[0], int(s.split("=")[1]))
                    c = True
                    break
            if not c:
                box[asciiHash(s.split("=")[0])].append((s.split("=")[0], int(s.split("=")[1])))
    return getPower(box)

def solve1(puzzle,testing=False):
    s=0
    s = sum([asciiHash(_) for _ in puzzle[0].split(",")])
    if testing:
        print(s)
    return s

def solve2(puzzle,testing=False):
    s = 0
    s = focusingPower(puzzle[0].split(","))
    if testing:
        print(s)
    return s

Il y a 10 sortes de gens dans le monde – ceux qui comprennent le ternaire, ceux qui ne le comprennent pas et ceux qui le confondent avec le binaire.

[^] # Re: Python, un peu poussif

Posté par vicnet le 16 décembre 2023 à 13:02. Évalué à 1.

Salut,
En effet, pas très complexe. C'était en effet un pb de jour 1 ou 2…
J'ai eu le même soucis sur la création de liste de liste avec [[],]*256 mais j'ai vite compris car ce n'est pas la 1re fois que cela m'arrive ce qui ne m'empeche pas de me faire piéger !

Suivre le flux des commentaires

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