• # Mode triche on

    Posté par  . Évalué à 4.

    Ce coup ci j'ai ete paresseux, et pour la deuxieme partie mon code ne marche pas avec tous les inputs.
    J'ai fait le cube correspondant a mon input en papier en inscrivant le numero des faces, pour voir quelle face transitionnait vers quelle face, et j'ai hardcode le passage d'une face a l'autre (methode wrap3D).

    from dataclasses import dataclass
import re

board = []
drawboard = []
ARROWS = {0: ">", 1: "v", 2: "<", 3: "^"}
isPart2 = False

@dataclass
class Me:
    x: int
    y: int
    direction: int  # 0=R 1=D 2=L 3=U

    def wrap2D(self):
        match self.direction:
            case 0:  # right
                return next(x for x in range(len(board[self.y])) if board[self.y][x] != " "), self.y, 0
            case 1:  # down
                return self.x, next(y for y in range(len(board)) if board[y][self.x] != " "), 1
            case 2:  # left
                return len(board[self.y]) - 1, self.y, 2
            case 3:  # up
                return self.x, next(y for y in range(len(board) - 1, -1, -1) if findInBoard(self.x, y) != " "), 3

    def wrap3D(self):
        match self.direction:
            case 0:  # right
                if self.y < 50:  # right of 2 -> right of 5 reversed
                    return 99, 149 - self.y, 2
                elif self.y < 100:  # right of 3 -> down of 2
                    return self.y + 50, 49, 3
                elif self.y < 150:  # right of 5 -> right of 2 reversed
                    return 149, 49 - self.y + 100, 2
                else:  # right of 6 -> down of 5
                    return self.y - 100, 149, 3
            case 1:  # down
                if self.x < 50:  # down of 6 -> up of 2
                    return self.x + 100, 0, 1
                elif self.x < 100:  # down of 5 -> right of 6
                    return 49, self.x + 100, 2
                else:  # down of 2 -> right of 3
                    return 99, self.x - 50, 2
            case 2:  # left
                if self.y < 50:  # left of 1 -> left of 4 reverse
                    return 0, 149 - self.y, 0
                elif self.y < 100:  # left of 3 -> up of 4
                    return self.y - 50, 100, 1
                elif self.y < 150:  # left of 4 -> left of 1 reverse
                    return 50, 49 - self.y + 100, 0
                else:  # left of 6 -> up of 1
                    return self.y - 100, 0, 1
            case 3:  # up
                if self.x < 50:  # up of 4 -> left of 3
                    return 50, self.x + 50, 0
                elif self.x < 100:  # up of 1 -> left of 6
                    return 0, self.x + 100, 0
                else:  # up of 2 -> down of 6
                    return self.x - 100, 199, 3

    def moveWrap(self):
        x, y, dir = self.wrap3D() if isPart2 else self.wrap2D()
        if findInBoard(x, y) == ".":
            self.x = x
            self.y = y
            self.direction = dir

    def drawPosition(self):
        s = drawboard[self.y]
        drawboard[self.y] = s[: self.x] + ARROWS[self.direction] + s[self.x + 1 :]

    def moveBy1(self, offsetX, offsetY):
        match findInBoard(self.x + offsetX, self.y + offsetY):
            case ".":
                self.x += offsetX
                self.y += offsetY
            case " ":
                self.moveWrap()
            case "#":
                pass

    def move(self, size: int):
        for i in range(size):
            match self.direction:
                case 0:  # right
                    self.moveBy1(1, 0)
                case 1:  # down
                    self.moveBy1(0, 1)
                case 2:  # left
                    self.moveBy1(-1, 0)
                case 3:  # up
                    self.moveBy1(0, -1)
            self.drawPosition()

def findInBoard(x, y):
    if x == -1 or y == -1 or y >= len(board) or x >= len(board[y]):
        return " "
    return board[y][x]

with open("2022/input_files/day22") as f:
    data = "".join([line for line in f])
    groups = [group.split("\n") for group in data.split("\n\n")]

board = groups[0]
drawboard = board.copy()
instructions = groups[1][0]

moveSizes = list(map(int, re.findall(r"(\d+)", instructions)))
turns = re.findall(r"([A-Z]+)", instructions)

me = Me(board[0].index("."), 0, 0)

for moveSize, turn in zip(moveSizes, turns):
    me.move(moveSize)
    me.direction += 1 if turn == "R" else -1
    me.direction %= 4
