Forum Programmation.autre Advent of Code 2023 : Day 9

Posté par steph1978 le 09 décembre 2023 à 09:58. Licence CC By‑SA.

Étiquettes :

déc.

2023

--- Jour 9 : Maintenance du Mirage ---

Vous chevauchez le chameau à travers la tempête de sable et vous arrêtez là où les cartes du fantôme vous ont dit de vous arrêter. La tempête de sable se calme ensuite, vous voyant étonnamment debout devant une oasis !

Le chameau va chercher de l'eau et vous étirez votre cou. En levant les yeux, vous découvrez ce qui doit être une autre île flottante géante, celle-ci faite de métal ! C'est sûrement là que viennent les pièces pour réparer les machines à sable.

Il y a même un deltaplane partiellement enterré dans le sable ici ; une fois que le soleil se lèvera et réchauffera le sable, vous pourrez peut-être utiliser le deltaplane et l'air chaud pour monter jusqu'à l'île de métal !

En attendant que le soleil se lève, vous admirez l'oasis cachée ici au milieu de l'île du Désert. Elle doit avoir un écosystème délicat ; autant prendre quelques mesures écologiques pendant que vous attendez. Peut-être pouvez-vous signaler toute instabilité environnementale que vous trouvez à quelqu'un pour que l'oasis puisse être préservée pour le prochain voyageur usé par la tempête de sable.

Vous sortez votre pratique Capteur d'Oasis et d'Instabilité du Sable et analysez votre environnement. L'OASIS produit un rapport de nombreuses valeurs et de leur évolution dans le temps (votre entrée de puzzle). Chaque ligne du rapport contient l'historique d'une seule valeur. Par exemple :

0 3 6 9 12 15
1 3 6 10 15 21
10 13 16 21 30 45

Pour protéger au mieux l'oasis, votre rapport environnemental devrait inclure une prédiction de la prochaine valeur dans chaque historique. Pour ce faire, commencez par créer une nouvelle séquence à partir de la différence à chaque étape de votre historique. Si cette séquence n'est pas entièrement composée de zéros, répétez ce processus en utilisant la séquence que vous venez de générer comme séquence d'entrée. Une fois que toutes les valeurs de votre dernière séquence sont des zéros, vous pouvez extrapoler quelle devrait être la prochaine valeur de l'historique d'origine.

Dans l'ensemble de données ci-dessus, le premier historique est 0 3 6 9 12 15. Comme les valeurs augmentent de 3 à chaque étape, la première séquence de différences que vous générez sera 3 3 3 3 3. Notez que cette séquence a une valeur de moins que la séquence d'entrée car à chaque étape, elle considère deux nombres de l'entrée. Comme ces valeurs ne sont pas toutes zéro, répétez le processus : les valeurs diffèrent de 0 à chaque étape, donc la prochaine séquence est 0 0 0 0. Cela signifie que vous avez suffisamment d'informations pour extrapoler l'historique ! Visuellement, ces séquences peuvent être disposées comme ceci :

0   3   6   9  12  15
  3   3   3   3   3
    0   0   0   0

Pour extrapoler, commencez par ajouter un nouveau zéro à la fin de votre liste de zéros ; parce que les zéros représentent les différences entre les deux valeurs au-dessus d'eux, cela signifie également qu'il y a maintenant un espace réservé dans chaque séquence au-dessus :

0   3   6   9  12  15   B
  3   3   3   3   3   A
    0   0   0   0   0

Vous pouvez ensuite commencer à remplir les espaces réservés de bas en haut. A doit être le résultat de l'augmentation de 3 (la valeur à sa gauche) de 0 (la valeur en dessous) ; cela signifie que A doit être 3 :

0   3   6   9  12  15   B
  3   3   3   3   3   3
    0   0   0   0   0

Enfin, vous pouvez remplir B, qui doit être le résultat de l'augmentation de 15 (la valeur à sa gauche) de 3 (la valeur en dessous), soit 18 :

0   3   6   9  12  15  18
  3   3   3   3   3   3
    0   0   0   0   0

Ainsi, la prochaine valeur du premier historique est 18.

Trouver les différences toutes zéro pour le deuxième historique nécessite une séquence supplémentaire :

1   3   6  10  15  21
  2   3   4   5   6
    1   1   1   1
      0   0   0

Ensuite, en suivant le même processus qu'auparavant, déterminez la prochaine valeur dans chaque séquence de bas en haut :

1   3   6  10  15  21  28
  2   3   4   5   6   7
    1   1   1   1   1
      0   0   0   0

Ainsi, la prochaine valeur du deuxième historique est 28.

