How do I check two Typescript object arrays for equivalence when some objects have multiple equivale-CodePudding

I am coding a cost function for a game. Players have a hand of n < 14 Resources of the following possible types:

Fire, Air, Water, Earth, Good, Evil, Law, Chaos, Void

These are subdivided into two Categories: Elements (Fire, Air, Water, Earth) and Philosophies (Good, Evil, Law, Chaos). Actions taken by the player have a cost, which may be any combination of Resources or Categories.

Example cost: [Fire, Air, Evil, Philosophy, Philosophy]

Each resource in the cost must be paid by the corresponding resource from the player's hand. Categories in the cost may be filled by any Resource in that Category. Costs may also include Any, which can be filled by any Resource type. To pay a cost, the player must select Resources from their hand, then click on the Action. This triggers an evaluation function which returns True if the selected Resources fulfill the cost.

Void is a "wildcard" Resource that may be used to pay for any other Resource. (This does not apply the other way around - a player cannot fulfill a Void cost by paying with another resource.)

A valid payment for the example cost above would be [Void, Void, Air, Good, Good]

I am currently stumped for how to implement this. My current evaluation function cannot handle the substitutions of Categories or Void; it simply checks for exact equivalence:

  /** Returns true if the resources currently selected by the player
   * satisfy the @cost of the option selected */
  evaluatePayment(cost: Resource[]): boolean {
    let isValidPayment: boolean = true;
    if (cost) {
      const playerSelectedResources: Resource[] = this.playerHand
        .filter(r => r.isSelected)
        .map(hr => hr.type);
      // Check that selected resources cover cost
      const missingCost = cost.filter(r => playerSelectedResources.indexOf(r));
      // Check that no additional resources are selected
      const excessPaid = playerSelectedResources.filter(r => cost.indexOf(r));
      if (missingCost.length > 0 || excessPaid.length > 0) {
        isValidPayment = false;
      }
    }
    return isCostSelected;
  }

Based on feedback, here is a better formulation of the problem:

enum Resource {
  FIRE,
  AIR,
  WATER,
  EARTH,
  GOOD,
  EVIL,
  LAW,
  CHAOS,
  VOID,
  ELEMENT,    // This can only appear in a Cost, never a Payment
  PHILOSOPHY, // This can only appear in a Cost, never a Payment
  ANY         // This can only appear in a Cost, never a Payment
}

export const ElementResources: Resource[] = [Resource.FIRE, Resource.AIR, Resource.WATER, Resource.EARTH];
export const PhilosophyResources: Resource[] = [Resource.GOOD, Resource.EVIL, Resource.LAW, Resource.CHAOS];


function isValidExactPayment(cost: Resource[], payment: Resource[]): boolean {
  /** Logic here
   * Returns True if payment matches cost exactly, 
   * according to the rules above */
}

Some more examples:

/** Example 1 */
const cost: Resource[] = [Resource.WATER, Resource, EVIL];

isValidExactPayment(cost, [Resource.WATER, Resource.EVIL]); // true
isValidExactPayment(cost, [Resource.EVIL, Resource.VOID]); // true
isValidExactPayment(cost, [Resource.VOID, Resource.EVIL]); // true, order should not matter
isValidExactPayment(cost, [Resource.WATER, Resource.VOID]); // true


/** Example 2 */
const cost: Resource[] = [Resource.VOID];

isValidExactPayment(cost, [Resource.VOID]); // true
isValidExactPayment(cost, [Resource.EVIL]); // false


/** Example 3 */
const cost: Resource[] = [Resource.GOOD];

isValidExactPayment(cost, [Resource.GOOD]); // true
isValidExactPayment(cost, [Resource.VOID]); // true
isValidExactPayment(cost, [Resource.EVIL]); // false


/** Example 4 */
const cost: Resource[] = [Resource.AIR, Resource.PHILOSOPHY, Resource.PHILOSOPHY];

isValidExactPayment(cost, [Resource.AIR, Resource.EVIL, Resource.CHAOS]); // true
isValidExactPayment(cost, [Resource.VOID, Resource.GOOD, Resource.GOOD]); // true
isValidExactPayment(cost, [Resource.AIR, Resource.CHAOS, Resource.VOID]); // true


/** Example 5 */
const cost: Resource[] = [Resource.ELEMENT]

isValidExactPayment(cost, [Resource.FIRE]); // true
isValidExactPayment(cost, [Resource.AIR]); // true
isValidExactPayment(cost, [Resource.WATER]); // true
isValidExactPayment(cost, [Resource.EARTH]); // true
isValidExactPayment(cost, [Resource.VOID]); // true


/** Example 6 */
const cost: Resource[] = [Resource.WATER, Resource.ANY, Resource.ANY]

isValidExactPayment(cost, [Resource.WATER, Resource.WATER, Resource.WATER]); // true
isValidExactPayment(cost, [Resource.FIRE, Resource.FIRE, Resource.FIRE]); // false
isValidExactPayment(cost, [Resource.VOID, Resource.WATER, Resource.LAW]); // true

/** Example 7 */
const cost: Resource[] = [Resource.FIRE, Resource.EVIL, Resource.PHILOSOPHY, Resource.ELEMENT];

