Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- # I have a problem at work that I _think_ is the Knapsack Problem but perhaps
- # someone here can help me research/find a heuristic solution: we have access
- # to the <redacted> and get a finite number of “rules” we can use (e.g. 1000)
- # and each rule can only be 1024 characters long and have a maximum of 30
- # operators in them (e.g. “foo OR bar OR baz”), we have a list of domains
- # (e.g. example.com, example.org) we want to pack domains into rules as
- # efficiently as possible in the minimum number of rules.
- # Here's an attempt at a Sentient program to solve the decision version of
- # this problem, i.e. Can 100 domains fit into 5 rules?
- # You could then ratchet the number of rules down by binary search to find
- # the minimum number of rules.
- # Some constants of the problem.
- maxLength = 1024;
- maxOrs = 30;
- orLength = 4;
- # An array containing the length of each domain.
- array100<int> domains;
- # A 2D array containing whether each domain is a member of each rule.
- # The number of rules can be reduced to see if the problem can be satisfied with
- # fewer rules. The number of members should match the number of domains.
- array5<array10<bool>> ruleMembers;
- # All domain lengths must be positive.
- domains.each(function (length) {
- invariant length.positive?;
- });
- # Track how many domains have been allocated to rules.
- accountedFor = 0;
- # Go through the members of each rule.
- ruleMembers.each(function^ (members, rule) {
- numberOfDomains = 0;
- lengthOfRule = 0;
- # Go through all the domains.
- domains.each(function^ (length, index) {
- # Check whether the current domain is a member of the rule.
- isMember = members[index];
- # If it is, increment the number of domains and add to the rule length.
- numberOfDomains += isMember ? 1 : 0;
- lengthOfRule += isMember ? length : 0;
- });
- # Add the ' OR ' lengths to the rule length.
- numberOfOrs = numberOfDomains - 1;
- lengthOfRule += numberOfOrs * orLength;
- # The rule should not exceed 1024 characters.
- invariant lengthOfRule <= maxLength;
- # The rule should not contain more than 30 ORs.
- invariant numberOfOrs <= maxOrs;
- # These domains are now accounted for.
- accountedFor += numberOfDomains;
- });
- # All domains should now be accounted for.
- invariant accountedFor == domains.count;
- # Allow the domains to be set at runtime.
- # Return the rule members as output.
- expose domains, ruleMembers;
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement