Forum Programmation.autre Advent of Code 2023 : Day 3

Posté par alberic89 🐧 le 03 décembre 2023 à 17:04. Licence CC By‑SA.

Étiquettes :

déc.

2023

Le troisième d'une série de 25 forums qui proposeront de partager vos solutions pour l'édition 2023 de l'Advent of Code.

Vous pouvez vous inscrire à un leadboard privé que j'ai créé pour LinuxFR : 2423220-c94050af

Jour 3 (résumé) :

Partie 1

Vous empruntez une télécabine pour vous rendre à la source. Mais elle ne fonctionne pas. Un lutin vous explique qu'il manque des pièces, mais on ne sait pas lesquelles.

Il faudrait la somme de tous les numéros de pièce sur le schéma pour savoir lesquelles manquent. Mais ne doivent être comptés comme des pièces les nombres qui sont adjacents (diagonaux ou directs) à un symbole (sauf le point).

Un exemple :

467..114..
...*......
..35..633.
......#...
617*......
.....+.58.
..592.....
......755.
...$.*....
.664.598..

Les nombres qui ne sont pas des pièces sont 114 et 58, la somme des autres à retrouver est 4361.

Partie 2

Mais ce n'est pas tout, il y a aussi un engrenage qui est faussé, il faut le trouver pour le changer.

Un engrenage est un symbole « * » qui est adjacent à exactement 2 pièces. Son ratio est la multiplication des numéros des deux pièces.

Le même exemple :

467..114..
...*......
..35..633.
......#...
617*......
.....+.58.
..592.....
......755.
...$.*....
.664.598..

Il y a là deux engrenages (celui à côté de 617 n'est adjacent qu'à une seule pièce). Le premier est en haut à gauche et a pour pièces 467 et 35, soit un ratio de 16345. Le deuxième en bas à droite en a un de 451490. Leur somme que vous devez trouver est de 467835.

# Je me lance ma soluce en Java

Posté par syj le 03 décembre 2023 à 21:32. Évalué à 1.

Un peu long à coder, j'ai passé plus de temps sur la première partie que sur la deuxième partie.

Partie 1 :

public class Aoc2023s3p1 {
    public static void main(String[] args) {
        try(Scanner in = new Scanner(Aoc2023s3p1.class.getResourceAsStream("res/Aoc2023s3p1.txt"))) {
                String row;
                int sum =0;

                List<String> rows = new ArrayList<>();

                while(in.hasNext()) {
                    row = in.nextLine();
                    rows.add(row);
                }

                for(int x=0;x < rows.size();x++) {
                    sum += check(x, rows);
                }


                System.out.println(sum);
        }
    }

    public static record Num(int start, int end, String data) {
    }


    public static int check(int rowIndex, List<String> rows) {

        String row = rows.get(rowIndex);

        List<Num> list = new ArrayList<>();
        Integer start = null;
        for(int x=0;x < row.length();x++) {
            int c = row.charAt(x) - '0';
            if(Character.isDigit(row.charAt(x))) {
                if(start == null) {
                    start = x;
                }
            } else {
                if(start != null) {
                list.add(new Num(start, x, row.substring(start, x)));
                start = null;
                }
            }
        }

        if(start !=null) {
            list.add(new Num(start, row.length(), row.substring(start)));
        }

        int sum = 0;
        for(Num num : list) {
            System.out.println(num);
            if(checkNum(num, rowIndex, rows)) {
                System.out.println("OK");
                sum += Integer.parseInt(num.data());
            }
        }

        return sum;
    }


    private static boolean checkNum(Num num, int rowIndex, List<String> rows) {
        int before = num.start-1;
        if(checkCharacter(rowIndex, before, rows)) {
            return true; 
        }

        if(checkCharacter(rowIndex, num.end, rows)) {
            return true; 
        }


        for(int x = num.start-1;x < num.end+1;x++) {
            if(checkCharacter(rowIndex - 1, x, rows)
                    || checkCharacter(rowIndex + 1, x, rows)) {
                return true;
            }
        }
        return false;
    }

    private static boolean checkCharacter(int rowIndex, int colIndex, List<String> rows) {
        if(rowIndex < 0 || rowIndex >= rows.size()) {
            return false;
        }
        String row = rows.get(rowIndex);

        if(colIndex < 0 || colIndex >= row.length()) {
            return false;
        }

        char c = row.charAt(colIndex);
        if(Character.isDigit(c) || c == '.') {
            return false;
        }

        return true;
    }

}

Pour la partie 2, l'idée est assez simple. J'identifie les engrenages '*' par leurs coordonnées et je stocke sur chaque coordonnée la liste des nombres associés (numsById)

public class Aoc2023s3p2 {
    public static Map<Coord, List<Num>> numsById = new HashMap<>();

