Forum Programmation.autre Advent of Code 2023, day 6

• # Maths

  Posté par 🚲 Tanguy Ortolo (site web personnel) le 06 décembre 2023 à 11:06. Évalué à 6. Dernière modification le 06 décembre 2023 à 11:06.

  

  Pour moi, à la lecture de l'énoncé, je n'y ai pas vu un problème d'algorithmique, mais de mathématiques. Une régate avec un temps de charge qui donne la vitesse pour dépasser la distance record en un temps limité, c'est une inéquation polynomiale de second degré.

  Un polynôme de second degré

  Soit la durée de la course, la distance record et t le temps de charge (notre variable). La vitesse atteinte est d'après l'énoncé égale au temps de charge. Sur la durée de la course, il ne reste plus que pendant lequel le bateau parcourra .

  On charge à battre le record, soit :

  Cela se normalise en :

  La partie gauche est un polynôme de second degré, en forme de cloche vers le haut. Ça tombe bien, si les données sont bien construites il devrait s'annuler en deux points, et être négatif entre les deux. Je sais très bien résoudre ça.

  Résolution

  Le discriminant de ce polynôme vaut :

  Comme je disais, si les données sont bien construites, ça devrait être strictement positif et donner les racines suivantes :

  En chargeant notre bateau pendant exactement ou , on égale le record. Entre et , on le dépasse.

  Retour à la réalité fiction

  Bon, c'est bien joli ça, on peut déterminer des temps minimum et maximum qui sont des réels, mais on nous demande un nombre de durées de charge possible, entières à la milliseconde près, pour dépasser strictement le record.

  Si le temps minimum, par exemple, n'est pas entier, c'est facile, il faut charger pendant une durée supérieur ou égale à son arrondi à l'entier supérieur. Mais les cas limites sont importants, qu'en est-il si le temps minimum est entier ? Il faut charger pendant une durée supérieure ou égale à l'entier suivant.

  En fait, la borne inférieure à considérer est l'entier inférieur au temps minimum, augmenté d'une unité. Mutatis mutandis pour le temps maximum.

  Les bornes incluses de notre intervalle de durées possibles seront donc :

  Quand au nombre d'options, c'est par conséquent la longueur de cet intervalle :

  Partie 1, partie 2

  Ce calcul s'applique aussi bien à la première qu'à la deuxième partie. Et c'est rapide, genre vraiment rapide puisque c'est simplement du calcul. Mieux encore, alors que pour la première partie il faut traiter trois ou quatre régates, pour la seconde il n'y en a plus qu'une seule, donc c'est trois ou quatre fois plus rapide. :-)

  En pratique, en Python 3 ça prend dans les 50 millisecondes pour la première comme pour la seconde partie, mais je soupçonne que ce soit essentiellement la compilation et le temps de chargement de la machine virtuelle Python.

  • [^] # Re: Maths

    Posté par barmic 🦦 le 10 décembre 2023 à 16:35. Évalué à 2. Dernière modification le 10 décembre 2023 à 16:35.

    

    J'ai enfin le temps d'avancer. Comme toi j'ai même hésité à coder. Pour la diversité je poste ma réponse rust

    use regex::Regex;
    use std::env;
    use std::io::{self, BufRead};
    
    fn course(time: u64, distance: u64) -> u64 {
        let delta = (time * time) - (4 * distance);
        if delta <= 0 {
            return 0;
        } else {
            let sqrt = (delta as f64).sqrt();
            let t = time as f64;
            let x1 = (-t + sqrt) / -2f64;
            let x2 = (-t - sqrt) / -2f64;
    
            let mut min = x1.abs().ceil() as u64;
            let mut max = x2.abs().floor() as u64;
            if (time - min) * min == distance {
                min += 1;
            }
            if (time - max) * max == distance {
                max -= 1;
            }
            return max - min + 1;
        }
    }
    
    fn part1() -> u64 {
        let token_pattern = Regex::new(r"(\d+)").unwrap();
        let mut times: Vec<u64> = Vec::new();
        let mut distances: Vec<u64> = Vec::new();
        for line in io::stdin().lock().lines() {
            let l = line.unwrap();
            if l.starts_with("Time:") {
                for (_, [seed]) in token_pattern.captures_iter(&l).map(|c| c.extract()) {
                    times.push(seed.parse::<u64>().unwrap());
                }
            } else if l.starts_with("Distance:") {
                for (_, [seed]) in token_pattern.captures_iter(&l).map(|c| c.extract()) {
                    distances.push(seed.parse::<u64>().unwrap());
                }
            }
        }
        let mut result: u64 = 1;
    
        for (time, distance) in times.iter().zip(distances.iter()) {
            let ways = course(*time, *distance);
            result *= ways;
        }
        return result;
    }
    
    fn part2() -> u64 {
        let token_pattern = Regex::new(r"(\d+)").unwrap();
        let mut times = "".to_owned();
        let mut distances = "".to_owned();
        for line in io::stdin().lock().lines() {
            let l = line.unwrap();
            if l.starts_with("Time:") {
                for (_, [seed]) in token_pattern.captures_iter(&l).map(|c| c.extract()) {
                    times.push_str(seed);
                }
            } else if l.starts_with("Distance:") {
                for (_, [seed]) in token_pattern.captures_iter(&l).map(|c| c.extract()) {
                    distances.push_str(seed);
                }
            }
        }
    
        let time = times.parse::<u64>().unwrap();
        let distance = distances.parse::<u64>().unwrap();
    
        return course(time, distance);
    }
    
    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

