@eturnity/eturnity_maths - npm Package Compare versions

Comparing version 8.4.2-EPDM-13208.0 to 8.4.2-EPDM-13208.1

package.json

 {
   "name": "@eturnity/eturnity_maths",
-  "version": "8.4.2-EPDM-13208.0",
+  "version": "8.4.2-EPDM-13208.1",
   "author": "Eturnity Team",
@@ -5,0 +5,0 @@ "main": "src/index.js",

src/panelFunctions.js

@@ -14,4 +14,4 @@ export function arePanelsAdjacent(panelA, panelB) {
   const areTouching =
-    Math.abs(panelB.row_index - panelA.row_index) == 1 &&
-    Math.abs(panelB.col_index - panelA.col_index) == 1
+    Math.abs(panelB.row_index - panelA.row_index) <= 1 &&
+    Math.abs(panelB.col_index - panelA.col_index) <= 1
   return areSameModuleField && areTouching
@@ -18,0 +18,0 @@ }

src/SHPSolver.js

@@ -22,3 +22,3 @@ import {
     {
-      maxRecursion = 100000,
+      maxRecursion = 500000,
       hasVirtualNode = true,
@@ -271,3 +271,3 @@ proximityMatrix = null,
       }
-
+      console.log('recCount', recursionCount)
       isOptimal = true
@@ -274,0 +274,0 @@ }

src/stringPatchMatching.js

@@ -1,2 +0,7 @@
-export function solveStringPatchMatching(stringList, patchList) {
+const DISTANCE_INTER_PATCH_THRESHOLDS = 5000
+export function solveStringPatchMatching(
+  stringList,
+  patchList,
+  distanceMatrixBetweenPatches
+) {
   // Problem Setup
@@ -8,8 +13,24 @@ const n = patchList.length // Number of rows
 
+  const patchesPair = []
+  for (let i = 0; i < R.length - 1; i++) {
+    for (let j = i + 1; j < R.length; j++) {
+      if (distanceMatrixBetweenPatches[i][j] < DISTANCE_INTER_PATCH_THRESHOLDS)
+        patchesPair.push({
+          pair: [i, j],
+          distance: distanceMatrixBetweenPatches[i][j],
+        })
+    }
+  }
+  patchesPair.sort((a, b) => {
+    a.distance - b.distance
+  })
+
   // Initialize matrix with zeros
   const matrix = Array.from({ length: n }, () => Array(m).fill(0))
+  //1. fill in matrix with one row which can be filled with multiple columns (strings)
+  //2. group close patches by two and for each pair (from closest to furthest < DISTANCE_INTER_PATCH_THRESHOLDS) find combinaison of columns
+  //3. [TODO] take each remaining unassigned string and from longest, fill the biggest patch.
 
   // Function to find combinations of columns to satisfy a row sum
   //each row represent a patch, each column represent a string
-  //we try to find matches to complete one patch with one or multiple strings
   function findCombinationMatchesForRow(rowSum, colSums) {
@@ -127,5 +148,77 @@ const matches = []
   // Run the greedy decomposition algorithm
+  //1.
+  //we try to find matches to complete one patch with one or multiple strings
   greedyDecomposition(R, C)
 
+  //2.
+  //we try to find matches to complete pair of close patches with one or multiple strings
+  patchesPair.forEach(({ pair }) => {
+    const i = pair[0]
+    const j = pair[1]
+    if (R[i] != null && R[j] != null) {
+      const colCombinations = findCombinationMatchesForRow(R[i] + R[j], C)
+      if (colCombinations.length > 0) {
+        const colCombinationIndexes = colCombinations[0]
+        colCombinationIndexes.sort((a, b) => R[a] - R[b])
+        for (let k = 0; k < colCombinationIndexes.length; k++) {
+          const colIndex = colCombinationIndexes[k]
+          const colSum = C[colIndex]
+          if (R[i] > colSum) {
+            matrix[i][colIndex] += colSum
+            R[i] -= colSum
+            C[colIndex] = null
+          } else {
+            const remains = colSum - R[i]
+            matrix[i][colCombinationIndexes[k]] += R[i]
+            matrix[j][colCombinationIndexes[k]] += remains
+            R[i] = null
+            R[j] -= remains
+            if (R[j] == 0) {
+              R[j] = null
+            }
+            C[colIndex] = null
+          }
+        }
+      }
+    }
+  })
+  //3. fill in unassigned column to patches
+  const availableRows = R.map((r, index) =>
+    r !== null ? { index, value: r } : null
+  ).filter((r) => r !== null)
+  const availableCols = C.map((c, index) =>
+    c !== null ? { index, value: c } : null
+  ).filter((c) => c !== null)
+  availableRows.sort((a, b) => b.value - a.value)
+  availableCols.sort((a, b) => b.value - a.value)
+  availableCols.forEach(({ index, value }) => {
+    let remainingNumberOfPanelInCol = value
+    for (let availableRow of availableRows) {
+      if (remainingNumberOfPanelInCol > 0 && R[availableRow.index] != null) {
+        if (R[availableRow.index] < remainingNumberOfPanelInCol) {
+          C[index] -= R[availableRow.index]
+          matrix[availableRow.index][index] += R[availableRow.index]
+          remainingNumberOfPanelInCol -= R[availableRow.index]
+          R[availableRow.index] = null
+        } else if (R[availableRow.index] == remainingNumberOfPanelInCol) {
+          C[index] = null
+          R[availableRow.index] = null
+          matrix[availableRow.index][index] += remainingNumberOfPanelInCol
+          remainingNumberOfPanelInCol = 0
+        } else {
+          C[index] = null
+          R[availableRow.index] -= remainingNumberOfPanelInCol
+          matrix[availableRow.index][index] += remainingNumberOfPanelInCol
+          remainingNumberOfPanelInCol = 0
+        }
+      }
+    }
+  })
   // Output the resulting matrix
+  if (!validateSum(stringList, patchList, matrix)) {
+    console.log('validateSUM problem')
+    console.log('stringList', stringList)
+    console.log('patchList', patchList)
+    console.log('matrix', matrix)
+  }
   return {
@@ -143,1 +236,9 @@ matrix,
 }
+function validateSum(stringList, patchList, matrix) {
+  return (
+    stringList.every(
+      (s, index) => matrix.reduce((a, b) => a + b[index], 0) == s
+    ) &&
+    patchList.every((p, index) => matrix[index].reduce((a, b) => a + b, 0) == p)
+  )
+}

src/tests/panelFunctions/stringPatchMatching.spec.js

@@ -11,6 +11,10 @@ import { solveStringPatchMatching } from '../../stringPatchMatching'
     ]
-
-    expect(solveStringPatchMatching(stringList, patchList).matrix).toEqual(
-      expected
-    )
+    const distanceBetweenPatches = [
+      [0, 0],
+      [0, 0],
+    ]
+    expect(
+      solveStringPatchMatching(stringList, patchList, distanceBetweenPatches)
+        .matrix
+    ).toEqual(expected)
   })
@@ -21,2 +25,6 @@
     const patchList = [5, 4]
+    const distanceBetweenPatches = [
+      [0, 0],
+      [0, 0],
+    ]
     const expected = [
@@ -27,5 +35,6 @@ [2, 3, 0],
 
-    expect(solveStringPatchMatching(stringList, patchList).matrix).toEqual(
-      expected
-    )
+    expect(
+      solveStringPatchMatching(stringList, patchList, distanceBetweenPatches)
+        .matrix
+    ).toEqual(expected)
   })
