import java.math.*;
import java.text.*;
import java.util.*;


// The main method must be in a class named "Main".
class Main {
    private static final List<String> excludeList = List.of(
            "new", 
            "grand",
            "all"
    );
    
    private static final List<String> list = List.of(
            "2",
            "3",
            "6",
            "ALL NEW BT50",
            "BT50",
            "CX3",
            "CX30",
            "CX5",
            "CX9",
            "MX5",
            "NEW 3",
            "NEW 6",
            "NEW BT50",
            "NEW CX5",
            "NEW CX9"
    );
    
    public static void main(String[] args) {
        var input = "all new bt50";
        
        System.out.println("input: " + input);
        var result1 = match(input, list, null);
        System.out.println("result no exclude: " + result1);
        var result2 = match(input, list, excludeList);
        System.out.println("result with exclude: " + result2);
    }
    
    @SuppressWarnings("java:S135")
    public static List<String> match(String text, List<String> list, List<String> excludeList) {
        if (text == null || list == null || list.isEmpty()) return new ArrayList<>();

        if (excludeList == null) excludeList = new ArrayList<>();
        excludeList = excludeList.stream()
                .filter(item -> item != null && item.trim().length() > 0)
                .map(item -> item.toLowerCase().trim())
                .toList();

        var result = new ArrayList<String>();
        var comparationresult = new TreeMap<Double, TreeMap<Double, List<String>>>();

        var textNormalized = Main.normalizeText(text);
        var textWords = Arrays.asList(textNormalized.split(" "));
        var textWordsSimplified = Main.removeListInList(textWords, excludeList);
        for (var item : list) {
            // validar datos
            if (item == null || item.length() == 0) continue;

            // normaliza dato
            var itemNormalized = Main.normalizeText(item);
            var itemWords = Arrays.asList(itemNormalized.split(" "));

            // si la coincidencia es exacta
            if (itemNormalized.equals(textNormalized)) {
                result.add(item);
                continue;
            }

            // comparar palabras
            var matches = Main.findMatches(textWordsSimplified, itemWords);
            var difference = Main.calculeMatchDifference(matches, textWordsSimplified, itemWords);
            var distance = Main.calculeMatchDistance(matches, itemWords);

            var differenceScaled = BigDecimal.valueOf(difference)
                    .setScale(4, RoundingMode.HALF_UP)
                    .doubleValue();
            var distanceScaled = BigDecimal.valueOf(distance)
                    .setScale(4, RoundingMode.HALF_UP)
                    .doubleValue();

            if (difference >= 1.0) continue;

            Main.addValue(comparationresult, differenceScaled, distanceScaled, item);
        }

        for (var entry : comparationresult.entrySet()) {
            for (var subEntry : entry.getValue().entrySet()) {
                result.addAll(subEntry.getValue());
            }
        }

        return result;
    }

    public static List<String> removeListInList(List<String> list1, List<String> list2) {
        if (list1 == null || list1.isEmpty()) return new ArrayList<>();

        if (list2 == null) list2 = new ArrayList<>();
        List<String> finalList = list2;
        return list1.stream().filter(item -> !finalList.contains(item)).toList();
    }

    public static String normalizeText(String text) {
        if (text == null) return "";

        text = text.toLowerCase().replaceAll("\\s+", " ").trim();
        return Normalizer.normalize(text, Normalizer.Form.NFD).replaceAll("\\p{InCombiningDiacriticalMarks}", "");
    }


    private static Map<Integer, String> findMatches(List<String> words1, List<String> words2) {
        var matches = new LinkedHashMap<Integer, String>();

        var nextMatchIndex = 0;
        for (var word : words1) {
            for (var j = nextMatchIndex; j < words2.size(); j++) {
                var item = words2.get(j);
                if (word.equals(item)) {
                    matches.put(j, word);
                    nextMatchIndex = j + 1;
                    break;
                }
            }
        }

        return matches;
    }

    private static double calculeMatchDifference(Map<Integer, String> matches, List<String> words, List<String> wordsToCompare) {
        var totalSize = (double) words.size() + (double) wordsToCompare.size();

        return (totalSize - (2 * matches.size())) / totalSize;
    }

    private static double calculeMatchDistance(Map<Integer, String> matches, List<String> wordsToCompare) {
        var matchSize = (double) matches.size();
        var maxDifference = (double) wordsToCompare.size();

        var matchIndex = 0;
        var distanceSum = 0;
        for (var index : matches.keySet()) {
            var distance = Math.abs(matchIndex - index);
            distanceSum += distance;
            matchIndex++;
        }

        return 1 - ((matchSize - (distanceSum / maxDifference)) / maxDifference);
    }

    private static void addValue(SortedMap<Double, TreeMap<Double, List<String>>> map, double mainkey, double subKey, String value) {
        map.computeIfAbsent(mainkey, k -> new TreeMap<>());
        map.get(mainkey).computeIfAbsent(subKey, k -> new ArrayList<>());
        map.get(mainkey).get(subKey).add(value);
    }

}