• # Un zest de math, pas de modélisation

  Posté par Yth (Mastodon) le 06 décembre 2023 à 11:08. Évalué à 4. Dernière modification le 06 décembre 2023 à 11:10.

  

  Ça fait en effet pas mal de possibilités, puisque ma réponse est de plus de 34 millions de façon de gagner.

  En fait, la meilleure course c'est simplement d'appuyer sur le bouton la moitié du temps et de laisser filer l'autre moitié.
  Mais c'est pas ça qu'on demande, on demande juste de calculer les racines d'un polynome du second degré, et de mesurer l'intervalle entre les deux.

  Ok, pour l'exercice 1, on modélise quand même, parce que ça a l'air plus simple que de réfléchir :

  races = list(zip(*[
    [
      int(y.strip())
      for y in x.split(":")[-1].strip().split()
    ] for x in sys.stdin.read().strip().splitlines()
  ][:2]))
  
  ex1 = reduce(lambda x, y: x * y, (
    sum(
      1
      for i in range(1, time)
      if i * (time - i) > distance
    )
    for time, distance in races
  ))
  print(f"Number of ways to win, score : {ex1}")

  Après, on prend peur, et on se dit que ça va être énorme, les chiffres sont gros, blabla, donc résolution de polynôme, cas limites, soustraction, résultat :

  data = sys.stdin.read().strip().splitlines()
  time, distance = (
    int(x.split(":")[-1].strip().replace(" ", ""))
    for x in data[:2]
  )
  print(f"Big race time {time}, high score : {distance}")
  Δ = math.sqrt(time**2 - 4 * distance)  # Ok, this is √Δ and not Δ
  r1 = math.floor((time - Δ) / 2 + 1)  # if r is an integer, it's not a winning race, it's a tie
  r2 = math.ceil((time + Δ) / 2 - 1)   # so we make sure to handle that edge case.
  # All winning solutions are between r1 and r2, included, hence:
  print(f"Result = {r2 - r1 + 1}")

  Bon, et puis au final on se dit que 35 millions c'est pas si lourd, alors on tente la force brute :

  ex2 = 0
  for i in range(1, time):
      if i * (time - i) > distance:
          ex2 += 1
  print(f"Brute Score : {ex2}")

  Et… des petites comparaisons :
  PyPy3, polynôme : 0,171s
  PyPy3, force brute : 0,268s
  Python3, polynôme : 0,031s
  Python3, force brute : 12,634s

  D'accord, PyPy a un surcoût au démarrage, environ 0.15 secondes, donc la solution efficace en python3 est plus rapide.
  Mais la force brute, bigre, quelle différence, dans les 50 fois plus rapide !

  Et bref, dans tous les cas, on peut y aller comme un bourrin, ou intelligemment, ya rien de difficile dans ces exercices.

  • Yth.