Le troisième historique nécessite encore plus de séquences, mais sa prochaine valeur peut être trouvée de la même manière :

10  13  16  21  30  45  68
   3   3   5   9  15  23
     0   2   4   6   8
       2   2   2   2
         0   0   0

Ainsi, la prochaine valeur du troisième historique est 68.

Si vous trouvez la prochaine valeur pour chaque historique dans cet exemple et les ajoutez toutes ensemble, vous obtenez 114.

Analysez votre rapport OASIS et extrapoler la prochaine valeur pour chaque historique. Quelle est la somme de ces valeurs extrapolées ?

# recursion

Posté par steph1978 le 09 décembre 2023 à 10:01. Évalué à 3.

Pour ma part, le jour le plus facile depuis le début

import sys

L = [list(map(int,l.split(' '))) for l in sys.stdin.read().splitlines()]

def extrapolate(L):
    if all(a == 0 for a in L):
        return L+[0]
    M = [b-a for a,b in zip(L,L[1:])]
    return L+[L[-1]+extrapolate(M)[-1]]

print(sum(extrapolate(l)[-1] for l in L))

# Résolution péripatéticienne...

Posté par Yth (Mastodon) le 09 décembre 2023 à 11:11. Évalué à 2.
Aujourd'hui je n'ai pas d'ordinateur disponible, alors c'est résolution sur téléphone.
Déjà, trouver un interpréteur python qui soit utilisable, c'est un premier exercice.
Ensuite, bah résolu en marchant entre les étals du marché.
Aucune difficulté à signaler, aucun algo à fournir non plus : je ne peux pas copier-coller mon travail !

Bref, on fait comme on peut 😃
- Yth, 3615 mavie…
- [^] # Re: Résolution péripatéticienne...
  
  Posté par steph1978 le 09 décembre 2023 à 18:46. Évalué à 2.
  
  Chapeau pour avoir fait le challenge depuis le phone. Moi qui passe par le PC pour un message de plus de trois lignes, j'aurai souffer.
  - [^] # Re: Résolution péripatéticienne...
    
    Posté par Yth (Mastodon) le 09 décembre 2023 à 23:22. Évalué à 2.
    Franchement, heureusement que c'était assez trivial aujourd'hui, parce que certaines des journées précédentes, je n'aurais pas pu faire ça…
```
data = """...
...
..."""
ex1, ex2 = 0, 0
for serie in (
  [int(x) for x in line.split()]
  for line in data.splitlines()
):
  sign = 1
  s = serie
  while any(s):
    ex2 += sign * s[0]
    ex1 += s[-1]
    sign = -sign
    s = [s[i + 1] - s[i] for i in range(len(s) - 1)]
print(ex1)
print(ex2)
```
    Sur l'éditeur en ligne sur le téléphone, j'ai commencé par copier-coller les données de l'exercice dans la variable data, et zou pour l'exercice 1, puis modifier le programme pour juste l'exercice 2, j'avais besoin des résultats à entrer, pas d'un code propre et complet.
    - Yth.
# Python

