Skip to content
Advertisement

Output Array of Simultaneously Possible Unique Element Combinations

My application references a database object that acts as a catalog. It’s a catalog of items that can be crafted if the user has the necessary components. Here is a small sample of the catalog:

const itemCatalog = {
    "bramble_vest" : {
        "components" : [ "Chain Vest", "Chain Vest" ],
        "name" : "Bramble Vest"
    },
    "guardian_angel" : {
        "components" : [ "B.F. Sword", "Chain Vest" ],
        "name" : "Guardian Angel"
    },
    "hextech_gunblade" : {
        "components" : [ "B.F. Sword", "Needlessly Large Rod" ],
        "name" : "Hextech Gunblade"
    },
    "locket_of_the_iron_solari" : {
        "components" : [ "Chain Vest", "Needlessly Large Rod" ],
        "name" : "Locket of the Iron Solari"
    },
    "morellonomicon" : {
        "components" : [ "Giant's Belt", "Needlessly Large Rod" ],
        "name" : "Morellonomicon"
    },
    "sunfire_cape" : {
        "components" : [ "Chain Vest", "Giant's Belt" ],
        "name" : "Sunfire Cape"
    },
    "zekes_herald" : {
        "components" : [ "B.F. Sword", "Giant's Belt" ],
        "name" : "Zeke's Herald"
    }
}

When the user has the necessary components for any given item, the user can assemble that item. The user is awarded components arbitrarily and randomly, but how the user receives the components is not relevant to my question. Suffice to say that the user’s components are put into an array on the client, which is then used to determine which items the user can assemble:

let myComponents = [
    "B.F. Sword",
    "Chain Vest",
    "Giant's Belt",
    "Chain Vest",
    "Needlessly Large Rod"
]

I have written a block of code that determines which items are possible with the elements in myComponents. That’s fairly straightforward, even though it isn’t particularly concise or stylish.

With the components listed in myComponents all of the items in this sample of itemCatalog are possible. However, they are not simultanesouly possible. The reason for this, of course, is that there are not enough components for all the items.

I need logic that can determine which items are simultaneously possible, given the components in myComponents when referenced against itemCatalog. The output should be an array of arrays. Each inner array would be a list of simultaneously possible catalog items. In this case, with the components currently in myComponents it would look like this:

[ 
    ["Bramble Vest", "Hextech Gunblade"], 
    ["Bramble Vest", "Morellonomicon"], 
    ["Bramble Vest", "Zeke's Herald"], 
    ["Guardian Angel", "Locket of the Iron Solari"], 
    ["Guardian Angel", "Morellonomicon"], 
    ["Guardian Angel", "Sunfire Cape"], 
    ["Hextech Gunblade", "Sunfire Cape"], 
    ["Locket of the Iron Solari", "Sunfire Cape"], 
    ["Locket of the Iron Solari","Zeke's Herald"]
]

Below is my current logic. There’s a lot of logging there to help sift through, but the main issue with the function buildSimultaneousItems() is that once an item is checked against another item during iteration, those two items aren’t checked again. I don’t want to get into it too much, as I don’t want to scare people away with information overload. It’s all pretty straightforward, despite its ugliness. The main thing is that the expected output is above. Please feel free to ask questions.

// A catalog of items that can be assembled using components.
// The app uses this as a reference. This catalog is larger in the app, with many more items.
const itemCatalog = {
  "bramble_vest" : {
    "components" : [ "Chain Vest", "Chain Vest" ],
    "name" : "Bramble Vest"
  },
  "guardian_angel" : {
    "components" : [ "B.F. Sword", "Chain Vest" ],
    "name" : "Guardian Angel"
  },
  "hextech_gunblade" : {
    "components" : [ "B.F. Sword", "Needlessly Large Rod" ],
    "name" : "Hextech Gunblade"
  },
  "locket_of_the_iron_solari" : {
    "components" : [ "Chain Vest", "Needlessly Large Rod" ],
    "name" : "Locket of the Iron Solari"
  },
  "morellonomicon" : {
    "components" : [ "Giant's Belt", "Needlessly Large Rod" ],
    "name" : "Morellonomicon"
  },
  "sunfire_cape" : {
    "components" : [ "Chain Vest", "Giant's Belt" ],
    "name" : "Sunfire Cape"
  },
  "zekes_herald" : {
    "components" : [ "B.F. Sword", "Giant's Belt" ],
    "name" : "Zeke's Herald"
  }
}

