J'en ai bavé.

6h au total ! J'ai commencé par prendre le problème de travers.

J'ai fait substitution récursive des '?' ,c'était mon erreur.

C'est après que j'ai compris qu'il fallait distribuer les espaces restant entre les groupes.

çà permet d'exprimer le problème avec une fonction recursive pour lequel on peut mettre en place un cache des valeurs par rapport au reste à évaluer.

Environ 414ms sur ma machine (après avoir commenté les println)

package aoc2023;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;
import java.util.concurrent.atomic.AtomicLong;
public class Aoc2023s12v4 { 
 public static record Evaluation(List<Integer> groupes, int totalDot, String dstSpring) { 
 }
 public static Evaluation[] cache = new Evaluation[1_000_000];
 public static long[] cacheValue = new long[1_000_000];
 public static void main(String[] args) { 
 assert (countExpandedPossibility("??# 2") == 16L);
 assert (countExpandedPossibility("???.### 1,1,3") == 1L); 
 assert (countExpandedPossibility(".??..??...?##. 1,1,3") == 16384L);
 assert (countExpandedPossibility("????.#...#... 4,1,1") == 16L);
 assert (countExpandedPossibility("????.######..#####. 1,6,5") == 2500L);
 assert (countExpandedPossibility("?###???????? 3,2,1") == 506250L);
 //assert (countExpandedPossibility("???.?#?????##?#????? 1,2,7,1") == 506250L);
 System.out.println("----------- -----------");
 System.out.println("----------- END TEST -----------");
 System.out.println("----------- -----------");
 try (Scanner in = new Scanner(Aoc2023s12v4.class.getResourceAsStream("res/t12.txt"))) {
 List<String> map = new ArrayList<>();
 while (in.hasNext()) {
 String row = in.nextLine();
 map.add(row);
 }
 long count = 0;
 for (String row : map) {
 count += countExpandedPossibility(row);
 }
 System.out.println(count);
 }
 }

 private static long countExpandedPossibility(String row) {
 String srcSprings = row.split(" ")[0];
 int[] srcRules = Arrays.stream(row.split(" ")[1].split(",")).mapToInt(s -> Integer.parseInt(s)).toArray();
 long r = countExpanded(srcSprings, srcRules, 5);
 System.out.println(r);
 return r;
 }

 private static long countExpanded(String srcSprings, int[] srcRules, int i) {
 int[] dstRules = new int[srcRules.length * 5];
 for (int x = 0; x < i; x++) {
 for (int y = 0; y < srcRules.length; y++) {
 dstRules[x * srcRules.length + y] = srcRules[y];
 }
 }
 String dstSpring = srcSprings;
 for(int x=0;x < i-1;x++) {
 dstSpring += '?' + srcSprings;
 } 
 System.out.println("Pattern:");
 System.out.println(dstSpring);
 int total = Arrays.stream(dstRules).sum();
 int totalDot = dstSpring.length() - total;
 System.out.println(total + " + " + totalDot + " => " + dstSpring.length());
 return distributeDotBetweenGroup(
 Arrays.stream(dstRules).mapToObj(Integer::valueOf).toList(),
 true,
 totalDot, 
 dstSpring); 
 }

 private static long distributeDotBetweenGroup(List<Integer> groupes, boolean first, int totalDot, String dstSpring) { 
 if(0 == groupes.size() ) {
 String current = "";
 for(int j=0;j < totalDot;j++) {
 current += '.';
 }
 //System.out.println(sb);
 if(match(current, dstSpring)) { 
 return 1; 
 }
 return 0;
 }
 int size = groupes.get(0);
 StringBuilder sb = new StringBuilder();
 long sum = 0;
 for(int ud=(first? 0:1);ud <= totalDot;ud++) {
 sb.setLength(0); 
 for(int j=0;j < ud;j++) {
 sb.append('.'); 
 } 
 for(int j=0;j < size;j++) {
 sb.append('#');
 }
 if(! match(sb, dstSpring, sb.length())) {
 continue;
 }
 Evaluation eva= new Evaluation(groupes.subList(1, groupes.size()), totalDot-ud, dstSpring.substring(sb.length()));
 int indexCache =Math.abs(eva.hashCode())% cache.length;
 if(cache[indexCache] !=null && cache[indexCache].equals(eva)) {
 sum += cacheValue[indexCache];
 } else {
 long i= distributeDotBetweenGroup(eva.groupes, false, eva.totalDot, eva.dstSpring);
 cache[indexCache] = eva;
 cacheValue[indexCache] = i;
 sum += i;
 } 
 }
 return sum;
 }

 private static boolean match(String test, String refPattern) {
 if(test.length() != refPattern.length()) {
 return false;
 }
 for (int x = 0; x < test.length(); x++) {
 char c = refPattern.charAt(x);
 if (c != '?') {
 if (test.charAt(x) != c) {
 return false;
 }
 }
 }
 return true;
 }

 private static boolean match(StringBuilder test, String refPattern, int wi) { 
 for (int x = 0; x < wi; x++) {
 char c = refPattern.charAt(x);
 if (c != '?') {
 if (test.charAt(x) != c) {
 return false;
 }
 }
 }
 return true;
 }
}