Crafting a LINQ based solution to determine if a set of predicates are satisfied for a pair of collections constrained by a set of invariants

Question

This isn't a question I feel I have the vocabulary to properly express, but I have two collections of the same anonymous type (lets call it 'a.)

'a is defined as new {string Name, int Count}

One of these collections of 'a we shall call requirements. One of these collections of 'a we shall call candidates.

Given these collections, I want to determine if the following assertions hold.

1. If there exists some element in requirements r such that r.Count == 0, each element in candidates c such that r.Name == c.Name must satisfy c.Count == 0. There must exist one such element in candidates for each such element in requirements.

2. For each element of requirements r where r.Count > 0, there must be some subset of elements in candidates c such that c₁.Name, c₂.Name, ..., cₓ.Name == r.Name and that c₁ + ... + cₓ >= r.Count. Each element of candidates used to satisfy this rule for some element in requirements may not be used for another element in requirements.

An example of this would be that given

requirements = {{"A",0}, {"B", 0}, {"C", 9}}
candidates = {{"B", 0},  {"C", 1}, {"A",0}, {"D", 2}, {"C", 4}, {"C", 4}}

That this query would be satisfied.

r={"A", 0} and r={"B", 0} would be satisfied according to rule #1 against c={"A", 0} and c={"B", 0}

-and-

r={"C", 9) is satisfied according to rule #2 by the group gc on collections c.Name derived from {{"C", 1}, {"C", 4}, {"C", 4}} as gc = {"C", 9}

However it is worth noting that if requirements contained {"C", 6} and {"C", 3} instead of {"C", 9}, this particular set of collections would fail to satisfy the predicates.

Now to the question finally. What is the best way to form this into a linq expression prioritizing speed (least iterations)?

The unsolved subset has been re-asked here

Answer 1

I finally came up with a workable solution

        IEnumerable<Glyph> requirements = t.Objectives.Cast<Glyph>().OrderBy(k => k.Name);
        IEnumerable<Glyph> candidates = Resources.Cast<Glyph>().OrderBy(k => k.Name);

        IEnumerable<Glyph> zeroCountCandidates = candidates.Where(c => c.Count == 0);
        IEnumerable<Glyph> zeroCountRequirements = requirements.Where(r => r.Count == 0);

        List<Glyph> remainingCandidates = zeroCountCandidates.ToList();

        if (zeroCountCandidates.Count() < zeroCountRequirements.Count())
        {
            return false;
        }

        foreach (var r in zeroCountRequirements)
        {
            if (!remainingCandidates.Contains(r))
            {
                return false;
            }
            else
            {
                remainingCandidates.Remove(r);
            }
        }

        IEnumerable<Glyph> nonZeroCountCandidates = candidates.Where(c => c.Count > 0);
        IEnumerable<Glyph> nonZeroCountRequirements = requirements.Where(r => r.Count > 0);

        var perms = nonZeroCountCandidates.Permutations();

        foreach (var perm in perms)
        {
            bool isViableSolution = true;

            remainingCandidates = perm.ToList();

            foreach (var requirement in nonZeroCountRequirements)
            {
                int countThreshold = requirement.Count;
                while (countThreshold > 0)
                {
                    if (remainingCandidates.Count() == 0)
                    {
                        isViableSolution = false;
                        break;
                    }

                    var c = remainingCandidates[0];
                    countThreshold -= c.Count;

                    remainingCandidates.Remove(c);
                }
            }

            if (isViableSolution)
            {
                return true;
            }
        }

        return false;

Disgusting isn't it?