Forum Programmation.autre Avent du Code, jour 24

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

Étiquettes :

déc.

2022

Aujourd'hui , on brave le blizzard. Il faut aider les elfes à traverser les blizzards qui parcours la plaine.

https://adventofcode.com/2022/day/24

'''
With everything replanted for next year (and with elephants and monkeys to tend the grove), you and the Elves leave for the extraction point.

Partway up the mountain that shields the grove is a flat, open area that serves as the extraction point. It's a bit of a climb, but nothing the expedition can't handle.

At least, that would normally be true; now that the mountain is covered in snow, things have become more difficult than the Elves are used to.

As the expedition reaches a valley that must be traversed to reach the extraction site, you find that strong, turbulent winds are pushing small blizzards of snow and sharp ice around the valley. It's a good thing everyone packed warm clothes! To make it across safely, you'll need to find a way to avoid them.'''

# Parcours en largeur.

Posté par syj le 24 décembre 2022 à 11:21. Évalué à 5.

On est dans le cas typique d'un parcours en largeur d'un arbre des possibles.

A chaque round, on regarde l'ensemble des actions possibles et on calcule les états suivants en fonction de ses possibilités
il y a des branches qui s'élimine d'elle-même car il n'y a plus d'action possible pour le joueur.
il y aussi des branches qui se rejoingne car il y a plusieurs chemin pour arriver à un même état.
J'utilise le hashCode/equals de mon State pour les dédupliquer sinon çà explose grave.

Au total,j'ai mis 1h50 pour debug les différentes conneries que j'ai fait à mon réveille.

Je mets 40s pour calculer la solution de la 2ème étoiles

Maintenant, je vais aller braver les magasins car j'ai plein de cadeau à acheter :-).
Joyeux Noël à tous.

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.Objects;
import java.util.Scanner;
import java.util.Set;
import java.util.stream.Collectors;

public class A2022D24 {
    public enum Move {
        EAST(1, 0, '>'),

        SOUTH(0, 1, 'v'), WEST(-1, 0, '<'), WAIT(0, 0, 'W'), NORTH(0, -1, '^');

        int dx;
        int dy;
        char d;

        private Move(int dx, int dy, char d) {
            this.dx = dx;
            this.dy = dy;
            this.d = d;
        };

    }

    public static class Point {
        int x;
        int y;

        public Point() {
        }

        public Point(int x, int y) {
            this.x = x;
            this.y = y;
        }

        public String toString() {
            return x + "," + y;
        }

        public void copyInto(Point p) {
            p.x = this.x;
            p.y = this.y;
        }

        @Override
        public int hashCode() {
            return Objects.hash(x, y);
        }

        @Override
        public boolean equals(Object obj) {
            if (this == obj)
                return true;
            if (obj == null)
                return false;
            if (getClass() != obj.getClass())
                return false;
            Point other = (Point) obj;
            return x == other.x && y == other.y;
        }


    }

    public static class Wind extends Point {
        Move m;

        public Wind(int x, int y) {
            this.x = x;
            this.y = y;
        }

        public void copyInto(Wind wind) {
            super.copyInto(wind);
            wind.m = m;

        }

    }

    public static class State {
        List<Wind> winds = new ArrayList<>();
        Point pos = new Point(1, 0);
        int round = 0;

        public void copyInto(State state) {
            state.winds.clear();
            for (Wind w : this.winds) {
                Wind newWind = new Wind(0, 0);
                w.copyInto(newWind);
                state.winds.add(newWind);
            }

            this.pos.copyInto(state.pos);
            state.round = this.round;

        }

        public char count(int x, int y) {
            char c = '.';
            int count = 0;
            for (Wind wind : this.winds) {
                if (wind.x == x && wind.y == y) {
                    count++;
                    c = wind.m.d;
                }
            }
            if(count > 1) {
                c = ("" + count).charAt(0);
            }
            return c;

        }