// Components the user currently has
let myComponents = [
  "B.F. Sword",
  "Chain Vest",
  "Giant's Belt",
  "Chain Vest",
  "Needlessly Large Rod"
]

// Returns array of possible items with provided component combinations (myComponents)
getPossibleItems = (arr) => {
  let possibleItems = [];
  for (const possItem in arr) {
    if (doArraysMatch(arr[possItem].components, myComponents) ==  true) {
      possibleItems.push(arr[possItem].name);
    }
  }
  return possibleItems;
}

// Returns array of components at corresponding indices that correspond to the array returned in the above function
getPossItemsComponents = (arrA, arrB) => {
  let possItemsComponents = []
  for (const item in arrA) {
    for (const combItem in arrB) {
      console.log(arrB[combItem].name, ": ",arrB[combItem].components);
      if (arrA[item] == arrB[combItem].name) {
        possItemsComponents.push(arrB[combItem].components);
      }
    }
  }
  return possItemsComponents;
}

// Attempts to return an array of arrays. Each inner array is a list of items that can be
// assembled SIMULTANEOUSLY with the provided components (myComponents)
buildSimultaneousItems = () => {
  let terms = [];   
  possibleItems = getPossibleItems(itemCatalog);
  possibleItemsComponents = getPossItemsComponents(possibleItems, itemCatalog);
  for (let i = 0; i < possibleItems.length; i++) {
    let simultaneousItems = [];
    let simultaneousItemsComponents = [];
    simultaneousItems.push(possibleItems[i]);
    console.log(JSON.stringify(possibleItems[i]), ": ", JSON.stringify(possibleItemsComponents[i]), "-----------------------")
    simultaneousItemsComponents.push(possibleItemsComponents[i]);
    //console.log(possibleItemsComponents[i][0])
    for (let j = 0; j < possibleItems.length; j++) {
      console.log("Does myItems", JSON.stringify(myComponents), " contain ",JSON.stringify(simultaneousItemsComponents[0].concat(possibleItemsComponents[j])), " for ", JSON.stringify(possibleItems[j]),this.containsAllItems(myComponents, simultaneousItemsComponents[0].concat(possibleItemsComponents[j])))
      while (containsAllItems(myComponents, simultaneousItemsComponents[0].concat(possibleItemsComponents[j]))) {
        simultaneousItems.push(possibleItems[j]);
        console.log("Add ", JSON.stringify(possibleItemsComponents[j]), " to ", JSON.stringify(simultaneousItemsComponents[0]))
        simultaneousItemsComponents[0].push(possibleItemsComponents[j][0]);
        simultaneousItemsComponents[0].push(possibleItemsComponents[j][1]);
      }
    }
    terms.push(simultaneousItems);
  }
  console.log(terms)
}

// Utility functions for comparing arrays -------------------------- //

doArraysMatch = (subset, superset) => {
  const subsetCount = _.countBy(subset);
  const supersetCount = _.countBy(superset);
  return _.every(subsetCount, (count, value) => supersetCount[value] >= count);
}

containsAllItems = (arrA, arrB) => {
  arrA.forEach(elA => {
    if (arrB.includes(elA)) {
      arrB.splice(arrB.indexOf(elA), 1);
    }
  })
  if (arrB.length == 0) {
    return true;
  } else {
    return false;
  }
}

buildSimultaneousItems()
<script src="https://cdn.jsdelivr.net/npm/lodash@4.17.10/lodash.min.js"></script>

Advertisement

Answer

(Note: there is an updated version below handling an additional requirement.)

Here’s another approach, based on a simple recursive algorithm: We look at the first item in the list and if we can make it, we combine it with each of the results formed by calling the function with the remainder of the targets and the list of components less the ones required to make this item. If we can’t make the first item, we just recur with the remainder of the items and the full list of components. The recursion bottoms out when the list of items is empty. To use this, we first convert your catalog to an array with Object.values, since we don’t need your object keys at all.

