Re: Modélisation trop longue à débugger

Au final, J'aurai mis 35min de plus.

Le problème venait que j'avais mis une règle qui réduisait le nombre d'action possible pendant mon parcours en profondeur

Il met 1min3s pour calculer le 2ème.

Pour une fois , mon code n'est pas trop moche :)

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Random;
import java.util.Scanner;
import java.util.Set;
import java.util.stream.Collectors;
public class A2022D19 {
 private static final String BUILD_ORE = "BUILD_ORE";
 private static final String BUILD_CLAY = "BUILD_CLAY";
 private static final String BUILD_OBSIDIAN = "BUILD_OBSIDIAN";
 private static final String BUILD_GEODE = "BUILD_GEODE";
 private static final String WAIT = "WAIT";
 static Map<BluePrint, Integer> bestMap = new HashMap<>();
 public static class Cost {
 int costOre;
 int costClay;
 int costObsidian;
 public String toString() {
 return costOre +";" + costClay + ";" + costObsidian;
 } 
 } 
 public static class BluePrint {
 int index;
 Cost buildOreRobot;
 Cost buildClayRobot;
 Cost obsidianRobot; 
 Cost geodeRobot;
 public BluePrint(String row, int index) {
 this.index = index;
 String[] robots = row.split("\\.");
 buildOreRobot = buildCost(robots[0]);
 buildClayRobot = buildCost(robots[1]);
 obsidianRobot = buildCost(robots[2]);
 geodeRobot = buildCost(robots[3]);
 }
 private Cost buildCost(String row) {
 Cost cost = new Cost();
 String regex;
 regex = ".* ([0-9]*) ore.*";
 if(row.matches(regex)) {
 String s = row.replaceAll(regex, "1ドル");
 cost.costOre = Integer.valueOf(s);
 }
 regex = ".* ([0-9]*) clay.*";
 if(row.matches(regex)) {
 String s = row.replaceAll(regex, "1ドル");
 cost.costClay = Integer.valueOf(s);
 }
 regex = ".* ([0-9]*) obsidian.*";
 if(row.matches(regex)) {
 String s = row.replaceAll(regex, "1ドル");
 cost.costObsidian = Integer.valueOf(s);
 }
 System.out.println(cost.toString());
 return cost;
 }
 } 
 public static class Action {
 int buildOreRobot = 0;
 int buildClayRobot = 0;
 int buildObsidianRobot = 0;
 int buildGeodeRobot = 0;
 }
 public static class State {
 BluePrint bp;
 int oreRobot = 1;
 int clayRobot = 0;
 int obsidianRobot = 0;
 int geodeRobot = 0;
 int ore = 0;
 int clay = 0;
 int obsidian = 0;
 int geode = 0;
 int index=0;
 public State(BluePrint bp) {
 this.bp = bp;
 }
 public boolean canPaid(Cost cost) {
 return ore >= cost.costOre
 && clay >= cost.costClay
 && obsidian >= cost.costObsidian; 
 }
 public void paid(Cost cost ) {
 ore -= cost.costOre;
 clay -= cost.costClay;
 obsidian -= cost.costObsidian;
 }
 public List<String> availablesAction() {
 List<String> actions = new ArrayList<>();
 if(canPaid(bp.geodeRobot)) { 
 actions.add(BUILD_GEODE);
 return actions;
 }
 if(canPaid(bp.obsidianRobot)) { 
 actions.add(BUILD_OBSIDIAN);
 return actions;
 }
 if(canPaid(bp.buildClayRobot) && max(bp.buildOreRobot.costClay, bp.buildClayRobot.costClay, bp.obsidianRobot.costClay, bp.geodeRobot.costClay) > this.clayRobot) { 
 actions.add(BUILD_CLAY); 
 }
 if(canPaid(bp.buildOreRobot) && max(bp.buildOreRobot.costOre, bp.buildClayRobot.costOre, bp.obsidianRobot.costOre, bp.geodeRobot.costOre) > this.oreRobot) { 
 actions.add(BUILD_ORE); 
 }
 actions.add(WAIT);
 return actions;
 }
 private int max(int costOre, int costOre2, int costOre3, int costOre4) {
 return Math.max(Math.max(Math.max(costOre, costOre2), costOre3), costOre4);
 }
 public void transform(String command) {
 ++index;
 //System.out.println(index);
 //System.out.println(command); 
 this.ore += this.oreRobot;
 this.clay += this.clayRobot;
 this.obsidian += this.obsidianRobot; 
 this.geode += this.geodeRobot; 
 if(command.equals(BUILD_GEODE)) {
 paid(bp.geodeRobot);
 this.geodeRobot++;
 }
 if(command.equals(BUILD_OBSIDIAN)) {
 paid(bp.obsidianRobot);
 this.obsidianRobot++;
 }
 if(command.equals(BUILD_CLAY)) {
 paid(bp.buildClayRobot);
 this.clayRobot++;
 }
 if(command.equals(BUILD_ORE)) {
 paid(bp.buildOreRobot);
 this.oreRobot++;
 }
 //System.out.println("S:" + this.ore + ";" + this.clay + ";" + this.obsidian + ";" + this.geode);
 //System.out.println("R:" + this.oreRobot + ";" + this.clayRobot + ";" + this.obsidianRobot + ";" + this.geodeRobot);
 }
 public void copyInto(A2022D19.State newState) {
 newState.bp = this.bp;
 newState.oreRobot = this.oreRobot;
 newState.clayRobot = this.clayRobot;
 newState.obsidianRobot = this.obsidianRobot;
 newState.geodeRobot = this.geodeRobot;
 newState.ore = this.ore;
 newState.clay = this.clay;
 newState.obsidian = this.obsidian;
 newState.geode = this.geode;
 newState.index= this.index;
 }
 }
 public static void main(String[] args) {
 step1();
 }
 public static void executeDFS(State state) {
 if(state.index == 32) {
 if(bestMap.get(state.bp) == null || state.geode > bestMap.get(state.bp)) { 
 bestMap.put(state.bp, state.geode); 
 System.out.println("Best:" + state.bp.index +";" + state.geode); 
 }
 return;
 }
 List<String> actions =state.availablesAction();
 State newState = new State(state.bp);
 for(String action : actions) { 
 state.copyInto(newState);
 newState.transform(action);
 executeDFS(newState);
 }
 }
 private static void step1() {
 try (Scanner in = new Scanner(A2022D19.class.getResourceAsStream("/res/i19.txt"))) {
 List<BluePrint> listBp = new ArrayList<>(); 
 while (in.hasNext()) {
 String row = in.nextLine();
 BluePrint bp = new BluePrint(row, listBp.size()+1); 
 listBp.add(bp);
 }
 State state; 
 for(BluePrint bp: listBp) {
 state =new State(bp);
 executeDFS(state);
 } 
 int sum = 0;
 int prod = 1;
 for(Map.Entry<BluePrint, Integer> e : bestMap.entrySet()) {
 System.out.println("Final:" + e.getKey().index + "," + e.getValue()); 
 prod *= e.getValue();
 sum += (e.getKey().index * e.getValue());
 }
 System.out.println(sum);
 System.out.println(prod);
 }
 }
}