Here is my code:
const fs = require("fs");
const { type } = require("os");
//Functions
const reformat = (types) => {
let map = new Map();
types.forEach((e) => {
let id = e.name;
let val = [e.strengths];
map.set(id, val);
});
return map;
};
const search = (types) => {
let arr = [];
let flags = [];
let count = 0;
types.forEach((strength, type) => {
// console.log(`1: ${type}: ${strength}`);
let a = type;
let b, c;
strength[0].forEach((type_b) => {
let strengths_b = types.get(type_b);
// console.log("2: " strengths_b);
strengths_b[0].forEach((type_c) => {
let strengths_c = types.get(type_c);
// console.log("3: " strengths_c);
if (strengths_c[0].includes(a)) {
let b = type_b;
let c = type_c;
console.log(`Found: ${a} => ${b} => ${c}`);
arr.push([a, b, c]);
} else {
}
});
});
});
// console.log(arr);
};
//Procedure
let types = JSON.parse(fs.readFileSync("types.json"));
types = reformat(types);
search(types);
// console.log(types);
Here's the JSON file:
[
{
"name": "Normal",
"immunes": ["Ghost"],
"weaknesses": ["Rock", "Steel"],
"strengths": []
},
{
"name": "Fire",
"immunes": [],
"weaknesses": ["Fire", "Water", "Rock", "Dragon"],
"strengths": ["Grass", "Ice", "Bug", "Steel"]
},
{
"name": "Water",
"immunes": [],
"weaknesses": ["Water", "Grass", "Dragon"],
"strengths": ["Fire", "Ground", "Rock"]
},
{
"name": "Electric",
"immunes": ["Ground"],
"weaknesses": ["Electric", "Grass", "Dragon"],
"strengths": ["Water", "Flying"]
},
{
"name": "Grass",
"immunes": [],
"weaknesses": [
"Fire",
"Grass",
"Poison",
"Flying",
"Bug",
"Dragon",
"Steel"
],
"strengths": ["Water", "Ground", "Rock"]
},
{
"name": "Ice",
"immunes": [],
"weaknesses": ["Fire", "Water", "Ice", "Steel"],
"strengths": ["Grass", "Ground", "Flying", "Dragon"]
},
{
"name": "Fighting",
"immunes": ["Ghost"],
"weaknesses": ["Poison", "Flying", "Psychic", "Bug", "Fairy"],
"strengths": ["Normal", "Ice", "Rock", "Dark", "Steel"]
},
{
"name": "Poison",
"immunes": ["Steel"],
"weaknesses": ["Poison", "Ground", "Rock", "Ghost"],
"strengths": ["Grass", "Fairy"]
},
{
"name": "Ground",
"immunes": ["Flying"],
"weaknesses": ["Grass", "Bug"],
"strengths": ["Fire", "Electric", "Poison", "Rock", "Steel"]
},
{
"name": "Flying",
"immunes": [],
"weaknesses": ["Electric", "Rock", "Steel"],
"strengths": ["Grass", "Fighting", "Bug"]
},
{
"name": "Psychic",
"immunes": ["Dark"],
"weaknesses": ["Psychic", "Steel"],
"strengths": ["Fighting", "Poison"]
},
{
"name": "Bug",
"immunes": [],
"weaknesses": [
"Fire",
"Fighting",
"Poison",
"Flying",
"Ghost",
"Steel",
"Fairy"
],
"strengths": ["Grass", "Psychic", "Dark"]
},
{
"name": "Rock",
"immunes": [],
"weaknesses": ["Fighting", "Ground", "Steel"],
"strengths": ["Fire", "Ice", "Flying", "Bug"]
},
{
"name": "Ghost",
"immunes": ["Normal"],
"weaknesses": ["Dark"],
"strengths": ["Psychic", "Ghost"]
},
{
"name": "Dragon",
"immunes": ["Fairy"],
"weaknesses": ["Steel"],
"strengths": ["Dragon"]
},
{
"name": "Dark",
"immunes": [],
"weaknesses": ["Fighting", "Dark", "Fairy"],
"strengths": ["Psychic", "Ghost"]
},
{
"name": "Steel",
"immunes": [],
"weaknesses": ["Fire", "Water", "Electric", "Steel"],
"strengths": ["Ice", "Rock", "Fairy"]
},
{
"name": "Fairy",
"immunes": [],
"weaknesses": ["Fire", "Poison", "Steel"],
"strengths": ["Fighting", "Dragon", "Dark"]
}
]
And here's the output:
Found: Fire => Grass => Water
Found: Fire => Grass => Ground
Found: Fire => Grass => Rock
Found: Fire => Ice => Ground
Found: Fire => Steel => Rock
Found: Water => Fire => Grass
Found: Water => Ground => Electric
Found: Electric => Water => Ground
Found: Grass => Water => Fire
Found: Grass => Ground => Fire
Found: Grass => Ground => Poison
Found: Grass => Rock => Fire
Found: Grass => Rock => Ice
Found: Grass => Rock => Flying
Found: Grass => Rock => Bug
Found: Ice => Grass => Rock
Found: Ice => Ground => Fire
Found: Ice => Ground => Rock
Found: Ice => Ground => Steel
Found: Ice => Flying => Fighting
Found: Fighting => Ice => Flying
Found: Fighting => Rock => Flying
Found: Fighting => Dark => Psychic
Found: Fighting => Steel => Fairy
Found: Poison => Grass => Ground
Found: Ground => Fire => Grass
Found: Ground => Fire => Ice
Found: Ground => Electric => Water
Found: Ground => Poison => Grass
Found: Ground => Rock => Ice
Found: Ground => Steel => Ice
Found: Flying => Grass => Rock
Found: Flying => Fighting => Ice
Found: Flying => Fighting => Rock
Found: Psychic => Fighting => Dark
Found: Bug => Grass => Rock
Found: Rock => Fire => Grass
Found: Rock => Fire => Steel
Found: Rock => Ice => Grass
Found: Rock => Ice => Ground
Found: Rock => Flying => Grass
Found: Rock => Flying => Fighting
Found: Rock => Bug => Grass
Found: Ghost => Ghost => Ghost
Found: Dragon => Dragon => Dragon
Found: Dark => Psychic => Fighting
Found: Steel => Ice => Ground
Found: Steel => Rock => Fire
Found: Steel => Fairy => Fighting
Found: Fairy => Fighting => Steel
As you noticed, similar results are printed multiple times (such that Fire/Grass/Water is printed 3 times for each element).
Also, the algorithm is super brute-force with three loops stacked on top each other (I assume that would make it O(n^3)?). I remember seeing a similar problem to this (not Pokemon, but similar structure etc.) but I can't remember or figure out what's the best way to go about this problem without going through brute-force and wasting processing power by iterating through existing element chains. I tried using Map and all that but nothing seem to work. This is my first stackoverflow post so pardon me if I put some of these wrong!
CodePudding user response：
I'm not sure its possible to reduce the complexity of the initial query (someone else, please prove me wrong :) )
However, since all results are static (weaknesses and strengths don't change) you could calculate everything once with your brute force approach and store the result in a flat object or json file. From then on the lookup would be O(1).
Depending on what information you want you could have a format like:
alternatives = {
fire: ['Grass Water', 'Grass Ground', 'Grass Rock', 'Ice Ground', 'Steel Rock'],
water: ['Fire Grass', 'Ground Electric'],
..
}
Best of luck
CodePudding user response：
This is my first stackoverflow post so pardon me if I put some of these wrong!
Actually, this is quite a well-done first post. Kudos!
But there are two things I would suggest:
You should probably give more description of the problem. Your working source code is great, but I'm sure I'm not the only one who knows nothing about Pokemon and so has no context for the question. I don't know what a "starter set" is, or what the arrows in your title and output represent (perhaps nothing.)
You might read How do I create a runnable stack snippet? so that readers can see the result right in their browsers. (You can edit the post at any time to add one.)
Now to the question itself.
You are worried about performance. Have you tested to see that it's not already fast enough? If the above is the extent of the data, then I would not expect this to take more than a handful of milliseconds to process. Is that too long? Or is the real data much larger? And if it is larger, can you not do what Zac Butko suggests and run it statically either as a build step, storing the result in a file or during application initialization, storing it in memory for the life of the application?
I don't have any suggestion for anything to speed this up. It seems to me that you have to visit all the O (n ^ 3) paths through the data, so there's a hard lower algorithmic bound. (I've been wrong on this before, and maybe I am here, but I'm not sure how it could be done.)
But I do have what I think is cleaner code to do the same thing. A first pass, which creates the same output that you found, could look like this:
const paths = (types, length, children = Object .keys (types)) =>
length <= 1
? children .map (s => [s])
: children .flatMap (s => paths (types, length - 1, types [s]) .map (p => [s, ...p]))
const search = (ts, types = Object .fromEntries (ts .map ((t) => [t .name, t .strengths]))) =>
paths (types, 3) .filter ((s) => types [s [s .length - 1]] .includes (s [0]))
const types = [{name: "Normal", immunes: ["Ghost"], weaknesses: ["Rock", "Steel"], strengths: []}, {name: "Fire", immunes: [], weaknesses: ["Fire", "Water", "Rock", "Dragon"], strengths: ["Grass", "Ice", "Bug", "Steel"]}, {name: "Water", immunes: [], weaknesses: ["Water", "Grass", "Dragon"], strengths: ["Fire", "Ground", "Rock"]}, {name: "Electric", immunes: ["Ground"], weaknesses: ["Electric", "Grass", "Dragon"], strengths: ["Water", "Flying"]}, {name: "Grass", immunes: [], weaknesses: ["Fire", "Grass", "Poison", "Flying", "Bug", "Dragon", "Steel"], strengths: ["Water", "Ground", "Rock"]}, {name: "Ice", immunes: [], weaknesses: ["Fire", "Water", "Ice", "Steel"], strengths: ["Grass", "Ground", "Flying", "Dragon"]}, {name: "Fighting", immunes: ["Ghost"], weaknesses: ["Poison", "Flying", "Psychic", "Bug", "Fairy"], strengths: ["Normal", "Ice", "Rock", "Dark", "Steel"]}, {name: "Poison", immunes: ["Steel"], weaknesses: ["Poison", "Ground", "Rock", "Ghost"], strengths: ["Grass", "Fairy"]}, {name: "Ground", immunes: ["Flying"], weaknesses: ["Grass", "Bug"], strengths: ["Fire", "Electric", "Poison", "Rock", "Steel"]}, {name: "Flying", immunes: [], weaknesses: ["Electric", "Rock", "Steel"], strengths: ["Grass", "Fighting", "Bug"]}, {name: "Psychic", immunes: ["Dark"], weaknesses: ["Psychic", "Steel"], strengths: ["Fighting", "Poison"]}, {name: "Bug", immunes: [], weaknesses: ["Fire", "Fighting", "Poison", "Flying", "Ghost", "Steel", "Fairy"], strengths: ["Grass", "Psychic", "Dark"]}, {name: "Rock", immunes: [], weaknesses: ["Fighting", "Ground", "Steel"], strengths: ["Fire", "Ice", "Flying", "Bug"]}, {name: "Ghost", immunes: ["Normal"], weaknesses: ["Dark"], strengths: ["Psychic", "Ghost"]}, {name: "Dragon", immunes: ["Fairy"], weaknesses: ["Steel"], strengths: ["Dragon"]}, {name: "Dark", immunes: [], weaknesses: ["Fighting", "Dark", "Fairy"], strengths: ["Psychic", "Ghost"]}, {name: "Steel", immunes: [], weaknesses: ["Fire", "Water", "Electric", "Steel"], strengths: ["Ice", "Rock", "Fairy"]}, {name: "Fairy", immunes: [], weaknesses: ["Fire", "Poison", "Steel"], strengths: ["Fighting", "Dragon", "Dark"]}]
console .log (search (types)).as-console-wrapper {max-height: 100% !important; top: 0}paths takes a structure like {a: ['b', 'c'], b: ['d', 'e'], c: ['e'], d: ['b', 'c'], e: ['a', 'b']} as well as the path length, say 3, returning all the length-3 paths, which we might describe as abd, abe, ace, bdb, bdc, bea, beb, cea, ceb, dbd, dbe, dce, eab, eac, ebd, and ebe.
search takes your input, reconfigures it to the format above, using the strengths properties, then calls paths on the result, with length of 3. Then it filters to include only those paths that will loop back from the final element to the initial one.
This gets you the answer you generated, but you want to remove duplicates, saying that many of these appear three times. You notation is slightly confusing, with output like Found: Rock => Fire => Grass. Those arrows make me assume that this is an ordered collection. But from the above, I think you want to treat these as unordered Sets, and only return one of these. If that's the case, we can filter after the fact to remove them, with code like:
const dedupe = (fn) => (xs, res = new Set()) => xs .filter (
(x, _, __, key = fn (x), dup = res .has (key)) => ((res .add (key)), ! dup)
)
const search = (ts, types = Object .fromEntries (ts .map ((t) => [t .name, t .strengths]))) =>
dedupe
(s => [... s] .sort () .join ('|'))
(paths (types, 3) .filter ((s) => types [s [s .length - 1]] .includes (s [0])))
Here dedupe takes a function which finds a consistent String key for each of our three-element sets. It returns a function which takes an array and keeps those that generate an unused key when passed to that function.
We wrap up the output in search with a call to dedupe, passing it a function which sorts the elements and concatenates them in a new String, interspersing a separator character. (If the "|" character might appear in your data, then I would choose a different separator, but even if you don't the only possible failure case is quite obscure.) For instance, when you hit ['Water', 'Ground', 'Electric'], it sorts and concatenates into the keys "Electric|Ground|Water" and is stores that in its set. Then when we see ['Electric', 'Water', 'Ground'] it also generates that same key, and so this array is not included.
You can see it altogether by expanding this snippet:
const paths = (types, length, children = Object .keys (types)) =>
length <= 1
? children .map (s => [s])
: children .flatMap (s => paths (types, length - 1, types [s]) .map (p => [s, ...p]))
const dedupe = (fn) => (xs, res = new Set()) => xs .filter (
(x, _, __, key = fn (x), dup = res .has (key)) => ((res .add (key)), ! dup)
)
const search = (ts, types = Object .fromEntries (ts .map ((t) => [t .name, t .strengths]))) =>
dedupe
(s => [... s] .sort () .join ('|'))
(paths (types, 3) .filter ((s) => types [s [s .length - 1]] .includes (s [0])))
const types = [{name: "Normal", immunes: ["Ghost"], weaknesses: ["Rock", "Steel"], strengths: []}, {name: "Fire", immunes: [], weaknesses: ["Fire", "Water", "Rock", "Dragon"], strengths: ["Grass", "Ice", "Bug", "Steel"]}, {name: "Water", immunes: [], weaknesses: ["Water", "Grass", "Dragon"], strengths: ["Fire", "Ground", "Rock"]}, {name: "Electric", immunes: ["Ground"], weaknesses: ["Electric", "Grass", "Dragon"], strengths: ["Water", "Flying"]}, {name: "Grass", immunes: [], weaknesses: ["Fire", "Grass", "Poison", "Flying", "Bug", "Dragon", "Steel"], strengths: ["Water", "Ground", "Rock"]}, {name: "Ice", immunes: [], weaknesses: ["Fire", "Water", "Ice", "Steel"], strengths: ["Grass", "Ground", "Flying", "Dragon"]}, {name: "Fighting", immunes: ["Ghost"], weaknesses: ["Poison", "Flying", "Psychic", "Bug", "Fairy"], strengths: ["Normal", "Ice", "Rock", "Dark", "Steel"]}, {name: "Poison", immunes: ["Steel"], weaknesses: ["Poison", "Ground", "Rock", "Ghost"], strengths: ["Grass", "Fairy"]}, {name: "Ground", immunes: ["Flying"], weaknesses: ["Grass", "Bug"], strengths: ["Fire", "Electric", "Poison", "Rock", "Steel"]}, {name: "Flying", immunes: [], weaknesses: ["Electric", "Rock", "Steel"], strengths: ["Grass", "Fighting", "Bug"]}, {name: "Psychic", immunes: ["Dark"], weaknesses: ["Psychic", "Steel"], strengths: ["Fighting", "Poison"]}, {name: "Bug", immunes: [], weaknesses: ["Fire", "Fighting", "Poison", "Flying", "Ghost", "Steel", "Fairy"], strengths: ["Grass", "Psychic", "Dark"]}, {name: "Rock", immunes: [], weaknesses: ["Fighting", "Ground", "Steel"], strengths: ["Fire", "Ice", "Flying", "Bug"]}, {name: "Ghost", immunes: ["Normal"], weaknesses: ["Dark"], strengths: ["Psychic", "Ghost"]}, {name: "Dragon", immunes: ["Fairy"], weaknesses: ["Steel"], strengths: ["Dragon"]}, {name: "Dark", immunes: [], weaknesses: ["Fighting", "Dark", "Fairy"], strengths: ["Psychic", "Ghost"]}, {name: "Steel", immunes: [], weaknesses: ["Fire", "Water", "Electric", "Steel"], strengths: ["Ice", "Rock", "Fairy"]}, {name: "Fairy", immunes: [], weaknesses: ["Fire", "Poison", "Steel"], strengths: ["Fighting", "Dragon", "Dark"]}]
console .log (search (types)).as-console-wrapper {max-height: 100% !important; top: 0}