Once we’ve found our collections, we remove those that are strict subsets of another. That is because as well as the full values you want, the collect function also gathers sets that could still contain others. With your above data, for instance, it collects [["Bramble Vest", "Hextech Gunblade"], ["Bramble Vest", "Morellonomicon"], ["Bramble Vest", "Zeke's Herald"], ["Bramble Vest"], ...] (with a dozen more items, many containing single components.) Note that the fourth item, ["Bramble Vest"], is a strict subset of each of the three earlier ones. Using maximize, we remove such subsets from the result.

This breakdown is useful because collect expresses a useful algorithm on its own. (The implementation is still tied to your structure, using the components and name properties of each item, but it would not be difficult to make more generic.) That algorithm takes items, a collection of collections of components, and components, a collection of components, and returns a list of all possible collections of items that could be made with that fixed list of components. Layering maximize atop this gives us both your goal and this somewhat more general algorithm together. It’s also a simpler algorithm, as far as I can tell. Perhaps someone can show me a simplification that does these two steps in one.

Here’s an implementation:

// utility functions
const dropFirst = (x, xs, i = xs .indexOf (x)) =>
  i < 0 ? [... xs] : [... xs .slice (0, i), ... xs .slice (i + 1)]

const dropEach = ([x, ...xs], ys) => 
  x == undefined ? ys : dropEach (xs, dropFirst (x, ys))

const canMake = ([c, ...cs], comps) => 
  c == undefined ? true : comps .includes (c) ? canMake (cs, dropFirst (c, comps)) : false

const isSubset = (xs, ys) =>
  xs .every (x => ys .includes (x))

const maximize = (xs) => 
  xs .filter (x => ! (xs .some (y => x !== y && isSubset (x, y))))


// main function
const collect = ([x, ...xs], ys) => 
  x == undefined
    ? [[]]
  : canMake (x.components, ys)
    ? [
        ... collect (xs, dropEach (x .components, ys)) .map (coll => [x .name, ... coll]), 
        ... collect (xs, ys)
      ]
    : collect (xs, ys)


// public function
const simultaneousItems = (catalog, components) => 
  maximize (collect (Object.values(catalog), components))


// sample data
const itemCatalog = { bramble_vest: {components : [ "Chain Vest", "Chain Vest" ], name : "Bramble Vest"}, guardian_angel: {components : [ "B.F. Sword", "Chain Vest" ], name : "Guardian Angel"}, hextech_gunblade: {components : [ "B.F. Sword", "Needlessly Large Rod" ], name : "Hextech Gunblade"}, locket_of_the_iron_solari: {components : [ "Chain Vest", "Needlessly Large Rod" ], name : "Locket of the Iron Solari"}, morellonomicon: {components : [ "Giant's Belt", "Needlessly Large Rod" ], name : "Morellonomicon"}, sunfire_cape: {components : [ "Chain Vest", "Giant's Belt" ], name : "Sunfire Cape"}, zekes_herald: {components : [ "B.F. Sword", "Giant's Belt" ], name : "Zeke's Herald"}}

const myComponents = ["B.F. Sword", "Chain Vest", "Giant's Belt", "Chain Vest", "Needlessly Large Rod"]


// demo
console .log (
  simultaneousItems(itemCatalog, myComponents)
)
.as-console-wrapper {max-height: 100% !important; top: 0}

We start with a collection of utility functions:

  • dropFirst removes the first occurrence of a value in an array of values. For instance,

    //                          v------------ First 'bar'
dropFirst ('bar', ['foo', 'bar', 'baz', 'qux', 'bar', 'bar', 'corge']) 
//=> ["foo", "baz", "qux", "bar", "bar", "corge"]
//          ^---------------------------- now missing

  • dropEvery extends this to remove each of a list of values from the main list, using dropFirst. For instance

    //   will all be removed -----------v------v--------------------v              
dropEach (['bar', 'foo', 'bar'], ['foo', 'bar', 'baz', 'qux', 'bar', 'bar', 'corge']) 
//=> ["baz", "qux", "bar", "corge"]

  • canMake reports whether we can make a list of components given the components at hand. For instance, using your sample list of components,

    canMake (['B.F. Sword', 'Chain Vest']) (myComponents) //=> true
canMake (['B.F. Sword', 'Chain Vest', 'B.F. Sword']) (myComponents) //=> false

    The first works because we have both the sword and the vest in our components. The second fails because we have only one sword.

    There are numerous other techniques we could use to write this function. The recursive version fit with the rest of these functions, but we could also have compared counts of the relevant strings between the item’s components and our available components.

