Reprise du message précédent :
Allez https://github.com/NJdevPro/Advento [...] in/aoc2020

C'est surtout bosser sur des problèmes plus proche du hardware, où chaque context switch compte etc. Et la satisfaction de voir tes VMs/OS démarrer plus vite et casser des barrières d'IOPS

edit : et de faire du C ou du Rust et que ça a beaucoup de sens ici

edit 2 : mais bon, on fait toute la pile aussi, jusqu'à de l'UI web pour gérer tout ça

Moi je craignais qu'il y ai des clés en double

Oui je voulais dire assez commune pour AoC Pour d'autres sites de challenge c'est très différents parce qu'il y a tout un jeu de validations secrétes, mais pour AoC c'est pas le cas, t'as toutes les infos et tu dois juste trouver la bonne réponse.

C'est mon habitude d'être défensif
Et oui c'est un pari de prendre des raccourcis dans la première partie qui ne fonctionnent plus dans la seconde
J'ai jamais fait l'AoC (ni d'autres coding game) alors je ne connais pas les habitudes et le côté vicieux (ou pas) des jeux de données

Ah oui bien vu, je n'ai pas pensé à ce cas-là  

note que je n'ai pas traité le cas non plus

Pareil, je me méfie un peu des données volontairement moisies cachées dans le tas.
Apparemment jusqu'à présent, pas trop de pièges de ce coté là, mais j'imagine que ça va venir après.

Et il y a aussi le cas où un enregistrement est en double.

J'ai sous traité les jours 5 et 6 à mon fils ce weekend. Fausse bonne idée, c'est sûr qu'on fait des économies mais la qualité laisse à désirer, et faut pas être pressé...

peut-être qu'il peut les sous-traiter à la fille d'HLM

Merci de pas saboter la discussion

putin d'enfoiré de résultat D3.2 > 4G  

Day 07 done , 23 minutes, j'ai pas choisi la bonne piste de suite
C'était déjà plus fun qu'hier

Et merde, je vois pas ce qu'il manque dans mon raisonnement.

edit: c'est bon je vois

Tout le monde a un input file différent donc je peux pas te confirmer que c'est ça, avec mon input la réponse de la partie 1 c'est 287 mais ça ne va pas t'aider plus

Franchement celui qui a fini en 5min45 ce matin chapeau

Oh putaiiiiiiiin le set m'a foutu dans une merde !!!

Bon, je n'ai fait que la première partie, pas le temps de faire la 2e.

import re
contains = {}
for line in open("puzzle7.txt","r" ):
    # bright indigo bags contain 4 shiny turquoise bags, 3 wavy yellow bags.
    m = re.split(" bags contain ", line.strip())
    bags = m[1].replace(" bags", '').replace(".", '').replace(" bag", '').replace('no other', '0 other'). split(', ')
    pairs = [bag.split(' ', maxsplit=1) for bag in bags]
    children = [(int(child[0]), child[1]) for child in pairs]
    contains[m[0]] = children
#print(contains)
 
def find_parents(child):
    parents = set()
    for k,v in contains.items():
        if child in [color for (number, color) in v]:
            parents.add(k)
    parents.discard(child)
    return parents
 
print(find_parents("shiny gold" ))
 
def get_roots(color, tree):
    parents = find_parents(color)
    tree |= parents
    if len(parents) == 0:
        return tree
    else:
        for p in parents:
            get_roots(p, tree)
 
ancestry = get_roots("shiny gold", set())

je ne sais pas pourquoi ancestry ne contient rien, mais au débugger j'obtiens le bon résultat dans tree
et oui c'est dégueu

Première partie en 38 minutes mais j'arrive pas à faire la seconde (j'y ai passé 1h, j'arrête les frais)
La récursivité ça a toujours été ma bête noire

import re
contains = {}
for line in open("puzzle7.txt","r" ):
    # bright indigo bags contain 4 shiny turquoise bags, 3 wavy yellow bags.
    m = re.split(" bags contain ", line.strip())
    bags = m[1].replace(" bags", '').replace(".", '').replace(" bag", '').replace('no other', '0 other'). split(', ')
    pairs = [bag.split(' ', maxsplit=1) for bag in bags]
    children = [(int(child[0]), child[1]) for child in pairs]
    contains[m[0]] = children
#print(contains)
 
def find_parents(child):
    parents = set()
    for k,v in contains.items():
        if child in [color for (number, color) in v]:
            parents.add(k)
    parents.discard(child)
    return parents
 
print(find_parents("shiny gold" ))
 
def get_roots(color, tree):
    parents = find_parents(color)
    tree |= parents
    if len(parents) == 0:
        return tree
    else:
        for p in parents:
            get_roots(p, tree)
 
ancestry = get_roots("shiny gold", set())

Dans le cas où len(parents) != 0 tu renvoies rien, donc sauf si t’as immédiatement pas de parents t’as jamais de résultat.  
 
Accessoirement, len(parents) != 0 => parents.

'tain je suis parti dans le parsing du graphe entirer alors qu'on nous demande juste un sous-graphe, j'aurai du y aller à l'arrache par reconnaissance de chaînes dans le texte.

Bon finalement la lecture de la page wikipedia sur la récursivité m'a éclairé
5 minutes plus tard j'avais la solution    
 
Donc :
partie 1 : 38 minutes
partie 2 : 1h09
 
Ca me saoule j'avais plié la lecture du graphe (dans les 2 sens) en quelques minutes

C'est pourtant simple ! Pour comprendre la récursivité, il faut d'abord comprendre la récursivité

Mais je ne comprends pas comme tu as fait la lecture du graphe sans récursivité.

Sans les traces de debug ça donne ça : https://github.com/ratibus/adventof [...] 020/day_07
 
Sur Github ça évitera les spoilers ici

ah mais oui... le boulet
 
Sinon pas compris ta 2e remarque

 
Ben techniquement tu peux toujours écrire une version non récursive d'un algo récursif

Avec une pile explicite?

En python les collections sont falsy quand elles sont vides, donc généralement tu testes juste si la collection, tu t’emmerdes pas à tester si a collection est d’une longueur différente de 0.

Je l'ai bien faite en récursif.

map = Object.fromEntries(document.getElementsByTagName('pre')[0].textContent.split('.\n').filter(l=>l.length).map(r=>r.split(' bags contain ')))
for (k in map){map[k] = map[k].split(', ')}
for (k in map){map[k] = map[k].map(r=>{a = r.split(' '); return {count: parseInt(a[0]), color: a[1] + ' '+a[2]}})}
reversed = {}
newEntry = (p,v)=> {if (p) {p.push(v); return p} else return [v]}
for (k in map){map[k].forEach(rule=>reversed[rule.color] = newEntry(reversed[rule.color], k))}
res = []
function collect(list, collector){list.forEach(e=>{collector.push(e); const p =reversed[e]; if (p) collect(p, collector)})}
collect(reversed['shiny gold'], res)
res

pour l'instant j'ai tout fait dans le debugger, mais c'est parfois un peu pénible.

J'ai fait la partie 1 avec un fold, surpris d'avoir eu bon du premier coup, d'habitude je me foire toujours quelque part dans la logique. Bon j'ai pas l'habitude de kotlin j'en ai chié avec la syntaxe.
 
Et comme d'hab, le parsing c'était le plus chiant de la partie 1.

De mon côté c'est rarement le parsing qui me pose souci, c'est la suite

 
Je me suis fait niquer sur le fait que "bags" était parfois au singulier, c'était magique.
Heureusement que j'avais des TU

ah ok, c'est un truc que j'avais oublié

C'est surtout le `withDefault` des Map Kotlin qui m'a brulé la tronche, vu que ça marche pas avec les accesseurs [] alors qu'IntelliJ te propose gentillement en refactoring d'utiliser ça car c'est plus court et plus clair

Genre quoi tu crées la map avec withDefault et c’est pas pris en compte par [] où bien quand tu accèdes à un élément avec withDefault ca remplit pas le slot?

Je voulais un comportement similaire à un defaultdict en Python.
 
Imaginons une Map de String vers Set<String> :  

 
Cette année l'AOC c'est pour moi un bon moyen de deep dive un peu plus dans Kotlin que je ne connais pas suffisament, et du coup j'ai été pas mal surpris que ça ne fonctionne pas.  
C'est expliqué ici: https://youtrack.jetbrains.com/issu [...] 1605262314 ça casserait le contrat de Map qui renvoie null si une clé n'est pas présente.
 
D'ailleurs le fait que les MutableMap ont des .put() et pas les Map c'est aussi un peu débile, je vois pas pourquoi Map n'a pas un .put() qui renvoie une nouvelle Map, ils ont juste surchargé l'opérateur +, mais quand tu sais pas tu cherches pour rien
Résultat j'ai gardé mes mutablesMapOf épicétou

Pour construire la map en Kotlin j'ai utilisé une fonction de parsing qui prend une ligne de l'input et renvoie une Pair<Bag, Set<Content>>. Quand je map ça sur les lignes de l'input, j'ai un Iterable<Pair<T, U>> qui a une fonction toMap() qui me construit la map d'un coup.

La fonction de parsing :

(y'avait probablement moyen de faire plus concis, mais j'essaye d'encapsuler un peu mes données)

Cette beauté
 

‘Tin c’est stupide.  
 

Ça c’est plus compréhensible, si tu pars du principe qu’une MutableMap est une Map tu peux pas te permette un changement pareil, ça fait que les collections sont pas substituables.  
 
Et c’est également important selon les détails de Map, genre si  ta map immutable est une hashmap standard tu veux pas encourager l’ajout clé par clé, c’est super inefficace de copier toute la map à chaque fois.