Javascript sorting array by shortest step
This is a warehouse aisle/row/rack issue. Looking down an aisle, I have row 6 on my left and row 5 on my right.
I need to visit a list of racks in the fewest possible steps. Here is an array of rows and racks:
[
{"rowIndex": 5, "rowRackIndexActual": 1},
{"rowIndex": 5, "rowRackIndexActual": 3},
{"rowIndex": 5, "rowRackIndexActual": 4},
{"rowIndex": 6, "rowRackIndexActual": 5},
{"rowIndex": 6, "rowRackIndexActual": 6},
{"rowIndex": 5, "rowRackIndexActual": 6},
{"rowIndex": 5, "rowRackIndexActual": 7},
{"rowIndex": 6, "rowRackIndexActual": 8},
{"rowIndex": 5, "rowRackIndexActual": 8},
{"rowIndex": 6, "rowRackIndexActual": 9}
]
The output should look something like this from the bottom up:
(step 9) row 6, rack 9 |
(step 8) row 6, rack 8 + row 5, rack 8 (step 7)
| row 5, rack 7 (step 6)
/ row 5, rack 6 (step 5)
(step 4) row 6, rack 5 \
| row 5, rack 4 (step 3)
| row 5, rack 3 (step 2)
| row 5, rack 1 (step 1)
This issue is with rack 8 which appears in both rows. My sort is choosing the left row first but the shortest step is actually moving up one, since my last rack was in row 5 (the right row) -- step 7, in this case;
I obviously need to keep track of when a row changes -- when we move left or right. Here is my sort statment so far:
let prevRow = aisleRackArr[0].rowIndex; // the first item in the array
aisleRackArr.sort(function(a, b) {
console.log(a.rowIndex, a.rowRackIndexActual, b.rowIndex, b.rowRackIndexActual, prevRow);
if (a.rowRackIndexActual === b.rowRackIndexActual) {
console.log(`got the same rowRackIndex`);
if (a.rowIndex === prevRow) {
console.log(`a should come first`);
return 0;
} else {
console.log(`a came second`);
return 1;
}
}
prevRow = b.rowIndex;
return 0;
});
Here is the output from the sort function (a.row, a.rack, b.row, b.rack, prevRow):
5 3 5 1 5
5 4 5 3 5
6 5 5 4 5
5 6 6 5 5
5 7 5 6 6
6 8 5 7 5
5 8 6 8 5 <---------- not returning a even though a.row===prevRow
got the same rowRackIndex
a should come first
6 9 5 8 5
At first blush, it would seem we could simply sort by rackIndex and then rowIndex. However, that would not account for the case when we need to move up in the left row and the next two racks are the same index.
What can I do to fix this?
edit Here is a picture of what it looks like:
As I suspected, I needed to keep track of the current row. Since we can move up a row or down a row, each rack in each row has been given two indexes which represent the optimal route through an aisle if every rack in the aisle were selected. The "down" index is not the converse of the "up" index. When moving down a row, the first rack will be on your left. When moving up a row, the first rack will be on your right. Then, the index is assigned by over/up/over when moving up the row and over/down/over when moving down.
We take our pick list -- an array of all the items being filled for an order which also contains the row and rack in which a product can be found -- and extract out the unique aisles.
Here is a sample record in a pick list:
{
"idorder": 527261,
"orderIndex": 3,
"sku": "WZH76-4-W-YRS-PKP-XL",
"upc": "195041059206",
"quantity": 1,
"warehouse": 10,
"zone": 10,
"row": "20",
"rack": 20,
"tier": 1,
"shelf": 2,
"bin": 5,
"rowNorm": "000020",
"aisleNum": 1,
"rowIndex": 2,
"rowRackIndex": 2,
"rowRackIndexActual": 2,
"revRowRackIndexActual": -2,
"ecFactor": 0,
"aisleMaxRackIndex": 10,
"aisleRackIndex": 3,
"reverseAisleRackIndex": 16,
"rackCode": "10-10-20-20"
}
From the entire pick list we get the unique aisles:
uniqueAisles = [...new Set(pickListArr.map((a) => a.aisleNum))].keySort({aisleNum: `asc`});
Then, we loop through the aisles, selecting every product from the pick list that matches the current aisle:
sarr = [];
aisleRackArr = pickListArr.filter((r) => r.aisleNum === aa);
and then refine our aisleRackArray again by getting the unique racks for that aisle:
aisleRackArr = [...new Map(aisleRackArr.map((item) => [item.aisleRackIndex, item])).values()];
Then we figure out which direction in the aisle we're going: up or down. That isn't pertinent to this discussion so we'll skip it.
Once we know which way we're heading, we do a gross sort of every selected rack in the row -- from the order pick list -- based on it's up or down index:
if (curDir === `up`) {
aisleRackArr.keySort({rowRackIndexActual: `asc`, rowindex: `desc`});
} else {
aisleRackArr.keySort({revRowRackIndexActual: `asc`, rowIndex: `asc`});
}
We know our first rack based on the above sort and we know what direction we're going.
const dirFactor = curDir === `up`?1 : -1;
curRack = aisleRackArr[0];
Let's take our first record and push it into a temporary sorting array (sarr)
sarr.push({rowIndex: curRack.rowIndex, rackIndex: curRack.rowRackIndexActual, aisleNum: curAisleNum, aisleSort: +(+(+curRack.rowRackIndex * 10)) * (+dirFactor), rackCode: curRack.rackCode});
and then remove it from our aisle Rack Array:
aisleRackArr.splice(0, 1);
Now, we will loop through the remaining records in the aisle Rack Array, looking for the next rack we should move to:
while (aisleRackArr.length > 0) {
curRack = getNextRack(aisleRackArr, dirFactor, curRack.rowIndex);
once we know our next rack, push it into the temp array and then remove it from our rack array:
sarr.push({rowIndex: curRack.rowIndex, rackIndex: curRack.rowRackIndexActual, aisleNum: curAisleNum, aisleSort: curRack.sorter, rackCode: curRack.rackCode});
const curIndex=aisleRackArr.indexOf(curRack);
aisleRackArr.splice(curIndex, 1);
and continue with the loop;
}
Once we are finished with the loop, push the entire temp array into our master route array:
mapRouteArr.push(...sarr);
The code to determine the next rack:
We need to get the next three records in the array because those records will encompass every possible step we can make next: move left, move right or move up. Once we have those three record, we assign a new sort order based on the rack index (how far up or down the row we are) and if one or more of those records is in the same row (left or right) we're currently on. We'll sort those three records based on that criteria. If two of the racks are on the same level, give the rack that is in our current row precedence.
We then return that row, and the while loop stores it in the temp sort array and then removes it from the mix.
We continue on until the Rack Array is empty.
function getNextRack(rackArray, dirFactor, curRow) {
next3Arr = rackArray.slice(0, 4);
if (dirFactor === 1) { // going up!
next3Arr.forEach((a) => {
a.sorter = +(+(+a.rowRackIndexActual * 10) + (+curRow === +a.rowIndex ? 0 : 1));
a.currentRow = curRow;
});
return next3Arr.sort((a, b)=> a.sorter-b.sorter)[0];
} else { // going down!
next3Arr.forEach((a) => {
a.sorter = +((+a.rowRackIndexActual) * -10) - (+curRow === +a.rowIndex ? 1 : 0);
a.currentRow = curRow;
});
return next3Arr.sort((a, b) => a.sorter - b.sorter)[0];
}
}
My test case uses 10 orders resulting in 47 different racks that need to be visited. The result of the sort looks like this. This array accounts for all possible left/right,up/down and different row length scenarios and is exactly the way it should be:
[
{
"rowIndex": 2,
"rackIndex": 2,
"aisleNum": 1,
"aisleSort": 20,
"rackCode": "10-10-20-20"
},
{
"rowIndex": 1,
"rackIndex": 6,
"aisleNum": 1,
"aisleSort": 61,
"rackCode": "10-10-10-70"
},
{
"rowIndex": 1,
"rackIndex": 8,
"aisleNum": 1,
"aisleSort": 80,
"rackCode": "10-10-10-90"
},
{
"rowIndex": 2,
"rackIndex": 9,
"aisleNum": 1,
"aisleSort": 91,
"rackCode": "10-10-20-90"
},
{
"rowIndex": 3,
"rackIndex": 9,
"aisleNum": 2,
"aisleSort": -100,
"rackCode": "10-10-30-90"
},
{
"rowIndex": 3,
"rackIndex": 8,
"aisleNum": 2,
"aisleSort": -81,
"rackCode": "10-10-30-80"
},
{
"rowIndex": 4,
"rackIndex": 8,
"aisleNum": 2,
"aisleSort": -80,
"rackCode": "10-10-40-80"
},
{
"rowIndex": 4,
"rackIndex": 7,
"aisleNum": 2,
"aisleSort": -71,
"rackCode": "10-10-40-70"
},
{
"rowIndex": 4,
"rackIndex": 4,
"aisleNum": 2,
"aisleSort": -41,
"rackCode": "10-10-40-40"
},
{
"rowIndex": 3,
"rackIndex": 0,
"aisleNum": 2,
"aisleSort": 0,
"rackCode": "10-10-e4-10"
},
{
"rowIndex": 5,
"rackIndex": 1,
"aisleNum": 3,
"aisleSort": 20,
"rackCode": "10-10-50-10"
},
{
"rowIndex": 5,
"rackIndex": 3,
"aisleNum": 3,
"aisleSort": 30,
"rackCode": "10-10-50-30"
},
{
"rowIndex": 5,
"rackIndex": 4,
"aisleNum": 3,
"aisleSort": 40,
"rackCode": "10-10-50-40"
},
{
"rowIndex": 6,
"rackIndex": 5,
"aisleNum": 3,
"aisleSort": 51,
"rackCode": "10-10-60-50"
},
{
"rowIndex": 6,
"rackIndex": 6,
"aisleNum": 3,
"aisleSort": 60,
"rackCode": "10-10-60-60"
},
{
"rowIndex": 5,
"rackIndex": 6,
"aisleNum": 3,
"aisleSort": 61,
"rackCode": "10-10-50-60"
},
{
"rowIndex": 5,
"rackIndex": 7,
"aisleNum": 3,
"aisleSort": 70,
"rackCode": "10-10-50-70"
},
{
"rowIndex": 5,
"rackIndex": 8,
"aisleNum": 3,
"aisleSort": 80,
"rackCode": "10-10-50-80"
},
{
"rowIndex": 6,
"rackIndex": 8,
"aisleNum": 3,
"aisleSort": 81,
"rackCode": "10-10-60-80"
},
{
"rowIndex": 6,
"rackIndex": 9,
"aisleNum": 3,
"aisleSort": 90,
"rackCode": "10-10-60-90"
},
{
"rowIndex": 7,
"rackIndex": 9,
"aisleNum": 4,
"aisleSort": -100,
"rackCode": "10-10-70-90"
},
{
"rowIndex": 8,
"rackIndex": 8,
"aisleNum": 4,
"aisleSort": -80,
"rackCode": "10-10-80-80"
},
{
"rowIndex": 7,
"rackIndex": 4,
"aisleNum": 4,
"aisleSort": -40,
"rackCode": "10-10-70-40"
},
{
"rowIndex": 9,
"rackIndex": 2,
"aisleNum": 5,
"aisleSort": 30,
"rackCode": "10-10-90-20"
},
{
"rowIndex": 10,
"rackIndex": 3,
"aisleNum": 5,
"aisleSort": 31,
"rackCode": "10-10-100-30"
},
{
"rowIndex": 10,
"rackIndex": 7,
"aisleNum": 5,
"aisleSort": 70,
"rackCode": "10-10-100-70"
},
{
"rowIndex": 11,
"rackIndex": 8,
"aisleNum": 6,
"aisleSort": -90,
"rackCode": "10-10-110-80"
},
{
"rowIndex": 11,
"rackIndex": 7,
"aisleNum": 6,
"aisleSort": -71,
"rackCode": "10-10-110-70"
},
{
"rowIndex": 12,
"rackIndex": 7,
"aisleNum": 6,
"aisleSort": -70,
"rackCode": "10-10-120-70"
},
{
"rowIndex": 12,
"rackIndex": 5,
"aisleNum": 6,
"aisleSort": -51,
"rackCode": "10-10-120-50"
},
{
"rowIndex": 11,
"rackIndex": 4,
"aisleNum": 6,
"aisleSort": -40,
"rackCode": "10-10-110-40"
},
{
"rowIndex": 12,
"rackIndex": 3,
"aisleNum": 6,
"aisleSort": -30,
"rackCode": "10-10-120-30"
},
{
"rowIndex": 11,
"rackIndex": 2,
"aisleNum": 6,
"aisleSort": -20,
"rackCode": "10-10-110-20"
},
{
"rowIndex": 11,
"rackIndex": 1,
"aisleNum": 6,
"aisleSort": -11,
"rackCode": "10-10-110-10"
},
{
"rowIndex": 12,
"rackIndex": 1,
"aisleNum": 6,
"aisleSort": -10,
"rackCode": "10-10-120-10"
},
{
"rowIndex": 13,
"rackIndex": 2,
"aisleNum": 7,
"aisleSort": 30,
"rackCode": "10-10-130-20"
},
{
"rowIndex": 13,
"rackIndex": 4,
"aisleNum": 7,
"aisleSort": 40,
"rackCode": "10-10-130-40"
},
{
"rowIndex": 13,
"rackIndex": 6,
"aisleNum": 7,
"aisleSort": 60,
"rackCode": "10-10-130-60"
},
{
"rowIndex": 15,
"rackIndex": 6,
"aisleNum": 8,
"aisleSort": -70,
"rackCode": "10-10-150-60"
},
{
"rowIndex": 16,
"rackIndex": 6,
"aisleNum": 8,
"aisleSort": -60,
"rackCode": "10-10-160-60"
},
{
"rowIndex": 15,
"rackIndex": 5,
"aisleNum": 8,
"aisleSort": -50,
"rackCode": "10-10-150-50"
},
{
"rowIndex": 15,
"rackIndex": 4,
"aisleNum": 8,
"aisleSort": -41,
"rackCode": "10-10-150-40"
},
{
"rowIndex": 15,
"rackIndex": 3,
"aisleNum": 8,
"aisleSort": -31,
"rackCode": "10-10-150-30"
},
{
"rowIndex": 16,
"rackIndex": 2,
"aisleNum": 8,
"aisleSort": -20,
"rackCode": "10-10-160-20"
},
{
"rowIndex": 15,
"rackIndex": 1,
"aisleNum": 8,
"aisleSort": -10,
"rackCode": "10-10-150-10"
},
{
"rowIndex": 17,
"rackIndex": 2,
"aisleNum": 9,
"aisleSort": 20,
"rackCode": "10-10-170-20"
},
{
"rowIndex": 17,
"rackIndex": 3,
"aisleNum": 9,
"aisleSort": 30,
"rackCode": "10-10-170-30"
}
]
The EC racks are end caps and they belong to the odd rows -- the rows on the right looking up the aisle. The first rack in the entire sort is colored red. Using that starting point and following the above array, we now have the shortest path possible to pick a set of orders.
As a note: when we are finished with an aisle, sometimes the closest rack in the next aisle will be behind us. Here is the calculation to determine the closest rack in the next aisle, which factors in having to turn around in the current aisle to move to the next closest rack:
if (curDir === `up`) {
x = reverseMinRack.reverseAisleRackIndex + previousReverseAisleRackIndex + curDir === `up` ? 0 : 1;// +1 accounts for having to turn around
y = minRack.aisleRackIndex + previousAisleRackIndex + curDir === `down` ? 0 : 1; // +1 accounts for having to turn around
}
if (x === y) {
curDir = curDir === `up` ? `down` : `up`;
}
if (x < y) {
curDir = `down`;
}
if (x > y) {
curDir = `up`;
}
- PDF file creation using html-pdf is not working in my deployment server?
- Not iterating over map in node js
- Select text in textarea, delete it by backspace/delete to add CSS for another element
- Jquery : Uncaught SyntaxError: Failed to execute 'appendChild' on 'Node': missing ) after argument list
- center megamenu div under nav button
- Firebase Authentication: Where is the token stored in web?
- plugin:vite:import-analysis - Failed to parse source for import analysis because the content contains invalid JS syntax. - Vue 3
- SCRAM-SERVER-FIRST-MESSAGE: client password must be a string
- Where Am I Going Wrong Here - JAVASCRIPT
- Why does the function expression in an IIFE have to be wrapped in parentheses?
- In an object-destructuring declaration, what do the identifiers on the target side refer to?
- Can I destructure an object property into a property of another object?
- How does the object destructuring syntax work in ES6?
- How does nested destructuring work in ES6?
- Why does choosing module imports not work like destructuring?
- What is “fail-soft destructuring”?
- navigator.clipboard.readText() is not working in Firefox
- Why does console.log on a WeakSet give <items unknown> in node.js?
- Why do I need a WeakMap to store private data, as opposed to just closing over a variable with limited scope?
- Get url params in API route handler in Next.js
- How to move all Custom Element related into separate file to be imported & reused
- How to fetch data server-side in the latest Next.js? Tried getStaticProps but it's not running and getting undefined
- How to render my components in a tree structure, like default file structure in IDE using React
- Contentful API returning 'version mismatch' on entry update
- jqGrid dynamically change search operator type on button click
- JS making loop animation for a progress-bar
- Given an array of numbers(arr) and the length of the array(n) as arguments, how do you create a tribonacci sequence?
- "Could not read source map for chrome-error..." when using Visual Studio Code to debug JavaScript in Edge
- LeetCode Question - 2634. Filter Elements from Array
- How to get {[space][caret][space]} and {{[space][caret][space]}}