me.move(moveSizes[-1])

password = 1000 * (me.y + 1) + 4 * (me.x + 1) + me.direction
print(f"{password=}")

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

    • [^] # Re: Mode triche on

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

      Ma grippe m'a rattrapé, le premier exo nickel, le second j'ai cédé comme toi sur les données des faces et rotations, et passé des heures à débugger un code bon à jeter !

      Mon dernier code tombe enfin sur le bon résultat, mais je sais pas bien pourquoi par rapport aux précédents.
      L'algo est bon depuis ce matin 9h30 environ…
      C'est juste qu'il est mal écrit, et que j'arrive à rien :)

      Dommage, si j'avais été plus vite, j'aurais peut-être essayé une représentation.

      • Yth.

      • [^] # Re: Mode triche on

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

        Titre de l'image

        Un truc dans ce goût là mais mieux fait parce que là c'est pas raccord, j'ai dû me planter dans mes rotations ^

        • Yth.

        • [^] # Re: Mode triche on

          Posté par  . Évalué à 3.

          Alors la je suis oblige de te demander plus de details sur cette visualisation qui est absolument sublime.
          Meme les axes sont super jolis.
          Quelle bibliotheque ou outil as-tu utilise pour ca?

          Personnellement je n'ai paradoxalement pas trop galere pour ce probleme. A peu pres une heure pour chaque partie. Pour la partie 2 je n'ai meme pas ecrit la fonction de transition de faces pour les donnees de test pour gagner du temps. C'est la premiere fois que je zappe les donnees de test. Les mouvements avaient l'air corrects sur ma visualisation, et une fois n'est pas coutume c'est passe du premier coup.

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

          • [^] # Re: Mode triche on

            Posté par  . Évalué à 5.

            C'est de l'openscad. Évoqué jour 18.

            • [^] # Re: Mode triche on

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

              faces = " 12  3  56  4   "  # positions des faces du d6 dans mon input, mis en ligne


