11
\$\begingroup\$

Introduction:

You're a key maker, and want to access something from a safe that has a lock. Unfortunately, the key to that lock is lost, so you'll have to make a new one. You have access to a bunch of blank keys, to which you can add notches to turn it into actual keys. You also have loads of keys with notches already applied lying around.

Challenge:

Given a list of list of digits (all of equal length) representing the list of keys with notches you have lying around, where each digit represents the height of the notch 'column', as well as an integer list of digits of the key you want to make for the lock of the safe, output the amount of keys you should potentially make in order to try to open the lock.

How would we determine this? Here an example:
Let's say the key that's supposed to go into the lock is [7,5,2,5] (where the first digit is at the opening of the lock). And let's say the list of keys you have available is [[2,5,3,5],[3,7,5,8],[8,2,1,0],[6,3,6,6],[7,9,5,7],[0,2,2,1]] (where the last digits are the tips of the keys).

Here is how far we can insert each key into the lock:

Let's take the first key [2,5,3,5] as more in-depth example:

[2,5,3,5]         # First notch:  5<=7, so it fits
    [7,5,2,5]     # Second notch: 5<=5 & 3<=7, so it fits
                  # Third notch:  5>2 (& 3<=5 & 5<=7), so it can't be inserted that far into the lock
                  # Based on this key we now know the following about the safe-key:
                  # First notch:  >=5
                  # Second notch: >=5
                  # Third notch:  <5

Here a visual representation, to perhaps better understand it, where the blue cells are key [2,5,3,5], the yellow parts is the key that's supposed to go into the lock [7,5,2,5], and the black parts are the lock itself:

enter image description here

As for the other keys:

[3,7,5,8]         # First notch: 8>7, so it can't even be inserted into the lock at all
        [7,5,2,5] # base on this key we now know the following about the safe-key:
                  # First notch:  <8

[8,2,1,0]         # First notch:  0<=7, so it fits
  [7,5,2,5]       # Second notch: 0<=5 & 1<=7, so it fits
                  # Third notch:  0<=2 & 1<=5 & 2<=7, so it fits
                  # Fourth notch: (0<=5 & 1<=2 & 2<=5 &) 8>7, so it can't be inserted that far
                  # Based on this key we now know the following about the safe-key:
                  # First notch:  >=2 & <8
                  # Second notch: >=1
                  # Third notch:  >=0 (duh)
                  # Fourth notch: nothing; we couldn't insert it to due to first notch

[6,3,6,6]         # First notch:  6<=7, so it fits
      [7,5,2,5]   # Second notch: 6>5 (& 6<=7), so it can't be inserted that far
                  # Based on this key we now know the following about the safe-key:
                  # First notch:  >=6
                  # Second notch: <6

[7,9,8,7]         # First notch:  7<=7, so it fits
      [7,5,2,5]   # Second notch: 7>5 & 8>7, so it can't be inserted that far
                  # Based on this key we now know the following about the safe-key:
                  # First notch:  >=7 & <8
                  # Second notch: <7

[0,2,2,1]         # First notch:  1<=7, so it fits
[7,5,2,5]         # Second notch: 1<=5 & 2<=7, so it fits
                  # Third notch:  1<=2 & 2<=5 & 2<=7, so it fits
                  # Fourth notch: 1<=5 & 2<=2 & 2<=5 & 0<=7, so it fits
                  # Based on this key we now know the following about the safe-key:
                  # First notch:  >=2
                  # Second notch: >=2
                  # Third notch:  >=2
                  # Fourth notch: >=1

Combining all that:

# First notch:  ==7 (>=7 & <8)
# Second notch: ==5 (>=5 & <6)
# Third notch:  >=2 & <5
# Fourth notch: >=1

Leaving all potential safe-keys (27 in total, which is our output):

[[1,2,5,7],[1,3,5,7],[1,4,5,7],[2,2,5,7],[2,3,5,7],[2,4,5,7],[3,2,5,7],[3,3,5,7],[3,4,5,7],[4,2,5,7],[4,3,5,7],[4,4,5,7],[5,2,5,7],[5,3,5,7],[5,4,5,7],[6,2,5,7],[6,3,5,7],[6,4,5,7],[7,2,5,7],[7,3,5,7],[7,4,5,7],[8,2,5,7],[8,3,5,7],[8,4,5,7],[9,2,5,7],[9,3,5,7],[9,4,5,7]]

