Forum Programmation.autre Advent of Code 2023, jour 11

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

Étiquettes :

déc.

2023

Nous continuons à suivre les panneaux qui indiquent les sources thermales, où avec un peu de chance nous finirons par trouver quelqu'un.

Nous arrivons à un observatoire où on lutin est en train d'étudier l'univers. Il veut bien vous aider mais il doit finir ses recherches, et vu l'efficacité de nos lutins, il serait utile de l'aider un peu.

Première partie

Il a une image du ciel avec des galaxies dedans et il doit déterminer la somme des distances de Manhattan qui séparent toutes les paires de galaxies :

...#......
.......#..
#.........
..........
......#...
.#........
.........#
..........
.......#..
#...#.....

Rien de bien compliqué, sauf que ces galaxies sont loin, donc anciennes. Depuis, l'espace s'est dilaté. En physique des lutins, l'espace se dilate de la façon suivante : les lignes et les colonnes qui ne contiennent aucune galaxie ont en fait une hauteur ou une largeur double. C'est simple n'est-ce pas ?

Je vous mets la deuxième partie en commentaire pour ne pas trop divulgâcher.

# Deuxième partie

Posté par 🚲 Tanguy Ortolo (site web personnel) le 11 décembre 2023 à 16:32. Évalué à 3.

Attention, spoiler, ne lisez pas si vous en êtes à la première partie et que vous ne voulez pas vous gâcher le plaisir de devoir peut-être réfléchir à nouveau pour implémenter la deuxième.

Deuxième partie

En fait l'espace s'étend plus vite que vous ne l'imaginiez. Les lignes et colonnes qui ne contiennent aucune galaxie ne prennent pas deux fois plus de place, mais un million. Bonne chance et attention à l'OOM killer.

# Strike

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

Bon, aujourd'hui nous sommes dans le cas d'un problème avec une solution naïve qui ne passe pas à l'échelle. Mais personnellement, comme l'optimisation de la première partie était quand même assez simple, j'ai fait un strike, la deuxième partie était résolue en changeant simplement une constante.

import itertools

from collections.abc import Iterable
from typing import Self

import aoc


Coords = tuple[int, int]


class Image:
    def __init__(self, galaxies: Iterable[Coords], factor: int):
        ys: set[int] = set()
        xs: set[int] = set()
        self.galaxies: set[Coords] = set()
        for galaxy in galaxies:
            self.galaxies.add(galaxy)
            ys.add(galaxy[0])
            xs.add(galaxy[1])
        # Space expansion factor: 2 everywhere…
        self.yfactor = [factor] * (max(ys) + 1)
        self.xfactor = [factor] * (max(xs) + 1)
        # … except where galaxies were found.
        for y in ys:
            self.yfactor[y] = 1
        for x in xs:
            self.xfactor[x] = 1

    def distance(self, g1: Coords, g2: Coords) -> int:
        y1, x1 = g1
        y2, x2 = g2
        ymin, ymax = min(y1, y2), max(y1, y2)
        xmin, xmax = min(x1, x2), max(x1, x2)
        return (sum(self.yfactor[y] for y in range(ymin, ymax))
                + sum(self.xfactor[x] for x in range(xmin, xmax)))

    @classmethod
    def import_lines(cls, lines: Iterable[str], factor: int) -> Self:
        return cls(((y, x)
                    for y, line in enumerate(lines)
                    for x, char in enumerate(line.rstrip())
                    if char == '#'),
                   factor)


def part1(lines: aoc.Data) -> int:
    """Solve puzzle part 1: determine total galaxy distances considering an
    expansion factor of 2."""
    image = Image.import_lines(lines, 2)
    total = 0
    for g1, g2 in itertools.combinations(image.galaxies, 2):
        total += image.distance(g1, g2)
    return total

def part2(lines: aoc.Data) -> int:
    """Solve puzzle part 2: determine total galaxy distances considering an
    expansion factor of 1000000."""
    image = Image.import_lines(lines, 1000000)
    total = 0
    for g1, g2 in itertools.combinations(image.galaxies, 2):
        total += image.distance(g1, g2)
    return total

