How secure are my locks?

Question

You have been assigned the task of installing new locks to the company's building. However, the locks you use are quite unusual: they require some combination of keys to open. Now, you want to figure out which locks are the most secure, so you can prioritize the most important locations.

The keys you use are numbered by security: key 1 is the weakest and could be given to the cat, key 2 is a bit better, and so on.

The locks are defined by AND and OR expressions between the keys. For example, a lock might open with just key 1, so it's defined by the string 1; another one might require key 3 and either key 1 or 2, so it's defined by 3 & (1 | 2). A lock opens if the expression is truthy when all key numbers are substituted for true/false depending on if the user possessed the respective keys. XOR and NOT are not needed, since possessing extra keys doesn't matter.

The security of a lock is defined by the weakest key combination required to open the lock. One way to compute this is the following algorithm:

1. Find all the subsets of the keys that open the lock.
2. Sort each combination descending (from the strongest key to the weakest).
3. Sort the combinations lexicographically ascending.
4. The security value of the lock is now the first item in the list.

In order to compare two locks, one just has to compare their security values lexicographically: the larger one is more secure.

Challenge

You are given a list of expressions that define locks. Your task is to sort the locks based on security in descending order.

Standard code-golf rules apply.

Input

You will receive a list of locks as input.

• The list may be taken as lines or in the list representation of your choice.
• Each lock can be given either as a string like 1 & ((2 | 3) & 4) or a nested list like [1, "&", [[2, "|", 3], "&", 4]].
  • Any whitespace in the string is optional, and all operations except for the outermost one will be wrapped in parentheses.
  • You are free to choose the list format that suits your needs.
• Each operator will have two operands.
• Key numbers will range from 1 to 99 and there will not be unused keys between 1 and the maximum used key.

Output

You will output the same list you got as input, sorted by security in descending order. All formats listed above are valid. If two locks are equally secure, their order does not matter.

Test cases

The test cases are in the "list" format. The outputs include the security values of each lock for reference; you should not output them.

Input:

[1]
[2]
[3]
[1, "&", 2]
[1, "&", 3]
[3, "&", 2]
[1, "|", 2]
[2, "|", 3]
[[1, "&", 2], "|", 3]
[[2, "|", 3], "&", 3]

Result:

[3, "&", 2]            # (3, 2)
[1, "&", 3]            # (3, 1)
[[2, "|", 3], "&", 3]  # (3)
[3]                    # (3)
[1, "&", 2]            # (2, 1)
[[1, "&", 2], "|", 3]  # (2, 1)
[2]                    # (2)
[2, "|", 3]            # (2)
[1]                    # (1)
[1, "|", 2]            # (1)

Input:

[[[6, '|', [[10, '|', 1], '&', [3, '&', 3]]], '|', 10], '&', [[12, '&', [9, '|', 7]], '|', [[3, '|', 8], '&', [[10, '|', [[1, '&', 3], '&', 9]], '|', [[2, '|', 1], '&', 1]]]]]
[[7, '|', 9], '&', [[5, '|', 10], '&', [[12, '|', 3], '&', 4]]]
[7, '|', 7]
[[[5, '|', [1, '|', 9]], '&', [[7, '&', [[6, '&', [1, '|', 7]], '|', 2]], '|', 5]], '&', [[[[8, '&', 6], '&', 1], '&', 5], '&', [10, '|', [11, '&', [3, '&', 6]]]]]
[[[[2, '&', [6, '&', 8]], '|', [[4, '|', 4], '|', [[5, '&', 4], '|', [[[1, '|', 5], '|', 1], '&', 7]]]], '&', [[[9, '|', [3, '&', 7]], '|', [9, '|', 5]], '&', [[[[8, '|', 11], '|', 8], '|', 2], '|', 2]]], '&', [[3, '|', 6], '&', 9]]
[[12, '|', [5, '&', [[12, '&', 3], '|', [9, '&', 1]]]], '|', [10, '&', [[8, '|', 9], '&', [[[8, '|', 3], '|', 8], '|', 11]]]]
[[9, '|', 11], '&', [[[11, '&', 12], '|', 10], '&', [3, '&', 12]]]
[[[5, '&', 9], '&', [10, '&', 2]], '|', [10, '|', 10]]
[[6, '&', 4], '&', [4, '|', 11]]
[[[[11, '&', [[[[5, '|', 11], '&', [10, '|', 7]], '&', 2], '|', 2]], '|', 12], '|', 5], '&', [[[2, '&', [5, '|', 9]], '&', 4], '&', [6, '|', [3, '&', 2]]]]

