Forum Programmation.autre Avent du Code, jour 8

Posté par steph1978 le 08 décembre 2022 à 11:10. Licence CC By‑SA.

Étiquettes :

déc.

2022

Suite de l'Avent du Code, jour 8.

Enfin un peu d'exploration. Les lutins veulent installer leur cabane dans une plantation d'arbres, avec la meilleure vue possible. Vous les y aider muni d'une carte.

# python procédural, moche mais efficace

Posté par steph1978 le 08 décembre 2022 à 11:19. Évalué à 3.

Même méthode pour les deux parties : un parcours de chaque position d'une matrice. Pour chaque position, regarder à gauche, à droite, en haut, en bas. Ça donne pas un code très beau mais ça marche.

part 1

import sys
L = list(list(map(int,s)) for s in sys.stdin.read().splitlines())
W = len(L[0]) ; H = len(L)
N=0
for i in range(H):
    for j in range(W):
        v = L[i][j]
        # look right
        r = all(L[i][k]<v for k in range(j+1, W))
        # look left
        l = all(L[i][k]<v for k in range(j))
        # look up
        u = all(L[k][j]<v for k in range(i))
        # look down
        d = all(L[k][j]<v for k in range(i+1,H))
        N += (r|l|u|d)
print(N, W*H)

part 2

Encore plus moche car le code à répéter quatre fois est plus long.

import sys
L = list(list(map(int,s)) for s in sys.stdin.read().splitlines())
W = len(L[0]) ; H = len(L)
S=0
for i in range(H):
    for j in range(W):
        v = L[i][j]
        # look right
        r = 0
        for k in range(j+1, W):
            r += 1
            if L[i][k]>=v:
                break
        # look left
        l = 0
        for k in range(j-1,-1,-1):
            l+=1
            if L[i][k]>=v:
                break
        # look up
        u = 0
        for k in range(i-1,-1,-1):
            u+=1
            if L[k][j]>=v:
                break
        # look down
        d = 0
        for k in range(i+1,H):
            d += 1
            if L[k][j]>=v:
                break
        S = max(S,r*l*u*d)
print(S)

[^] # Re: python procédural, moche mais efficace

Posté par Yth (Mastodon) le 08 décembre 2022 à 11:51. Évalué à 3.

Mon premier parcours est moins bourrin, je ne cherche pas à savoir pour chaque arbre s'il est visible, mais bien à noter les arbres vus depuis chaque angle de vue, donc au lieu d'avoir size=width*height traitements, j'en ai 2*(width+height).

def check(rows, cols):
    h = -1
    for r in rows:
        for c in cols:
            if input[r][c] > h:
                visible[r * width + c] = True
                h = input[r][c]

visible = [False for _ in range(size)]
for r in range(height):
    check([r], range(width))
    check([r], range(width-1, -1, -1))
for c in range(width):
    check(range(height), [c])
    check(range(height-1, -1, -1), [c])
print(f"Visible Trees : {sum(visible)}")

Pour la seconde partie c'est algorithmiquement équivalent :

def look(h, rows, cols):
    n = 0
    for r in rows:
        for c in cols:
            n += 1
            if input[r][c] >= h:
                return n
    return n

scenic = [0 for _ in range(size)]
for r in range(1, height-1):
    for c in range(1, width-1):
        h = input[r][c]
        scenic[r * width + c] = (
            look(h, range(r-1, -1, -1), [c])  # top
            * look(h, range(r+1, height), [c])  # bottom
            * look(h, [r], range(c-1, -1, -1))  # left
            * look(h, [r], range(c+1, width))  # right
        )
print(f"Best scenic tree : {max(scenic)}")

Yth.

[^] # Re: python procédural, moche mais efficace

Posté par 🚲 Tanguy Ortolo (site web personnel) le 08 décembre 2022 à 13:12. Évalué à 4.

Une petite optimisation pour la première partie : si on arrive à une hauteur de 9, pas la peine de regarder plus loin, aucun arbre ne sera plus haut que ça.

Mais bon, la seconde partie est bien plus coûteuse en temps de toute façon.
[^] # Re: python procédural, moche mais efficace

Posté par steph1978 le 08 décembre 2022 à 15:43. Évalué à 2. Dernière modification le 08 décembre 2022 à 15:43.