    public static void main(String[] args) {

        try(Scanner in = new Scanner(Aoc2023s3p2.class.getResourceAsStream("res/Aoc2023s3p1.txt"))) {
                String row;


                List<String> rows = new ArrayList<>();

                while(in.hasNext()) {
                    row = in.nextLine();
                    rows.add(row);
                }

                for(int x=0;x < rows.size();x++) {
                    check(x, rows);
                }


                int sum =0;
                for(List<Num> nums: numsById.values()) {

                    if(nums.size() <= 1) {
                        continue;
                    }
                    System.out.println("=====");
                    int prod = 1;
                    for(Num num : nums) {
                        prod *= Integer.parseInt(num.data);
                        System.out.println(num.data);
                    }
                    System.out.println("=>" + prod);
                    sum += prod;
                }

                System.out.println(sum);
        }
    }

    public static record Num(int start, int end, String data) {
    }


    public static void check(int rowIndex, List<String> rows) {
        String row = rows.get(rowIndex);

        List<Num> list = new ArrayList<>();
        Integer start = null;
        for(int x=0;x < row.length();x++) {
            int c = row.charAt(x) - '0';
            if(Character.isDigit(row.charAt(x))) {
                if(start == null) {
                    start = x;
                }
            } else {
                if(start != null) {
                list.add(new Num(start, x, row.substring(start, x)));
                start = null;
                }
            }
        }

        if(start !=null) {
            list.add(new Num(start, row.length(), row.substring(start)));
        }

        for(Num num : list) {
            System.out.println(num);
            if(isGearPart(num, rowIndex, rows)) {
                System.out.println("OK");
            }
        }


    }


    private static boolean isGearPart(Num num, int rowIndex, List<String> rows) {


        int before = num.start-1;
        checkGear(num, rowIndex, before, rows);
        checkGear(num, rowIndex, num.end, rows);


        for(int x = num.start-1;x < num.end+1;x++) {
            checkGear(num, rowIndex - 1, x, rows);
            checkGear(num, rowIndex + 1, x, rows);
        }



        return false;
    }


    public static record Coord(int rowIndex, int colIndex) {

    }

    private static boolean checkGear(Num num, int rowIndex, int colIndex, List<String> rows) {
        if(rowIndex < 0 || rowIndex >= rows.size()) {
            return false;
        }
        String row = rows.get(rowIndex);

        if(colIndex < 0 || colIndex >= row.length()) {
            return false;
        }

        char c = row.charAt(colIndex);
        if(c == '*') {
            numsById.computeIfAbsent(new Coord(rowIndex, colIndex),k->new ArrayList<>()).add(num);

        }

        return false;
    }

}

# Bonne idée.

Posté par djibb (site web personnel) le 04 décembre 2023 à 08:27. Évalué à 2. Dernière modification le 04 décembre 2023 à 08:27.

moi c'est en python, mais c'est une NON réponse… il doit me manquer des cas que je n'identifie pas…

        def nettoyer_point(chaine) :
            """recupère les symboles à utiliser autres que '.'"""
            chaine = chaine.replace(".", "")
            for i in [i for i in range(10)] : 
                chaine = chaine.replace(str(i), '')
            liste = []
            for carac in chaine : 
                if not carac in liste : 
                    liste.append(carac)
            return liste
        print(nettoyer_point(computer2))


        def est_voisin_symbol(matrice_, x,y) : 
            "renvoie si la case x, y est voisine d'un symbole"
            matrice = matrice_.copy()

            for i in range(-1,2) : 
                for j in range(-1, 2) : 
                    matrice
                    if 0<=x+i and 0<=y+j and not (i==j==0): 
                        try : 
                            #if not(matrice[x][y]=='.' or matrice[x][y].isdigit()):
                            if matrice[x+i][y+j] in ['*', '&', '/', '@', '=', '+', '#', '$', '%', '-']: 

                                return True, matrice[x+i][y+j]

                        except IndexError : 
                            pass
            return False, None

        matrice =[]
        for ligne in computer2.split('\n'):
            #print(ligne)
            ligne_ = []
            for carac in ligne : 
                ligne_.append(carac)
            matrice.append(ligne_)



        def verifie_chaine(matrice, chaine,x,y) : 
            "parcours la chaine de gauche à droite jusqu'a un espace"
            x, y = x, y-1
            for _ in range(len(chaine)) : 
                result, symbol = est_voisin_symbol(matrice, x, y)
                if result : 
                    return True, symbol
                y-=1
            return False, None


    i=0
    somme = 0
    while i<len(matrice) : 
        j= 0
        nombre=""
        while j<len(matrice[0]) : 

            if matrice[i][j].isdigit() and j!=len(matrice[0])-1 : 
                nombre += matrice[i][j]
            else :
                #gestion dernier sympbol : 
                if j==len(matrice[0])-1 :
                    if matrice[i][j].isdigit() : 
                        nombre += matrice[i][j]
                result, symbol = verifie_chaine(matrice, nombre, i, j)
                if result : 
                    #print(nombre, symbol)
                    somme +=int(nombre)
                else :
                    if nombre!='' : 
                        print('NON', nombre)
                nombre =""
            j+=1
        i+=1