Posté par alberic89 🐧 le 09 décembre 2023 à 13:50. Évalué à 1.
Un exercice étonnamment simple aujourd'hui, mais les explications me semblent un peu embrouillées, est-ce fait exprès ?
Quoi qu'il en soit, voici mon code :
```
def parse_input(puzzle):
    r = []
    for p in puzzle:
        if p == "":
            continue
        p = p.split()
        p.reverse()
        r.append([int(i) for i in p])
    return r

def parse_input_not_reversed(puzzle):
    r = []
    for p in puzzle:
        if p == "":
            continue
        r.append([int(i) for i in p.split()])
    return r

def are_null(suite):
    for n in suite:
        if n != 0:
            return False
    return True

def find_number(suite):
    suivant = []
    for i,n in enumerate(suite[:-1]):
        suivant.append(n-suite[i+1])
    if are_null(suivant):
        return suite[0]
    else:
        return find_number(suivant)+suite[0]

def solve1(puzzle,testing=False):
    s=0
    for l in parse_input(puzzle):
        s += find_number(l)
    if testing:
        print(s)
    return s

def solve2(puzzle,testing=False):
    s = 0
    for l in parse_input_not_reversed(puzzle):
        s += find_number(l)
    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
  
  Posté par vicnet le 09 décembre 2023 à 14:08. Évalué à 1.
  
  Trouvé aussi que c'était plutôt étonnamment simple, y compris la 2e partie.
  Je m'attendais à pire pour la 2e partie, un twist qui remets tout (la force brute) en cause comme hier.
  Mais non, 0 au lieu de -1 dans l'extraction des valeurs du tableau et un - au lieu d'un + et le tour est jouée…
  
  J'ai juste loupé un truc au début car pour déterminer si tout était à 0, j'ai utilisé sum(L) or il s'avère que certaines lignes ont une somme nulle sans avoir tout à 0 !!
  
  J'ai bien aimé l'utilisation de all quelques posts plus haut pour tester la nullité du tableau, je n'y avait pas pensé…
  - [^] # Re: Python
    
    Posté par mac le 09 décembre 2023 à 14:27. Évalué à 1.
    
    +1 sur l'erreur du sum(), j'ai fait la même :(
    
    A force de vérifier si tous les booléens d'un tableau sont à False avec un sum, ça finit par donner de mauvais réflexes..
    - [^] # Re: Python
      
      Posté par Sacha Trémoureux (site web personnel) le 10 décembre 2023 à 16:19. Évalué à 1.
      
      Je me joins au groupe de l’erreur du sum()
  - [^] # Re: Python
    
    Posté par alberic89 🐧 le 09 décembre 2023 à 16:48. Évalué à 1.
    
    Je ne connaissais pas moi-même la fonction all, j'ai fait au plus simple avec une fonction codée par mes soins. Mais c'est vrai qu'on pourrait gagner en efficacité.
    
    Et avec des nombres négatifs, il doit sûrement y avoir des nombres négatifs, ce qui explique que sum retourne 0.
    
    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
      
      Posté par Yth (Mastodon) le 09 décembre 2023 à 23:12. Évalué à 2.
      Tu as any aussi, à la place de if all(a == 0 for a in L): j'ai fait if not any(L):
      
      Yth.
# Pas besoin de tout stocker !

Posté par 🚲 Tanguy Ortolo (site web personnel) le 11 décembre 2023 à 17:49. Évalué à 3.
En fait, si on y réfléchit un peu, on s'aperçoit qu'il n'est pas utile de stocker toute la liste, ni toute la liste des dérivées, ni toute la liste des dérivées secondes, etc. Tout ce dont on a besoin, c'est :
- pendant la phase de calcul des dérivées, la liste des valeurs de la dernière dérivée calculée, pour pouvoir vérifier si elle sont toutes nulles ;
- pour pouvoir extrapoler, les dernières valeurs – et pour la seconde partie, les premières valeur – de chaque dérivée jusqu'à la dernière significative.
Par exemple, en cours de calcul :
```
10  13  16  21  30  45  68 ← données d'origines
10                      68 ← données stockées
   3                  23
     0   2   4   6   8
       ?   ?   ?   ?
```
En fin de calcul :
```
10                      68 ← données stockées
   3                  23
     0               8
       2           2
```
Pour extrapoler à droite, si vous prenez le temps de vérifier ce qui se passe, il suffit en fait de faire la somme de toutes les dernières valeurs.

Et pour extrapoler à gauche, la somme de toutes les valeurs, en passant en négatif celles d'une ligne sur deux. Ou, pour le dire autrement, la somme du produit des premières valeurs multipliées par moins un élevé à une puissance égale au rang de la ligne d'où vient la valeur courante.
- [^] # Re: Pas besoin de tout stocker !
  
  Posté par 🚲 Tanguy Ortolo (site web personnel) le 11 décembre 2023 à 17:50. Évalué à 3. Dernière modification le 11 décembre 2023 à 17:50.
  Trève de blabla, l'implémentation :
```
class History:
    def __init__(self, values: Iterable[int]):
        self.firsts: list[int] = []
        self.lasts: list[int] = []
        current_values = list(values)
        while any(value != 0 for value in current_values):
            self.firsts.append(current_values[0])
            self.lasts.append(current_values[-1])
            next_values: list[int] = []
            for i in range(len(current_values) - 1):
                next_values.append(current_values[i + 1] - current_values[i])
            current_values = next_values

    @classmethod
    def import_line(cls, line: str) -> Self:
        return cls(int(word) for word in line.split())

    def prev(self) -> int:
        return sum((-1)**i * value for (i, value) in enumerate(self.firsts))

    def next(self) -> int:
        return sum(value for value in self.lasts)
```
- [^] # Re: Pas besoin de tout stocker !
  
  Posté par barmic 🦦 le 11 décembre 2023 à 21:56. Évalué à 2.
  
  Ça se voit particulièrement bien quand tu l'implémente en récursif, même si tu n'a pas l'optimisation puisque tu va implémenter une méthode qui prend une liste d'entier et qui en retourne 1 ou 2.
  
  https://linuxfr.org/users/barmic/journaux/y-en-a-marre-de-ce-gros-troll

Suivre le flux des commentaires

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