First clear solution for [old] Break Rings by Sim0000 - javascript coding challenges

Enable Javascript in your browser and then refresh this page, for a much enhanced experience.

First solution in Clear category for [old] Break Rings by Sim0000

"use strict";

function breakRings(rings){
    function removeRing(rings, ring){
        var result = []
        for(var r of rings){
            if(r[0] != ring && r[1] != ring) result.push(r)
        }
        return result
    }
    if(rings.length == 0) return 0
    var n0 = breakRings(removeRing(rings, rings[0][0])) + 1
    var n1 = breakRings(removeRing(rings, rings[0][1])) + 1
    return Math.min(n0, n1)
}

var assert = require('assert');

if (!global.is_checking) {
    assert.equal(breakRings([[1, 2], [2, 3], [3, 4], [4, 5], [5, 6], [4, 6]]), 3, "Example");
    assert.equal(breakRings([[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]]), 3, "All to all");
    assert.equal(breakRings([[5, 6], [4, 5], [3, 4], [3, 2], [2, 1], [1, 6]]), 3, "Chain");
    assert.equal(breakRings([[8, 9], [1, 9], [1, 2], [2, 3], [3, 4], [4, 5], [5, 6], [6, 7], [8, 7]]), 5, "Long chain");
    console.log("Coding complete? Click 'Check' to review your tests and earn cool rewards!");
}

July 20, 2016

Comments:

nickie on Sept. 12, 2016, 11:49 p.m.
Well done, this is an elegantly coded recursive solution. Notice that this solution is O(C*2^C), where C (=`len(rings)`) is the number of connections. The problem can be solved in O(C*2^N), where N is the number of rings. C can be smaller than N, in which case this solution is better, but it can be as large as N*(N-1)/2.

Sim0000 on Sept. 14, 2016, 1:36 p.m.
Thank you. When I solved in Python, it was more speedy. But we have no itertools in javascript.

jackhftang on Sept. 16, 2016, 3:01 a.m.
Actually, not O(C*2^C). Because removeRing(rings,ring) remove all 'ring' appeared in 'rings'. The range of ring is [1,N]. So the depth of stack call of breakRing(rings) is at most N. And hence, this algorithm run in O(C*2^N)

nickie on Sept. 21, 2016, 6:25 a.m.
Hmm, yes, I think you're right. I missed this in my first analysis. Sorry about that...

cyclopentan on Jan. 13, 2018, 5:42 p.m.
For brute force yes, be there is math solution with finding max subgraph of inverted unions graph, that is much more fast, but difficult to code

Sim0000 on Sept. 16, 2016, 7:58 a.m.
I examined the depth of stack call of breakRing(rings). d is the maximum depth of recursive call. count is how many call breakRing(rings). In range of this investigation, <ol> <li>d < n is hold.</li> <li>count < 2**n</li> </ol> As @jackhftang say, since there is only n rings, always d \< n holds in general case. This imply count < 2**n. Thanks @nickie , @jackhftang :-) <pre class='brush: javascript'>Basics-1 d 5 n 6 d/n 0.83 count 31 Basics-2 d 3 n 4 d/n 0.75 count 15 Basics-3 d 5 n 6 d/n 0.83 count 31 Basics-4 d 8 n 9 d/n 0.89 count 135 Extra-1 d 8 n 9 d/n 0.89 count 93 Extra-2 d 7 n 9 d/n 0.78 count 151 Extra-3 d 8 n 9 d/n 0.89 count 153 Extra-4 d 7 n 9 d/n 0.78 count 179 Extra-5 d 6 n 9 d/n 0.67 count 95 Extra-6 d 8 n 9 d/n 0.89 count 177 Extra-7 d 8 n 9 d/n 0.89 count 177 Extra-8 d 8 n 9 d/n 0.89 count 143 Extra-9 d 8 n 9 d/n 0.89 count 205 Extra-10 d 7 n 9 d/n 0.78 count 91 Extra-11 d 7 n 9 d/n 0.78 count 157 Extra-12 d 7 n 9 d/n 0.78 count 107 Extra-13 d 13 n 17 d/n 0.76 count 5021 Extra-14 d 8 n 9 d/n 0.89 count 195 Extra-15 d 7 n 9 d/n 0.78 count 105 Extra-16 d 8 n 9 d/n 0.89 count 135 Extra-17 d 15 n 20 d/n 0.75 count 2415 Extra-18 d 14 n 20 d/n 0.70 count 3943 Extra-19 d 8 n 9 d/n 0.89 count 135 Extra-20 d 12 n 14 d/n 0.86 count 1095 Extra-21 d 5 n 6 d/n 0.83 count 31 </pre>

bronya100 on Dec. 2, 2017, 6:31 a.m.
charming!!! It is only two lines: <pre class='brush: javascript'>const d = (r,i) => r.filter( v => v[0] != i & v[1] != i ); const breakRings = r => r.length ? Math.min( breakRings( d(r, r[0][0]) ), breakRings( d(r, r[0][1]) )) + 1 : 0; </pre>

Sim0000 on Dec. 3, 2017, 11:44 p.m.
Great solution!

No Station

WebStorm The smartest JavaScript IDE. WebStorm is a powerful JavaScript IDE that makes you productive. Try free!