Result:

[[9, '|', 11], '&', [[[11, '&', 12], '|', 10], '&', [3, '&', 12]]] # (12, 10, 9, 3)
[[[5, '|', [1, '|', 9]], '&', [[7, '&', [[6, '&', [1, '|', 7]], '|', 2]], '|', 5]], '&', [[[[8, '&', 6], '&', 1], '&', 5], '&', [10, '|', [11, '&', [3, '&', 6]]]]] # (10, 8, 6, 5, 1)
[[[5, '&', 9], '&', [10, '&', 2]], '|', [10, '|', 10]] # (10)
[[12, '|', [5, '&', [[12, '&', 3], '|', [9, '&', 1]]]], '|', [10, '&', [[8, '|', 9], '&', [[[8, '|', 3], '|', 8], '|', 11]]]] # (9, 5, 1)
[[[[2, '&', [6, '&', 8]], '|', [[4, '|', 4], '|', [[5, '&', 4], '|', [[[1, '|', 5], '|', 1], '&', 7]]]], '&', [[[9, '|', [3, '&', 7]], '|', [9, '|', 5]], '&', [[[[8, '|', 11], '|', 8], '|', 2], '|', 2]]], '&', [[3, '|', 6], '&', 9]] # (9, 4, 3, 2)
[[7, '|', 9], '&', [[5, '|', 10], '&', [[12, '|', 3], '&', 4]]] # (7, 5, 4, 3)
[7, '|', 7] # (7)
[[6, '&', 4], '&', [4, '|', 11]] # (6, 4)
[[[[11, '&', [[[[5, '|', 11], '&', [10, '|', 7]], '&', 2], '|', 2]], '|', 12], '|', 5], '&', [[[2, '&', [5, '|', 9]], '&', 4], '&', [6, '|', [3, '&', 2]]]] # (5, 4, 3, 2)
[[[6, '|', [[10, '|', 1], '&', [3, '&', 3]]], '|', 10], '&', [[12, '&', [9, '|', 7]], '|', [[3, '|', 8], '&', [[10, '|', [[1, '&', 3], '&', 9]], '|', [[2, '|', 1], '&', 1]]]]] # (3, 1)

This program can be used to generate additional test cases. It also outputs the security values of each lock generated.

Answer 1

Perl 6: 132 124 bytes

{reverse .sort: {use MONKEY-SEE-NO-EVAL;my &infix:<|>={|$^a,|$^b}
min map *.flat.sort.squish.reverse,EVAL .trans('&'=>'X')}}

A lambda that takes a list of lines as input.

It generates the sort key for each line as follows:

• Declare | as a list concatenation operator within the lexical scope.
• Replace & in the string with X, the Perl 6 cartesian product operator.
• Eval the string (which unfortunately requires the ghastly MONKEY-SEE-NO-EVAL pragma), yielding all possible combinations of keys that open the door.
• Post-process the lists and pick the "least secure" combination.

Answer 2

Python, 253 246 bytes

m=lambda a,b:min(sorted(a),sorted(b))
def w(s):
    if type(s)!=list:return[s]
    if len(s)==1:return s
    k=w(s[0])
    z=w(s[2])
    if s[1]=="|":return m(k,z)
    return k+z
r=[]
for i in n:r+=[(i,sorted(w(i),reverse=1))]
sorted(r,reverse=1,key=lambda x:x[1])