(Note: these first three functions might have been much easier if we implemented a MultiSet/Bag type for both the items’ components and our overall list of components. I won’t try that here, but it might be worth investigating.)

  • isSubset simply reports if one array of strings is a subset of another. Here we don’t care about multiplicities, as our outputs don’t include many copies of any one of our items.

  • maximize is discussed above. It removes from a list of collections those that are subsets of another in the list.

Then we have our central function,

  • collect, which determines which subsets of our list of items can be made with our components. The algorithm is described above.

And our public wrapper function,

  • simultaneousItems, which calls Object.values on your input to put it into a useful format for collect, passes that and the list of components to collect, and then calls maximize on the results. This function yields the input I think you want.

This is the output from the data supplied:

[
  ["Bramble Vest", "Hextech Gunblade"],
  ["Bramble Vest", "Morellonomicon"],
  ["Bramble Vest", "Zeke's Herald"],
  ["Guardian Angel", "Locket of the Iron Solari"],
  ["Guardian Angel", "Morellonomicon"],
  ["Guardian Angel", "Sunfire Cape"],
  ["Hextech Gunblade", "Sunfire Cape"],
  ["Locket of the Iron Solari", "Sunfire Cape"], 
  ["Locket of the Iron Solari", "Zeke's Herald"]
]

If we add a second “B.F. Sword” to our list of components, we get this list:

[
  ["Bramble Vest", "Hextech Gunblade", "Zeke's Herald"],
  ["Bramble Vest", "Morellonomicon"],
  ["Guardian Angel", "Hextech Gunblade", "Sunfire Cape"],
  ["Guardian Angel", "Locket of the Iron Solari", "Zeke's Herald"],
  ["Guardian Angel", "Morellonomicon"],
  ["Locket of the Iron Solari", "Sunfire Cape"]
]

It would be an interesting exercise to turn collect into a more generic function that was still easy to use to define makeSimultaneous. I would also not be surprised if that generic problem was a well-known problem with some optimized algorithms for it. I’d be curious about the algorithmic performance as well. But all that’s for another day.

There is also a reasonable argument to be made for turning your output into a Set of Sets rather than an array of arrays. The ordering of the arrays is irrelevant, and in any such case, a Set is a more logical data structure. I probably wouldn’t do this, as logical as it is, as I still find arrays easier to work with. But it’s worth considering.

Update

A comment from the OP described an additional requirement not met by the above: The items we collect can occur multiple times. This might be clear to someone who knows the underlying game in question, but the code above doesn’t handle it.

Moreover, it’s not a simple fix. The design of collect above was to choose whether to gather the first item supplied (if possible) or not, and then recur on the remaining items and the components left after using up the necessary ones for the item. I saw no simple way to change that to allow multiple copies.

So here is a rewrite of collect with a mixture of existing helper functions and new ones to support it:

// utility functions
const dropFirst = (x, xs, i = xs .indexOf (x)) =>
  i < 0 ? [... xs] : [... xs .slice (0, i), ... xs .slice (i + 1)]

const dropEach = ([x, ...xs], ys) => 
  x == undefined ? ys : dropEach (xs, dropFirst (x, ys))

const dropEachRepeatedly = (n, xs, ys) =>
  n == 0 ? ys : dropEach(xs, dropEachRepeatedly(n - 1, xs, ys))

const canMake = ([c, ...cs], comps) => 
  c == undefined ? true : comps .includes (c) ? canMake (cs, dropFirst (c, comps)) : false

const howMany = (xs, ys) => 
  canMake (xs, ys)
    ? 1 + howMany (xs, dropEach(xs, ys))
    : 0

const range = (lo, hi) => Array .from ({length: hi - lo + 1}, (_, i) => i + lo)

const count = (xs) => 
  xs .reduce ((a, x) => ((a[x] = (a[x] || 0) + 1), a), {})

const isMultiSubset = (xs, ys, cx = count (xs), cy = count (ys)) =>
  Object .keys (cx) .every (x => cx [x] <= (cy [x] || 0))

const maximize = (xs) => 
  xs .filter (x => ! (xs .some (y => x !== y && isMultiSubset (x, y))))


// main function
const collect = ([x, ...xs], ys) => 
  x == undefined
    ? [[]]
    : range (0, howMany (x.components, ys)) .reverse() .flatMap(
        (n) => collect(xs, dropEachRepeatedly(n, x.components, ys)) .map (
          coll =>  [...Array(n).fill(x.name), ...coll]
        )
      )


