Reorder array of objects so that each position of the array has a particular key/value pair

Question

I have an array of object that looks something like this:

var players = [
  {
    "imagePos1": '',
    "imagePos2": 'test',
    "imagePos3": '',
    "imagePos4": ''
  },
  {
    "imagePos1": '',
    "imagePos2": 'test',
    "imagePos3": 'test',
    "imagePos4": ''
  },
  {
    "imagePos1": '',
    "imagePos2": 'test',
    "imagePos3": '',
    "imagePos4": 'test'
  },
  {
    "imagePos1": 'test',
    "imagePos2": '',
    "imagePos3": 'test',
    "imagePos4": ''
  }
];

I need to reorganize the players array so that the item at the 0 index has a value for the 'imagePos1' key, and the item at the 1 index has a value for the 'imagePos2' key, and on and on through the fourth item. So for the array above the correct output would be:

var players = [
  {
    "imagePos1": 'test', // index 0
    "imagePos2": '',
    "imagePos3": 'test',
    "imagePos4": ''
  },
  {
    "imagePos1": '',
    "imagePos2": 'test', // index 1
    "imagePos3": '',
    "imagePos4": ''
  },
  {
    "imagePos1": '',
    "imagePos2": 'test',
    "imagePos3": 'test', // index 2
    "imagePos4": ''
  },
  {
    "imagePos1": '',
    "imagePos2": 'test',
    "imagePos3": '',
    "imagePos4": 'test' // index 3
  }
];

I don't know what the objects in the array will look like before hand, so I also need to account for the possibility that the object cannot be ordered in this way and output some message.

Here's what I have so far (It's terrible, I know):

var objCache = {};
var noInfiniteLoopsPlz = 0;

function findDuds() {
  if (noInfiniteLoopsPlz > 256) { 
    console.log('aint gonna happen')
    return false;
  } else {
    // add one to this to make sure the recursive func doesn't go forever
    noInfiniteLoopsPlz++
    for (var i = 0; i < players.length; i++) {
      // find what images don't have the image needed
      if (players[i]['imagePos' + (i + 1)].length === 0) { 
        // find what ones do
        for (var j = 0; j < players.length; j++) {
          // when you find an image...
          if (players[i]['imagePos' + (j + 1)].length) {
            // save the object that's currently in that spot for now
            objCache = players[j];
            // then put the object that you're moving in its place
            players[j] = players[i];

            // place the saved object where the old one was
            players[i] = objCache;
            // see if the saved object has an image for the place that has opened up. If it hasn't, start this all over again
            if (objCache['imagePos' + (i + 1)].length) {
              findDuds();
            }
          }
        }
      }
    } 
  }
}

findDuds();


console.log(players);

Answer 1

You want to find a permutation of your players satisfying a set of constraints.

If you remove the first player from the correct answer and the pool, the rest of the correct answer is a permutation of the pool satisfying an analogous set of constraints. The sequence is also of a small length. So, we can use a recursive search.

For every player than could be in position 1, we see if there's a permutation of the remaining players from 2 to 4. If there is, we return the candidate plus that permutation. If there isn't, an exception will be thrown and we move on to the next candidate. If there are no candidates, or we tried them all, the problem cannot be solved. Testing for position 2 is analogous, so the code is the same.

var players = [
  {
    "imagePos1": '',
    "imagePos2": 'test',
    "imagePos3": '',
    "imagePos4": ''
  },
  {
    "imagePos1": '',
    "imagePos2": 'test',
    "imagePos3": 'test',
    "imagePos4": ''
  },
  {
    "imagePos1": '',
    "imagePos2": 'test',
    "imagePos3": '',
    "imagePos4": 'test'
  },
  {
    "imagePos1": 'test',
    "imagePos2": '',
    "imagePos3": 'test',
    "imagePos4": ''
  }
];

/*
 * Returns a function which tests whether the player passed to it has
 * an image in the given position.
 */
function has(index) {
    return function (player) {
        return player["imagePos"+index];
    }
}

/*
 * Orders elements in `rest` numbered from from to `to`.
 * `start` is prepended.
 */
function order(from, to, start, rest) {
    /* check if we are done */
    if (from > to) {
        return start;
    }

    /* find elements that might come next */
    var candidates = rest.filter(has(from));

    var len = candidates.length;

    /* Try each candidate. */
    for (var i = 0; i < len; i++) {
        var candidate = candidates[i],
            /* elements that may come later assuming this candidate comes next */
            remainder = rest.filter(function (el) { return el !== candidate; }),
            /* new prefix including this candidate */
            newStart = start.concat(candidate);
        try {
            /* order the remaining candidates by the rest of the numbers */
            return order(1+from, to, newStart, remainder);
        } catch (e) {
            /* on failure we try the next candidate */
        }
    }

    /* If we get here we tried all the candidates (possibly 0) and none of them worked. */
    throw "unsatisfiable";
}

order(1, 4, [], players); 

Answer 2

Given your input data, we can simply do the following. Assuming that empty values are represented as empty strings; you can just modify the check if it's needed.

var players = [{
  "imagePos1": '',
  "imagePos2": 'test',
  "imagePos3": '',
  "imagePos4": ''
}, {
  "imagePos1": '',
  "imagePos2": 'test',
  "imagePos3": 'test',
  "imagePos4": ''
}, {
  "imagePos1": '',
  "imagePos2": 'test',
  "imagePos3": '',
  "imagePos4": 'test'
}, {
  "imagePos1": 'test',
  "imagePos2": '',
  "imagePos3": 'test',
  "imagePos4": ''
}];

//Make choices binary, store as ints, create possible combination parts
var bin = [];
var com = [];
for (var i in players) {
    bin[i] = 0;
    com[i] = [];
    for (prop in players[i]) {
        bin[i] <<= 1;
        bin[i] += ~~(players[i][prop].length > 0);
    }
    //Too lazy to write reasonably readable loops
    for (var j = 0, n = bin[i]; n; j++, n >>= 1) {
        if (n & 1) {
            com[i].push(1 << j);
        }
    }
}

//The object keys part is essentially just telling us how many properties there are, we could hardcode this or whatever
var v = (1 << Object.keys(players[0]).length) - 1;
var per = [];
var match;
var max = com.length - 1;
//Create all combinations of the above
var rec = function(a, i) {
    for (var j in com[i]) {
        var cpy = a.slice();
        cpy.push(com[i][j]);
        if (i < max) {
            rec(cpy, i + 1);
        } else {
            //We have a full combination, check if it fits
            var n = cpy[0];
            for (var j = 1; j < cpy.length; j++) {
                n |= cpy[j];
            }
            //Stop at first match, you can change this if you want all matches
            if (n === v) {
                match = cpy;
                return;
            }
        }
    }
}
rec([], 0);

//This is just for pretty-printing
if (match === void 0) {
    alert('there is no matching combination');
} else {
    var out = '';
    for (var i = 0; i < match.length; i++) {
        for (var j = 0; match[i] < v; match[i] <<= 1, j++) {
            //Empty loop body because snafucate
        }
        //Make both indexes 1-based for clarity
        out += 'element ' + (i + 1) + ' goes to slot ' + j + '; ';
    }
    alert(out);
}