這是我的代碼:
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);
這是 JSON 檔案:
[
{
"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"]
}
]
這是輸出:
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
正如您所注意到的,類似的結果會被列印多次(例如,火/草/水為每個元素列印 3 次)。
此外,該演算法是超級強力的,三個回圈相互堆疊(我認為這會使它成為 O(n^3)?)。我記得看到過一個類似的問題(不是口袋妖怪,而是類似的結構等),但我不記得或想不出解決這個問題的最佳方法是什么,而不用蠻力和通過迭代現有的來浪費處理能力元素鏈。我嘗試使用 Map 和所有這些,但似乎沒有任何效果。這是我的第一個 stackoverflow 帖子,如果我把其中的一些寫錯了,請原諒我!
uj5u.com熱心網友回復:
這是我的第一個 stackoverflow 帖子,如果我把其中的一些寫錯了,請原諒我!
實際上,這是一篇做得很好的第一篇文章。榮譽!
但是我有兩點建議:
您可能應該對問題進行更多描述。你的作業源代碼很棒,但我敢肯定我不是唯一一個對 Pokemon 一無所知的人,因此對這個問題沒有背景。我不知道什么是“入門組”,或者你的標題和輸出中的箭頭代表什么(也許什么都沒有。)
您可能會閱讀如何創建可運行的堆疊片段?以便讀者可以在瀏覽器中直接看到結果。(您可以隨時編輯帖子以添加帖子。)
現在回到問題本身。
你擔心性能。你有沒有測驗過它的速度還不夠快?如果以上是資料的范圍,那么我不希望這需要超過幾毫秒的時間來處理。是不是太長了?還是真實資料要大得多?如果它更大,您是否可以不按照 Zac Butko 的建議執行并靜態運行它,要么作為構建步驟,將結果存盤在檔案中,要么在應用程式初始化期間,在應用程式的整個生命周期中將其存盤在記憶體中?
我沒有任何建議可以加快速度。在我看來,您必須訪問O (n ^ 3)資料中的所有路徑,因此有一個很難的演算法下界。(我以前在這方面錯了,也許我在這里,但我不確定如何做到。)
但我確實有我認為更干凈的代碼來做同樣的事情。創建與您找到的相同輸出的第一遍可能如下所示:
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采用類似于{a: ['b', 'c'], b: ['d', 'e'], c: ['e'], d: ['b', 'c'], e: ['a', 'b']}路徑長度的結構,例如3,回傳所有長度為 3 的路徑,我們可以將其描述為abd, abe, ace, bdb, bdc, bea, beb, cea, ceb, dbd, dbe, dce, eab, eac, ebd, 和ebe。
search接受您的輸入,使用strengths屬性將其重新配置為上述格式,然后呼叫paths結果,長度為3. 然后它過濾以僅包含將從最后一個元素回傳到初始元素的那些路徑。
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.
我們dedupe通過呼叫 將搜索中的輸出包裝起來,向它傳遞一個函式,該函式對元素進行排序并將它們連接到一個新的字串中,并穿插一個分隔符。(如果“ |”字符可能出現在您的資料中,那么我會選擇一個不同的分隔符,但即使您不這樣做,唯一可能的失敗情況也很模糊。)例如,當您點擊 時['Water', 'Ground', 'Electric'],它會排序并連接到鍵"Electric|Ground|Water"并將其存盤在其集合中。然后當我們看到['Electric', 'Water', 'Ground']它也生成相同的密鑰時,因此不包含此陣列。
您可以通過展開此代碼段來完全查看它:
顯示代碼片段
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}
uj5u.com熱心網友回復:
我不確定是否可以降低初始查詢的復雜性(其他人,請證明我錯了:))
但是,由于所有結果都是靜態的(弱點和強項不會改變),您可以使用蠻力方法計算一次所有結果并將結果存盤在平面物件或 json 檔案中。從那時起,查找將是 O(1)。
根據您想要的資訊,您可以使用以下格式:
alternatives = {
fire: ['Grass Water', 'Grass Ground', 'Grass Rock', 'Ice Ground', 'Steel Rock'],
water: ['Fire Grass', 'Ground Electric'],
..
}
祝你好運
轉載請註明出處,本文鏈接:https://www.uj5u.com/qukuanlian/359121.html
標籤:javascript 算法 表现 蛮力
下一篇:遺傳演算法:收斂問題
