Forum Programmation.autre Advent of Code, jour 18

Posté par  . Licence CC By‑SA.
Étiquettes :
1
18
déc.
2023

Pour ce jour ci, le type d'input est le suivant

R 6 (#70c710)
D 5 (#0dc571)
L 2 (#5713f0)
D 2 (#d2c081)
R 2 (#59c680)
D 2 (#411b91)
L 5 (#8ceee2)
U 2 (#caa173)
L 1 (#1b58a2)
U 2 (#caa171)
R 2 (#7807d2)
U 3 (#a77fa3)
L 2 (#015232)
U 2 (#7a21e3)

C'est une liste d'instructions pour creuser.
Le premier symbole indique dans quelle direction il faut aller (L pour gauche, R pour droite, U pour haut, D pour bas) et l'entier qui suit indique de quelle distance il faut se déplacer.
Le code hexadécimal qui suit est ignoré pour la partie 1.

Si l'on part du point (0, 0) et que l'on suit les instructions, on obtient donc la grille suivante où les caractères "#" indiquent les endroits où l'on a creusé:

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

Si l'on remplit la surface délimitée par les "#", on obtient la grille suivante:

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

Le but de la partie 1 est de compter le nombre de "#" dans la dernière grille.

Dans la partie 2, on change les instructions et l'on considère le code hexadécimal.
Les 5 premiers caractères indique la distance de déplacement et le dernier caractère indique dans quelle direction on se déplace: 0 signifie droite, 1 signifie bas, 2 signifie gauche et 3 signifie haut.

Les distances de déplacement étant très grandes, on ne peut pas calculer directement la grille.
Il faut trouver quelque chose de plus astucieux.

  • # Solution en Haskell

    Posté par  . Évalué à 3.

    Ce problème ressemble à la partie 2 du jour 10 de cette année.

    La première partie peut être aisément fait avec un parcours en largeur/profondeur mais ça devient clairement impossible pour la partie 2.

    Remarquons que l'on cherche à trouver le nombre de sommets de coordonnées entières situées à l'intérieur d'un polygone.
    On va donc de baser sur le théorème de Pick et la shoelace formula.
    La shoelace formula est une formule pour calculer l'aire d'un polygone.
    Si les sommets du polygone sont (x1, y1), ..., (xn, yn) alors l'aire du polygone est
    |x1 y2 - y1 x2 + ... + x_{n-1} yn - y_{n-1} xn + xn y1 - yn x1| / 2

    Le théorème de Pick donne une formule pour calculer le nombre de points intérieurs à un polygone à partir de son aire (qui est calculé par la shoelace formula) et du nombre de points à sa frontière (c'est juste la somme des distances données par les instructions).

    La formule est la suivante: A = i + b/2 - 1 où A est l'aire, i le nombre de points à l'intérieur et b le nombre de points à la frontière.

    Pour calculer le nombre de "#" total, il faut faire la somme i + b où i = A - b/2 - 1.

    Donc, voici le code Haskell

    data Direction = Up | Down | Left | Right
data Instr = Instr !Direction !Int

hexToInt :: String -> Int
hexToInt = foldl' (\acc x -> acc * 16 + hexDigitToInt x) 0
   where hexDigitToInt x
          | isDigit x = ord x - ord '0'
          | otherwise = ord x - ord 'a' + 10

parser :: Parser [(Instr, Instr)]
parser = instr `sepEndBy1` eol where
    instr = do
        dir1 <- direction <* " "
        len1 <- decimal <* " (#" 
        len2 <- hexToInt <$> count 5 hexDigitChar
        dir2 <- direction2 <* ")"
        pure (Instr dir1 len1, Instr dir2 len2)

    direction = choice [Up <$ "U", Down <$ "D", Left <$ "L", Right <$ "R"] 
    direction2 = choice [Right <$ "0", Down <$ "1", Left <$ "2", Up <$ "3"] 

trenchPoints :: [Instr] -> [V2 Int]
trenchPoints = scanl' go (V2 0 0) where
    go p (Instr dir len) = p + case dir of
        Left -> V2 0 (-len)
        Right -> V2 0 len
        Up -> V2 (-len) 0
        Down -> V2 len 0

-- return the double of the polygon area
shoelaceFormula :: [V2 Int] -> Int
shoelaceFormula points = abs $ sum (zipWith go points (drop 1 points ++ points))
    where go (V2 x y) (V2 x' y') = x * y' - x' * y

-- via Pick theorem and Shoelace Formula
-- https://en.wikipedia.org/wiki/Pick%27s_theorem
-- https://en.wikipedia.org/wiki/Shoelace_formula
solveFor  :: ((Instr, Instr) -> Instr) -> [(Instr, Instr)] -> Int
solveFor f instrs = boundary + interior  where
    instrs' = map f instrs
    doubleArea = shoelaceFormula (trenchPoints instrs')
    boundary = sum [len | Instr _ len <- instrs']
    interior = (doubleArea - boundary) `div` 2 + 1

solve :: Text -> IO ()
solve = aoc parser (solveFor fst) (solveFor snd)

  • # J'ai un peu honte...

    Posté par  . Évalué à 2.

    … ou pas, je sais pas trop le justifier.

    La partie 1 a été faite à la main avec des algos de remplissages de polygones.

    Pour la partie 2, c'est devenu impossible - j'ai utilisé la lib-qui-va-bien - à savoir Shapely en Python, sa fonction area et un petit correctif pour prendre en compte l'épaisseur des murs.

    Du coup, ça devient "trivial", il y a juste à identifier les sommets du polygone et la librairie fait le reste.

    Après… s'agit-il vraiment de triche ? Après tout, qui dit "j'ai triché" quand il fait faire à son ordinateur des milliers de multiplications pour répondre à un problème Advent Of Code ?… le débat est ouvert…

    Toujours est-il que je n'aurais pas su répondre à cette question avec mes connaissances pures.

    • [^] # Re: J'ai un peu honte...

      Posté par  . Évalué à 2.

      Tout pareil, mas dès la première partie.
      Ce jour m'a permis de découvrir shapely.
      Qui permet aussi de beau tracés:

  • # Sans géométrie

    Posté par  (site web personnel) . Évalué à 3.

    Première partie

    Pour la première partie, je fais du remplissage, voici les étapes :

    1. J'alloue une matrice suffisante pour contenir tout le tracé – oui, il y a une étape pour déterminer la taille nécessaire, mais c'est sans intérêt à dérailler –, plus une marge d'une unité. En fait, pas une matrice mais trois, à valeurs booléennes : le terrain, une matrice qui indiquera si on est à l'extérieur du tracé, et une matrice qui indiquera si on a déjà visité chaque point.
    2. Je trace les tranchées.
    3. Je pars du point en haut à gauche, dont je suis certain qu'il est hors du bassin puisqu'il fait partie de la marge sus-mentionnée. De proche en proche, je remplis l'extérieur du bassin dans la seconde de mes matrices. C'est beaucoup plus facile que d'essayer de remplir directement l'intérieur. La troisième matrice sert à cette étape, pour ne pas passer indéfiniment sur les mêmes points.
    4. Je remplis l'intérieur du bassin dans la matrice du terrain, la seule que je vais garder.

    Trouver l'aire, c'est trivial.

    Deuxième partie

    Pareil. Comment ça, pareil, alors que les coordonnées sont beaucoup trop grandes pour pouvoir faire ça avec des matrices ? Eh bien, on n'a pas besoin de toutes les coordonnées, voyez-vous. On a seulement besoin de celles où commencent ou finissent des tranchées en fait.

    Bref, je me construis une matrice donc les cases ont des dimensions virtuelles carrément variables. Ensuite, on se ramène à l'algorithme précédent, avec un détail de pondération pour le calcul de l'aire.

    • [^] # Re: Sans géométrie

      Posté par  (site web personnel) . Évalué à 3. Dernière modification le 18 décembre 2023 à 20:01.

      Le code :

      import dataclasses
import enum
import io
import re

from collections.abc import Iterable, Iterator
from typing import ClassVar, Self

import numpy as np
import numpy.typing as npt

import aoc


Coords = tuple[int, int]
Vector = tuple[int, int]


class Direction(enum.Enum):
    UP = 'U'
    DOWN = 'D'
    LEFT = 'L'
    RIGHT = 'R'

    @property
    def vector(self) -> Vector:
        if self is self.UP:
            return (-1, 0)
        if self is self.DOWN:
            return (1, 0)
        if self is self.LEFT:
            return (0, -1)
        if self is self.RIGHT:
            return (0, 1)
        assert False, "we covered all cases"

    def translate(self, position: Coords) -> Coords:
        y, x = position
        dy, dx = self.vector
        return y + dy, x + dx


@dataclasses.dataclass(frozen=True)
class Instruction:
    direction: Direction
    length: int

    import_pattern1: ClassVar[re.Pattern] = re.compile(
            r'^([UDLR]) (\d+) \(#[0-9A-Fa-f]{6}\)\n?$')
    import_pattern2: ClassVar[re.Pattern] = re.compile(
            r'^[UDLR] \d+ \(#([0-9A-Fa-f]{5})([0-9A-Fa-f])\)\n?$')

    @classmethod
    def import_line1(cls, line: str) -> Self:
        if (m := cls.import_pattern1.match(line)) is not None:
            return cls(Direction(m[1]), int(m[2]))
        raise ValueError("invalid instruction line")

    @classmethod
    def import_line2(cls, line: str) -> Self:
        if (m := cls.import_pattern2.match(line)) is not None:
            length = int(m[1], 16)
            if m[2] == '0':
                direction = Direction.RIGHT
            elif m[2] == '1':
                direction = Direction.DOWN
            elif m[2] == '2':
                direction = Direction.LEFT
            elif m[2] == '3':
                direction = Direction.UP
            else:
                raise ValueError("invalid instruction line")
            return cls(direction, length)
        raise ValueError("invalid instruction line")

    def apply(self, position: Coords) -> Coords:
        y, x = position
        dy, dx = self.direction.vector
        return y + self.length * dy, x + self.length * dx


class Terrain1:
    def __init__(self, instructions: Iterable[Instruction]) -> None:
        position: Coords = (0, 0)
        excavated: set[Coords] = {(0, 0)}
        for instruction in instructions:
            for _ in range(instruction.length):
                position = instruction.direction.translate(position)
                excavated.add(position)
        ymin, ymax = 0, 0
        xmin, xmax = 0, 0
        for (y, x) in excavated:
            ymin = min(ymin, y)
            ymax = max(ymax, y)
            xmin = min(xmin, x)
            xmax = max(xmax, x)
        # Time to write a terrain matrix
        # It needs to span the entire excavated area, plus a margin:
        # * vertically: from ymin - 1 to ymax + 1 included;
        # * horizontally: fron xmin - 1 to xmax + 1 included.
        self.matrix: npt.NDArray[np.bool_] = np.zeros(
                (ymax - ymin + 3, xmax - xmin + 3), dtype=np.bool_)
        self.ly, self.lx = self.matrix.shape
        for (y, x) in excavated:
            y = y - ymin + 1
            x = x - xmin + 1
            self.matrix[y, x] = True

    def dig_pool(self) -> None:
        def neighs(coords: Coords) -> Iterator[Coords]:
            def _neighs(coords: Coords):
                y, x = coords
                yield y, x - 1
                yield y, x + 1
                yield y - 1, x
                yield y + 1, x
            for y, x in _neighs(coords):
                if 0 <= y < self.ly and 0 <= x < self.lx:
                    yield y, x

        outside = np.zeros_like(self.matrix)
        visited = np.zeros_like(self.matrix)
        start = (0, 0)
        outside[start] = True
        visited[start] = True
        currents: set[Coords] = {(0, 0)}
        while len(currents) > 0:
            nexts: set[Coords] = set()
            for position in currents:
                for neigh in neighs(position):
                    if visited[neigh]:
                        continue
                    if not self.matrix[neigh]:
                        outside[neigh] = True
                        nexts.add(neigh)
                    visited[neigh] = True
            currents = nexts
        for position, _ in np.ndenumerate(self.matrix):  # type: ignore
            if not outside[position]:
                self.matrix[position] = True

    def area(self) -> int:
        return np.sum(self.matrix)  # type: ignore

    def __str__(self) -> str:
        s = io.StringIO()
        for line in self.matrix:
            for excavated in line:
                if excavated:
                    s.write('█')
                else:
                    s.write(' ')
            s.write('\n')
        return s.getvalue()


@dataclasses.dataclass(frozen=True)
class HSegment:
    x1: int
    x2: int
    y: int

    def cuts(self, x: int) -> bool:
        return self.x1 <= x <= self.x2

    def __len__(self) -> int:
        return self.x2 - self.x1 + 1


@dataclasses.dataclass(frozen=True)
class VSegment:
    x: int
    y1: int
    y2: int

    def cuts(self, y: int) -> bool:
        return self.y1 <= y <= self.y2

    def __len__(self) -> int:
        return self.y2 - self.y1 + 1


class Terrain2:
    def __init__(self, instructions: Iterable[Instruction]):
        hsegments: set[HSegment] = set()
        vsegments: set[VSegment] = set()
        ys: set[int] = {0, 1}
        xs: set[int] = {0, 1}
        ymin, ymax = 0, 1
        xmin, xmax = 0, 1
        y, x = 0, 0
        for instruction in instructions:
            y_, x_ = instruction.apply((y, x))
            ymin, ymax = min(ymin, y_), max(ymax, y_ + 1)
            xmin, xmax = min(xmin, x_), max(xmax, x_ + 1)
            ys.add(y_)
            ys.add(y_ + 1)
            xs.add(x_)
            xs.add(x_ + 1)
            if instruction.direction is Direction.UP:
                vsegments.add(VSegment(x, y_, y))
            elif instruction.direction is Direction.DOWN:
                vsegments.add(VSegment(x, y, y_))
            elif instruction.direction is Direction.LEFT:
                hsegments.add(HSegment(x_, x, y))
            elif instruction.direction is Direction.RIGHT:
                hsegments.add(HSegment(x, x_, y))
            else:
                assert False, "we covered all cases for instruction direction"
            y, x = y_, x_
        ys.add(ymin - 1)
        ys.add(ymax + 1)
        xs.add(xmin - 1)
        xs.add(xmax + 1)
        self.ys = sorted(ys)
        self.xs = sorted(xs)
        self.matrix: npt.NDArray[np.bool_] = np.zeros(
                (len(ys) - 1, len(xs) - 1), dtype=np.bool_)
        self.lj, self.li = self.matrix.shape
        for hsegment in hsegments:
            j = self.ys.index(hsegment.y)
            for i in range(self.xs.index(hsegment.x1),
                           self.xs.index(hsegment.x2) + 1):
                self.matrix[j, i] = True
        for vsegment in vsegments:
            i = self.xs.index(vsegment.x)
            for j in range(self.ys.index(vsegment.y1),
                           self.ys.index(vsegment.y2) + 1):
                self.matrix[j, i] = True

    def dig_pool(self) -> None:
        def neighs(coords: Coords) -> Iterator[Coords]:
            def _neighs(coords: Coords):
                j, i = coords
                yield j, i - 1
                yield j, i + 1
                yield j - 1, i
                yield j + 1, i
            for j, i in _neighs(coords):
                if 0 <= j < self.lj and 0 <= i < self.li:
                    yield j, i

        outside = np.zeros_like(self.matrix)
        visited = np.zeros_like(self.matrix)
        start = (0, 0)
        outside[start] = True
        visited[start] = True
        currents: set[Coords] = {(0, 0)}
        while len(currents) > 0:
            nexts: set[Coords] = set()
            for position in currents:
                for neigh in neighs(position):
                    if visited[neigh]:
                        continue
                    if not self.matrix[neigh]:
                        outside[neigh] = True
                        nexts.add(neigh)
                    visited[neigh] = True
            currents = nexts
        for position, _ in np.ndenumerate(self.matrix):  # type: ignore
            if not outside[position]:
                self.matrix[position] = True

    def area(self) -> int:
        count = 0
        for j in range(self.lj):
            for i in range(self.li):
                if self.matrix[j, i]:
                    count += ((self.ys[j + 1] - self.ys[j])
                              * (self.xs[i + 1] - self.xs[i]))
        return count

    def __str__(self) -> str:
        s = io.StringIO()
        for line in self.matrix:
            for excavated in line:
                if excavated:
                    s.write('█')
                else:
                    s.write(' ')
            s.write('\n')
        return s.getvalue()


def part1(lines: aoc.Data) -> int:
    """Solve puzzle part 1: determine the sum of stuff"""
    terrain = Terrain1(Instruction.import_line1(line) for line in lines)
    terrain.dig_pool()
    return terrain.area()


def part2(lines: aoc.Data) -> int:
    """Solve puzzle part 2: determine the sum of staff"""
    terrain = Terrain2(Instruction.import_line2(line) for line in lines)
    terrain.dig_pool()
    return terrain.area()

  • # Bof , bof, je n'ai pas vraiment trouvé par moi-même.

    Posté par  . Évalué à 1.

    Pour la première partie, j'ai utilisé un bête algo de remplissage de forme par propagation.

    Pour la deuxième partie, je connaissais l'algorithme du lacets(Shoelace) pour en avoir entendu parlé récemment.
    Je me doutais qu'il fallait retirer le périmètre du polygone.

    Par contre, je ne trouvais pas malgré toutes mes investigations ,c'est en lisant le CR de Guillaume que j'ai découvert le théorème de Pick et son usage.

    Mon implémtentation en Java.

    package aoc2023;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Map;
import java.util.Scanner;

public class Aoc2023s18v2 {
    public static record Point(long x, long y) {
        public Point createRelative(Point dir, long factor) {
            return new Point(x + dir.x * factor, y + dir.y * factor);
        }

        public double dist(Point p) {
            long dx = p.x - x;
            long dy = p.y - y;

            return Math.sqrt(dx * dx + dy * dy);
        }
    }

    public static List<String> ORDERS = Arrays.asList("R", "D", "L", "U");

    public static Map<String, Point> DIRECTIONS = Map.of("U", new Point(0, -1), "R", new Point(1, 0), "D",
            new Point(0, 1), "L", new Point(-1, 0));

    public static Map<String, String> DIRECTIONS_TRAD = Map.of("3", "U", "0", "R", "1", "D", "2", "L");

    public static long calculateArea2(List<Point> listPoints) {
        Point[] points = listPoints.toArray(new Point[listPoints.size()]);
        double sum = 0.0;

        for (int i = 0; i < points.length - 1; ++i) {
            sum += (points[i].x * points[i + 1].y) - (points[i + 1].x * points[i].y);
        }
        long perimeter = dist(listPoints);
        long s1 = (long) (Math.abs(sum) - perimeter);
        s1 = s1 / 2;
        s1 += 1;
        return s1 + perimeter;
    }

    public static long dist(List<Point> poly) {
        double sum = 0;
        for (int x = 1; x < (poly.size()); x++) {
            sum += poly.get(x - 1).dist(poly.get(x));
        }

        sum += poly.get(poly.size() - 1).dist(poly.get(0));
        return (long) sum;
    }

    public static void main(String[] args) {
        try (Scanner in = new Scanner(Aoc2023s18v2.class.getResourceAsStream("res/t18.txt"))) {
            List<String> rows = new ArrayList<>();

            while (in.hasNext()) {
                String row = in.nextLine();
                rows.add(row);
            }
            List<Point> polyPoints = polygons2(rows);

            System.out.println("found=" + calculateArea2(polyPoints));

        }
    }

    private static List<Point> polygons2(List<String> rows) {
        List<Point> points = new ArrayList<>();
        Point p = new Point(0, 0);
        points.add(p);
        for (String row : rows) {
            String dirKey = row.split(" ")[2];
            long factor = Long.valueOf(dirKey.substring(2, 7), 16);
            String dir = "" + dirKey.charAt(dirKey.length() - 2);
            System.out.println(factor + " " + dir);
            Point np = p.createRelative(DIRECTIONS.get(DIRECTIONS_TRAD.get(dir)), factor);
            points.add(np);
            p = np;
        }
        return points;
    }
}

  • # La solution la plus courte à écrire, la plus longue à expliquer.

    Posté par  (Mastodon) . Évalué à 2.

    Hier encore, j'ai sévèrement lutté pour coder : repas d'entreprise en montagne (dur la vie…), donc j'ai eu rien de temps pour coder, à moitié sur PC, à moitié sur téléphone.
    En pratique, j'ai honte un peu, j'ai fini de coder en voiture (au volant oui, oui), avec un algo sous-optimisé qui a mit un bon quart d'heure à s'exécuter, et m'a sorti le bon résultat.
    Le même code prend 70s sur mon petit PC.

    Mais j'ai eu le temps de réfléchir à une autre approche, que je n'avais pas eu le temps de coder, mais que j'ai validé le soir.
    Et là c'est magique, une fonction de 12 lignes, 3 lignes pour les deux jeux de données, et 2 structures constantes, allez 22 lignes avec le she-bang python3.
    Le résultat sort en rien de temps, O(n).

    L'idée c'est de considérer une unique zone rectangulaire qu'on va agrandir ou rétrécir au fur et à mesure de l'exploration des sommets, en notant ce qu'on a tranché, ou rajouté.
    Voilà les données de test et quelques itérations :

    ####### 0# 1####### 2####### 3#####__ 4##### 5#####** 8##
#+++++#              #######  #####__  #####  #####**  ##
###+++#              #######  #####__  #####  #####**  ##
..#+++#              #######  #####__  #####  #####**  ##
..#+++#              #######  #####__  #####  #####**  ##
###+###              #######  #####__  #####  #####**  ##
#+++#..                                #####  #####**  ##
##++###                                #####  #######  ##
.#++++#                                                .*
.######                                                .*

    Étape 0 j'ai la zone (0, 0) -> (0, 0), facile.
    Étape 1 j'étends vers la droite de 6 cases, rien à faire, ma zone fini en (6, 0), je prends tout.
    Étape 2, pas mieux, j'étends vers le bas jusque (6, 5), je prends encore tout (je ne sais pas encore ce qui se passe à la fin, on enlèvera plus tard, sommet par sommet).
    Étape 3, je réduis vers la gauche vers (4, 5) ! Là je perd une zone, indiquée avec des _, elle fait 12 cases, donc je la supprime du problème mais je note une superficie de 12.
    Étape 4, j'étends vers le bas, rien à dire, ma zone se termine en (4, 7).
    Étape 5, j'étends vers la droite encore, jusque (6, 7), et là on voit bien qu'on a agrandit dans une zone de vide, les *, il faut les retirer, mais attention, les # en bas sont l'épaisseur du trait, on les garde ! Donc on note que notre superficie est de 14 trop grand maintenant, notre superficie de côté est donc 12-14 = -2, ce qui correspond bien aux deux . à droite du résultat cherché.
    Je saute, étape 6 on descends vers (6, 9) rien à faire, étape 7 on va vers la droite jusque (1, 9) donc on ajoute à notre superficie stockée 50 cases, on est à 48.
    Étape 8, on remonte vers (1, 7) ! On doit considérer l'épaisseur du trait qui va disparaître, ici 2, mais le reste était en dehors de notre résultat, donc la superficie augmente simplement de 2 pour arriver à 50.

    On a vu les 4 règles, on termine les 14 étapes ainsi :
    Étape 9 : gauche de 1 vers (0, 7) superficie + 8 = 58
    Étape 10 : haut de 2 vers (0, 5) superficie + 2 = 60
    Étape 11 : droite de 2 vers (2, 5) superficie - 10 = 50
    Étape 12 : haut de 3 vers (2, 2) superficie + 3 = 53
    Étape 13 : gauche de 2 vers (0, 2) superficie + 6 = 59
    Étape 14 : haut de 2 vers (0, 0) superficie + 2 = 61
    Et enfin, il nous reste la zone qui se termine en (0, 0) et qui fait donc # et a une superficie de 1.
    J'ajoute 1 : 62, youpi.

    Cet algo est pensé sur un départ à gauche et en bas, avec le (0, 0) qui est dans le coin.
    Pour valider que ça marche un peu partout, surtout en débordant à gauche ou en haut, on peut constater que les instructions peuvent cycler, on peut commencer à la seconde instruction et reboucler jusque la 1ère, etc.
    Donc j'ai validé avec toutes les positions de départ : 62 tout le temps, on est bons.
    Ok, bah plus qu'à tester en grand et sur données réelles : ça marche, bingo.

    Le code :

    from sys import stdin
import re
data = re.findall(r"([UDLR]) (\d+) [(]#([0-9abcdef]+)[)]", stdin.read().strip())
DIR = [(1, 0), (0, 1), (-1, 0), (0, -1)]
Dir = {"R": DIR[0], "D": DIR[1], "L": DIR[2], "U": DIR[3]}
data1 = [(int(b), Dir[a]) for a, b, _ in data]
data2 = [(int(d[:-1], 16), DIR[int(d[-1])]) for *_, d in data]
def run(d):
  x = y = s = 0
  for n, (a, b) in d:
    x1, y1 = x + n * a, y + n * b
    if a == -1:
      s += (y + 1) * (x - x1)
    elif a == 1:
      s -= y * (x1 - x)
    elif b == -1:
      s += y - y1
    x, y = x1, y1
  return s + 1
ex1 = run(data1)
ex2 = run(data2)

    Voilà, voilà, sans théorème, sans connaissances particulières, sans module externe, juste des méninges torturées pendant des heures à ne pas pouvoir coder les algos qui tournent dans la tête.
    Inutile de dire que le temps d'exécution c'est l'overhead python, et c'est tout.

    Par contre difficile de bien coder ça en vrac, dehors, dans la neige et le froid, avec un téléphone, on est mieux sur un bureau, avec un papier, et un clavier.

    • Yth.

    • [^] # Re: La solution la plus courte à écrire, la plus longue à expliquer.

      Posté par  (site web personnel) . Évalué à 3.

      En pratique, j'ai honte un peu, j'ai fini de coder en voiture (au volant oui, oui),

      Non mais là, faut savoir s'arrêter quand même. Ce serait dommage de mourir ou de tuer quelqu'un pour cause d'AoC.

    • [^] # Re: La solution la plus courte à écrire, la plus longue à expliquer.

      Posté par  . Évalué à 1.

      Salut,
      J'ai commencé la partie 1 par un remplissage ligne à ligne en calculant le nombre de point dedans/dehors.
      Si on croise une ligne, on passe de dehors à dedans ou le contraire.
      Pour la 2, ca marche pô.
      Je n'ai pas pensé à la matrice virtuelle, enfin si plus ou moins, j'ai tenté de déterminer les groupes de lignes où cela ne change pas et utiliser mon algo précédent en multipliant par la surface du groupe, mais KO, pas réussi

      J'ai testé aussi le coup d'agrandir ou réduire la zone au fur et à mesure de l'ajout de segments.
      Meme chose, ca ne fonctionnait pas sur des cas simple: carré, carré avec un coin en moins.
      Bref, abandon.

      Je viens de reprendre seulement hier en utilisant 'tout simplement' le théorème des lacets pour calculer la surface d'un polygone quelconque.
      J'avais des doutes sur l'utilisation de cette technique avec des blocs et des coordonnées entières. Mais en relisant l'algo, et en dessinant quelques crobar vite fait, j'ai compris que c'était faisable avec un twist: j'ai juste agrandi le polygone vers son extérieur (technique de la main gauche le long d'un mur) de 1/2.
      Ca fonctionne même pour le 1 et c'est plus beaucoup beaucoup plus simple.

Suivre le flux des commentaires

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