Need help writing a function

user_10231558 0
Viewed 128

I need some help writing a function for an app I'm creating.

Suppose I have an array of 5 objects.

var pool = [
    {"color":"Pink"},
    {"color":"Pink"},
    {"color":"Green"},
    {"color":"Orange"},
    {"color":"Orange"}
];

I also have an array that defines tasks to fulfill.

var tasks = [
    [
        {
            "amount": 1,
            "color": "Orange"
        },
        {
            "amount": 1,
            "color": "Pink"
        }
    ],
    [
        {
            "amount": 2,
            "color": "Green"
        },
        {
            "amount": 1,
            "color": "Orange"
        }
    ],
    [
        {
            "amount": 1,
            "color": "Orange"
        }
    ]
];

The tasks array contains 3 arrays. Those arrays represent the following tasks:

  1. Remove 1 Pink object or 1 Orange object from the pool.
  2. Remove 2 Green objects or 1 Orange object from the pool.
  3. Remove 1 Orange object from the pool.

I need a function that can determine if I have enough objects to complete all 3 tasks. The tasks must be done in sequence.

So for the first task, we would check if we have either 1 Pink object or 1 Orange object in the pool. We have 2 Pink objects and 2 Orange objects in the pool, so we know we can complete this task.

For the second task, we check if we have 2 Green objects or 1 Orange object to remove from the pool. We only have 1 Green object, so removing 2 Green objects is not an option. Our only option is to remove 1 Orange object from the pool. We considered removing one of the Orange objects for the first task, but that task can still be completed if we remove 1 of the Orange objects for this task.

For the third task, we check if we have 1 Orange object to remove. We have 2, but we know the second task must remove 1 of the Orange objects. This also means we cannot remove an Orange object for the first task.

So in the end, we know that the only objects we can remove for the first task are either of the 2 Pink objects. The second task must remove 1 of the Orange objects, and the third must remove the other Orange object.

I need to write a function that can determine all of that logic before attempting to complete any of the tasks.

The following function canDoTasks does not quite work, because it does not take into account whether a previous task needs to use any of the objects.

function canDoTasks1() {
    outerloop:
    for (var i = 0; i < tasks.length; i++) {
        var mandatory_task = tasks[i];
        for (var j = 0; j < mandatory_task.length; j++) {
            var optional_task = mandatory_task[j];
            var amount = countRemainingObjects(pool, optional_task.color);
            if (amount >= optional_task.amount) {
                continue outerloop;
            }
        }
        return false;
    }
    return true;
}

function countRemainingObjects(arr, color) {
    var total = 0;
    for (var i = 0; i < arr.length; i++) {
        if (arr[i].color == color) {
            total++;
        }
    }
    return total;
}

This next function canDoTasks2 also does not quite work, because it does not do a smart enough job at determining which objects need to be removed for each task.

function canDoTasks2() {
    var pool_copy = pool.slice();
    outerloop:
    for (var i = 0; i < tasks.length; i++) {
        var mandatory_task = tasks[i];
        for (var j = 0; j < mandatory_task.length; j++) {
            var optional_task = mandatory_task[j];
            var amount = countRemainingObjects(pool_copy, optional_task.color);
            if (amount >= optional_task.amount) {
                removeFromPool(pool_copy, optional_task.color);
                continue outerloop;
            }
        }
        return false;
    }
    return true;
}

function removeFromPool(arr, color) {
    for (var i = 0; i < arr.length; i++) {
        if (arr[i].color == color) {
            arr.splice(i, 1);
            return;
        }
    }
}
arrays json javascript
3 Answers

Performing a depth-first search is one solution.

In the function findTheWay() we re-arrange the pool into a dictionary telling us how many of each color is currently available. We then use that to do a depth-first search of the tasks list to find the first way that they can all be completed.

findTheWay() returns an array of indexes into the steps in the task list.

const pool = [
  {"color":"Pink"},
  {"color":"Pink"},
  {"color":"Green"},
  {"color":"Orange"},
  {"color":"Orange"}
];

