LoginSignup
0

More than 5 years have passed since last update.

[checkio] Power Supply

Posted at

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

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

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

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
0