Конкурентное программирование - приготовьте идеальное карри с ингредиентами P, Q и R

Question

Недавно я получил конкурсное задание по программированию, которое мне не удалось выполнить. Просто любопытно узнать лучшее решение проблемы

«А» - это индексированный нулем массив из N целых чисел. Элементами A являются целые числа в диапазоне от [−99,999,999 до 99,999,999]

«Карри» - это строка, состоящая из N символов, так что каждый символ представляет собой «P», «Q» или «R» и соответствующий индекс массива - это вес каждого ингредиента.

Карри идеально подходит, если сумма общих весов 'P', 'Q' и 'R' равна.

написать функцию

makeCurry(Array)

таким образом, чтобы при заданном нулевом индексе массива Array, состоящего из N целых чисел, возвращалось идеальное карри этого массива.

Функция должна возвращать строку "noLuck" если для этого массива не существует идеального карри.

Например, для данного массива Array, такого, что

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

, функция может вернуть "PQRRP", как объяснено выше. Учитывая массив A такой, что

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

функция должна возвращать "noLuck".

Подход, который я пробовал, был следующим:

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)

Но это было неверно. Последние четыре часа почесал голову, чтобы найти лучшее решение этой проблемы

Answer 1

Возможен следующий алгоритм:

• Суммирование весов. Если это не кратно 3, не повезло. Если это так, разделите на 3, чтобы получить цель.

• Найдите подмножества A, которые суммируются с целью. Для таких подмножеств удалите его, и вы получите B. Найдите подмножество B, которое добавляет к цели.

Вот реализация Java (я не Python парень извините):

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<a.length;i++)
        {
            if(((selection>>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<a.length;i++)
        {
            if(((selection>>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<<a.length; // 2^length
        for(int i=0;i<max1;i++)
        {
            if(check(a, i, target))
            {
                int[] b = exclude(a, i);
                int max2 = 1<<b.length; // 2^length
                for(int j=0;j<max2;j++)
                {
                    if(check(b, j, target))
                        return formatSolution(i, j, a.length);
                }
            }
        }
        return "noLuck";
    }

    static String formatSolution(int p, int q, int len)
    {
        char[] res = new char[len];
        Arrays.fill(res, 'R');
        int j = 0;
        for(int i=0;i<len;i++)
        {
            if(((p>>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));
    }
}

Вы можете проверить это здесь .