JavaScript

[checkio] Power Supply

More than 1 year has passed since last update.

うむ・・・うむ・・・・
難しかった。。。

お題のシチュエーションは、発電所がまかないきれず停電してしまった都市を探せというもの。
適当な説明を描いてもしょうがないので、問題本文を引用。

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}) == []

出典:checkio - PowerSupply

自分の回答

"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にホイホイできるようになりたい♂