Méthode de Guillaume

J'ai implémenté la méthode avec séquence quadratique de Guillaume B.
Je suis un peu décu de ne pas avoir trouvé par moi-même

Mais je suis très heureux d'avoir découvert ce point des maths que je ne connaissais pas.

package aoc2023;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Scanner;
import java.util.Set;
public class Aoc2023s21s3 {
 public static Point[] DIRECTIONS = new Point[] { new Point(1, 0), new Point(-1, 0), new Point(0, -1),
 new Point(0, 1) };
 public record Point(int x, int y) { 
 }
 public static class State { 
 Set<Point> current = new HashSet<>();;
 Set<Point> next = new HashSet<>();;
 char[][] map;
 int width;
 int height;
 List<Long> quadraticsSeries = new ArrayList<>();
 public void propagate(Point p) {
 for (Point move : DIRECTIONS) {
 int dx = p.x + move.x;
 int dy = p.y + move.y;
 int rx = dx % width;
 if (rx < 0) {
 rx += width;
 }
 int ry = dy % height;
 if (ry < 0) {
 ry += height;
 }
 Point np = new Point(dx, dy); 
 if (map[ry][rx] == '.') {
 next.add(np);
 }
 }
 }
 public long propagate(World world, int step) {
 map = world.map;
 width = world.width;
 height = world.height;
 // gridSize d'une taille arbitaire suffisant propage au moins une grille complète (à priori)
 int gridSize = width * 2;
 // étape pour lesquels on va récupérer les valeurs de u(n) pour la séquence quadratique.
 int same = (step-1) % gridSize;
 int end = same + gridSize*2+1; 
 // Boucle de propagation (très inefficace) 
 System.out.println("Propagation maximum à calculer :" + end);
 for (int i = 0; i < end; i++) {
 next.clear();
 current.forEach(p -> propagate(p));
 // switch
 Set<Point> tmp = next;
 next = current;
 current = tmp;
 if(i >= 0 && (i % (gridSize)) == same) { 
 System.out.println("u(" + current.size() + ") = " + current.size());
 quadraticsSeries.add((long)current.size());
 } 
 }
 long d1 = quadraticsSeries.get(1) - quadraticsSeries.get(0); 
 long d2 = quadraticsSeries.get(2) - quadraticsSeries.get(1); 
 //long d3 = quadraticsSeries.get(3) - quadraticsSeries.get(2);
 System.out.println("dp:" + (d2-d1));
 //System.out.println("dp:" + (d3-d2)); // si la séquence est quadratique d2-d1 == d3-d2 == d4-d3 ...
 long a = (d2-d1)/2;
 long c = quadraticsSeries.get(0);
 // a n^2 + b n + c = u(n) 
 // b = (u(n) - a n^2 - c)/n
 int n = 2;
 double b = (quadraticsSeries.get(n) - a * n * n - c)/n;
 System.out.println(quadraticsSeries);
 System.out.println(a + "," + b + "," + c);
 /*
 // Vérifie via la propagation jusqu'à u(3) que la formule u(n) = a*x^2 + bx+c est bien paramétré.
 n = 3; 
 long control3 = (long)(a * n * n + n * b + c);
 System.out.println("Control3:" + control3);
 if(control3 != quadraticsSeries.get(3)) {
 throw new RuntimeException("Failed to compute u(n) = a*x^2 + bx+c ");
 }*/
 n = ((step)/gridSize);
 return (long)(a * n * n + n * b + c); 
 } 
 public boolean match(int x, int y) {
 return current.contains(new Point(x, y));
 }
 }
 public static class World {
 final int width;
 final int height;
 char[][] map;
 State state = new State();
 public World(List<String> rows) {
 height = rows.size();
 width = rows.get(0).length();
 map = new char[height][width];
 for (int y = 0; y < height; y++) {
 String row = rows.get(y);
 for (int x = 0; x < width; x++) {
 if (row.charAt(x) == 'S') {
 state.current.add(new Point(x, y));
 map[y][x] = '.';
 } else {
 map[y][x] = row.charAt(x);
 }
 }
 }
 }
 }
 public static void main(String[] args) {
 try (Scanner in = new Scanner(Aoc2023s21s3.class.getResourceAsStream("res/t21.txt"))) {
 List<String> rows = new ArrayList<>();
 while (in.hasNext()) {
 rows.add(in.nextLine());
 }
 World world = new World(rows); 
 System.out.println(world.state.propagate(world, 26501365)); 
 } 
 }
}