• # Python et math

  Posté par alberic89 🐧 le 06 décembre 2023 à 20:21. Évalué à 1.

  

  Très clairement un exos de math qui pourrait être donné à des secondes, il fallait que ça tombe le jour où je n'avais pas le temps avant le soir.
  Ma solution :

  #!/bin/python3
  
  from math import sqrt
  
  def parse_input(puzzle):
      return [[int(i) for i in puzzle[0].split(":")[1].split()], [int(i) for i in puzzle[1].split(":")[1].split()]]
  
  def parse_input2(puzzle):
      time = int(''.join(puzzle[0].split(":")[1].split()))
      dist = int(''.join(puzzle[1].split(":")[1].split()))
      return [time,dist]
  
  def solve_equ(time,dist):
      x1 = int((time-sqrt(time**2-4*dist))/2)+1
      x2 = (time+sqrt(time**2-4*dist))/2
      if int(x2) == x2:
          x2 = int(x2)-1
      else:
          x2 = int(x2)
      return [x1,x2]
  
  def solve1(puzzle,testing=False):
      s=0
      game = parse_input(puzzle)
      sol = []
      for i,t in enumerate(game[0]):
          p = solve_equ(t,game[1][i])
          sol.append(p[1]-p[0]+1)
      s=sol[0]
      for n in sol[1:]:
          s *= n
      if testing:
          print(s)
      return s
  
  def solve2(puzzle,testing=False):
      s = 0
      game = parse_input2(puzzle)
      p = solve_equ(game[0],game[1])
      s = p[1]-p[0]+1
      if testing:
          print(s)
      return s
  
  test1 = """Time:      7  15   30
  Distance:  9  40  200"""
  result1 = 288
  test2 = test1
  result2 = 71503
  
  # for cli invocation
  
  def solve(short=False,one=True,two=True):
  
      s1, s2 = False , False
  
      if one:
          print("----Part 1----")
          if short == False:
              if solve1(test1.split("\n"),testing=True) != result1:
                  print("Not working.")
                  return False
              else :
                  print("Maybe working?")
          with open("input.txt",'r') as file:
              lines = file.read().split("\n")
              s1 = solve1(lines)
              print(s1)
  
      if two:
          print("----Part 2----")
          if short == False:
              if solve2(test2.split("\n"),testing=True) != result2:
                  print("Not working.")
                  return False
              else :
                  print("Maybe working?")
          with open("input.txt",'r') as file:
              lines = file.read().split("\n")
              s2 = solve2(lines)
              print(s2)
  
      return s1, s2
  
  if __name__ == "__main__":
  
      from sys import argv
  
      s = False
      one = True
      two = True
  
      if len(argv) >= 2:
  
          if "-s" in argv or "--summary" in argv or "--short" in argv:
              s = True
          if "1" in argv:
              two = False
              one = True
          elif "2" in argv:
              one = False
              two = True
          if "2" in argv:
              two = True
  
      solve(short=s,one=one,two=two)

  L'informatique n'est pas une science exacte, on n'est jamais à l'abri d'un succès

• # en mode brute, et c'est passé

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

  

  j'ai énuméré toutes les unités de temps.

  import sys
  
  (t,r) = (int(sys.argv[1]), int(sys.argv[2]))
  
  print(
          # i : time of charging, between 0 and t
          # v = i # speed in m/s
          # d = v * (t-i)  # distance = speed * remaining time
          sum(i*(t-i) > r for i in range(t))
  )

  je pensais que ça allait coincer pour la partie 2, car ça sentait le gros chiffre pour exploser le cpu ou la mémoire.
  mais il n'est est rien.

Suivre le flux des commentaires

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