Frankenstein solution in java

 avatar
unknown
plain_text
10 months ago
4.6 kB
14
Indexable
import java.util.*;

public class Frankenstein {
        static Map<String, List<List<String>>> recipes = new HashMap<>();
            static Map<String, Integer> memo = new HashMap<>();

                public static void main(String[] args) {
                            Scanner sc = new Scanner(System.in);
                                    int N = Integer.parseInt(sc.nextLine().trim());

                                            // Read recipes
                                                    for (int i = 0; i < N; i++) {
                                                                    String line = sc.nextLine().trim();
                                                                                String[] parts = line.split("=");
                                                                                            String potion = parts[0].trim();
                                                                                                        String[] ingArr = parts[1].split("\\+");
                                                                                                                    List<String> ingredients = new ArrayList<>();
                                                                                                                                for (String ing : ingArr) {
                                                                                                                                                    ingredients.add(ing.trim());
                                                                                                                                }
                                                                                                                                            recipes.computeIfAbsent(potion, k -> new ArrayList<>()).add(ingredients);
                                                    }

                                                            // Target potion
                                                                    String target = sc.nextLine().trim();

                                                                            // Calculate and print minimum orbs
                                                                                    int result = getMinOrbs(target);
                                                                                            System.out.println(result);
                }

                    static int getMinOrbs(String potion) {
                                if (memo.containsKey(potion)) return memo.get(potion);

                                        // If potion is not in recipes, it is a base item
                                                if (!recipes.containsKey(potion)) {
                                                                memo.put(potion, 0);
                                                                            return 0;
                                                }

                                                        int minOrbs = Integer.MAX_VALUE;

                                                                for (List<String> ingredients : recipes.get(potion)) {
                                                                                int orbs = ingredients.size() - 1; // base orbs for combining ingredients
                                                                                            for (String ing : ingredients) {
                                                                                                                orbs += getMinOrbs(ing); // add cost of brewing each ingredient
                                                                                            }
                                                                                                        minOrbs = Math.min(minOrbs, orbs);
                                                                }

                                                                        memo.put(potion, minOrbs);
                                                                                return minOrbs;
                    }
}
                                                                                            }
                                                                }
                                                }
                    }
                                                                                                                                }
                                                    }
                }
}
Editor is loading...
Leave a Comment