# Solution en Haskell

Posté par Guillaume.B le 11 décembre 2023 à 16:38. Évalué à 2.

Hello tout le monde, c'est mon premier post sur linuxfr (même si je fréquente le site depuis longtemps).

Voici une solution en Haskell (pour ne pas faire comme tout le monde et accessoirement c'est mon langage préféré).
Pas de commentaire à faire la dessus. C'était un problème assez simple.

type Coord = (Int, Int)
type Grid = [[Bool]]

parser :: Parser Grid
parser = some isGalaxy `sepEndBy1` eol where
    isGalaxy = False <$ "." <|> True <$ "#"

manhattan :: Coord -> Coord -> Int
manhattan (x1, y1) (x2, y2) = abs (x1 - x2) + abs (y1 - y2)

gridToCoords :: Grid -> [Coord]
gridToCoords grid = [(i, j) | (i, row) <- zip [0..] grid, (j, True) <- zip [0..] row] 

countEmptyRows :: Grid -> Vector Int
countEmptyRows = V.fromList . drop 1 . scanl' (\acc row -> if all not row then acc+1 else acc) 0

solveWith :: Int -> Grid -> Int
solveWith expand grid = sum (manhattan <$> expGalaxies <*> expGalaxies) `div` 2 where
    galaxies = gridToCoords grid
    emptyRows = countEmptyRows grid
    emptyCols = countEmptyRows (transpose grid)
    expGalaxies = [(x + (expand - 1) * emptyRows V.! x, y + (expand - 1) * emptyCols V.! y) | (x, y) <- galaxies]

solve :: Text -> IO ()
solve = aoc parser (solveWith 2) (solveWith 1000000)

# Simple et qui rappelle des souvenirs.

Posté par Yth (Mastodon) le 11 décembre 2023 à 17:58. Évalué à 2. Dernière modification le 11 décembre 2023 à 18:00.
Aujourd'hui, j'ai fait assez simple, et c'est passé immédiatement pour la seconde partie.

Il me semble qu'on a déjà fait un bidule similaire l'an passé, avec des expansions de galaxies, et peut-être même des distances de Manhattan aussi, mais c'était peut-être dans deux problèmes différents…

Bref, je n'ai jamais cherché à doubler les lignes vides, mais à doubler les espaces vides.
En fait j'ai considéré la liste des galaxies, avec leurs positions.
Ensuite je travaille sur les abscisses, puis les ordonnées, l'un après l'autre, donc j'ai une liste de nombres, croissants, d'abord en Y puis en X.
Et pour chaque espace non nul entre deux de ces nombres, j'ajoute la taille de cet espace à tout ce qui est après : galaxies (en X ou en Y selon l'étape) et aux nombres restants. Bref, j'étends vers le bas, puis vers la droite.

Ajouter la taille à la taille ça double.
Pour l'exercice 2, on n'ajoute pas la taille mais (1 million moins 1) de fois cette taille. Exercice terminé.
```
import sys
data = sys.stdin.read().strip().splitlines()

def run(starmap, mult):
  stars = [(x, y) for y, line in enumerate(starmap) for x, _ in enumerate(line) if _ == "#"]
  Xs = sorted({x for x, y in stars})
  Ys = sorted({y for x, y in stars})
  y0 = 0
  while Ys:
    adding = (Ys[0] - y0) * mult
    stars = [(x, y if y < y0 else y + adding) for x, y in stars]
    Ys = [y + adding for y in Ys]
    y0 = Ys.pop(0) + 1
  x0 = 0
  while Xs:
    adding = (Xs[0] - x0) * mult
    stars = [(x if x < x0 else x + adding, y) for x, y in stars]
    Xs = [x + adding for x in Xs]
    x0 = Xs.pop(0) + 1
  return sum(
    abs(x2 - x1) + abs(y2 - y1)
    for x1, y1 in stars
    for x2, y2 in stars
  )//2

ex1 = run(data, 1)
ex2 = run(data, 1000000-1)
```
- Yth.
- [^] # Re: Simple et qui rappelle des souvenirs.
  
  Posté par 🚲 Tanguy Ortolo (site web personnel) le 11 décembre 2023 à 18:04. Évalué à 3.
  
  C'est… bizarre comme façon de penser je trouve. Non ?
  - [^] # Re: Simple et qui rappelle des souvenirs.
    
    Posté par Yth (Mastodon) le 11 décembre 2023 à 18:15. Évalué à 2.
    Ouais.
    En écrivant le commentaire, j'ai pensé à mieux, et voilà :