        public boolean isFree(int x, int y) {
            if ((x == WIDTH - 2) && (y == HEIGHT - 1)) {
                return true;
            }

            if ((x == 1) && (y == 0)) {
                return true;
            }

            if (y <= 0 || x <= 0 || x >= (WIDTH - 1) || y >= (HEIGHT - 1)) {
                return false;
            }

            for (Wind wind : this.winds) {
                if (wind.x == x && wind.y == y) {
                    return false;
                }
            }
            return true;

        }

        public List<A2022D24.Move> getAvailables() {
            return Arrays.stream(Move.values()).filter(m -> isFree(pos.x + m.dx, pos.y + m.dy))
                    .collect(Collectors.toList());
        }

        public void moveWind() {
            for (Wind wind : winds) {
                wind.x = wind.x + wind.m.dx;
                wind.y = wind.y + wind.m.dy;

                if (wind.x == 0) {
                    wind.x = WIDTH - 2;
                } else if (wind.x == WIDTH - 1) {
                    wind.x = 1;
                }

                if (wind.y == 0) {
                    wind.y = HEIGHT - 2;
                } else if (wind.y == HEIGHT - 1) {
                    wind.y = 1;
                }
            }
        }

        public void print() {
            for (int y = 0; y < HEIGHT; y++) {
                for (int x = 0; x < WIDTH; x++) {

                    if (x == pos.x && y == pos.y) {
                        System.out.print("E");
                    } else if (isFree(x, y)) {
                        System.out.print(".");
                    } else if(x == 0 || x == (WIDTH-1) || y == 0 || y == HEIGHT-1) {
                        System.out.print("#");
                    } else {
                        System.out.print(count(x, y));
                    }

                }
                System.out.println();
            }
        }

        @Override
        public int hashCode() {
            return Objects.hash(pos, round);
        }

        @Override
        public boolean equals(Object obj) {
            if (this == obj)
                return true;
            if (obj == null)
                return false;
            if (getClass() != obj.getClass())
                return false;
            State other = (State) obj;
            return Objects.equals(pos, other.pos) && round == other.round;
        }
    }

    public static void main(String[] args) {
        step1();
    }

    public static int WIDTH = 0;
    public static int HEIGHT = 0;

    private static void step1() {
        List<Wind> winds = new ArrayList<>();

        try (Scanner in = new Scanner(A2022D24.class.getResourceAsStream("/res/i24.txt"))) {
            int y = 0;
            while (in.hasNext()) {
                String row = in.nextLine();

                for (int x = 0; x < row.length(); x++) {
                    final char d = row.charAt(x);

                    Move blizzard = Arrays.stream(Move.values()).filter(c -> {
                        return c.d == d;
                    }).findAny().orElse(null);

                    if(blizzard != null) {
                        Wind wind = new Wind(x, y);
                        wind.m = blizzard;
                        winds.add(wind);
                    }

                }
                WIDTH = row.length();
                y++;
            }

            HEIGHT = y;



            State state = new State();
            state.pos = new Point(1, 0);
            state.winds = winds;


            int round = 0;
            int targetX = WIDTH-2;
            int targetY = HEIGHT-1;
            state = foundSolution(state, targetX, targetY);

            state = foundSolution(state, 1, 0);
            state = foundSolution(state, targetX, targetY);
            System.out.println(state.round);
        }
    }

    private static State foundSolution(State start, int targetX, int targetY) {
        Set<State> previous = new HashSet<>();

        previous.add(start);
        Set<State> next = new HashSet<>(); 

        Set<State> tmp;
        State state;
        while(true) {
            System.out.println("States stack:" + previous.size() + " round:" + previous.iterator().next().round);
            next.clear();
            for(State s :previous) {
                if(s.pos.x == targetX && s.pos.y == targetY)  {
                    return s;

                }


                explore(next, s);
            }

            tmp = previous;
            previous = next;
            next = tmp;
        }
    }

