Forum Programmation.autre Advent of Code 2023 : Day 5

Posté par 🚲 Tanguy Ortolo (site web personnel) le 05 décembre 2023 à 16:04. Licence CC By‑SA.

Étiquettes :

déc.

2023

Partie 1

Le jardinier nous explique que cette île est bien la source d'eau destinée à l'île de la neige. Seulement il a dû couper l'eau parce qu'il ne recevait plus de sable pour la filtrer et qu'on ne peut pas faire de neige avec de l'eau sale. C'est une interruption temporaire, juste le temps de régler le problème d'approvisionnement en sable. L'ennui, c'est qu'il n'a pas du tout le temps de penser à ça, donc c'est du temporaire qui commence à durer un peu trop longtemps.

Heureusement, il y a un ferry qui va pouvoir vous amener au fournisseur de sable. Le temps qu'il arrive, vous allez pouvoir aider le jardinier avec son nouvel almanach des plantes. C'est un document qui indique quelle graine a besoin de quel substrat, quel substrat a besoin de quel engrais, quel engrais nécessite quel arrosage, quel arrosage correspond à quelle ensoleillement, puis à quelle température, puis à quelle humidité, puis à quel emplacement. Pour commencer à planter le plus vite possible, il s'agit de trouver quel est, parmi toutes les graines disponibles, celle qui devra être plantée dans l'emplacement le plus proche (celui avec le plus petit numéro).

L'entrée d'exemple :

seeds: 79 14 55 13

seed-to-soil map:
50 98 2
52 50 48

soil-to-fertilizer map:
0 15 37
37 52 2
39 0 15

fertilizer-to-water map:
49 53 8
0 11 42
42 0 7
57 7 4

water-to-light map:
88 18 7
18 25 70

light-to-temperature map:
45 77 23
81 45 19
68 64 13

temperature-to-humidity map:
0 69 1
1 0 69

humidity-to-location map:
60 56 37
56 93 4

La première ligne est juste une liste de graines. Les groupes de lignes suivantes donnent des tables de correspondance entre les graines et les substrats, et ainsi de suite. Ces tables sont composées de séries de trois chiffres, dont le premier donne le début d'un intervalle destination, le second le début d'un intervalle d'origine et le troisième la longueur de ces intervalles. Ce qui n'est pas dans ces intervalles reste inchangé.

Partie 2

En fait vous avez mal compris, la premier ligne n'est pas une liste de graines mais une liste d'intervalles de graines. Les chiffres sont à lire par paires, le premier donne le début d'un intervalle et le second sa longueur. Par exemple, 79 14 ne signifie pas que vous avez le graines 79 et 14 à votre disposition, mais que vous avez les graines 79, 80, 81, …, 92.

Même exercice, sauf que ça change tout, parce que sur les données réelles, les intervalles en question ont une longueur de l'ordre plusieurs centaines de millions de graines, voire du milliard. Pas question de procéder graine par graine, on va devoir couper des intervalles en morceaux.

# Découpage d'intervalles en Python

Posté par 🚲 Tanguy Ortolo (site web personnel) le 05 décembre 2023 à 16:11. Évalué à 5.
On arrive au genre d'exercice où la résolution simple de la première partie devient inapplicable à la seconde partie, parce qu'il lui faudrait plus de mémoire qu'il n'y en a sur Terre ou plus de temps que l'âge de l'univers. Là, on est plutôt dans le second cas, je dirais.

Bref, ce n'est pas la première fois que je me retrouve à couper des intervalles en morceaux, alors c'est cadeau, voici du code pour faire ça. Je réutilise le type range qui correspond plutôt bien au concept.
```
def intersects(range1: range, range2: range) -> bool:
    """Tell whether or not the two ranges have a part in common."""
    if range1.start >= range1.stop or range2.start >= range2.stop:
        raise ValueError("usupported empty range") 
    if range1.step != 1 or range2.step != 1:
        raise ValueError("unsupported stepped range")
    return range1.stop > range2.start and range2.stop > range1.start

def intersect(range1: range, range2: range) \
        -> tuple[Optional[range], Sequence[range], Sequence[range]]:
    """Given two ranges, returns:
    1. the eventual intersection of both ranges;
    2. parts of the first range that are not part of the second one;
    3. parts of the second range that are not part of the first one.
    """
    if range1.start >= range1.stop or range2.start >= range2.stop:
        raise ValueError("usupported empty range") 
    if range1.step != 1 or range2.step != 1:
        raise ValueError("unsupported stepped range")
    if not intersects(range1, range2):
        # Disjoint ranges
        return None, (range1,), (range2,)
    diff1: list[range] = []
    if range1.start < range2.start:
        diff1.append(range(range1.start, range2.start))
    if range2.stop < range1.stop:
        diff1.append(range(range2.stop, range1.stop))
    diff2: list[range] = []
    if range2.start < range1.start:
        diff2.append(range(range2.start, range1.start))
    if range1.stop < range2.stop:
        diff2.append(range(range1.stop, range2.stop))
    return (range(max(range1.start, range2.start),
                  min(range1.stop, range2.stop)),
            diff1, diff2)
```
- [^] # Re: Découpage d'intervalles en Python
  
  Posté par mac__ le 05 décembre 2023 à 17:35. Évalué à 3.
  
  Tu peux faire du bruteforce sur la 2ème partie, ça prend 4 ou 5 heures de calcul en Python (sur 1 seul core).
  
  C'est probablement plus rapide que d'attendre d'avoir le temps de chercher un meilleur algo…
  - [^] # Re: Découpage d'intervalles en Python
    
    Posté par Yth (Mastodon) le 05 décembre 2023 à 19:51. Évalué à 3.
    Ici on peut faire du brute-force tout découpé, donc éviter de blinder la RAM.
    Par exemple si tu redécoupes tous tes intervalles en intervalles de 1 million, et un dernier pour les éléments qui restent.
    Tu vas avoir quelque chose comme 2500/2600 intervalles, que tu traites séquentiellement, et la RAM utilisée n'est « que » pour une liste de 1 million d'éléments.
    
    La RAM est basse donc tu ne fais presque que du pompage de CPU, sans mettre la machine à genoux, et ça tourne a peu près vite.
    
    Chez moi, sur la petite machine (i3@2,3Ghz), ça fait environ 1h, en mono-thread, bien sûr (et avec PyPy, surtout pas CPython pour ça !).
    Sur l'autre qui a 4 coeurs, en découpant le travail en quatre pour profiter de tous les coeurs, ça se termine en moins d'un quart d'heure.
    
    Donc ça reste « facile » en force brute :)
    - Yth.
    - [^] # Re: Découpage d'intervalles en Python
      
      Posté par 🚲 Tanguy Ortolo (site web personnel) le 06 décembre 2023 à 12:08. Évalué à 3.
      
      Je ne comprends pas. On peut bien découper des intervalles à l'avance, si le découpage ne correspond pas exactement à aux intervalles définis pour les conversions, il va falloir redécouper non ?
      
      Je veux dire, on peut bien couper l'intervalle de graines 46 546+34 234 234 en 46 546+999 999, 1 046 546 + 999 999, … 34 046 546 + 234 235, mais ça ne va pas aider si on doit ensuite convertir les graines 25 561 123+3 123 458 en quelque chose d'autre. Sauf si j'ai vraiment une chance monstrueuse, les limites de cet intervalle à convertir ne correspondent pas du tout à celles des intervalles de graines prédécoupés.
      
      Donc on se retrouve de toute façon à faire de la découpe d'intervalles par intersection. Tant qu'à faire, autant le faire à partir des intervalles entiers, le prédécoupage n'a aucun intérêt. Qu'est-ce que j'ai loupé ?
      - [^] # Re: Découpage d'intervalles en Python
        
        Posté par Yth (Mastodon) le 06 décembre 2023 à 13:23. Évalué à 2.
        
        Ah, je parlais juste en brute force, comme ça tu traites les graines par paquets de 1 million seulement, et ça prend moins de RAM. Que 850 millions par exemple, qui peuvent mettre une machine à genoux, et invoquer l'OOM.
        
        Yth.
        
        [^] # Re: Découpage d'intervalles en Python
        
        Posté par 🚲 Tanguy Ortolo (site web personnel) le 06 décembre 2023 à 14:14. Évalué à 3.
        
        Ah, d'accord, je comprends mieux.
  - [^] # Re: Découpage d'intervalles en Python
    
    Posté par steph1978 le 08 décembre 2023 à 16:08. Évalué à 2. Dernière modification le 08 décembre 2023 à 16:09.
    
    Je te confirme.
    
    Après une partie 1 torchée en cinq minutes, j'ai eu la flemme d'écrire les algo d'intersection. J'avais laissé de côté.
    
    Puis j'ai quand même tenté en brute force (vraiment crassouille d'itérer sur une range de plusieurs millions). Mais en compilant le programme, réponse en 7 minutes.
    
    J'aurai fait ça à l'ouverture du challenge, j'aurai tapé le top 100 :D
- [^] # Re: Découpage d'intervalles en Python
  
  Posté par 🚲 Tanguy Ortolo (site web personnel) le 06 décembre 2023 à 12:09. Évalué à 3.
  
  Au fait, je vous conseille de garder ce code quelque part. Ça a des chances de resservir. :-)
- [^] # Re: Découpage d'intervalles en Python
  
  Posté par Florent Bonamis le 08 décembre 2023 à 17:03. Évalué à 0.
  
  Bonjour, c'est un peu naif comme question mais en quoi, ce découpage aide à la résolution ?
  
  Je l'ai fait en Brute Force et java, ça a pris 10 minutes avec du parallélisme sur 4 cœurs
  - [^] # Re: Découpage d'intervalles en Python
    
    Posté par steph1978 le 09 décembre 2023 à 09:53. Évalué à 2.
    
    Je crois que tu réponds à ta propre question. Au lieu de tourner pendant 10 minutes, cela aurait tourné pendant une poignée de secondes.

# Manque de temps aujourd'hui

Posté par barmic 🦦 le 05 décembre 2023 à 16:32. Évalué à 2.

Je manque de temps aujourd'hui. J'ai une première partie qui devrait fonctionner qui sort le bon résultat sur l'exemple, mais pas sur mes données d'entrée. J'ai fais une petite visualisation qui ne m'a pas montré grand chose, donc je vais devoir debuger à la main… mais ce sera pour demain. Je découvre rust du coup le code n'est probablement pas optimal (je présume qu'il y a trop de unwrap() par exemple).

use regex::Regex;
use std::cmp;
use std::collections::HashMap;
use std::env;
use std::io::{self, BufRead};
use std::ops::Range;

fn mapping(value: i64, mapper: &HashMap<Range<i64>, i64>) -> i64 {
    for (ran, delta) in mapper {
        if ran.contains(&value) {
            //dbg!(value - delta, delta, value);
            return value + delta;
        }
    }
    return value;
}

fn part1() -> i64 {
    let token_pattern = Regex::new(r"(\d+)").unwrap();
    let map_pattern = Regex::new(r"(\d+) (\d+) (\d+)").unwrap();
    let mut seeds: Vec<i64> = Vec::new();
    let mut mapper = HashMap::new();
    for line in io::stdin().lock().lines() {
        let l = line.unwrap();
        if l.is_empty() {
            // dbg!(&mapper);
            seeds = seeds.iter().map(|a| mapping(*a, &mapper)).collect();
            mapper.clear();
            dbg!(&seeds);
        } else if seeds.is_empty() {
            for (_, [seed]) in token_pattern.captures_iter(&l).map(|c| c.extract()) {
                seeds.push(seed.parse::<i64>().unwrap());
            }
        } else {
            for (_, values) in map_pattern.captures_iter(&l).map(|c| c.extract()) {
                let [target, src, len] = values.map(|str| str.parse::<i64>().unwrap());
                let ran = Range { start: src, end: src + len };
                let delta = target - src;
                mapper.insert(ran, delta);
            }
        }
    }
    return *seeds.iter().reduce(|a, b| cmp::min(a, b)).unwrap();
}

fn main() {
    let args: Vec<String> = env::args().collect();
    if args.len() > 1 && args[1] == "part2" {
        //println!("Part 2: {}", part2());
    } else {
        println!("Part 1: {}", part1());
    }
}

https://linuxfr.org/users/barmic/journaux/y-en-a-marre-de-ce-gros-troll

[^] # Re: Manque de temps aujourd'hui

Posté par barmic 🦦 le 05 décembre 2023 à 18:41. Évalué à 3.

Trouvé, il n'y a pas de ligne vide à la fin de mon input… Je l'ai juste ajouté. À moi la partie 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.