# On bourrine, on bourrine et on fait des bêtises...

Posté par Yth (Mastodon) le 04 décembre 2023 à 17:25. Évalué à 2.
Faut dire, j'ai pu m'y mettre vers 23h30 hier soir…
Et ma bêtise a été de transformer "927*741" en 927741 au lieu de 927 et 741 séparés.

Déjà, la somme totale de tous les nombre du jeu se calcule ainsi :
```
s = ".".join(x.strip() for x in sys.stdin)
for i in set(x for x in s if x not in "0123456789"):
    s = s.replace(i, " ")
all_numbers = sum(int(i) for i in s.split(" ") if i) # =598313
```
Ce calcul fait à l'avance m'aurait permis de voir que 9691964 comme résultat, c'était ouvertement faux…

Bref, j'ai commencé à chercher certaines optimisations, en utilisant des comparaisons de set() en python, qui sont plutôt efficaces. Et j'aurais probablement dû utiliser des frozenset, car c'est plus rapide, quand on n'a pas besoin de les modifier.
Il reste aussi des optimisations faisables, mais la taille des données ne les justifient pas encore.

Zéro structures de données, un traitement très linéaire, ça reste simple, on ne fait pas encore de réelles abstractions.
```
import sys
directions = ((-1, -1), (-1, 0), (-1, 1), (0, -1), (0, 0), (0, 1), (1, -1), (1, 0), (1, 1))

def envelope(positions):
  return set(
    tuple(sum(x) for x in zip(a, p))
    for p in positions
    for a in directions
  )

numbers = list()
symbols = set()
gears = set()
nl = 0
for line in sys.stdin:
  number = []
  positions = set()
  nc = 0
  for c in line.strip():
    if c in "0123456789":
      number.append(c)
      positions.add((nl, nc))
    else:
      if c != ".":
        print(f"Symbol {c} at {nl}, {nc}")
        symbols.add((nl, nc))
      if c == "*":
        gears.add((nl, nc))
      if number:
        numbers.append((int("".join(number)), envelope(positions)))
        number = []
        positions = set()
    nc += 1
  if number:
    numbers.append((int("".join(number)), envelope(positions)))
    number = []
    positions = set()
  nl += 1
```
numbers est la liste des nombres et de leur « enveloppe » c'est à dire des coordonnées de toutes les cases composant ce nombre et adjacentes à lui.
C'est un set() de doublets.
symbols contient la liste des coordonnées (doublets) de tous les symboles du plan.
gears contient la liste des coordonnées des symboles * uniquement, et ne servira que pour la seconde partie.