    private static void explore(Set<State> next,  A2022D24.State state) {

        //state.print();
        state.moveWind();
        List<Move> moves = state.getAvailables();
        if(moves.size() == 0) {
            //System.out.println("empty");
        }

        for (Move move : moves) {
            State newState = new State();
            state.copyInto(newState);
            newState.pos.x += move.dx;
            newState.pos.y += move.dy;
            newState.round++;

            if (!newState.isFree(newState.pos.x, newState.pos.y)) {
                throw new RuntimeException(); 
            }

            next.add(newState);
        }

    }
}

# Sympa

Posté par Eric P. le 24 décembre 2022 à 11:47. Évalué à 4.

Bien joue!

Ma solution prend:
epignet@dell> time bin/pypy 2022/day24.py trip1=249 trip2=246 trip3=240 (trip1+trip2+trip3)=735 bin/pypy 2022/day24.py 5.65s user 0.07s system 99% cpu 5.748 total
5.65s pour la partie 2.

J'utilise une liste de dictionaires pour ma grille, le dictionnaire etait le nombre de chaque caractere dans la case.
J'utilise un deque pour mon BFS.

Ce que j'ai fait pour optimiser au maximum, c'est:
python -m cProfile 2022\day24.py
qui ma dit que c'etait ma fonction qui retourne les cases libres autour de moi, qui etait la ou je passais le plus de temps. Du coup j'ai precalcule si chaque case etait libre au moment de mettre a jour les blizzards, pour ne pas avoir a le faire pour chaque essai.
Chaque essai consiste juste a est verifier les cases libres autour de soi et ajouter a un deque, ce qui est ultra rapide si les cases libres sont precalculees.

J'ai fait la partie 2 apres le repas de reveillon - eh oui il est 21:46 a Sydney a l'heure ou j'ecris, c'est peut-etre les quelques verres de Champagne qui m'ont fait un peu galerer sur un bug bete (je recalculais la grille une fois de trop apres chaque trajet) mais la partie 2 n'ajoutait pas de difficulte.

Excusez l'absence d'accents dans mes commentaires, j'habite en Australie et n'ai pas de clavier francais sous la main.

# Belle modélisation, rapide, efficace.

Posté par Yth (Mastodon) le 24 décembre 2022 à 16:34. Évalué à 4.

Je suis fier de moi !
Bon, j'ai pu démarrer très tard aujourd'hui, mais j'ai été efficace et j'ai fait du joli code, court et propre.
Une bête erreur de préparation a flingué ma perfection, pour le calcule des 4 directions de mouvements, j'avais fait droite, gauche, bas, gauche… Et les données de test passent : ya jamais besoin d'aller en haut pour trouver la bonne solution, rhaaa !

Bref, j'ai relu, j'ai trouvé, et j'ai passé à peine quelques minutes entre le 1 et le 2, le temps de mettre le code d'itération dans une fonction avec une position de départ et une d'arrivée, et de l'appeler trois fois d'affilé.

Exécution en 1,5 secondes.
Utilisation extensives des set(), union, intersection.
J'ai aussi eu une flemme terrifiante de calculer un PPCM, alors il est mochement en dur dans le code, comme quoi tout n'est pas si beau ^{^}

from collections import deque

class Position(tuple):
    def __add__(self, other):
        return Position((self[0] + other[0], self[1] + other[1]))
    def __contains__(self, other):
        return (
            0 <= other[0] < self[0] and
            0 <= other[1] < self[1])
    def moves(self, dimensions):
        return (
            _
            for _ in (self + (1, 0), self + (-1, 0), self + (0, 1), self + (0, -1))
            if _ in dimensions
        )

