CodeFights: countClouds - crazy hard way to solve it

countClouds solution.js

/** 
 * Solution for this: https://codefights.com/interview-practice/task/HdgqPhHqs3NciAHqH
 */
function countClouds(skyMap) {
  let clouds = [];
  let completeClouds = 0;

  for (let skyLine of skyMap) {
    let newCloudsMapping = {
      cloudToRange: {}, // {[cloud number]: [list of ranges]} - to continue the cloud
      rangeToCloud: {} // {[range hash]: [list of clouds]} - to merge clouds
    };
    let newClouds = [];
    let i = 0;
    let range;

    while (range = getRange(skyLine, i)) {
      log(`Processing range ${range.start}-${range.end}`);

      let rangeIsNew = true;
      let rangeHash = getRangeHash(range);
      
      for (let j = 0; j < clouds.length; j++) {
        let cloud = clouds[j];
        
        if (cloud.intersectsRange(range)) {
          newCloudsMapping.cloudToRange[j] = newCloudsMapping.cloudToRange[j] || [];
          newCloudsMapping.cloudToRange[j].push(range);
          newCloudsMapping.rangeToCloud[rangeHash] = newCloudsMapping.rangeToCloud[rangeHash] || new Set;
          newCloudsMapping.rangeToCloud[rangeHash].add(j);
          rangeIsNew = false;
        }
      }

      if (rangeIsNew) {
        let newCloud = new Cloud([range]);
        newClouds.push(newCloud);
        log(`New cloud created: ${newCloud}`);
      }

      i = range.end + 1;
    }

    // Count complete clouds
    for (let k = 0; k < clouds.length; k++) {
      if (typeof newCloudsMapping.cloudToRange[k] === 'undefined') {
        log(`Complete cloud: ${clouds[k]}`);
        completeClouds++;
      }
    }

    // Build clusters for new clouds
    let cloudClusters = clusterize(Object.values(newCloudsMapping.rangeToCloud));

    log(`Clouds to ranges: ${JSON.stringify(newCloudsMapping.cloudToRange)}`);
    log(`Ranges to clouds: ${Object.entries(newCloudsMapping.rangeToCloud).map(e => e[0] +':' + [...e[1]])}`);
    log(`Cloud clusters: ${'[' + cloudClusters.map(c => '[' + [...c] + ']') + ']'}`);

    // Create new clouds
    for (let cloudCluster of cloudClusters) {
      let cloudRanges = [];

      for (let m of cloudCluster) {
        log(`Merging ${JSON.stringify(cloudRanges)} and ${JSON.stringify(newCloudsMapping.cloudToRange[m])}`)
        cloudRanges = mergeRanges(cloudRanges, newCloudsMapping.cloudToRange[m]);
      }

      newClouds.push(new Cloud(cloudRanges));
    }

    log(`Clouds: ${newClouds}`);
    log(`Finished clouds: ${completeClouds}`);

    clouds = newClouds;
  }

  completeClouds += clouds.length;

  return completeClouds;
}

const DEBUG = false;

function log(...args) {
  if (DEBUG)
    console.log(...args);
}

function getRange(skyLine, startIdx=0) {
  let rangeStartIdx = skyLine.indexOf('1', startIdx);
  
  if (rangeStartIdx !== -1) {
    let rangeEndIdx = skyLine.indexOf('0', rangeStartIdx);
    
    if (rangeEndIdx === -1)
      rangeEndIdx = skyLine.length;
    
    return {
      start: rangeStartIdx, 
      end: rangeEndIdx - 1
    };
  }
}

function getRangeHash(range) {
  return `${range.start}-${range.end}`;
}

// Array of sets of integers
function clusterize(sets) {
  let clusters;
  let needsTraversal = true;

  do {
    clusters = [];

    for (let set of sets) {
      let clusterFound = false;
      
      for (let cluster of clusters) {
        for (let n of cluster) {
          if (set.has(n)) {
            for (let m of set) {
              cluster.add(m);
            }
            clusterFound = true;
            break;
          }
        }
      }

      if (!clusterFound) {
        clusters.push(new Set(set));
      }
    }

    needsTraversal = sets.length != clusters.length;
    sets = clusters;
  } while (needsTraversal);

  return clusters;
}