@@ -35,7 +44,9 @@ it('should solve case where there is only one patch which needs multiple strings', () => {
     const patchList = [9]
+    const distanceBetweenPatches = [[0]]
     const expected = [[2, 3, 4]]
 
-    expect(solveStringPatchMatching(stringList, patchList).matrix).toEqual(
-      expected
-    )
+    expect(
+      solveStringPatchMatching(stringList, patchList, distanceBetweenPatches)
+        .matrix
+    ).toEqual(expected)
   })
@@ -47,6 +58,7 @@
     const expected = []
-
-    expect(solveStringPatchMatching(stringList, patchList).matrix).toEqual(
-      expected
-    )
+    const distanceBetweenPatches = []
+    expect(
+      solveStringPatchMatching(stringList, patchList, distanceBetweenPatches)
+        .matrix
+    ).toEqual(expected)
   })
@@ -57,2 +69,6 @@
     const patchList = [4, 7]
+    const distanceBetweenPatches = [
+      [0, 0],
+      [0, 0],
+    ]
     const expected = [
@@ -74,3 +90,4 @@ [0, 0, 0, 4],
       stringList,
-      patchList
+      patchList,
+      distanceBetweenPatches
     ).matrix
@@ -77,0 +94,0 @@ expect(validateSum(stringList, patchList, receivedMatrix)).toBe(true)

No alert changes

Improved metrics

Total package byte prevSize

255822

increased by2.48%

Number of package files

65

increased by1.56%

Lines of code

8791

increased by2.15%

No dependency changes