BreakThePieces

    0

    0

    function breakPieces(shape) {
      const drawing = new Drawing(shape);
      const vertices = drawing.vertices;
    
      const graph = new Graph(vertices);
      for (let i = 0; i < vertices.length-1; ++i) {
        for (let j = i + 1; j < vertices.length; ++j) {
          if (drawing.connected(vertices[i], vertices[j])) {
            graph.connect(vertices[i], vertices[j]);
          }
        }
      }
      //console.log(graph);
      const mcb = graph.minimumCycleBasis();
      console.log(mcb.map(x => x.area))
    
      return mcb.map(c => c.print());
    }
    
    class Drawing {
      constructor(str) {
        this.drawing = str.split('\n').map(r => r.split(''));
        this.vertices = this.drawing.flatMap((row, i) =>
          row.map((c, j) => c === '+' ? [i, j] : null).filter(Boolean)
        );
      }
    
      connected(from, to) {
        if (from[0] !== to[0] && from[1] !== to[1]) {
          return false;
        }
        if (from[0] === to[0]) {
          const line = this.drawing[from[0]].slice(from[1]+1, to[1]);
          return !line.includes(' ') && !line.includes('+');
        } else {
          const line = this.drawing.map(r => r[from[1]]).slice(from[0]+1, to[0]);
          return !line.includes(' ') && !line.includes('+');
        }
        return false;
      }
    }
    
    class Cycle {
      constructor(vertices) {
        this.vertices = vertices;
        this.edges = this.getEdges();
      }
    
      independent(cycles) {
        const edgesFound = {};
        for (let e of this.edges) {
          edgesFound[e] = false;
          for (let cycle of cycles) {
            for (let e0 of cycle.edges) {
              if ((e0[0] === e[0] && e0[1] === e[1] ||
                  e0[0] === e[1] && e0[1] === e[0])) {
                edgesFound[e] = true;
              }
            }
          }
        }
        return Object.values(edgesFound).includes(false);
      }
    
      getEdges() {
        let last = this.vertices[0];
        const e = [];
        for (let i = 1; i < this.vertices.length; ++i) {
          e.push([last, this.vertices[i]]);
          last = this.vertices[i];
        }
        return e;
      }
    
      get length() {
        return this.vertices.length;
      }
    
      get area() {
        const corners = this.cornerVertices().sort(([y0, x0], [y1, x1]) => {
          if (y0 === y1) return x0 - x1;
          return y0 - y1;
        }).reduce((acc, [y, x]) => {
          acc[y] = [...(acc[y] || []), [y, x]];
          return acc;
        }, {});
        console.log(corners)
      }
    
      cornerVertices() {
        const vertices = this.vertices.map(v => v.split(',').map(Number));
        const corners = [vertices[0]];
        for (let i = 1; i < vertices.length-1; ++i) {
          const [y0, x0] = vertices[i-1];
          const [y1, x1] = vertices[i];
          const [y2, x2] = vertices[i+1];
          if (y0 === y1 && y0 === y2 || x0 === x1 && x0 === x2) {
            continue;
          }
          corners.push(vertices[i]);
        }
        corners.push(vertices[vertices.length-1]);
        return corners;
      }
    
      print() {
        const points = this.cornerVertices();
        const minx = points.reduce((min, [y, x]) => x < min ? x : min, Infinity);
        const miny = points.reduce((min, [y, x]) => y < min ? y : min, Infinity);
        const maxx = points.reduce((max, [y, x]) => x > max ? x : max, 0);
        const maxy = points.reduce((max, [y, x]) => y > max ? y : max, 0);
        const sizey = maxy - miny + 1;
        const sizex = maxx - minx + 1;
        const shape = Array.from(Array(sizey), () => new Array(sizex).fill(' '));
    
        let [y0, x0] = points[0];
        for (let i = 1; i < points.length; ++i) {
          const [y1, x1] = points[i];
    
          if (y0 === y1) {
            for (let x = Math.min(x0, x1); x <= Math.max(x0, x1); ++x) {
              shape[y0-miny][x-minx] = '-';
            }
          } else if (x0 === x1) {
            for (let y = Math.min(y0, y1); y <= Math.max(y0, y1); ++y) {
              shape[y-miny][x0-minx] = '|';
            }
          }
          [x0, y0] = [x1, y1];
        }
    
        for (let [y, x] of points) {
          shape[y-miny][x-minx] = '+';
        }
    
        return shape.map(r => r.join('')).join('\n');
      }
    }
    
    class Graph {
      constructor(nodes) {
        this.matrix = nodes.reduce((acc, node) => {
          acc[node] = [];
          return acc;
        }, {});
        this.nodes = nodes.map(n => n.toString());
        this.edges = [];
      }
    
      connect(fr, to) {
        this.matrix[fr].push(to.toString())
        this.matrix[to].push(fr.toString());
        this.edges.push([fr.toString(), to.toString()]);
      }
    
      minimumCycleBasis() {
        /*
        https://www.researchgate.net/publication/273471519_On_Computing_the_Translations_Norm_in_the_Epipolar_Graph#pf3
        Horton algorithm - Find the minimum cycle basis (MCB)
        Input: Biconnected graph G = (V, E)
        Output: Minimum Cycle Basis B
          1.  Find the shortest path P (x, y) between each pair of
              vertices x, y ∈ V. Use Dijkstra's algorithm.
          2.  for v ∈ V do
                for (x, y) ∈ E do
                  Create the cycle C(v, x, y) = P (v, x) ∪ P (v, y) ∪ (x, y)
                  and calculate its length. De-generate cases in which P (v, x)
                  and P (v, y) have vertices other than v in common can be omitted.
                end
              end
          3.  Order the cycles by increasing lengths.
          4.  Initialize B = ∅. Add to B the next shortest cycle if it is independent
              from the already selected ones.
        */
        const shortestDistances = this.shortestDistanceMatrix();
    
        const cycles = [];
        for (let node of this.nodes) {
          for (let edge of this.edges) {
            if (edge[0] === node || edge[1] === node) {
              continue;
            }
            const path0 = [...shortestDistances[node][edge[0]]];
            const path1 = [...shortestDistances[node][edge[1]]];
            if (path0[0] !== node) path0.reverse();
            if (path1[0] !== node) path1.reverse();
            //console.log(node, edge, path0, path1)
            if (path0.slice(1).findIndex(x => path1.slice(1).includes(x)) >= 0) {
              continue;
            }
            const vertices = [...path0, ...path1.reverse()];
            const cycle = new Cycle(vertices)
            //console.log(cycle);
            cycles.push(cycle);
          }
        }
        cycles.sort((a, b) => a.length - b.length);
    
        const cycleBasis = [];
        for (let cycle of cycles) {
          if (cycle.independent(cycleBasis)) {
            cycleBasis.push(cycle);
          }
        }
        return cycleBasis;
      }
    
      shortestDistanceMatrix() {
        const shortestDistances = this.nodes.reduce((acc, node) => {
          acc[node] = {};
          return acc;
        }, {});
        for (let i = 0; i < this.nodes.length-1; ++i) {
          for (let j = i; j < this.nodes.length; ++j) {
            const fr = this.nodes[i];
            const to = this.nodes[j];
            if (fr === to) {
              shortestDistances[fr][to] = [];
            } else {
              shortestDistances[fr][to] = this.shortestPathDijkstra(fr, to);
              shortestDistances[to][fr] = [...shortestDistances[fr][to]].reverse();
            }
          }
        }
        return shortestDistances;
      }
    
      shortestPathDijkstra(start, end) {
        if (!this.nodes.includes(start) || !this.nodes.includes(end)) {
          return [];
        }
        const costs = {};
        const parents = {};
        const queue = new PriorityQueue();
    
        this.nodes.forEach(node => {
          costs[node] = Infinity
        });
        costs[start] = 0;
    
        queue.enqueue([start, 0]);
    
        while (!queue.isEmpty()) {
          let shortestStep = queue.dequeue();
          let currentNode = shortestStep[0];
          if (currentNode === end) {
            break;
          }
          this.matrix[currentNode].forEach(neighbor => {
            let cost = costs[currentNode] + 1;
            if (cost < costs[neighbor]) {
              costs[neighbor] = cost;
              parents[neighbor] = currentNode;
              queue.enqueue([neighbor, cost]);
            }
          });
        }
    
        const path = [end];
        let lastStep = end;
        while (lastStep !== start) {
          path.unshift(parents[lastStep])
          lastStep = parents[lastStep]
        }
        return path;
      }
    }
    
    class PriorityQueue {
      constructor() {
        this.collection = [];
      }
    
      enqueue(element){
        if (this.isEmpty()){ 
          this.collection.push(element);
        } else {
          let added = false;
          for (let i = 1; i <= this.collection.length; i++){
            if (element[1] < this.collection[i-1][1]){ 
              this.collection.splice(i-1, 0, element);
              added = true;
              break;
            }
          }
          if (!added){
            this.collection.push(element);
          }
        }
      }
    
      dequeue() {
        const value = this.collection.shift();
        return value;
      }
    
      isEmpty() {
        return (this.collection.length === 0) 
      }
    }
    
    const shape0 =
      ["+------+-----+",
      "|      |     |",
      "|      |     |",
      "+------+-----+"].join("\n");
    
    const shape1 =
      ["+------------+",
      "|            |",
      "|            |",
      "|            |",
      "+------+-----+",
      "|      |     |",
      "|      |     |",
      "+------+-----+"].join("\n");
    
    const shape2 =
      ["    +---+",
      "    |   |",
      "+---+   |",
      "|       |",
      "+-------+"].join("\n");
    
    const shape3 =
      ["    +---+     ",
      "    |   +----+",
      "+---+   +----+",
      "|       |     ",
      "+-------+     "].join("\n");
    
    const shape4 =
    ["+-------------------+--+",
      "|                   |  |",
      "|                   |  |",
      "|  +----------------+  |",
      "|  |                   |",
      "|  |                   |",
      "+--+-------------------+"].join("\n");
    
    //document.getElementById('sol0').innerHTML = `<pre>${breakPieces(shape0).join('\n')}</pre>`;
    //document.getElementById('sol1').innerHTML = `<pre>${breakPieces(shape1).join('\n')}</pre>`;
    //document.getElementById('sol2').innerHTML = `<pre>${breakPieces(shape2).join('\n')}</pre>`;
    document.getElementById('sol3').innerHTML = `<pre>${breakPieces(shape3).join('\n')}</pre>`;
    //document.getElementById('sol4').innerHTML = `<pre>${breakPieces(shape4).join('\n')}</pre>`;
    
    Codiga Logo
    Codiga Hub
    • Rulesets
    • Playground
    • Snippets
    • Cookbooks
    soc-2 icon

    We are SOC-2 Compliance Certified

    G2 high performer medal

    Codiga – All rights reserved 2022.