Je trouve le code un poil moche, et un meilleur travail sur les entrées, et les conditions boucles, pourrait alléger, mais il faut absolument ne pas se planter dans les cas limites : un nombre en fin de ligne, deux nombres séparés par un symbole (celui-là m'a mis dedans), etc.
Être carré, clairs, précis, sinon c'est l'écran bleu… Euh, enfin, la mauvaise réponse quoi…

La résolution des problèmes est assez simple après ça.
Problème n°1 :
```
result = list()
nope = 0
for number, pos in numbers:
  if symbols.intersection(pos):
    result.append(number)
  else:
    nope += number
print(result)
print(f"Sum of Numbers : {sum(result)} ({nope})")
```
nope me sert à la validation, vu que j'ai la somme de tous ems chiffres qui vaut 598313, je dois avoir result + nope = 598313, et j'aurais pu aussi juste calculer nope et obtenir mon résultat comme ça, par soustraction.
Ça pourra servir comme façon de faire plus tard, je me rappelle d'un exercice avec du sable qui s'écoule, qui peut se résoudre très facilement en regardant uniquement là où il ne s'écoule pas et en faisant une soustraction…

Et le second challenge :
```
gear_value = 0
for gear in gears:
  parts = [
    number
    for number, pos in numbers
    if gear in pos
  ]
  if len(parts) == 2:
    gear_value += parts[0] * parts[1]

print(f"Sum of NumbersGear Value : {gear_value})")
```
Rien à recalculer, on va analyser dans l'autre sens : pour chaque « gear » on regarde dans combien de « number » il se trouve, si c'est 2, bingo, on l'ajoute.
C'est tout.
- Yth.
- [^] # Re: On bourrine, on bourrine et on fait des bêtises...
  
  Posté par barmic 🦦 le 04 décembre 2023 à 17:58. Évalué à 3.
  
  J'ai une solution proche, mais pas le code sous la main. J'ai trouvé très confortable de lire les lignes via une expression régulière : ([^.\d]|\d+).
  
  Quand tu itère dessus, chaque groupe que tu capture est soit un nombre soit un symbole et je n'ai pas vraiment rencontré de cas au limite.
  
  Pour la seconde partie changer l'expression régulière par (\*|\d+) et le seul changement nécessaire dans l'initialisation.
  
  https://linuxfr.org/users/barmic/journaux/y-en-a-marre-de-ce-gros-troll

# Python

Posté par alberic89 🐧 le 04 décembre 2023 à 20:47. Évalué à 1. Dernière modification le 04 décembre 2023 à 20:49.

Voici ma solution du jour :

#!/bin/python3

def intlen(nb):
    l = 0
    while nb >= 1:
        nb = nb / 10
        l +=1
    return l

def ispart(puzzle,line,col,n):
    try :
        if puzzle[line][col-1].isdigit():
            return 0
    except IndexError:
        pass
    try :
        for i in range(1,5):
            if puzzle[line][col+i].isdigit():
                n = n*10 + int(puzzle[line][col+i])
            else:
                break
    except IndexError:
        pass
    for j in [1,-1]:
        for i in range(-1,intlen(n)+1):
            try :
                if puzzle[line+j][col+i].isdigit() == False and puzzle[line+j][col+i] != ".":
                    return n
            except IndexError:
                pass
    for i in [-1,intlen(n)]:
        try :
            if puzzle[line][col+i].isdigit() == False and puzzle[line][col+i] != ".":
                return n
        except IndexError:
            pass
    return 0

def isgear(puzzle,line,col,j):
    try:
        if puzzle[line][col].isdigit() == False:
            return 0
    except IndexError:
        return 0
    if j != -1:
        try:
            if puzzle[line][col-1].isdigit():
                return 0
        except IndexError:
            pass
    start = 0
    for i in range(-1,-5,-1):
        try:
            if puzzle[line][col+i].isdigit():
                start -= 1
            else:
                break
        except IndexError:
            break
    p = ispart(puzzle, line, col+start, int(puzzle[line][col+start]))
    return p

def solve1(puzzle,testing=False):
    s=0
    for line in range(len(puzzle)):
        for col in range(len(puzzle[line])):
            if puzzle[line][col] == ".":
                continue
            elif puzzle[line][col].isdigit():
                p = ispart(puzzle,line,col,int(puzzle[line][col]))
                s += p
                if testing and p!=0:
                    print("The part ", p," at ", line, ";", col, " is ok.")
    if testing:
        print(s)
    return s

def solve2(puzzle,testing=False):
    s = 0
    for line in range(len(puzzle)):
        for col in range(len(puzzle[line])):
            if puzzle[line][col] == "*":
                ng = 0
                g = [0,0,0]
                for i in [1,0,-1]:
                    for j in [1,0,-1]:
                        g[ng] = isgear(puzzle,line+i,col+j,j)
                        if g[ng] != 0:
                            ng += 1
                        if ng == 3:
                            break
                    if ng == 3:
                            break
                if ng == 2:
                    if testing:
                        print("Gear at ",line,";",col," with parts ",g[0],";",g[1])
                    s += g[0] * g[1]
                elif testing:
                    print("Gear at ",line,";",col," but with ",ng," parts.")
    if testing:
        print(s)
    return s

test1 ="""
467..114..
...*......
..35..633.
......#...
617*......
.....+.58.
..592.....
......755.
...$.*....
.664.598.."""
result1 = 4361
test2 = test1
result2 = 467835

def solve(short=False):

    print("----Part 1----")
    if short == False:
        if solve1(test1.split("\n"),testing=True) != result1:
            print("Not working.")
            return False
        else :
            print("Maybe working?")
    with open("input.txt",'r') as file:
        lines = file.read().split("\n")
        s1 = solve1(lines)
        print(s1)

    print("----Part 2----")
    if short == False:
        if solve2(test2.split("\n"),testing=True) != result2:
            print("Not working.")
            return False
        else :
            print("Maybe working?")
    with open("input.txt",'r') as file:
        lines = file.read().split("\n")
        s2 = solve2(lines)
        print(s2)

    return s1, s2

if __name__ == "__main__":

    from sys import argv

    try:
        if argv[1] == "--summary" or argv[1] == "-s":
            solve(short=True)
    except IndexError:
        solve()

J'ai passé beaucoup de temps à essayer de comprendre pourquoi diable les test fonctionnaient mais pas l'input ! La réponse était dans ma fonction pour récupérer la taille d'un entier :

def intlen(nb):
    l = 0
    while nb > 0:
        nb = nb / 10
        l +=1
    return l

Avec while nb > 0 au lieu de while nb >= 1. Mais les données de test fonctionnaient, c'était incompréhensible.

Et oui, je suis un grand adepte du try ... except quand je code vite et crade.

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.