// public function
const simultaneousItems = (catalog, components) => 
  maximize (collect (Object .values (catalog), components))


// sample data
const itemCatalog = { bramble_vest: {components : [ "Chain Vest", "Chain Vest" ], name : "Bramble Vest"}, guardian_angel: {components : [ "B.F. Sword", "Chain Vest" ], name : "Guardian Angel"}, hextech_gunblade: {components : [ "B.F. Sword", "Needlessly Large Rod" ], name : "Hextech Gunblade"}, locket_of_the_iron_solari: {components : [ "Chain Vest", "Needlessly Large Rod" ], name : "Locket of the Iron Solari"}, morellonomicon: {components : [ "Giant's Belt", "Needlessly Large Rod" ], name : "Morellonomicon"}, sunfire_cape: {components : [ "Chain Vest", "Giant's Belt" ], name : "Sunfire Cape"}, zekes_herald: {components : [ "B.F. Sword", "Giant's Belt" ], name : "Zeke's Herald"}}

// const myComponents = ["B.F. Sword", "Chain Vest", "Giant's Belt", "Chain Vest", "Needlessly Large Rod"]
const myComponents = ["B.F. Sword", "Chain Vest", "Giant's Belt", "Chain Vest", "Chain Vest", "Needlessly Large Rod", "Chain Vest"]


// demo
console .log (
  simultaneousItems (itemCatalog, myComponents)
)
.as-console-wrapper {max-height: 100% !important; top: 0}

Adding two more “Chain Vest”s into our components, we now get this result:

[
    ["Bramble Vest", "Bramble Vest", "Hextech Gunblade"],
    ["Bramble Vest", "Bramble Vest", "Morellonomicon"],
    ["Bramble Vest", "Bramble Vest", "Zeke's Herald"],
    ["Bramble Vest", "Guardian Angel", "Locket of the Iron Solari"],
    ["Bramble Vest", "Guardian Angel", "Morellonomicon"],
    ["Bramble Vest", "Guardian Angel", "Sunfire Cape"],
    ["Bramble Vest", "Hextech Gunblade", "Sunfire Cape"],
    ["Bramble Vest", "Locket of the Iron Solari", "Sunfire Cape"],
    ["Bramble Vest", "Locket of the Iron Solari", "Zeke's Herald"],
    ["Guardian Angel", "Locket of the Iron Solari", "Sunfire Cape"]
]

As before, collect is our main function, with simultaneousItems being a simple wrapper that massages the input before calling collect and then running maximize on the result.

Many of the helper functions are the same. Only maximize changed. It now depends on isMultiSubset instead of isSubset (which we no longer need.) But we also have some additional helpers:

  • dropEachRepeatedly drops multiple copies of one list (here the item’s components) from another (our available components)

  • howMany reports how many copies of one list can be made from the members of another

  • range simply generates a range of integers. For example

    range (3, 12) //=> [3, 4, 5, 6, 7, 8, 9, 10, 11, 12]

  • count counts the occurrences of each value in a list. For example

    count (['a', 'b', 'a', 'c', 'b', 'd', 'b'])
//=> {a: 2, b: 3, c: 1, d: 1}

  • isMultiSubset reports whether one multiset (here expressed as an array, but order doesn’t matter) is a subset of another one. For example, ['a' , 'b' , 'a'] is not a multi-subset of ['a', 'b', 'c', 'd'] since there are two 'a's in the first and only one in the second. But it is a multi-subset of ['a', 'b', 'c', 'a'] since there are enough 'a's and 'b' to go around. Because we now allow for multiple copies of components in each output configuration, we need to use this when we do our maximizing.

Our main function, collect now works like this: If we have no items in our input, we return an array containing only the empty array. If we do, we focus on the first component, count how many times it fits in our list of components, then for each value from that number down to zero, we choose to include that many copies of the item, and recur on the remaining items and the components reduced by that many copies of item’s component list. We just return a flattened version of this result.

It’s quite likely that this code can be simplified. I started from what we already had and altered from there. Often that does not lead to results as good as when we plan it from the start. But many times we don’t have that luxury.

User contributions licensed under: CC BY-SA
3 People found this is helpful
Advertisement