Challenge rules:

  • Assume we'll know all notches when it doesn't fit, even though the lock would in reality be a black box. Let's just assume the key maker is very experienced, and can feel such a thing. What I mean by this, is for example shown with key [7,9,8,7] in the example above. It fails at the second stage because of both 7>5 and 8>7. In reality we wouldn't know which of those two caused it to be blocked and making us unable to insert the key any further, but for the sake of this challenge we'll assume we know all of them if there are more than one.
    • Also note that for [8,2,1,0] we don't know anything about the fourth notch, because we couldn't insert it past the third.
    • Also, in reality the key maker could test some of the keys he makes after testing all existing ones to further decrease the amount of potential keys he has to make, so the number would be much lower than 72 in the example, but for the sake of this challenge we'll just determine the amount of all possible safe-keys for the lock based on the given existing keys once.
    • EDIT/NOTE: Even the intended [7,5,2,5] key wouldn't be able to insert all the way into its intended lock [7,5,2,5] in how the keys and locks interact in this challenge. This doesn't change the actual challenge nor test cases, but does make the backstory pretty flawed.. :/ Key [7,5,2,5] in lock [7,5,2,5] would act like this: first notch: 5<=7, so it fits; second notch: 5<=5 & 2<=7, so it fits; third notch: 5>2 (& 2<=5 & 5<=7), so it can't be inserted that far.
  • You can take the I/O in any reasonable format. Can be a list of strings or integers (note that leading 0s are possible for the keys) instead of the list of lists of digits I've used.
  • You can assume all keys of the input have the same length, which is \$1\leq L\leq10\$.
  • You are allowed to take the safe-key input in reversed order, and/or all keys in the list in reversed order. Make sure to mention this in your answer if you do!
  • You can assume the safe-key is not in the list of other keys.

General rules:

  • This is , so shortest answer in bytes wins.
    Don't let code-golf languages discourage you from posting answers with non-codegolfing languages. Try to come up with an as short as possible answer for 'any' programming language.
  • Standard rules apply for your answer with default I/O rules, so you are allowed to use STDIN/STDOUT, functions/method with the proper parameters and return-type, full programs. Your call.
  • Default Loopholes are forbidden.
  • If possible, please add a link with a test for your code (i.e. TIO).
  • Also, adding an explanation for your answer is highly recommended.

Test cases:

Input safe-key:   [7,5,2,5]
Input other keys: [[2,5,3,5],[3,7,5,8],[8,2,1,0],[6,3,6,6],[7,9,5,7],[0,2,2,1]]
Output:           27  ([[1,2,5,7],[1,3,5,7],[1,4,5,7],[2,2,5,7],[2,3,5,7],[2,4,5,7],[3,2,5,7],[3,3,5,7],[3,4,5,7],[4,2,5,7],[4,3,5,7],[4,4,5,7],[5,2,5,7],[5,3,5,7],[5,4,5,7],[6,2,5,7],[6,3,5,7],[6,4,5,7],[7,2,5,7],[7,3,5,7],[7,4,5,7],[8,2,5,7],[8,3,5,7],[8,4,5,7],[9,2,5,7],[9,3,5,7],[9,4,5,7]])
                      (==7, ==5, >=2&<5, >=1)

Input safe-key:   [3]
Input other keys: [[1],[6],[2],[9]]
Output:           4  ([[2],[3],[4],[5]])
                     (>=2&<6)

Input safe-key:   [4,2]
Input other keys: [[4,1],[3,7],[4,4],[2,0]]
Output:           9  ([[1,4],[1,5],[1,6],[2,4],[2,5],[2,6],[3,4],[3,5],[3,6]])
                     (>=1&<4, >=4&<7)

Input safe-key:   [9,8,7,5,3]
Input other keys: [[4,6,7,0,6],[5,5,0,7,9],[6,3,3,7,6],[9,1,0,3,1],[3,8,5,3,4],[3,6,4,9,7]]
Output:           48  ([[9,7,6,4,1],[9,7,6,4,2],[9,7,6,4,3],[9,7,6,5,1],[9,7,6,5,2],[9,7,6,5,3],[9,7,7,4,1],[9,7,7,4,2],[9,7,7,4,3],[9,7,7,5,1],[9,7,7,5,2],[9,7,7,5,3],[9,7,8,4,1],[9,7,8,4,2],[9,7,8,4,3],[9,7,8,5,1],[9,7,8,5,2],[9,7,8,5,3],[9,7,9,4,1],[9,7,9,4,2],[9,7,9,4,3],[9,7,9,5,1],[9,7,9,5,2],[9,7,9,5,3],[9,8,6,4,1],[9,8,6,4,2],[9,8,6,4,3],[9,8,6,5,1],[9,8,6,5,2],[9,8,6,5,3],[9,8,7,4,1],[9,8,7,4,2],[9,8,7,4,3],[9,8,7,5,1],[9,8,7,5,2],[9,8,7,5,3],[9,8,8,4,1],[9,8,8,4,2],[9,8,8,4,3],[9,8,8,5,1],[9,8,8,5,2],[9,8,8,5,3],[9,8,9,4,1],[9,8,9,4,2],[9,8,9,4,3],[9,8,9,5,1],[9,8,9,5,2],[9,8,9,5,3]])
                      (==9, >=7&<9, >=6, >=4&<6, >=1&<4)

Input safe-key:   [5,4]
Input other keys: [[6,3]]
Output:           30  ([[0,3],[0,4],[0,5],[1,3],[1,4],[1,5],[2,3],[2,4],[2,5],[3,3],[3,4],[3,5],[4,3],[4,4],[4,5],[5,3],[5,4],[5,5],[6,3],[6,4],[6,5],[7,3],[7,4],[7,5],[8,3],[8,4],[8,5],[9,3],[9,4],[9,5]])
                      (>=3&<6, n/a)
\$\endgroup\$
  • 2
    \$\begingroup\$ What would you be able to deduce by fitting a 3525 key into a 7525 lock and why? \$\endgroup\$ – Neil Oct 1 at 9:54
  • \$\begingroup\$ @Neil Hmm, your question made me realize that even the intended key 7525 wouldn't be able to fit into lock 7525, haha.. I will mention this in the rules. But to answer your question regarding key 3525: first notch: 5<=7, so it fits; second notch: 5<=5 & 2<=7, so it fits; third notch: 5>2 (& 2<=5 & 5<=7), so it can't be inserted that far. \$\endgroup\$ – Kevin Cruijssen Oct 1 at 10:11
  • \$\begingroup\$ Assume we'll know all notches when it doesn't fit, does that mean we also know all notches that would fit? Do we have to update the corresponding lower bounds? An example covering this would be safe-key: [5,2], other keys:[[4,3]]. \$\endgroup\$ – ovs Oct 1 at 11:39
  • \$\begingroup\$ @ovs Hmm. I think I may have overlooked the rule you're talking about and that's probably why we don't get the same results. This rule makes the challenge quite confusing and counterintuitive, IMO. \$\endgroup\$ – Arnauld Oct 1 at 11:46
  • \$\begingroup\$ Interesting challenge, but I don't think that's how keys work :P with your system you can only fit flat or descending height notches into holes.. \$\endgroup\$ – Kaddath Oct 1 at 11:55
9
\$\begingroup\$

Python 2, 196 bytes

l,o=input()
b=[[[0],[10]]for _ in l]
for k in o:
 R=range(len(l))
 for i in R:
	for x in 0,1:
	 for j in R[:i+1]:
		if(k[~i+j]>l[j])+x:b[j][~x]+=k[~i+j],;R*=x
for a,b in b:x*=min(b)-max(a)
print x

Try it online!

Commented:

l,o=input()                    # input: safe-key/lock, other keys
b=[[[0],[10]]for _ in l]       # for each column in the lock b stores:
                               #   a list of inclusive lower bounds and
                               #   a list of exclusive upper bounds
for k in o:                    # iterate over the other keys
  R=range(len(l))
  for i in R:                  #   each insertion-level i (0-indexed)
    for x in 0,1:              #     x=0: check if the key can't move there, update upper bounds
                               #     x=1: if the key fits, update lower bounds
                               #     this final value of x will be used later
      for j in R[:i+1]:        #     for each column:
        if(k[~i+j]>l[j])+x:    #       if the key doesn't fit at column j of the lock or x=1:
          b[j][~x]+=k[~i+j],   #         update the the right list of bounds
          R*=x                 #         and, if x=0, set R to the empty list
                               #          if this happens the 'for j in R[:i+1]'-loop will complete,
                               #          but will then never run again for the current key

for a,b in b:                  # for lower and upper bounds of each column
 x*=min(b)-max(a)              #   calculate the product in x (previously 1)
print x                        # print the result
| improve this answer | |
\$\endgroup\$

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.