Calendrier de l'avent 🎄 (mais sans chocolats)

[arzhuras]

Effectivement, pas de soucis non plus sur ce day 11
et effectivement part 2 = part1 si la première partie a été faite de façon rusée!.

[anon10092024]

Jour 11 beaucoup plus simple

Jour 11

https://github.com/Nebsorg/AdventOfCode/blob/main/2023/Day11.py

2023 --- Day 11: Cosmic Expansion ---
****** First Star = 9312968
****** Second Star = 597714117556

Duration: 0:00:00.037152

Bon maintenant faut que je trouve le courage de retourner aux frontières du jour 10

[deneb]

Jour 12 très intéressant !

J’ai implementé la partie 1 en essayant d’optimiser autant que possible sentant la douille arriver pour la partie 2, malheureusement ce n’est pas suffisant et mon CPU est en train de chauffer. N’hésitez pas à investir votre temps de cerveau disponible dès la partie 1.

[Edit] Je bloque pour le moment, je ne vois pas trop comment prendre le problème plus efficacement.

[Xerto]

J’ai un truc qui fonctionne à peu près pour la partie 1 du jour 12 (ça tourne en 1.5s sur mon vieux laptop en Python), par contre c’est clairement pas suffisant pour la partie 2.

Idées

Pour le moment, ma façon de faire c’est : au fur et à mesure, j’avance dans ma string en remplaçant un ? par # ou ., et à chaque fois je vérifie que c’est cohérent avec la règle.

Sauf que c’est overkill : on ne veut pas toutes les strings possibles, on veut toutes les combinaisons possibles. Je pensais qu’un autre moyen était de dire : on récupère les blocks ([#?]+), pour chaque block on calcule toutes leurs règles possibles et leur occurence, et après il suffit de « concaténer » les blocks pour que la règle globale soit respectée. Sauf que ça ne marche pas pour une string du type ???####???####??? vu que ça fait un énorme block.

[deneb]

Idée

Je pense essayer de commencer par caser les plus gros blocks, ça devrait relativement contraindre les possibilités pour caser les plus petits.

Après il ne faut pas avoir des millions de possibilités de caser les gros blocks non plus… à tester, mais c’est pas gagner. J’ai l’impression de louper un truc important.

Deuxième Idée

Au lieu de me prendre la tête avec les plus grosses valeurs, je prend une value en milieu de liste et je divise la liste de part et d’autre. Ensuite, je trouve toutes les positions valides pour la valeur du milieu, et pour chaque position valide, je recurse sur la droite et la gauche, en élagant dès qu’une possiblité retourne 0 position valide. Ça se tente, même is ça serait plus efficace en prenant la plus grande valeur de la liste plutôt que la valeur du milieu.

Rhaaaaa la deuxième idée rame à mort sur certaines lignes mais ça passe !
Victoire ! Du coup j’ai paumé mon après midi avec ces conneries, mais bon sang que ça valait le coup. Je n’ai jamais rencontré un problème qui m’a forcé à abandonner 3 approches différentes à la suite avant de trouver un truc qui marche à peu près.

[arzhuras]

partie 1 réalisée proprement surement optimisable (10s). Nonogramme for ever pour ceux a qui ça parle
On sent bien le gag arriver pour la part 2. J’ai même pas tenté le brut force !
Pour la partie 2, j’ai des idées pour y arriver, mais non dispo jusqu’à demain. Je le ferai donc sûrement demain.

[deneb]

'nuf said (pourcentage de participants qui n’ont fait que la partie 1).

Espérons que le jour 13 soit moins prise de tête. ([Edit] En effet c’est bien plus abordable)

Source

Sinon il semblerait (une fois de plus pour les problème de parcours d’arbres trop grands) qu’une bonne approche pour la partie 2 soit le Dynamic Programming, autrement dit de la récursion (ou pas) tout en mettant en cache les résultats déjà trouvés pour un input donné afin d’éviter de refaire la même chose encore et encore. Perso mon algo n’utilise pas de DP (juste de la récursion) et il se finit en environ 2 minutes (en Kotlin), donc à vous de voir.

[Xerto]

Pour le moment je met 12.2 de côté
Jour 13 partie 1 OK sans trop de soucis, pas eu le temps de trop regarder la partie 2 mais j’ai encore peur que le brute force pose problème. J’ai essayé d’être malin pour ma partie 1, peut-être que ça peut passer pour 2.

Edit: ça passe pour la partie 2, le code

[deneb]

@Xerto

j’ai encore peur que le brute force pose problème

Non non ça passe crème.

[anon10092024]

j’ai du mettre en pose AoC hier, et je serai en deplacement pendant 4 jours à partir de demain, donc plus d’AoC pour moi avant la semaine prochaine

[arzhuras]

Pas de gros soucis pour ce day 13. Même code pour la partie 1 & 2. Pas de brut force.

J’ai mis un peu de temps avant de percuter que : les miroirs démarrent toujours en première ou dernière ligne/colonne

Une petite astuce pour optimiser le tout: d’abord chercher le début et la fin d’un mirroir avant de regarder si tout est identique (a 0 ou 1 près) entre les 2

Je garde le 12.2 dans ma todo mais pas mal occupé aussi!

[Grenat2]

Hier mon code pour 12.2 n’était pas du tout assez optimisé, ça bloquait déjà sur l’exemple.
Là c’est en train de tourner sur mon input, ça devrait le faire.

En attendant je vais regarder le jour 13.

[deneb]

@Grenat2

Là c’est en train de tourner sur mon input, ça devrait le faire.

Je pense que tout le monde a dû avoir comme moi un input avec que des « ? » - Tu peux commencer par tenter juste celui-la et voir si ça se termine.

[Grenat2]

Ouais non du coup ça n’a pas fini cette nuit

Tant pis je passe, idem pour 13.2 où je ne suis pas inspiré.
Heureusement le 14 j’ai réussi les deux parties

[deneb]

Le 14.2 je l’ai fini à la main pour trouver quand ça se répétait après quelques centaines de cycles, puis j’ai calculé la valeur qui tombait au milliard avec la calculatrice windows.
Même pas honte

[Xerto]

Pas de soucis pour 14.1, pour 14.2 j’imagine que ça va cycler, mais pas le temps ce matin de coder l’algo. On verra plus tard.

Edit: partie 2 finie, le code

[arzhuras]

Ah ah, bon pareil. Mais j’ai au moins fait le modulo en Python

[deneb]

Jour 15 tranquille, le seul challenge c’est de comprendre le problème.

[Xerto]

Je suis bien d’accord, beaucoup de blabla pour pas beaucoup de code au final

[arzhuras]

le fil rouge sur le fil vert, le fil bleu sur…