Competitive programming - Prepare the perfect curry with ingredients P, Q, and R

Question

Recently i got a competetive programming task which i couldn't manage to complete. Just curious to know the best solution for the problem

"A" is a zero-indexed array of N integers. Elements of A are integers within the range [−99,999,999 to 99,999,999]

The 'curry' is a string consisting of N characters such that each character is either 'P', 'Q' or 'R' and the corresponding index of the array is the weight of each ingredient.

The curry is perfect if the sum of the total weights of 'P', 'Q' and 'R' is equal.

write a function

makeCurry(Array)

such that, given a zero-indexed array Array consisting of N integers, returns the perfect curry of this array.

The function should return the string "noLuck" if no perfect curry exists for that Array.

For example, given array Array such that

A[0] = 3 A[1] = 7 A[2] = 2 A[3] = 5 A[4] = 4

the function may return "PQRRP", as explained above. Given array A such that

A[0] = 3 A[1] = 6 A[2] = 9

the function should return "noLuck".

The approach i tried was this

import collections

class GetPerfectCurry(object):
    def __init__(self):
        self.curry = ''
        self.curry_stats = collections.Counter({'P': 0, 'Q': 0, 'R': 0})
        pass

    def get_perfect_curry(self, A):
        if len(A) == 0:
            return "noLuck"
        A.sort(reverse=True)
        for i, ele in enumerate(A):
            self.check_which_key_to_add_new_element_and_add_element(ele)
        if self.curry_stats['P'] == self.curry_stats['Q'] == self.curry_stats['R']:
            return self.curry
        else:
            return "noLuck"

    def check_which_key_to_add_new_element_and_add_element(self, val):
        # get the maximum current value
        # check if addition of new value with any of the other two key equals the max value
        # if yes then add that value and append the key in the curry string
        current_max_key = max(self.curry_stats, key=self.curry_stats.get)
        check_for_equality = False
        key_to_append = None
        for key, ele in enumerate(self.curry_stats):
            if ele != current_max_key:
                if self.curry_stats[ele] + val == self.curry_stats[current_max_key]:
                    check_for_equality = True
                    key_to_append = ele
        if check_for_equality:
            self.curry_stats.update(str(key_to_append) * val)
            self.curry += str(key_to_append)
            pass
        else:
            # if no value addition equals the current max
            # then find the current lowest value and add it to that key
            current_lowest_key = min(self.curry_stats, key=self.curry_stats.get)
            self.curry_stats.update(str(current_lowest_key)*val)
            self.curry += str(current_lowest_key)


if __name__ == '__main__':
    perfect_curry = GetPerfectCurry()
    A = [3, 7, 2, 5, 4]
    # A = [3, 6, 9]
    # A = [2, 9, 6, 3, 7]
    res = perfect_curry.get_perfect_curry(A)
    print(res)

But it was incorrect. Scratching my head for the past four hours for the best solution for this problem

user_12763954 · Answer

A possible algorithm is as follows:

Sum the weights. If it's not a multiple of 3, no luck. If it is, divide by 3 to get the target.
Find subsets of A that add up to target. For such subsets, remove it and you get B. Find a subset of B that adds up to target.

Here's a Java implementation (I'm not a Python guy, sorry):

import java.util.Arrays;

public class Main
{
    // Test if selected elements add up to target
    static boolean check(int[] a, int selection, int target)
    {
        int sum = 0;
        for(int i=0;i>i) & 1) == 1)
                sum += a[i];
        }
        return sum==target;
    }

    // Remove the selected elements
    static int[] exclude(int[] a, int selection)
    {
        int[] res = new int[a.length];
        int j = 0;
        for(int i=0;i>i) & 1) == 0)
                res[j++] = a[i];
        }
        return Arrays.copyOf(res, j);
    }

    static String getCurry(int[] a)
    {
        int sum = 0;
        for(int x : a)
            sum += x;
        if(sum%3 > 0)
            return "noLuck";
        int target = sum/3;
        int max1 = 1<>i) & 1) == 1)
                res[i] = 'P';
            else
            {
                if(((q>>j) & 1) == 1)
                    res[i] = 'Q';
                j++;
            }
        }
        return new String(res);
    }

    public static void main(String[] args)
    {
//      int[] a = new int[]{3, 7, 2, 5, 4};
//      int[] a = new int[]{1, 1, 2, -1};
        int[] a = new int[]{5, 4, 3, 3, 3, 3, 3, 3};
        System.out.println(getCurry(a));
    }
}

You can test it here.

user_7844349 · Answer

Hereafter so many years I'm writing code for js for needed people. (TBH I took the ref of the accepted answer)

As he mentioned, A possible algorithm is as follows:

Sum the weights. If it's not a multiple of 3, no luck. If it is, divide by 3 to get the target.

Find subsets of A that add up to target. For such subsets, remove it and you get B. Find a subset of B that adds up to target.

// Test if selected elements add up to target
function check(a, selection, target)
{
  let sum = 0;
  for(let i=0;i>i) & 1) == 1)
      sum += a[i];
  }
  return sum==target;
}

// Remove the selected elements
function exclude(a, selection)
{
  let res = [a.length];
  let j = 0;
  for(let i=0;i>i) & 1) == 0)
      res[j++] = a[i];
  }
  return res
}

function getCurry(a)
{
  let sum = a.reduce((accumulator, currentValue) => accumulator + currentValue);
  if(sum%3 > 0)
    return "noLuck";
  let target = sum/3;
  let max1 = 1<>i) & 1) == 1)
      res[i] = 'P';
    else
    {
      if(((q>>j) & 1) == 1)
        res[i] = 'Q';
      j++;
    }
  }
  return new String(res);
}

//      let a = [3, 7, 2, 5, 4]
//      let a = [1, 1, 2, -1]
        let a = [5, 4, 3, 3, 3, 3, 3, 3]
        getCurry(a)

Competitive programming - Prepare the perfect curry with ingredients P, Q, and R

2 Answers