7
\$\begingroup\$

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 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.

\$\endgroup\$
  • \$\begingroup\$ Can we take input locks in a format like or(3,and(4,6))? \$\endgroup\$ – xnor Aug 23 '16 at 18:04
  • \$\begingroup\$ @xnor No, sorry. Infix as string or array is the only option since that would require me to allow any "directly evaluable" format, which would in turn probably end up in a rewrite of the existing answers. \$\endgroup\$ – PurkkaKoodari Aug 23 '16 at 18:15
  • \$\begingroup\$ You should add an example like [[2, "|", 3], '&', 3] # (3) to the first input set, so that people notice when their solution prematurely prunes the set of possible keys. (See my comment under the Python solution.) \$\endgroup\$ – smls Aug 24 '16 at 10:15
2
\$\begingroup\$

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.
\$\endgroup\$
2
\$\begingroup\$

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])
\$\endgroup\$
  • 1
    \$\begingroup\$ You can save 5 bytes by using a lambda for m(a,b): m=lambda a,b:min(sorted(a),sorted(b)) \$\endgroup\$ – acrolith Aug 23 '16 at 22:45
  • 1
    \$\begingroup\$ This gives wrong results for keys where a higher alternative in one branch results in a lower overall security value for the lock. For example for the lock [[2, "|", 3], '&', 3] it calculates the security value [2, 3] instead of [3]. \$\endgroup\$ – smls Aug 24 '16 at 10:12
  • \$\begingroup\$ @smls That's an excellent point. I'll fix it as soon as I get time. Any suggestions? \$\endgroup\$ – gowrath Aug 24 '16 at 12:16
  • \$\begingroup\$ @gowrath In the Perl 6 solution, I first generate a flat list of all possible sets of keys that open the lock, and only then pick the "minimum" set. I generate the sets from the textual input basically by replacing each & with a cartesian product operator, and each | with a list concatenation operator, and then EVALing it, but the same could be done using a recursive function as well. \$\endgroup\$ – smls Aug 24 '16 at 13:22
  • \$\begingroup\$ @smls I was hoping there would be a way to do it without generating all possible sets; that was the motivation behind using a recursive function. \$\endgroup\$ – gowrath Aug 27 '16 at 10:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.