// Assuming that ranges don't intersect but some of them are repeated
function mergeRanges(ranges1, ranges2) {
  let res = [...ranges1];
  let rangeFound;

  for (let r2 of ranges2) {
    rangeFound = false;

    for (let r1 of ranges1) {
      if ((r1.start === r2.start) && (r1.end === r2.end)) {
        rangeFound = true;
      }
    }

    if (!rangeFound) {
      res.push(r2);
    }
  }

  return res;
}

class Cloud {
  constructor(ranges) {
    this.ranges = ranges;
  }

  intersectsRange(givenRange) {
    for (let range of this.ranges) {
      if (!(range.end < givenRange.start || range.start > givenRange.end)) {
        return true;
      }
    }
    return false;
  }

  toString() {
    return `<Cloud ranges: ${this.ranges.map(range => range.start + '-' + range.end)}>`;
  }
}

// ------------------------------------------ Garbage from here --------------------------------------------
// Supplemental functions, not used in the solution but may be useful in the future.
function getDiff(line1, line2) {
  let diff = 0;

  for (let i = 0; i < line2.length; i++) {
    if (line2[i] === '1') {
      while (line2[i] === '1' && line1[i] !== '1') {
        i++;
      }

      if (line2[i] !== '1') {
        diff++;
      } else {
        while (line2[i] === '1') {
          i++;
        }
      }
    }
  }

  return diff;
}

function getSame(line1, line2) {
  let same = 0;

  for (let i = 0; i < line1.length; i++) {
    if (line1[i] === '1' && line2[i] === '1') {
      while (line1[i] === '1' || line2[i] === '1') {
        i++;
      }

      same++;
    }
  }

  return same;
}


function debug(skyMap) {
  p = [];

  for (let l of skyMap) {
    console.log(l.join(''), getDiff(p, l), getSame(l, p), getDiff(l, p));
    p = l;
  }
}

// Initial attempt, which still looks interesting to me.
function countClouds(skyMap) {
    var prevSkyLineClouds = [];
    var cloudCount = 0;
    var cloudNumber = null;
    var mode = null;
    
    for (var skyLine of skyMap) {
        var skyLineClouds = []; // index of cluod numbers in a line, 
                                // e.g. [1, 1, null, null, 2, null, 3, 3, 3, null]
        
        for (var i = 0; i < skyLine.length; i++) {
            cloudNumber = null;
            
            if (skyLine[i] === '1') {
                var prevCloudNumber = skyLineClouds[i - 1];
                var prevLineCloudNumber = prevSkyLineClouds[i];

                if (!prevCloudNumber && !prevLineCloudNumber) {
                    cloudCount++;
                    cloudNumber = cloudCount;
                    mode = 'stripe-from-new';
                } else if (prevCloudNumber && !prevLineCloudNumber) {
                    cloudNumber = prevCloudNumber;
                } else if (!prevCloudNumber && prevLineCloudNumber) {
                    cloudNumber = prevLineCloudNumber;
                    mode = 'stripe-from-prev-line';
                } else if (prevCloudNumber && prevLineCloudNumber) {   
                    cloudNumber = Math.min(prevCloudNumber, prevLineCloudNumber);
                    
                    if (prevCloudNumber !== prevLineCloudNumber || mode === 'stripe-from-new') {
                        var j = i - 1;

                        while (skyLineClouds[j]) {
                            skyLineClouds[j] = cloudNumber;
                            j--;
                        }

                        if (mode === 'stripe-from-new')
                            mode = 'stripe-from-prev-line';
                    
                        var cc = cloudCount;

                        while (j >= 0) {
                            if (skyLineClouds[j] === cc) {
                                while (skyLineClouds[j] === cc) {
                                    skyLineClouds[j] = cc - 1;
                                    j--;
                                }
                                cc--;
                            }
                            j--;
                        }

                        cloudCount--;
                    }
                }
            } else {
                mode = null;
            }
            
            skyLineClouds[i] = cloudNumber;
        }

        // console.log(skyLineClouds, cloudCount);
        
        prevSkyLineClouds = skyLineClouds;
    }
    
    return cloudCount;
}