CODEWITHSUNDEEP
javascript
Jim Davis
Jim Davis

Reputation: 1230

How to reorder sparse array into new, non-sparse array efficiently

[I apologize in advance for the complexity of the problem... but what good problem is simple?]

I manage the on-call roster for a largish (22 member) production support team. the list is a "full escalation" (all team members are listed) and generated monthly. Since those near the top of the list are called into overnight issues (and tend to be unavailable) we leverage the list in reverse to create our daytime assignment roster.

The Problem

After an unreasonable amount of time, politics and argument (don't ask) a rather silly rule set was created and agreed upon to generate this roster. To generate the daily assignment roster:

"Going backwards up the on-call list select the "even" ranks on the list and place them first in descending order. Then do the same thing for the "odds" placing them on the roster."

So, a simple example:

On-call: "1-Jack, 2-Jim, 3-Jane, 4-John, 5-Jill, 6-Joe" Roster: "1-Joe, 2-John, 3-Jim, 4-Jill, 3-Jane, 1-Jack"

The primary wrinkle is that, due to vacation, PTO, other assignments, etc time the on-call list is sparse (there may be empty slots). So a more real-world example might be:

On-call: "1-Jack, 3-Jane, 4-John, 6-Joe" Roster: "1-Joe, 2-John, 3-Jane, 4-Jack

The real list is 22 people. On any given given day we average about 17 or 18 available. The missing people don't impact the on-call - you just keep moving to the next highest - but they are making working within the roster rules painful.

The Current (Inelegant) Solution

Currently I have this working brute-force style. I first create an array of objects representing the on-call where each object has the name and on-call rank of a person. (It did just occur to me that I could probably simplify this by creating a sparse array of just the names where the index represented the actual rank... but I don't think it changes the issue).

I then loop through the array twice from last-to-first: first to collect the even ranks (by getting the modulus of the Rank) and push them onto a new array, second to collect the odds:

                       // Get the Current Oncall 
           var Oncall = new Array(); 
           for ( var iCnt = 1; iCnt <= 22; iCnt++ ) { 
                   var CurOncall = DataRows[Cnt].getAttribute("ows_OnCall" + iCnt); 
                   if ( CurOncall != null ) { 
                           Oncall[Oncall.length] =  {"Name":CurOncall, "Rank": iCnt}; 
                   }; 
           }; 
                   // Get the Current Roster 
           var Roster = new Array(); 
                   // Add the "evens" 
           for ( var iCnt = Oncall.length - 1; iCnt >= 0; iCnt-- ) { 
                           // Get the Current Incident Rank 
                   if ( Oncall[iCnt].Rank % 2 == 0 ) { 
                           Roster[Roster.length] = Oncall[iCnt].Name; 
                   }; 
           } 
                   // Add the "odds" 
           for ( var iCnt = Oncall.length - 1; iCnt >= 0; iCnt-- ) { 
                           // Get the Current Incident Rank 
                   if ( Oncall[iCnt].Rank % 2 != 0 ) { 
                           Roster[Roster.length] = Oncall[iCnt].Name; 
                   }; 
           }

Note that this snippet exists within a larger loop (I'm looping over a week's worth of data, this is only one day). DataRows[Cnt] is the current day's information as pulled from a SharePoint web service.

Again, this works fine, but requires three loops over the same data for each day's processing.

The Current (Broken) Solution

What I'd like to do is get to the poing where I can generate the Roster from the on-call using a single loop. Moving in that directly I've been working on just combining the second two loops into one. Assuming that the Oncall array is generated the same as above this is my current attempt (it's a little ugly):

       var IncCnt = 1; 
   for ( var Cnt = OnCall.length - 1; Cnt >= 0; Cnt-- ) { 

                   // Get the Current Incident (Roster) Rank 
           if ( OnCall[Cnt].Rank % 2 == 0 ) { 
                   CurIncRank = Math.ceil(IncCnt / 2); 
           } else { 
                   CurIncRank = Math.ceil(IncCnt / 2) + Math.floor(OnCall.length / 2) 
           }; 

           Roster[CurIncRank] = OnCall[Cnt].Name;
                   // Increase the Incident Cnt
           IncCnt = IncCnt + 1; 

   };

This comes close to working, but tends to either overlap (overwriting the last "even" with the first "odd") or leave a gap between the evens and odds depending the sparseness and total number of elements.

Conclusion

The primary goal is to generate the roster "on the fly" directly in the first loop rather than creating a specific on-call array then generating it from that - but currently I'd happy settle for getting just the second snippt to work in all cases.

I'm also open to the possibility that this may just not be able to work. Maybe the combination of an inelegant rule set and inelegant data simply require the brute-force method. If that's the case I'd just prefer to hear it from better programmers than myself before giving up.

Thanks in advance. Feel free to ask for any clarifications.

Upvotes: 2

Views: 181

Answers (2)

JonnyReeves
JonnyReeves

Reputation: 6209

And here's a very similar answer in coffeescript (:

# List of all employees
employees = [
    { name: "Jack", onCall: false, Rank: 1 }
    { name: "Jim", onCall: true, Rank: 2 }
    { name: "Jane", onCall: false, Rank: 3 }
    { name: "John", onCall: false, Rank: 4 }
    { name: "Jill", onCall: true, Rank: 5 }
    { name: "Joe", onCall: false, Rank: 6 }
]

# Returns an array of eligible Employees in the order which they should be called
generateRoster = (employees) ->
    a = []
    b = []

    employees
        .reverse()
        .filter (employee) ->
            not employee.onCall
        .forEach (employee) ->
            if employee % 2 
                a.push(employee) 
            else 
                b.push(employee)
            return

    a.concat(b)

# Output the roster
console.log generateRoster employees

Upvotes: 0

jackwanders
jackwanders

Reputation: 16020

So, if I read you correctly, you have an 'onCall' array of objects, each object containing a name and rank, like so:

var onCall = [
    {
        rank: 1,
        name: 'Jack'
    },
    {
        rank: 3,
        name: 'Jill'
    },
    ...
];

Then, you want to create a roster array that contains the evenly ranked people in descending order followed by the odd ranked people in descending order. If that's correct, then the following code would produce such an array:

for(var i = onCall.length-1; i >= 0; i--) {
    person = onCall[i];
    if(person.rank % 2 === 0) {
        evens.push(person);
    } else {
        odds.push(person);
    }
}
roster = evens.concat(odds);

You go through the array once, in reverse. For each person, append them to either 'evens' or 'odds' depending on their rank. Finally, you simply concatenate the two arrays into a new 'roster' array.

Here is a demo:

--- jsFiddle DEMO ---

I apologize that this isn't written with your particular variable names, but if this is what you're looking for, it should be easily changed to suit your environment.

Upvotes: 2

Related Questions