isValidExactPayment(cost, [Resource.FIRE, Resource.EVIL, Resource.EVIL, Resource.EARTH]); // true
isValidExactPayment(cost, [Resource.FIRE, Resource.EVIL, Resource.EVIL, Resource.VOID]); // true
isValidExactPayment(cost, [Resource.VOID, Resource.EVIL, Resource.GOOD, Resource.WATER]); // true

I'm currently pretty stumped for how to implement the more complex cost evaluation function.

CodePudding user response：

To make things simpler you can reorganize the resources / costs. For example ANY is not a resource, it is only a cost. Here is one way to do it:

enum Elements {
  FIRE = 'fire',
  AIR = 'air',
  WATER = 'water',
  EARTH = 'earth',
}

enum Philosophies {
  GOOD = 'good',
  EVIL = 'evil',
  LAW = 'law',
  CHAOS = 'chaos',
}

enum Void {
  VOID = 'void',
}

enum Resource {
  VOID = Void.VOID,
  FIRE = Elements.FIRE,
  AIR = Elements.AIR,
  WATER = Elements.WATER,
  EARTH = Elements.EARTH,
  GOOD = Philosophies.GOOD,
  EVIL = Philosophies.EVIL,
  LAW = Philosophies.LAW,
  CHAOS = Philosophies.CHAOS,
}

const ANY = 'any';
const ELEMENT = 'element';
const PHILOSOPHY = 'philosophy';
type Cost = Resource | typeof ANY | typeof ELEMENT | typeof PHILOSOPHY;

I like to use string constants rather than numeric enums, much better for debugging.

There are some other logical groups here, for instance a cost of ELEMENT can be paid for with Elements or Void so we can create some data structures for those. Also, turning the enums into an array will be helpful for iterating.

const allResources = Object.values(Resource);

const elementsAndVoid: (Elements | Void)[] = [];
for (const e of Object.values(Elements)) elementsAndVoid.push(e);
elementsAndVoid.push(Void.VOID);

const philosophiesAndVoid: (Philosophies | Void)[] = [];
for (const p of Object.values(Philosophies)) philosophiesAndVoid.push(p);
philosophiesAndVoid.push(Void.VOID);

We need to know the amounts of each resource in both the cost and payment arrays before we can begin processing. It would be much easier to store the resources as key-value pairs rather than arrays (for example { fire: 2, water: 3 }). Instead of refactoring your code I'll just convert the array to key-value pairs in the function, but definitely something you should consider.

If our costs and payments are all counted, we can pay for each cost by decrementing the cost by one, and decrementing whatever we pay with by one. This needs to be done in order of specificity. For example if we blow all our FIRE on ELEMENT, we might be short on FIRE when we try to pay for it, when we had plenty of WATER to pay for ELEMENT. So the more specific costs take precedence.

If we ever get a cost that is greater than 0, but nothing to pay with, then we know we can't cover the cost.

Here's an implementation:

function isValidExactPayment(costs: Cost[], payments: Resource[]): boolean {
  // count payment amounts
  const paymentCounts: { [key: string]: number } = {};
  for (const p of payments) {
    if (paymentCounts[p] === undefined) paymentCounts[p] = 0;
    paymentCounts[p]  ;
  }
  // count cost amounts
  const costCounts: { [key: string]: number } = {};
  for (const c of costs) {
    if (costCounts[c] === undefined) costCounts[c] = 0;
    costCounts[c]  ;
  }
  // Attempt to pay for specific resource - void first
  for (const r of allResources) {
    while (costCounts[r] > 0) {
      if (paymentCounts[r] > 0) {
        costCounts[r]--;
        paymentCounts[r]--;
      }
      // Use leftover void if there's not enough
      else if (paymentCounts[Resource.VOID] > 0) {
        costCounts[r]--;
        paymentCounts[Resource.VOID]--;
      }
      // Not enough specific resource
      else {
        console.log('Not enough:', r);
        return false;
      }
    }
  }
  // Attempt to pay for general elements
  for (const r of elementsAndVoid) {
    while (costCounts[ELEMENT] > 0 && paymentCounts[r] > 0) {
      costCounts[ELEMENT]--;
      paymentCounts[r]--;
    }
  }
  // Not enough elements
  if (costCounts[ELEMENT] > 0) {
    console.log('Not enough:', ELEMENT);
    return false;
  }
  // Attempt to pay for general philosophies
  for (const r of philosophiesAndVoid) {
    while (costCounts[PHILOSOPHY] > 0 && paymentCounts[r] > 0) {
      costCounts[PHILOSOPHY]--;
      paymentCounts[r]--;
    }
  }
  // Not enough philosophies
  if (costCounts[PHILOSOPHY] > 0) {
    console.log('Not enough:', PHILOSOPHY);
    return false;
  }
  // Attempt to pay for any with anything
  for (const r of allResources) {
    while (costCounts[ANY] > 0 && paymentCounts[r] > 0) {
      costCounts[ANY]--;
      paymentCounts[r]--;
    }
  }
  // Not enough any
  if (costCounts[ANY] > 0) {
    console.log('Not enough:', ANY);
    return false;
  }
  // Paid in full :)
  console.log('Paid in full');
  return true;
}

There's obviously performance optimizations that can be done, but this works.