const tasks = [
  [
    { "amount": 1, "color": "Orange" },
    { "amount": 1, "color": "Pink" }
  ],
  [
    { "amount": 2, "color": "Green" },
    { "amount": 1, "color": "Orange" }
  ],
  [
    { "amount": 1, "color": "Orange" }
  ]
];

const findTheWay = (items, tasks) => {
  // Collate the items into a color:count dictionary
  const pool = {};
  // Only care about the items that could be handled by the task list
  tasks.forEach(t => t.forEach(c => c.color in pool ? null : pool[c.color] = 0));
  // Count up the items
  items.forEach(i => i.color in pool ? pool[i.color]++ : null);
  
  // Prep a choices array that matches up with the tasks array
  const choice = new Array(tasks.length).fill(0);
  var idx = 0;
  
  // Perform the depth-first search
  while(true) {
    // If we've run out of options for a particular step, rewind to the 
    // previous step and choose its next option. If we rewind past the 
    // beginning of the list, there are no solutions.
    if(choice[idx] >= tasks[idx].length) {
      if(--idx < 0) break;
      const subtask = tasks[idx][choice[idx]];
      pool[subtask.color] += subtask.amount;
      choice[idx]++;
      continue;
    }
    
    // If the current choice in the current step is feasible, move to 
    // the next step. If we move past the end of the list, we've found
    // a solution.
    const subtask = tasks[idx][choice[idx]];
    if(pool[subtask.color] >= subtask.amount) {
      pool[subtask.color] -= subtask.amount;
      if(++idx >= choice.length) break;
      choice[idx] = 0;
      continue;
    }
    
    // This choice for this step didn't work out so move on to the 
    // next option.
    choice[idx]++;
  }

  if(idx < 0) return null;
  return choice;
};

const thisIsTheWay = findTheWay(pool, tasks);
console.log(thisIsTheWay);
console.log(thisIsTheWay.map((v,i) => tasks[i][v]));

Iterator/Iterable

You asked for code that finds all solutions as an add-on to your original question. Doing this requires some relatively minor adjustments.

Below, I've converted the above solution to an iterator/iterable. (More can be read about these in MDN's Iterators and generators and Iteration protocols.)

Note that the time to find all solutions increases very quickly as the number of tasks and options increases. For example, adding one task with three options triples the time required.

Note that the particular example set you provided only has the one solution.

const pool = [
  {"color":"Pink"},
  {"color":"Pink"},
  {"color":"Green"},
  {"color":"Orange"},
  {"color":"Orange"}
];

const tasks = [
  [
    { "amount": 1, "color": "Orange" },
    { "amount": 1, "color": "Pink" }
  ],
  [
    { "amount": 2, "color": "Green" },
    { "amount": 1, "color": "Orange" }
  ],
  [
    { "amount": 1, "color": "Orange" }
  ]
];

const theWays = (items, tasks) => {
  // Collate the items into a color:count dictionary
  const pool = {};
  // Only care about the items that could be handled by the task list
  tasks.forEach(t => t.forEach(c => c.color in pool ? null : pool[c.color] = 0));
  // Count up the items
  items.forEach(i => i.color in pool ? pool[i.color]++ : null);
  
  // Prep a choices array that matches up with the tasks array
  const choice = new Array(tasks.length).fill(0);
  var idx = 0;

  var isDone = false;
  
  // Create an iterator/iterable object
  const iter = {
    next: () => {
      if(isDone) return { done: true };

      // Perform the depth-first search
      while(true) {
        // If we've run out of options for a particular step, rewind to the 
        // previous step and choose its next option. If we rewind past the 
        // beginning of the list, we've found all the solutions.
        if(choice[idx] >= tasks[idx].length) {
          if(--idx < 0) {
            isDone = true;
            return { done: true };
          };
          const subtask = tasks[idx][choice[idx]];
          pool[subtask.color] += subtask.amount;
          choice[idx]++;
          continue;
        }
        
        // If the current choice in the current step is feasible, move to 
        // the next step. If we move past the end of the list, we've found
        // a solution.
        const subtask = tasks[idx][choice[idx]];
        if(pool[subtask.color] >= subtask.amount) {
          pool[subtask.color] -= subtask.amount;
          if(++idx >= choice.length) {
            // The choice state is the solution. Make a copy and return that
            // while also selecting next option for the next loop.
            const solution = Array.from(choice);
            choice[--idx]++;
            return {
              value: solution,
              done: false
            };
          }
          choice[idx] = 0;
          continue;
        }
        
        // This choice for this step didn't work out so move on to the 
        // next option.
        choice[idx]++;
      }
    },
    [Symbol.iterator]: () => iter,
  };

  return iter;
};