```
def run(starmap, expansion):
  stars = [(x, y) for y, line in enumerate(starmap) for x, _ in enumerate(line) if _ == "#"]
  Xs = sorted({x for x, y in stars})
  Ys = sorted({y for x, y in stars})
  stars = [
    (
      sum(1 if _ in Xs else expansion for _ in range(x + 1)),
      sum(1 if _ in Ys else expansion for _ in range(y + 1)),
    )
    for x, y in stars
  ]
  return sum(
    abs(x2 - x1) + abs(y2 - y1)
    for x1, y1 in stars
    for x2, y2 in stars
  )//2
```
    On calcule directement les coordonnées en parcourant les lignes/colonnes vides ou pleines.
    Parfois on a beau essayer de simplifier notre vision du problème, on reste bloqué sur un truc, et on voit pas qu'il y a plus simple.
    - Yth.

# Python

Posté par alberic89 🐧 le 11 décembre 2023 à 18:22. Évalué à 1.

Aujourd'hui, je considère ma carte comme une grille avec 0,0 en haut à gauche, puis je cherche les lignes/colonnes vides, puis l'emplacement des galaxies que j'associe par paires.

Je cherche ensuite la distance entre les paires de galaxies, et ajoute à ces distances le nombre de lignes/colonnes vides comprises entre les deux galaxies multiplié par un facteur (1 pour la 1^er partie, 1000000-1 pour la 2^e ).

Le code :

#!/bin/python3

def getVoid(puzzle):
    void_lines = []
    for i, line in enumerate(puzzle):
        if all([e == "." for e in line]):
            void_lines.append(i)
    void_columns = []
    for col in range(len(puzzle[0])):
        if all([l[col] == "." for l in puzzle]):
            void_columns.append(col)
    return void_lines, void_columns

def getGalaxies(puzzle):
    galaxies = []
    for i, line in enumerate(puzzle):
        for j, space in enumerate(line):
            if space == "#":
                galaxies.append((j,i))
    return galaxies

def getPairs(galaxies):
    pairs = []
    for i in range(len(galaxies)):
        for p in range(i):
            pairs.append((galaxies[i],galaxies[p]))
    return pairs

def getSpaceBetween(pair, void_lines, void_columns, space_void):
    spacex = abs(pair[1][0] - pair[0][0])
    spacex += sum([space_void if i in void_columns else 0 for i in range(min([pair[0][0],pair[1][0]]),max(pair[0][0],pair[1][0]))])
    spacey = abs(pair[1][1] - pair[0][1])
    spacey += sum([space_void if i in void_lines else 0 for i in range(min([pair[0][1],pair[1][1]]),max(pair[0][1],pair[1][1]))])
    return spacex+spacey

def solve1(puzzle,testing=False):
    s=0
    void_lines, void_columns = getVoid(puzzle)
    galaxies = getGalaxies(puzzle)
    pairs = getPairs(galaxies)
    for p in pairs:
        s += getSpaceBetween(p,void_lines,void_columns,1)
    if testing:
        print(s)
    return s

def solve2(puzzle,testing=False):
    s = 0
    void_lines, void_columns = getVoid(puzzle)
    galaxies = getGalaxies(puzzle)
    pairs = getPairs(galaxies)
    for p in pairs:
        s += getSpaceBetween(p,void_lines,void_columns,1000000-1)
    if testing:
        print(s)
    return s

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

Suivre le flux des commentaires

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

Première partie

Deuxième partie