Tu as eu une meilleure approche pour le première partie en effet. Il vaut mieux considérer les bords (N²⁾ que toute les position de la grille (N^3).
En pratique all va s'arrêter au premier False, ce qui fait que les chronos sont assez poche (0:33 pour les deux). Aussi parce que N est petit (N=99) et que lancer l'interpréteur est incompressible. Mais en théorie, c'est bien meilleur.

# Python avec Numpy

Posté par 🚲 Tanguy Ortolo (site web personnel) le 08 décembre 2022 à 12:09. Évalué à 4.

Bon, j'ai sorti Numpy du coup. C'est modélisé, et assez long en fait.

# Advent of Code 2022, day 8

from __future__ import annotations

from math import prod
from typing import Iterable, Iterator, Set, Tuple, Type

import numpy as np


Coords = Tuple[int, int]


class Grid:
    def __init__(self, matrix: np.ndarray) -> None:
        self.matrix = matrix
        self.ly = matrix.shape[0]
        self.lx = matrix.shape[1]

    def __scans(self) -> Iterator[Iterator[Iterator[Coords]]]:
        yield (((y, x) for x in range(self.lx)) for y in range(self.ly))
        yield (((y, x) for x in range(self.lx - 1, -1, -1))
               for y in range(self.ly))
        yield (((y, x) for y in range(self.ly)) for x in range(self.lx))
        yield (((y, x) for y in range(self.ly - 1, -1, -1))
               for x in range(self.lx))

    def visible_from_outside(self) -> Set[Coords]:
        visible_trees = set()  # type: Set[Coords]
        for scan in self.__scans():
            for line in scan:
                max_height = -1
                for coords in line:
                    cur_height = self.matrix[coords]
                    if cur_height > max_height:
                        visible_trees.add(coords)
                        max_height = cur_height
        return visible_trees

    def __viewing_distance(self, orig: Coords, line: Iterator[Coords]) -> int:
        height = self.matrix[orig]
        d = 0
        for coords in line:
            d += 1
            if self.matrix[coords] >= height:
                return d
        return d

    def __lines_of_sight(self, coords: Coords):
        y, x = coords
        yield ((y, x_) for x_ in range(x + 1, self.lx))
        yield ((y, x_) for x_ in range(x - 1, -1, -1))
        yield ((y_, x) for y_ in range(y + 1, self.ly))
        yield ((y_, x) for y_ in range(y - 1, -1, -1))

    def scenic_score(self, coords: Coords):
        return prod(self.__viewing_distance(coords, line)
                    for line in self.__lines_of_sight(coords))

    @classmethod
    def import_lines(class_: Type[Grid], lines: Iterable[str]) -> Grid:
        matrix = np.genfromtxt(lines, delimiter=1, autostrip=True, dtype=int)
        return class_(matrix)


def solve_both(lines: Iterable[str]) -> Tuple[int, int]:
    """Solve both parts of today's puzzle"""
    # Import
    grid = Grid.import_lines(lines)
    # Part 1
    visible = len(grid.visible_from_outside())
    # Part 2
    max_score = max(grid.scenic_score(coords) for coords
                    in np.ndindex(grid.matrix.shape))
    return visible, max_score

# Procrastination

Posté par 🚲 Tanguy Ortolo (site web personnel) le 08 décembre 2022 à 13:05. Évalué à 3.

Alors qu'on a enfin quitté le camp pour aller chercher des caramboles, je ne peux m'empêcher que ça procrastine encore :

– Voilà, le verger c'est par là…
– Oh, regardez, la forêt que nous avons planté il y a quelques années, on pourrait y construire une cabane !
– Oui, super, ça nous changera les idées. Lutin drone-opérateur, tu nous cartographie ça ?
– Patron, venez nous donner un coup de main pour calculer le meilleur emplacement pour notre cabane au lieu d'essayer de régler votre communicateur. On vous l'a déjà dit, il est défectueux, et vous aurez tout le temps pour le réparer plus tard. On a plus important à faire là !
– Et les fruits pour les rennes alors ?
– Les quoi ? Ah, ça… On n'y est pas encore, soyez patient. Vous êtes pressé, vous avez un rendez-vous qui approche ou quoi ?
- [^] # Re: Procrastination
  
  Posté par Yth (Mastodon) le 08 décembre 2022 à 13:14. Évalué à 3.
  Ouais, c'est des glandus ces elfes, on dirait moi le lundi matin…
  - Yth.
- [^] # Re: Procrastination
  
  Posté par Ysabeau 🧶 (site web personnel, Mastodon) le 08 décembre 2022 à 13:47. Évalué à 4.
  
  Faut tenir 24 jours remarque. Alors faire un tour du jardin et dans tous les ateliers ne semble pas complètement inopportun.
  
  Je te rappelle, tout de même, que la livraison se fait en une seule fois pour tout le monde, alors, forcément.
  
  « Tak ne veut pas quʼon pense à lui, il veut quʼon pense », Terry Pratchett, Déraillé.

# En faisant pivoter la forêt

Posté par gled le 09 décembre 2022 à 11:41. Évalué à 1.

Une version sans doute pas du tout optimisée pour compter les arbres visibles depuis les lisières, faisant pivoter le tuple des arbres.

trees = ("30373", "25512", "65332", "33549", "35390")


def count_visible_trees(trees):
    n = 0
    for row in trees:
        tmax = 0
        i = 0
        for tree in row:
            tree = int(tree)
            if not tree:
                continue
            if tree > tmax:
                i += 1
                tmax = tree
        n += i
    return n


def rotate_trees(trees):
    return tuple("".join(row[i] for row in trees) for i in range(len(trees)))[::-1]


n = count_visible_trees(trees)
for _ in range(3):
    trees = rotate_trees(trees)
    n += count_visible_trees(trees)

print(f"Il y a {n} arbres visibles depuis les orées cardinales du bois")

J'imagine qu'en faiasant le même principe avec numpy, ce sera bien plus optimisé.

[^] # Re: En faisant pivoter la forêt

Posté par Yth (Mastodon) le 10 décembre 2022 à 20:24. Évalué à 2. Dernière modification le 10 décembre 2022 à 20:25.
Ya ça en numpy :
https://numpy.org/doc/stable/reference/generated/numpy.rot90.html

J'aime bien l'idée, c'est bourrin, c'est fun, ça fait du code plus léger, et ça ressemble à ce qu'on ferait à la main avec une maquette ou une feuille de papier : on fait tourner (ou on tourne autour) !

Par contre c'est faux je pense.
Il y a des arbres visibles depuis plusieurs côtés, et tu vas les compter plusieurs fois…
- Yth.

Suivre le flux des commentaires

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