What is the best way to compare two TypeScript object arrays for equality, especially when some objects may have multiple ways to be considered equivalent

Question

What is the best way to compare two TypeScript object arrays for equality, especially when some objects may have multiple ways to be considered equivalent

Currently, I am in the process of developing a cost function for a game where players are given a set of resources in their hand. The resources can be categorized into different types such as Fire, Air, Water, Earth, Good, Evil, Law, Chaos, and Void.

These resources are further divided into two categories: Elements (Fire, Air, Water, Earth) and Philosophies (Good, Evil, Law, Chaos). In this game, player actions come with a cost that can consist of any combination of resources or categories.

For example:

[Fire, Air, Evil, Philosophy, Philosophy]

To pay a cost, players need to select resources from their hand that correspond to the specified cost. They can use resources from the same category to fulfill category costs, and there is also a wildcard resource called Void that can be used to pay for any other resource.

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

However, my current evaluation function is struggling to handle substitutions of categories or the Void resource. It currently only 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;
  }

After receiving feedback, I have restructured the problem as follows:

enum Resource {
  FIRE,
  AIR,
  WATER,
  EARTH,
  GOOD,
  EVIL,
  LAW,
  CHAOS,
  VOID,
  ELEMENT,    
  PHILOSOPHY, 
  ANY         
}

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 */
}

Further examples are provided for better understanding:

/** 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

...
(Additional examples were provided but omitted for brevity)

...

I am facing challenges in implementing a more advanced cost evaluation function due to the complexity of the requirements.

angular typescript algorithm compare equivalent

Answer 1

Answer №1

To simplify things, you can rearrange the resources and costs. For instance, ANY is considered a cost rather than a resource. Here's one approach:

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 prefer using string constants over numeric enums as they are easier for debugging.

There are other logical groupings here; for example, a cost of ELEMENT can be paid with either Elements or Void, so we can create data structures for those. Converting the enums into arrays will also aid in iteration.

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);

Before processing, it's important to determine the quantities of each resource in both the cost and payment arrays. Storing the resources as key-value pairs rather than arrays would make this task much simpler (e.g., { fire: 2, water: 3 }). Although I'll convert the array to key-value pairs within the function, consider refactoring your code accordingly.

If all costs and payments are accounted for, we can cover each cost by decrementing it by one and reducing the corresponding payment resource by one as well. This should be done sequentially based on specificity to avoid shortages. For instance, if we exhaust our FIRE paying for ELEMENT, we may lack sufficient FIRE when required later, even if we had excess WATER to cover ELEMENT. Hence, specific costs take precedence.

If a cost remains greater than 0 without any available payment, we cannot meet that cost.

Below is 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;
}

While there are obvious performance optimizations that can be made, this solution gets the job done.

Answer 2

To simplify things, you can rearrange the resources and costs. For instance, ANY is considered a cost rather than a resource. Here's one approach:

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 prefer using string constants over numeric enums as they are easier for debugging.

There are other logical groupings here; for example, a cost of ELEMENT can be paid with either Elements or Void, so we can create data structures for those. Converting the enums into arrays will also aid in iteration.

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);

Before processing, it's important to determine the quantities of each resource in both the cost and payment arrays. Storing the resources as key-value pairs rather than arrays would make this task much simpler (e.g., { fire: 2, water: 3 }). Although I'll convert the array to key-value pairs within the function, consider refactoring your code accordingly.

If all costs and payments are accounted for, we can cover each cost by decrementing it by one and reducing the corresponding payment resource by one as well. This should be done sequentially based on specificity to avoid shortages. For instance, if we exhaust our FIRE paying for ELEMENT, we may lack sufficient FIRE when required later, even if we had excess WATER to cover ELEMENT. Hence, specific costs take precedence.

If a cost remains greater than 0 without any available payment, we cannot meet that cost.

Below is 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;
}

While there are obvious performance optimizations that can be made, this solution gets the job done.

What is the best way to compare two TypeScript object arrays for equality, especially when some objects may have multiple ways to be considered equivalent

Answer №1

Similar questions

The .ts source file is mysteriously missing from the development tool's view after being deployed

Monitoring the download status in the web browser: Angular 5

Waiting for the execution of the loop to be completed before proceeding - Typescript (Angular)

Converting SQL COUNT query to angularfire2: A guide on translating Firebase / angularfire2

Generate a basic collection of strings from an object

Show Firebase data on Angular 6 mat-card in a randomized sequence when the page loads or refreshes

The React-widgets DateTimePicker is malfunctioning and displaying an error stating that it cannot assign to the type of 'Readonly<DateTimePickerProps>'

What allows mapped types to yield primitive outputs when using {[P in keyof T]}?

Triggering a subsequent action in Ngrx depending on the data from the initial action

Tips for correctly specifying the theme as a prop in the styled() function of Material UI using TypeScript

npm encountered an issue when attempting to install a package from a local directory: EISDIR: illegal operation on a directory, read

Discover the steps to dynamically alter the inclusion of the Bootstrap CSS file within an Angular project

Implementing Global Value Assignment Post Angular Service Subscription

Using node-fetch version 3.0.0 with jest results in a SyntaxError stating that import statements cannot be used outside a module

Customize the element of the root node of a MUI component using the styled()

Once the table is created in TypeORM, make sure to insert essential master data such as types and statuses

The issue of SVG not displaying on Chrome has been observed in Angular 6

Why do selected items in Ionic 3 ion-option not get deselected even after reloading or reinitializing the array

Exploring the use of two different array types in the useState hook with TypeScript

How to effectively handle null in Typescript when accessing types with index signatures unsafely