Codegolf — Количество Потенциальных Ключей, Подходящих К Замку

Введение:

Вы изготовитель ключей и хотите получить доступ к чему-либо из сейфа с замком. К сожалению, ключ от этого замка утерян, поэтому вам придется сделать новый. У вас есть доступ к множеству пустые клавиши, к которому можно добавить выемки, чтобы превратить его в настоящие ключи. У вас также есть множество ключей с уже нанесенными насечками.

Испытание:

Дан список цифр (все одинаковой длины), представляющий список ключей с выемками, которые у вас лежат, где каждая цифра представляет высоту «столбца» выемки, а также целочисленный список цифр ключа, который вы хотите сделать замок сейфа, выведите количество ключей, которое вам потенциально нужно изготовить, чтобы попытаться открыть замок.

Как бы мы это определили? Вот пример:
Допустим, ключ, который должен входить в замок,

 
 
 
 
 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)
 
 
 
 
 

Вот как далеко мы можем вставить каждый ключ в замок:

Возьмем первый ключ 5<=5 & 2<=7 as more in-depth example:

Вот визуальное представление, чтобы, возможно, лучше понять, где синие ячейки являются ключевыми. [7,5,2,5] , the yellow parts is the key that's supposed to go into the lock [7,5,2,5] , а черные части — это сам замок:

Что касается остальных ключей:

Объединив все это:

Оставляя все потенциальные ключи от сейфа (27 итого, что и является нашим результатом):

Правила конкурса:

• Предположим, мы знаем все зазубрины, когда замок не подходит, даже если на самом деле замок будет черным ящиком. Давайте просто предположим, что изготовитель ключей очень опытен и может чувствовать такие вещи. То, что я имею в виду, показано, например, с помощью ключа [8,2,1,0] in the example above. It fails at the second stage because of both 8>7 и 7>5 . 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.
  • Также обратите внимание, что для [7,9,8,7] we don't know anything about the fourth notch, because we couldn't insert it past the third.
  • Кроме того, в действительности изготовитель ключей может протестировать некоторые из ключей, которые он делает, после тестирования всех существующих, чтобы еще больше уменьшить количество потенциальных ключей, которые ему нужно изготовить, поэтому их число будет намного меньше, чем [[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]] 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.
  • РЕДАКТИРОВАТЬ/ПРИМЕЧАНИЕ: Даже предполагаемое # First notch: ==7 (>=7 & <8) # Second notch: ==5 (>=5 & <6) # Third notch: >=2 & <5 # Fourth notch: >=1 key wouldn't be able to insert all the way into its intended lock [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 в том, как ключи и замки взаимодействуют в этом задании. Это не меняет ни сути задачи, ни тестовых примеров, но делает предысторию довольно ошибочной. :/ Ключ [7,5,2,5] in lock [2,5,3,5] будет действовать так: первая отметка: [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 , so it fits; second notch: [2,5,3,5] , так что подходит; третья отметка: [[2,5,3,5],[3,7,5,8],[8,2,1,0],[6,3,6,6],[7,9,5,7],[0,2,2,1]] , so it can't be inserted that far.
• Вы можете использовать ввод-вывод в любом разумном формате. Может быть списком строк или целых чисел (обратите внимание, что для ключей возможны ведущие 0) вместо списка списков цифр, которые я использовал.
• Вы можете предположить, что все ключи ввода имеют одинаковую длину, которая равна \$1\leq L\leq10\$.
• Вам разрешено вводить безопасный ключ в обратном порядке и/или все ключи в списке в обратном порядке. Если да, обязательно укажите это в своем ответе!
• Вы можете предположить, что безопасного ключа нет в списке других ключей.

Общие правила:

• Это , поэтому побеждает самый короткий ответ в байтах.
  Не позволяйте языкам код-гольфа отговаривать вас от публикации ответов на языках, не связанных с код-гольфом. Постарайтесь дать как можно более короткий ответ для «любого» языка программирования.
• Применяются стандартные правила за ваш ответ с правила ввода-вывода по умолчанию, поэтому вам разрешено использовать STDIN/STDOUT, функции/методы с соответствующими параметрами и типом возвращаемого значения, полные программы. Ваш звонок.
• Лазейки по умолчанию запрещены.
• Если возможно, добавьте ссылку с тестом вашего кода (т. ТИО).
• Кроме того, настоятельно рекомендуется добавить объяснение вашего ответа.

Тестовые случаи:

#код-гольф #код-гольф #число #целое число

Питон 2, 196 байт

 
 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
 
 

Попробуйте онлайн!

Прокомментировал: