-
Question about breakRings
 
I have a question about breakRings. My code passes all of the tests shown in the try-me page. But when I try to check-in the code it fails on
breakRings([[1,9],[1,2],[8,5],[4,6],[5,6],[8,1],[3,4],[2,6], [9,6],[8,4],[8,3],[5,7],[9,7],[2,3],[1,7]]) My result: 6 Right result: 5
Could someone who has completed this mission confirm that the answer to this ring config is 5. I keep getting 6 with my solution and after a bunch of debugging, I'm doubtful about 5 being correct since its such a large ring config. My code breaks rings (in order), 1, 6, 3, 5, 4 and 7.
My basic strategy was to built a function that found the ring with the most connections then break that ring. Then use recursion to keep breaking the most connected ring until there aren't any more connections. Maybe this is the wrong approach.
Thanks.
var ringBreaks = 0; var recursionComplete = false; function breakRings(connectionPairs) { // look for a ring number with the most connection and break it // by replacing it's number with 0 // recurse until all arrays contain one 0. (counting as you recurse) var remainingConnections = []; var RingConnectionCounter = []; var onePair = []; var mostConnections = 0; var whichRing = 0; if(recursionComplete) { ringBreaks = 0; recursionComplete = false; } // initialize the RingConnectionCounter RingConnectionCounter[0] = 0; for(let i=0; i<connectionPairs.length; i++) { onePair = connectionPairs[i] RingConnectionCounter[onePair[0]] = 0; RingConnectionCounter[onePair[1]] = 0; } // fill up the RingConnectionCounter, (use index as ring number, count the connections) for(let i=0; i<connectionPairs.length; i++) { onePair = connectionPairs[i]; // (ignore pairs with a 0, those are free rings) if(onePair[0] > 0 && onePair[1] > 0) { RingConnectionCounter[onePair[0]] = RingConnectionCounter[onePair[0]] + 1; RingConnectionCounter[onePair[1]] = RingConnectionCounter[onePair[1]] + 1; } } // now find the ring with most connections for(let i=0; i<RingConnectionCounter.length; i++) { // ignore index 0 if(RingConnectionCounter[i] > mostConnections && i!=0) { whichRing = i; mostConnections = RingConnectionCounter[i]; } } if(whichRing !=0) { // break the ring for(let i=0; i<connectionPairs.length; i++) { onePair = connectionPairs[i]; if(whichRing == onePair[0] && onePair[1] != 0) { onePair[0] = 0; } if(whichRing == onePair[1] && onePair[0] != 0) { onePair[1] = 0; } remainingConnections.push(onePair); } ringBreaks++; // recurse breakRings(remainingConnections); } recursionComplete = true; return ringBreaks; }
Created at: 2016/10/21 09:14; Updated at: 2016/11/13 04:39