MatchyMatchy

Program.cs

using System;
using System.Collections.Generic;
using System.Linq;

namespace exclusive
{
    class Program
    {
        // ruleId, transactionIds that satisfied the rule
        static Dictionary<int, HashSet<int>> RulesSatisfied;
        static void Main(string[] args)
        {
            var ruleIds = new HashSet<int> { 1, 2, 3 };
            RulesSatisfied = new Dictionary<int, HashSet<int>>(ruleIds.Count);

            IEnumerable<int> transactions = new List<int> { 1, 2, 3, 4, 5, 6 };

            // Loop through transactions one at a time
            // For each transaction, see if it satisfies each of the rules.
            // If it does, add it to the rulesSatisfied dictionary
            foreach (int transaction in transactions)
            {
                foreach (int ruleId in ruleIds)
                {
                    if (SatisfiesRule(ruleId, transaction))
                    {
                        _ = RulesSatisfied.TryAdd(ruleId, new HashSet<int>());
                        _ = RulesSatisfied[ruleId].Add(transaction);
                    }
                }

                // check if each rule is satisfied at least once. If not, there is no way we can match the ruleset.
                if (RulesSatisfied.Count < ruleIds.Count)
                {
                    continue;
                }

                // Loop through each transaction that has satisfied a rule thus far.
                // Note: if RuleSatisfied was sorted, could this reduce complexity?
                foreach ((int ruleId, HashSet<int> transactionIds) in RulesSatisfied)
                {
                    foreach (int transactionId in transactionIds)
                    {
                        // Loop through all the other satisfied rules and try to find a combination where each rule is
                        // satisfied by a different transaction.
                        List<int> used = Solve(ruleId, transactionId);

                        if (used.Count == ruleIds.Count)
                        {
                            Console.WriteLine("Solution found:");
                            foreach (int u in used)
                            {
                                Console.WriteLine(u);
                            }
                            return;
                        }
                    }
                }
            }
        }

        private static bool SatisfiesRule(int ruleId, int transactionId)
        {
            return ruleId switch
            {
                1 when transactionId is 1 or 4 or 6 => true,
                2 when transactionId is 2 or 5 => true,
                3 when transactionId is 4 or 5 or 6 => true,
                _ => false
            };
        }

        private static List<int> Solve(int currentRuleId, int currentTransactionId)
        {
            // 'burned' transactions, ie: already used to satisfy a rule and can't be used again.
            var used = new List<int>
            {
                currentTransactionId
            };

            // Find the first unused transaction for each rule.
            // Each time we find one, burn it and move to the next rule.
            foreach ((int ruleId, HashSet<int> transactions) in RulesSatisfied.Where(x => x.Key != currentRuleId))
            {
                foreach (int item in transactions)
                {
                    if (!used.Contains(item))
                    {
                        used.Add(item);
                        continue;
                    }
                }
            }

            return used;
        }
    }
}