smax = cubesize - 1
for row in range(totalsize):
    for col in range(totalsize):
        c = board2[row][col]
        if c == " ":
            continue
        color = {".": "Blue", "#": "Gray", "<": "White", ">": "White", "v": "White", "^": "White"}[c]
        face = faces[(col//cubesize) + (row//cubesize) * 4]
        a, b = col % cubesize, row % cubesize
        if face == "1":
            x, y, z, X, Y, Z = a, b, smax + 1, 1, 1, .01
        elif face == "2":
            x, y, z, X, Y, Z = smax + 1, b, smax - a, .01, 1, 1
        elif face == "3":
            x, y, z, X, Y, Z = a, 0, smax - b, 1, .01, 1
        elif face == "4":
            x, y, z, X, Y, Z = b, smax + 1, smax - a, 1, .01, 1
        elif face == "5":
            x, y, z, X, Y, Z = 0, smax - b, smax - a, .01, 1, 1
        elif face == "6":
            x, y, z, X, Y, Z = a, smax - b, 0, 1, 1, .01
        print(f"color(\"{color}\") translate([{x},{y},{z}]) cube([{X},{Y},{Z}]);")

              Le switch de 1 à 6 applique les rotations, et déplacements en 3D pour poser la surface de la face du cube sur la face du cube 3D, j'ai dû inverser des trucs à des endroits.
              C'est sous optimisé pour de l'openScad, mais j'ai fait ça rapidement, on génère tout de même 15000 objets (50x50x6), ça le perturbe pas beaucoup cela dit !

              Le fichier scad est xzippé ici : aoc-2022-22-01.scad.xz

              Et OpenScad se trouve dans toutes les bonnes crémeries de logiciels libres ;)

              • Yth.

  • # Il était vraiment sympa celui-ci :-)

    Posté par  . Évalué à 1.

    Environ 4h-4h30 effectif dessus.
    La première partie est fastidieuse, mais çà se code bien (~2h)

    La deuxième partie est encore plus fastidieuse.
    J'ai opté pour une classe "Arrete" agrégeant 2 segments caractérisés par une direction.

    Si on est dans un de ces 2 segments en matchant la direction de ce dernier, j'applique la transformation de changement d’arête.
    J'ai donc pris le temps d'identifier manuellement les arêtes du jeu de test pour valider mon algo. Je me suis aidé d'un petit découpage papier
    pour faciliter l'opération.

    Puis, j'ai fait pareil pour mon jeu de données. C'est le plus long.

    Par exemple pour le Jeu de test, elle donne ceci.
    9,9->9,12L 8,8->5,8D
    5,5->8,5U 9,1->9,4L
    13,9->16,9U 12,8->12,5R
    1,5->4,5U 12,1->9,1U
    4,8->1,8D 9,12->12,12D
    13,12->16,12D 1,8->1,5L
    12,4->12,1R 16,9->16,12R

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



public class A2022D22V2 {


    public static List<String> memory = new ArrayList<>();
    public static class Point  {
        int x;
        int y;

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

    public static class Segment {
        Point start;
        Point end;
        Direction direction;

        Segment(String part) {
            String[] points=  part.split("->");
            start = parsePoint(points[0]);
            end = parsePoint(points[1].substring(0, points[1].length()-1));

            char dir = points[1].charAt(points[1].length()-1);
            direction = Arrays.stream(Direction.values()).filter(a->a.name().charAt(0) == dir).findAny().orElse(null);
        }

        public Point parsePoint(String point) {

            String[] coords = point.split(",");
            Point p = new Point();
            p.x = Integer.valueOf(coords[0]);           
            p.x -= 1 ;

            p.y = Integer.valueOf(coords[1]);
            p.y -= 1;

            return p;
        }

        public String toString() {
            return start + " -> " + end + " " + direction;
        }

        public boolean include(int s, int v, int e) {
            if(s > e) {
                int t = s;
                s = e;
                e = t;
            }
            return s <= v && v <= e;
        }

        public boolean include(A2022D22V2.Point p) {
            return include(start.x, p.x, end.x)
                    && include(start.y, p.y , end.y); 
        }
    }

    public static class Arrete {
        Segment a;      
        Segment b;

        public Arrete(String row) {
            String[] part = row.split(" ");
            a = new Segment(part[0]);
            b = new Segment(part[1]);           
        }       

        public String toString() {
            return a + " <=> " + b;
        }

        public static int normalize(int dx) {
            if(dx < 0 ) {
                return -1;
            }
            if(dx == 0) {
                return 0;
            }
            return 1;
        }

        public boolean moveTo(List<String> rowMap, A2022D22V2.Segment src, A2022D22V2.Segment dst, Monkey p) {
            int dx = normalize(src.end.x - src.start.x);
            int dy = normalize(src.end.y - src.start.y);

            int sx = src.start.x;
            int sy = src.start.y;

            int i = 0;

            while (sx != p.x || sy != p.y) {
                sx += dx;
                sy += dy;
                i++;
            }

            dx = normalize(dst.end.x - dst.start.x);
            dy = normalize(dst.end.y - dst.start.y);

            sx = dst.start.x;
            sy = dst.start.y;

            while(i > 0) {
                sx += dx;
                sy += dy;
                i--;                
            }

            System.out.println("Move:" + p.x + "," + p.y);
            System.out.println("====>" + sx + "," + sy);
            if(getChar(rowMap, sx ,sy) == '#') {
                System.out.println("Blocked");
                return false;

            }
            System.out.println("Ok!");


            p.x = sx;
            p.y = sy;
            p.direction = dst.direction.left().left();

            displayMap(p, true);
            return true;
        }
    }

    public enum Direction {
        RIGHT(1, 0, "UP", "DOWN",0),
        DOWN(0, 1, "RIGHT", "LEFT", 1),
        LEFT(-1,0, "DOWN", "UP", 2),
        UP(0, -1, "LEFT", "RIGHT", 3),

        ;
        int dx;
        int dy;
        int score;

        String rotateLeft;
        String rotateRight;
        private Direction(int dx, int dy, String rotateLeft,String rotateRight, int score) {
            this.dx = dx;
            this.dy = dy;
            this.rotateLeft = rotateLeft;
            this.rotateRight = rotateRight;
            this.score =score;
        };

        Direction left() {
            return Direction.valueOf(rotateLeft);
        }

        Direction right() {
            return Direction.valueOf(rotateRight);
        }
    }


    public static class Monkey extends Point{


        Direction direction = Direction.RIGHT;

    }

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

    private static void step1() {
        List<String> rowMap = new ArrayList<>();
        String path = "";
        int maxWidth = 0;
        try (Scanner in = new Scanner(A2022D22V2.class.getResourceAsStream("/res/i22V2.txt"))) {            
            while (in.hasNext()) {
                String row = in.nextLine();
                if(row.isEmpty()) {
                    path = in.nextLine();
                } else {
                    maxWidth = Math.max(maxWidth, row.length());
                    rowMap.add(row);
                }
            }
        }

        List<Arrete> arretes = new ArrayList<>();


        try (Scanner in = new Scanner(A2022D22V2.class.getResourceAsStream("/res/i22V2rf.txt"))) {
            boolean parse = false;
            while (in.hasNext()) {
                String row = in.nextLine().trim();
                if("Parse".equals(row)) {
                    parse = true;
                } else if(parse) {
                    System.out.println(row);
                    Arrete arrete  =new Arrete(row);
                    arretes.add(arrete);
                    System.out.println(arrete);
                }

            }
        }

        normalizeMap(rowMap, maxWidth);

        Monkey monkey = new Monkey();
        monkey.x = rowMap.get(0).indexOf("."); 
        monkey.y = 0;

        System.out.println(path);

        int index = 0;
        while(index < path.length() && index >= 0) {
            if(path.charAt(index) == 'L') {
                System.out.println("Left");
                monkey.direction = monkey.direction.left();
                index+=1;
            } else if(path.charAt(index) == 'R') {
                System.out.println("Right");
                monkey.direction = monkey.direction.right();
                index+=1;
            } else {

                int i = Integer.valueOf(path.substring(index).replaceAll("^([0-9]*).*", "$1"));
                System.out.println("Move " + i);
                index += (""+i).length();
                do {                    
                    if(!translateToValid(rowMap, arretes, monkey))  {
                        break;
                    }                   
                    i--;
                    displayMap(monkey, false);
                } while(i > 0);

            }
            displayMap(monkey, false);
        }
        displayMap(monkey, true);
        System.out.println(monkey.y+1);
        System.out.println(monkey.x+1);
        System.out.println(monkey.direction);
        int result = (monkey.y+1)*1000+(monkey.x+1)*4+monkey.direction.score;
        System.out.println(result);
    }

    private static void normalizeMap(List<String> rowMap, int maxWidth) {

        for(int y=0;y < rowMap.size();y++) {
            if(rowMap.get(y).length() < maxWidth) {

                String row = rowMap.get(y);
                while(row.length() < maxWidth) {
                    row += " ";
                }
                rowMap.set(y, row);
            }
            memory.add(new String(rowMap.get(y)));
        }
    }

    public static char getChar(List<String> rowMap, int sx, int sy) {
        String row = rowMap.get(sy);
        return row.charAt(sx);
    }

    private static boolean translateToValid(List<String> rowMap, List<Arrete> arretes, Monkey monkey) {     
        for(Arrete arrete: arretes) {           
            //System.out.println(arrete.a);
            if(arrete.a.include(monkey) && arrete.a.direction == monkey.direction) {
                System.out.println(arrete.a + " " + monkey.direction);
                return arrete.moveTo(rowMap, arrete.a, arrete.b, monkey);


            }


            if(arrete.b.include(monkey) && arrete.b.direction == monkey.direction) {
                System.out.println(arrete.b + " " + monkey.direction);
                return arrete.moveTo(rowMap, arrete.b, arrete.a, monkey);

            }

        }

        if(getChar(rowMap, monkey.x + monkey.direction.dx , monkey.y + monkey.direction.dy) == '#') {
            return false;
        }

        monkey.x += monkey.direction.dx;
        monkey.y += monkey.direction.dy;
        return true;
    }

    private static void displayMap(Monkey monkey, boolean print) {
        System.out.println();
        for(int y=0;y < memory.size();y++) {
            String row = memory.get(y);
            for(int x=0;x < row.length(); x++) {
                if(monkey.x == x && monkey.y== y) {
                    char c;
                    switch (monkey.direction) {
                            case UP: 
                                c = '^';
                                break;                              
                            case DOWN: 
                                c = 'u';
                                break;                  
                            case RIGHT: 
                                c = '>';
                                break;                  
                            case LEFT: 
                                c = '<';
                                break;                      
                            default:
                                throw new IllegalArgumentException("Unexpected value: " + monkey.direction);
                    }
                    if(print) System.out.print(c);
                    StringBuilder sb = new StringBuilder(row);
                    sb.setCharAt(x, c);
                    row = sb.toString();
                    memory.set(y, row);
                } else {
                    if(print) System.out.print(row.charAt(x));
                }

            }
            if(print) System.out.println();
        }
    }

}

  • # papier, ciseaux, colle

    Posté par  . Évalué à 5.

  • # Trop pour moi

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

    Bon, aucun problème pour la première partie, en revanche pour la seconde, j'y renonce… pour le moment.

    L'intérêt de Avent du Code est entre autres, pour moi, dans la satisfaction d'avoir implémenté des algorithmes originaux, astucieux, élégants, etc. Dans ce cas, en particulier, coder en dur la disposition particulière de mes données d'entrée serait très insatisfaisant. Quant à coder un algorithme qui implémente la modélisation des faces d'un cube à partir d'un patron arbitraire, je n'ai trouvé pour cela aucun moyen qui ne soit pas très, très fastidieux à écrire.

    Donc, pour le moment, je laisse tomber. J'y reviendrai peut-être plus tard dans l'année.

    • [^] # Re: Trop pour moi

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

      C'est amusant, l'AoC regorge d'exemples de choses qui sont évidentes pour un humain, mais assez ou très difficiles à mettre en algorithme, qui sera d'ailleurs fort différent de la pensée humaine.

      Deux beaux exemples cette année :

      • Comment trouver les trous dans une pierre ponce (ou un emmental, ou une éponge) ? Facile, ça se voit ! Et en algorithme ? Euh, inondation depuis l'extérieur, ça ne remplit pas les trous, qu'on peut déterminer ensuite par différence, par exemple.
      • Comment relier et orienter les faces d'un patron de cube ? Facile, on découpe et on plie ! Et comme algorithme ? Euh, c'est compliqué !

      • [^] # Re: Trop pour moi

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

        Je pense que l'idée du patron peut fonctionner.
        Tu as 12 liens à faire, les 12 arêtes, et déjà quelques-unes de posées : les faces adjacentes, il y en a 5 dans un patron.
        Et là de proche en proche tu peux recontruire les liens manquants.

        Avec les données d'exemple mais en modélisant un vrai dé, tu as ça:
        __1_
        453_
        __62

        Les liens sont : 1-3, 3-6, 3-5, 5-4, 6-2
        À gauche de la face 1 et de la face 3 tu as la même face, ici on l'a à gauche de la face 3, c'est la 5, tu peux donc lier 1 et 5 avec une rotation de -1 de 1 vers 5 et de +1 de 5 vers 1.

        Et tu cherches des faces adjacentes dont une des deux a un voisin, tu vas pouvoir faire :

        • 1 et 3 -> 5 -> ajoute 1-5
        • 3 et 5 -> 6 -> ajoute 5-6
        • 3 et 6 -> 2 -> ajoute 3-2

        Tu viens de passer à 8 arêtes, et tu sais qui te manque :
        1-2, 1-4, 2-4, 4-6.
        Là je suppose qu'il faut chercher des voisins virtuels, par exemple tu as le lien construit 3-2, 3 adjacent à 1, selon la première méthode :

        • 1 et 3 -> 2' -> ajoute 1-2' où 2' est la rotation de 2 selon le lien construit 3-2, en additionnant les rotations, on a un demi-tour entre 1 et 2.
        • 4 et 5 -> 1' -> ajoute 4-1' où 1' est la rotation de 1 selon le lien construit 1-5, en additionnant les rotations, on a aussi un demi-tour entre 1 et 4.
        • 4 et 5 -> 6' -> ajoute 4-6' où 6' est la rotation de 6 selon le lien construit 5-6, en additionnant les rotations, on a aussi un demi-tour entre 4 et 6.

        Trois liens de premier niveau nous permettent de trouver trois liens de second niveau, il nous reste un dernier lien à trouver : 4-2, chacun à l'autre bout du bidule.
        Mais avec 2', le 2 construit à côté de 3 avec une rotation de -1, on a un alignement de 4 faces : 4-5-3-2, qu'on aurait pu avoir sur un patron initial d'ailleurs. Et là 4-2' est lié directement parce que la terre est ronde (un truc du genre), donc on a notre lien 4-2 avec une rotation dont il faut bien calculer le sens avec une aspirine.

        Bref, on doit pouvoir bricoler un algorithme en deux passe et un dernier lien, et tout reconstruire.

        • Yth.

Suivre le flux des commentaires

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