What is the lowest combination of dual-types that can resist/be immune to every single possible combination of 2 types?

Question

The lowest amount of dual-types required and what they are to resist each possible combination of 2 different types.

Basically what I'm asking is for the lowest amount of dual-types needed to have one dual-type that resists/is immune to both types of another given dual-type, and have that for every dual-type.
I'm getting confused writing this, but I hope you understand.

Thanks in advance.

Comments

i wanna claim this question but i need a lot of time, currently trying to figure out a c++ algorithm that gets the solution that doesnt require just brute forcing every possible combination of defensive dual types

---

You could start with a greedy algorithm that iteratively picks dual types that resist the highest (or near-highest) number of remaining attacker dual types. I think the problem is logically simple enough that a brute force (or some smarter approach that is also 100% conclusive) may not necessarily find a smaller set of type combinations.

Edit: actually scratch that, tried it myself and don't really trust the outputs are the smallest possible. Important thing to get out of the way is whether you're allowed to reuse types? I don't think you can solve the problem at all without this.

---

yeah, but then what after that? you prolly need to store what dual types each dual type resists in some sort of vector array, and then prolly get like a large int array to store what dual types have already been resisted to make sure you dont count unneeded dual types, which itself requires a nested loop, and then it's rinse and repeat like 20 more times minimum

i'll try a very primitive approach but i doubt it's going to be very effective, after all i dont want my computer to blow up. imma say you're allowed to reuse types just for sanity sake

---

You sure? I just did a Python dict matrix of single types, e.g. {'Normal': {'Rock': 0.5, 'Ghost': 0, 'Steel': 0.5}, ...}, then you can calculate dual type effectiveness like: for def_type in [def_type_1, def_type_2]: defender_multiplier *= get_effectiveness(att_type, def_type)
No need to store the outcomes for every dual-type interaction, you only need to count the resistances scored by each defender in order to pick a best candidate to proceed with on each iteration. You still need to store which "attackers" have already been dealt with as the while-loop runs, but that isn't too heavy as there are only 153 of them.

I think the best way to maximise this approach would be to have the greedy algorithm on each iteration randomly pick a defender from a pool that's within a certain % of the top-scoring candidate, then run the whole thing thousands of times. Introducing randomness and running it many times should allow it uncover some veins of type combinations that are efficient. But obviously it cannot ever prove what it found was the lowest.

I'll go ask AI to write that for me, unless you're really keen to work on your own algorithm without seeing any other results?

---

my experience with AI doesnt give me much confidence on your results. i do already have a 2d array setup for the resistances (same purpose as the matrix honestly, also i code in c++) and i'll do a full greedy algorithm to make sure i get the best results (ik it's going to take quite a bit of time but that's what i have tmr lmao)

introducing randomness does increase effeciency, it's just that my competition minded self really wants to try all in case the random approach misses certain combinations