うむ・・・うむ・・・・
難しかった。。。
お題のシチュエーションは、発電所がまかないきれず停電してしまった都市を探せというもの。
適当な説明を描いてもしょうがないので、問題本文を引用。
Two arguments. The first one is the network, represented as a list of connections. Each connection is a list of two nodes that are connected. A city or power plant can be a node. Each city or power plant is a unique string. The second argument is a dict where keys are power plants and values are the power plant's range.
Examples
powerSupply([['p1', 'c1'], ['c1', 'c2']], {'p1': 1}) == ['с2']
powerSupply([['c0', 'c1'], ['c1', 'p1'], ['c1', 'c3'], ['p1', 'c4']], {'p1': 1}) == ['c0', 'c3']
powerSupply([['p1', 'c1'], ['c1', 'c2'], ['c2', 'c3']], {'p1': 3}) == []
自分の回答
"use strict";
function powerSupply(network, power_plants) {
var
nodes = [],
savedCities = [],
preSaved = [],
neighbors = [],
blackouts = [],
targets, power,
initializer, neighborSeeker, darkSeeker;
// set up the battle field
initializer = function() {
// all nodes
network.forEach(function(x,idx,self) {nodes = nodes.concat(x)});
// set the initialState of savedCities
for (let plants in power_plants) {
savedCities = savedCities.concat(plants);
};
};
// find target neighbors
neighborSeeker = function(target, tarArray) {
var saveArray = [];
for (let i of tarArray) {
if (i.indexOf(target) !== -1) {
for (let j of i) {
if (j !== target) {
saveArray = saveArray.concat(j);
};
};
};
};
return saveArray;
};
// find which city is in despair
darkSeeker = function(tarArray, collection) {
var saveArray = collection.filter(function(x,i,self) {
return tarArray.indexOf(x) === -1;
});
return saveArray;
};
// here we go
initializer();
for (let plant in power_plants) {
targets = [];
power = power_plants[plant];
while(power) {
if (targets.length === 0) {
targets = neighborSeeker(plant, network);
}
else {
neighbors = targets.concat();
targets = [];
preSaved = [];
for (let city of neighbors) {
preSaved = neighborSeeker(city, network);
targets = targets.concat(preSaved);
};
}
power -= 1;
for (let city of targets) {
if (savedCities.indexOf(city)===-1) {
savedCities = savedCities.concat(city);
};
};
};
};
blackouts = darkSeeker(savedCities, nodes);
return blackouts;
}
再帰的な関数を書いて見たかったんだけど、時間とオツムが許さぬところとなり挫折。
whileのelse節内で脳みそが溶けそうになった。
forとifだらけである。
すごいかいとう
"use strict";
function powerSupply(network, power_plants) {
const findConnect = (point) => network
.filter(el => el.some(e => e === point))
.map(el => el[0] === point ? el[1] : el[0]);
let allNodes = new Set(network.reduce((a, b) => a.concat(b), []));
let powerOn = [];
const recursiveFinder = (points, step, stop) => {
if (step === stop) return;
let recursiveStack = [];
points.map(el => {
if (powerOn.indexOf(el) === -1) powerOn.push(el);
findConnect(el).map(nel => { if (recursiveStack.indexOf(nel) === -1) recursiveStack.push(nel) })
});
recursiveFinder(recursiveStack, step+=1, stop)
};
for (let power in power_plants) {
powerOn.push(power);
recursiveFinder(findConnect(power), 0, power_plants[power]);
}
powerOn.map(el => allNodes.delete(el));
return [...allNodes]
}
短い!recursiveな関数もある!
6行目のfilterの部分は書き方として簡潔。someとの組み合わせは便利そう。
7行目のmapではneighborだけを探し出して配列にする。15行目で実際に使われているけど、新しい配列を返すメソッドはそのままチェーンして使うというのがあるのか。
8行目では全てのnodeの集合を作っている。reduceで全部をまとめた配列を作り、それをsetに渡すことで、重複をなくす。
10-18行目はrecursiveに実行される関数を定義。
最後にreturnしている部分は見慣れない書き方だと思ったら、setでの記法らしい。
学び
array.some(function(elem, idx, thisArray))
・呼ばれた配列に対して1つずつcallback関数を実行し、合格するものがあれば、trueを返す。なければfalse。
new Set
・新しいsetを作り出す。いろんなメソッドがあって便利そう。
set.has(elem)
setがelemを持っているか真偽値を返す。
set.delete(elem)
setからelemを削除。
set.size()
setのサイズを調べる。
[...set]
setを配列にしたものを生成して返す。
参考: [JavaScript] ECMAScript6のMapとSetを使ってみよう
array.reduce(function(prev, current, idx, thisArray){some function}[,initialValue])
呼び出した配列の要素に対し、1つずつcallbackを呼び出して、1つにまとめた新しい配列を生成する。
for - in -
オブジェクトに対して呼び出す。
反省
多分今回のすごいかいとうをまだよくわかっていないので、後日もう一回読む。
relationを探して、芋づる式に特定の要素を探すというパターンはこの前の問題でもあった。
このパターンだけでもrecursiveにホイホイできるようになりたい♂