def whirlwind(x, y, d, w, h, n):
    if d == ">":
        return [(_ % w, y) for _ in range(x, x + n)]
    if d == "<":
        return [(_ % w, y) for _ in range(x, x - n, -1)]
    if d == "^":
        return [(x, _ % h) for _ in range(y, y - n, -1)]
    if d == "v":
        return [(x, _ % h) for _ in range(y, y + n)]


data = sys.stdin.read().strip().splitlines()
dimensions = Position((len(data[0]) - 2, len(data) - 2))  # should be 120, 25
ppcm = 12 if dimensions[0] == 6 else 600  # complete whirlwind board cycle length
start = Position((data[0].index(".") - 1, -1))  # Should be (0, -1)
startpos = start + (0, 1)  # Should be (0, 0)
end = Position((data[-1].index(".") - 1, dimensions[1]))  # should be (6, 3) or (120, 24)
# ending on the tile before the end, north of it, last move being unique, and unstoppable
endpos = end + (0, -1)  # Should be (5, 3) or (119, 24)
board = deque((set(_) for _ in zip(*[
    whirlwind(x - 1, y - 1, c, dimensions[0], dimensions[1], ppcm)
    for y, line in enumerate(data)
    for x, c in enumerate(line)
    if c in "<>^v"
])), ppcm)


def reach(start, end, board, dimensions):
    positions = {start}
    i = 0
    while end not in positions:
        positions = positions.union(
            p
            for _ in positions
            for p in _.moves(dimensions)
        ).difference(board[0])
        board.rotate(-1)
        i += 1
    return i


r1 = reach(start, endpos, board, dimensions)
r2 = reach(end, startpos, board, dimensions)
r3 = reach(start, endpos, board, dimensions)
print(f"Reaching destination in {r1} rounds")
print(f"Returning to start in {r2} rounds")
print(f"Reaching destination again in {r3} rounds")
print(f"Total of {r1+r2+r3=} rounds")

L'état du terrain avec ses tornades est cycliques en PPCM(largeur, hauteur), donc je calcule tous les états possibles au début et je me balade après en faisant tourner le deque.
L'initialisation est presque plus longue que la solution…

Yth.

[^] # Re: Belle modélisation, rapide, efficace.

Posté par Eric P. le 24 décembre 2022 à 23:36. Évalué à 1. Dernière modification le 24 décembre 2022 à 23:36.

J'aime beaucoup ta solution en effet. Joli et super efficace!

Chez moi aussi, c'est le calcul des grilles qui est plus long que la solution. Vu qu'il n'etait execute que moins de 300 fois par trajet, je n'ai pas cherche a l'optimiser. La ou je passe le plus de temps c'est pendant le deepcopy de ma grille avant de commencer la suivante.
Justement j'ai beaucoup ton calcul de grilles. A la place de looper sur les etats et mettre a jour la grille complete, tu calcules chaque blizzard pour chaque etat, et ensuite tu zippes tout ca avec l'unpacking operator.

Le PPCM par contre ne te fait pas gagner tant que ca vu qu'il n'est pas beaucoup plus petit que le nombre complet d'etats a connaitre.

Excusez l'absence d'accents dans mes commentaires, j'habite en Australie et n'ai pas de clavier francais sous la main.
- [^] # Re: Belle modélisation, rapide, efficace.
  
  Posté par Yth (Mastodon) le 25 décembre 2022 à 12:20. Évalué à 3.
  Le PPCM ça me permet juste d'avoir une modélisation complète directement, et plus un calcul après.
  Je t'assure qu'avec mon bug initial où on n'allait jamais vers le haut, on fait défiler les rounds, le temps de relire le code, c'est plus de 100 000 qui sont passés à tourner en rond sur un cycle de 600, logique 😅
  
  Bref, ça permet un plantage très performant !
  - Yth.

Suivre le flux des commentaires

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

# Parcours en largeur.

# Sympa

# Belle modélisation, rapide, efficace.

[^] # Re: Belle modélisation, rapide, efficace.

[^] # Re: Belle modélisation, rapide, efficace.