// Find first solution
const findTheWay = (items, tasks) => {
  const results = theWays(items, tasks).next();
  return results.done ? null : results.value;
}

// Find all solutions
const findTheWays = (items, tasks) => Array.from(theWays(items, tasks));

// Demos
const thisIsTheWay = findTheWay(pool, tasks);
console.log('First solution');
console.log(thisIsTheWay);
console.log(thisIsTheWay.map((v,i) => tasks[i][v]));

const theseAreTheWays = findTheWays(pool, tasks);
console.log(`All solutions: ${theseAreTheWays.length} found.`);
console.log(theseAreTheWays);
console.log(theseAreTheWays.map(v => v.map((v,i) => tasks[i][v])));

user_3678650

we can include an array to track what needs to be deleted in each task

const removeFromPool = (pool, task, removed) => {
    const cachePool = [].concat(pool);
  const color = task.color;
  let amount = task.amount;

  for (let i = pool.length - 1; i >= 0; --i) {
    const item = pool[i];
    if (item.color === color) {
      pool.splice(i, 1);
      amount--;
      if (amount === 0) {
        removed.push(task);
        return true;
      }
    }
  }
  // restore pool
  pool.splice(0, pool.length);
  cachePool.forEach(p => pool.push(p));
  return false;
}

const canCompleteTask = (tasks, pool, removed, index = 0) => {
  const cachePool = [].concat(pool);
  const task = tasks[index];

  if (task === undefined) { // completed all tasks
    return true;
  }

  for (let i = 0; i < task.length; i++) {
    const taskItem = task[i];
    if (removeFromPool(cachePool, taskItem, removed) &&
      canCompleteTask(tasks, cachePool, removed, index + 1)) {
      return true;
    }
  }
  return false;
}

const toRemove = []

console.log(canCompleteTask([
  [{
      "amount": 1,
      "color": "Orange"
    },
    {
      "amount": 1,
      "color": "Pink"
    }
  ],
  [{
      "amount": 2,
      "color": "Green"
    },
    {
      "amount": 1,
      "color": "Green"
    }
  ],
  [{
    "amount": 1,
    "color": "Orange"
  }]
], [{
    "color": "Pink"
  },
  {
    "color": "Pink"
  },
  {
    "color": "Green"
  },
  {
    "color": "Orange"
  },
  {
    "color": "Orange"
  }
], toRemove));

console.log(toRemove);

user_38088260

For now I could only come up with a solution to check if all tasks combined are possible, using all options - not picking one option. So this is just half a solution.

Using up all tasks & options

function isJobPossible (inputPool, inputTask) {
  
  // First I would transform the pool into a object, telling me how many of each color are available
  let inPool = {};
  for (let element of inputPool) {
    if (inPool[element.color]) {
      inPool[element.color] == inPool[element.color] + 1;
    } else {
      inPool[element.color] = 1;
    }
  }
 
  // Then I would sum up all colors needed from the tasks
  let inTask= {};
  for (let group in tasks) {
    for (let task in group) {
      if (inTask[task.color]) {
        inTask[task.color] = inTask[task.color] + task.amount;
      } else {
        inTask[task.color] = task.amount;
      }
    }
  }

  function isAvailableInPool (color, amount) {
    if (!inPool[color]) { return false }
    return inPool[color] >= amount
  }

  // now check if all tasks can be fullfilled with all options
  for (let color of Object.keys(inTask)) {
    let isPossible = isAvailbleInPool( color , inTask[color] ); 
    if (!isPossible) { return false }
  }

  return true

}

console.log( isJobPossible(pool, tasks) );
user_73768540
Related