Введение

Для предотвращения кражи паролем клавиатурных шпионов пароля пользователя в определенной системе банковских счетов реализована следующая мера безопасности: каждый раз вводятся только определенные цифры.

Например, скажем, пароль вашей цели - 89097система может предложить им ввести 2-ю, 4-ю и 5-ю цифры

997

Или это может побудить их ввести 1-ю, 3-ю и 5-ю цифру:

807

Все, что вы знаете, это то, что ваша цель ввела цифры по порядку, но вы не знаете, к какой позиции они принадлежат в действительном пароле . Все, что вы знаете, это две 9, которые должны предшествовать 7; и что 8 предшествует 0, а 0 - 7. Следовательно, существует шесть возможных паролей:

80997
89097
89907
98097
98907
99807

Кейлоггер на компьютере вашей целевой системы собирал пароли уже несколько месяцев, так что давайте взломать!

Вызов

Учитывая список трехзначных входов, выведите все возможные пароли, которые действительны для всех входов. Чтобы уменьшить сложность вычислений и сохранить количество возможных результатов на низком уровне, пароль гарантированно должен быть числовым и иметь фиксированный размер 5. Цифры в каждом входе располагаются по порядку: если это 123, цель сначала набрала 1, затем 2, затем 3.

Примеры ввода / вывода

|----------------------|--------------------------------------------|
|         Input        |                   Output                   |
|----------------------|--------------------------------------------|
| [320, 723, 730]      | [37230, 72320, 73203, 73230]               |
| [374, 842]           | [37842, 38742, 83742]                      |
| [010, 103, 301]      | [30103]                                    |
| [123, 124, 125, 235] | [12345, 12354, 12435]                      |
| [239, 944]           | [23944]                                    |
| [111, 120]           | [11201, 11120, 11210, 12011, 12110, 12101] |
| [456, 789]           | []                                         |
| [756, 586]           | [07586, 17586, 27586, 37586, 47586, 57586, 57856, 58756, 67586, 70586, 71586, 72586, 73586, 74586, 75086, 75186, 75286, 75386, 75486, 75586, 75686, 75786, 75806, 75816, 75826, 75836, 75846, 75856, 75860, 75861, 75862, 75863, 75864, 75865, 75866, 75867, 75868, 75869, 75876, 75886, 75896, 75986, 76586, 77586, 78586, 79586, 87586, 97586] |
| [123]                | [00123, 01023, 01123, 01203, 01213, 01223, 01230, 01231, 01232, 01233, 01234, 01235, 01236, 01237, 01238, 01239, 01243, 01253, 01263, 01273, 01283, 01293, 01323, 01423, 01523, 01623, 01723, 01823, 01923, 02123, 03123, 04123, 05123, 06123, 07123, 08123, 09123, 10023, 10123, 10203, 10213, 10223, 10230, 10231, 10232, 10233, 10234, 10235, 10236, 10237, 10238, 10239, 10243, 10253, 10263, 10273, 10283, 10293, 10323, 10423, 10523, 10623, 10723, 10823, 10923, 11023, 11123, 11203, 11213, 11223, 11230, 11231, 11232, 11233, 11234, 11235, 11236, 11237, 11238, 11239, 11243, 11253, 11263, 11273, 11283, 11293, 11323, 11423, 11523, 11623, 11723, 11823, 11923, 12003, 12013, 12023, 12030, 12031, 12032, 12033, 12034, 12035, 12036, 12037, 12038, 12039, 12043, 12053, 12063, 12073, 12083, 12093, 12103, 12113, 12123, 12130, 12131, 12132, 12133, 12134, 12135, 12136, 12137, 12138, 12139, 12143, 12153, 12163, 12173, 12183, 12193, 12203, 12213, 12223, 12230, 12231, 12232, 12233, 12234, 12235, 12236, 12237, 12238, 12239, 12243, 12253, 12263, 12273, 12283, 12293, 12300, 12301, 12302, 12303, 12304, 12305, 12306, 12307, 12308, 12309, 12310, 12311, 12312, 12313, 12314, 12315, 12316, 12317, 12318, 12319, 12320, 12321, 12322, 12323, 12324, 12325, 12326, 12327, 12328, 12329, 12330, 12331, 12332, 12333, 12334, 12335, 12336, 12337, 12338, 12339, 12340, 12341, 12342, 12343, 12344, 12345, 12346, 12347, 12348, 12349, 12350, 12351, 12352, 12353, 12354, 12355, 12356, 12357, 12358, 12359, 12360, 12361, 12362, 12363, 12364, 12365, 12366, 12367, 12368, 12369, 12370, 12371, 12372, 12373, 12374, 12375, 12376, 12377, 12378, 12379, 12380, 12381, 12382, 12383, 12384, 12385, 12386, 12387, 12388, 12389, 12390, 12391, 12392, 12393, 12394, 12395, 12396, 12397, 12398, 12399, 12403, 12413, 12423, 12430, 12431, 12432, 12433, 12434, 12435, 12436, 12437, 12438, 12439, 12443, 12453, 12463, 12473, 12483, 12493, 12503, 12513, 12523, 12530, 12531, 12532, 12533, 12534, 12535, 12536, 12537, 12538, 12539, 12543, 12553, 12563, 12573, 12583, 12593, 12603, 12613, 12623, 12630, 12631, 12632, 12633, 12634, 12635, 12636, 12637, 12638, 12639, 12643, 12653, 12663, 12673, 12683, 12693, 12703, 12713, 12723, 12730, 12731, 12732, 12733, 12734, 12735, 12736, 12737, 12738, 12739, 12743, 12753, 12763, 12773, 12783, 12793, 12803, 12813, 12823, 12830, 12831, 12832, 12833, 12834, 12835, 12836, 12837, 12838, 12839, 12843, 12853, 12863, 12873, 12883, 12893, 12903, 12913, 12923, 12930, 12931, 12932, 12933, 12934, 12935, 12936, 12937, 12938, 12939, 12943, 12953, 12963, 12973, 12983, 12993, 13023, 13123, 13203, 13213, 13223, 13230, 13231, 13232, 13233, 13234, 13235, 13236, 13237, 13238, 13239, 13243, 13253, 13263, 13273, 13283, 13293, 13323, 13423, 13523, 13623, 13723, 13823, 13923, 14023, 14123, 14203, 14213, 14223, 14230, 14231, 14232, 14233, 14234, 14235, 14236, 14237, 14238, 14239, 14243, 14253, 14263, 14273, 14283, 14293, 14323, 14423, 14523, 14623, 14723, 14823, 14923, 15023, 15123, 15203, 15213, 15223, 15230, 15231, 15232, 15233, 15234, 15235, 15236, 15237, 15238, 15239, 15243, 15253, 15263, 15273, 15283, 15293, 15323, 15423, 15523, 15623, 15723, 15823, 15923, 16023, 16123, 16203, 16213, 16223, 16230, 16231, 16232, 16233, 16234, 16235, 16236, 16237, 16238, 16239, 16243, 16253, 16263, 16273, 16283, 16293, 16323, 16423, 16523, 16623, 16723, 16823, 16923, 17023, 17123, 17203, 17213, 17223, 17230, 17231, 17232, 17233, 17234, 17235, 17236, 17237, 17238, 17239, 17243, 17253, 17263, 17273, 17283, 17293, 17323, 17423, 17523, 17623, 17723, 17823, 17923, 18023, 18123, 18203, 18213, 18223, 18230, 18231, 18232, 18233, 18234, 18235, 18236, 18237, 18238, 18239, 18243, 18253, 18263, 18273, 18283, 18293, 18323, 18423, 18523, 18623, 18723, 18823, 18923, 19023, 19123, 19203, 19213, 19223, 19230, 19231, 19232, 19233, 19234, 19235, 19236, 19237, 19238, 19239, 19243, 19253, 19263, 19273, 19283, 19293, 19323, 19423, 19523, 19623, 19723, 19823, 19923, 20123, 21023, 21123, 21203, 21213, 21223, 21230, 21231, 21232, 21233, 21234, 21235, 21236, 21237, 21238, 21239, 21243, 21253, 21263, 21273, 21283, 21293, 21323, 21423, 21523, 21623, 21723, 21823, 21923, 22123, 23123, 24123, 25123, 26123, 27123, 28123, 29123, 30123, 31023, 31123, 31203, 31213, 31223, 31230, 31231, 31232, 31233, 31234, 31235, 31236, 31237, 31238, 31239, 31243, 31253, 31263, 31273, 31283, 31293, 31323, 31423, 31523, 31623, 31723, 31823, 31923, 32123, 33123, 34123, 35123, 36123, 37123, 38123, 39123, 40123, 41023, 41123, 41203, 41213, 41223, 41230, 41231, 41232, 41233, 41234, 41235, 41236, 41237, 41238, 41239, 41243, 41253, 41263, 41273, 41283, 41293, 41323, 41423, 41523, 41623, 41723, 41823, 41923, 42123, 43123, 44123, 45123, 46123, 47123, 48123, 49123, 50123, 51023, 51123, 51203, 51213, 51223, 51230, 51231, 51232, 51233, 51234, 51235, 51236, 51237, 51238, 51239, 51243, 51253, 51263, 51273, 51283, 51293, 51323, 51423, 51523, 51623, 51723, 51823, 51923, 52123, 53123, 54123, 55123, 56123, 57123, 58123, 59123, 60123, 61023, 61123, 61203, 61213, 61223, 61230, 61231, 61232, 61233, 61234, 61235, 61236, 61237, 61238, 61239, 61243, 61253, 61263, 61273, 61283, 61293, 61323, 61423, 61523, 61623, 61723, 61823, 61923, 62123, 63123, 64123, 65123, 66123, 67123, 68123, 69123, 70123, 71023, 71123, 71203, 71213, 71223, 71230, 71231, 71232, 71233, 71234, 71235, 71236, 71237, 71238, 71239, 71243, 71253, 71263, 71273, 71283, 71293, 71323, 71423, 71523, 71623, 71723, 71823, 71923, 72123, 73123, 74123, 75123, 76123, 77123, 78123, 79123, 80123, 81023, 81123, 81203, 81213, 81223, 81230, 81231, 81232, 81233, 81234, 81235, 81236, 81237, 81238, 81239, 81243, 81253, 81263, 81273, 81283, 81293, 81323, 81423, 81523, 81623, 81723, 81823, 81923, 82123, 83123, 84123, 85123, 86123, 87123, 88123, 89123, 90123, 91023, 91123, 91203, 91213, 91223, 91230, 91231, 91232, 91233, 91234, 91235, 91236, 91237, 91238, 91239, 91243, 91253, 91263, 91273, 91283, 91293, 91323, 91423, 91523, 91623, 91723, 91823, 91923, 92123, 93123, 94123, 95123, 96123, 97123, 98123, 99123] |
|----------------------|--------------------------------------------|

правила

• Ввод гарантированно не пустой.
• Начальные и конечные нули имеют значение: 01234отличается от пароля 12340и 1234не взламывает его. Подумайте, как работают настоящие пароли!
• Стандартные правила ввода / выводаПрименяются .
• Нет стандартных лазеек .
• Это код-гольф , поэтому выигрывает самый короткий ответ в байтах. Языки без кодекса в гольф приветствуются!

Python, 100 байт

lambda e,d='%05d':[d%i for i in range(10**5)if all(re.search('.*'.join(x),d%i)for x in e)]
import re

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

Работает в Python 2, а также Python 3.

( 97 байт в Python 3.8 :)

lambda e:[p for i in range(10**5)if all(re.search('.*'.join(x),p:='%05d'%i)for x in e)]
import re

05AB1E , 11 9 байтов

žh5ãʒæIåP

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

объяснение

žh          # push 0123456789
  5ã        # 5 times cartesian product
    ʒ       # filter, keep only values are true under:
     æ      # powerset of value
      Iå    # check if each of the input values are in this list
        P   # product

JavaScript (ES6), 88 байт

Печатает результаты с alert().

a=>{for(k=n=1e5;n--;)a.every(x=>(s=([k]+n).slice(-5)).match([...x].join`.*`))&&alert(s)}

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

комментарии

a => {                    // a[] = input array of 3-character strings
  for(k = n = 1e5; n--;)  // initialize k to 100000; for n = 99999 to 0:
    a.every(x =>          // for each string x = 'XYZ' in a[]:
      ( s =               //   define s as the concatenation of
          ([k] + n)       //   '100000' and n; e.g. '100000' + 1337 -> '1000001337'
          .slice(-5)      //   keep the last 5 digits; e.g. '01337'
      ).match(            //   test whether this string is matching
        [...x].join`.*`   //   the pattern /X.*Y.*Z/
      )                   //
    ) &&                  // end of every(); if all tests were successful:
      alert(s)            //   output s
}                         //

Haskell, 81 80 78 76 байтов

f x=[p|p<-mapM(:['1'..'9'])"00000",all(`elem`(concat.words<$>mapM(:" ")p))x]

Очевидный подход грубой силы в Haskell: строит список всех возможных паролей и сохраняет те, где все элементы из входного списка находятся в соответствующем списке подпоследовательностей.

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

Изменить: -1 байт благодаря @xnor, -2 -4 байта благодаря @ H.PWiz

Желе , 11 байт

9Żṗ5ŒPiⱮẠɗƇ

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

Pyth, 11 байт

f<QyT^s`MT5

Принимает ввод как набор строк.
Попробуй здесь

объяснение

f<QyT^s`MT5
      s`MT      Take the digits as a string.
     ^    5     Take the Cartesian product with itself 5 times.
f   T           Filter the ones...
 <Qy            ... where the input is a subset of the power set.

Рубин , 54 байта

->a{(?0*5..?9*5).select{|x|a.all?{|y|x=~/#{y*'.*'}/}}}

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

Принимает ввод в виде массива символьных массивов.

Python 3 , 98 байт

f=lambda l,s='':any(l)or print(s)if s[4:]else[f([x[x[:1]==c:]for x in l],s+c)for c in'0123456789']

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

Рекурсивно пытается встраивать каждую пятизначную числовую строку s, отслеживая подпоследовательности, которые lеще предстоит выполнить. Если к концу все пусто, выводится результат.

Python 3.8 (предварительная версия) , 94 байта

lambda l:[s for n in range(10**5)if all(''in[x:=x[x[:1]==c:]for c in(s:='%05d'%n)]for x in l)]

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

Вот сила выражений присваивания ! Здесь используется метод для проверки подпоследовательностей.

Perl 5 -a , 80 байт

map{s||($t=0)x(5-y///c)|e;for$b(map s//.*/gr,@F){/$b/&&$t++}$t==@F&&say}0..99999

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

Сетчатка , 53 байта

~(`
.$*
m`^
G`
^
K`¶5+%`$$¶0"1"2"3"4"5"6"7"8"9¶
"
$$"

Попробуйте онлайн! Объяснение:

~(`

После выполнения сценария возьмите результат как новый сценарий и выполните его тоже.

.$*

Вставить .*везде. Это приводит к тому, .*3.*2.*0.*что нам нужно только то 3.*2.*0, что не имеет значения.

m`^
G`

Вставьте G`в начале каждой строки. Это превращает его в команду Retina Grep.

^
K`¶5+%`$$¶0"1"2"3"4"5"6"7"8"9¶
"
$$"

Префикс еще две команды Retina. Таким образом, полученный скрипт будет выглядеть примерно так:

K`

Очистите буфер (который содержит исходный ввод).

5+

Повторите 5 раз ...

%`$

... добавить к каждой строке ...

0$"1$"2$"3$"4$"5$"6$"7$"8$"9

... цифра 0, затем копия строки, затем цифра 1и т. д. до 9. Это означает, что после nциклов у вас будут все n-значные числа.

G`.*3.*2.*0.*
G`.*7.*2.*3.*
G`.*7.*3.*0.*

Отфильтруйте возможные числа на основе ввода.

R , 80 82 байта

Reduce(intersect,lapply(gsub("",".*",scan(,"")),grep,sprintf("%05d",0:99999),v=T))

Вот базовое решение R с использованием регулярных выражений. Написание этой вложенной серии функций заставило меня понять, насколько я научился ценить пакет magrittr!

Изначально не читал правила ввода, поэтому теперь читает из stdin (спасибо @KirillL).

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

Рубин , 79 77 байт

->x{(0...1e5).map{|i|'%05d'%i}.select{|i|x.all?{|c|i=~/#{c.gsub('','.*')}/}}}

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

Ввод представляет собой массив строк.

Вот более читаемая версия того же кода:

def f(codes)
  (0...10**5).map{|i| '%05d'%i}.select do |i|
    codes.all? do |code|
      i =~ Regexp.new(code.chars.join('.*'))
    end
  end
end

PHP 128 байт

for(;$i++<1e5;$k>$argc||print$s)for($k=0;$n=$argv[++$k];)preg_match("/$n[0].*$n[1].*$n[2]/",$s=sprintf("%05d
",$i-1))||$k=$argc;

или же

for(;$i<1e5;$i+=$k<$argc||print$s)for($k=0;$n=$argv[++$k];)if(!preg_match("/$n[0].*$n[1].*$n[2]/",$s=sprintf("%05d
",$i)))break;

принимать входные данные из аргументов командной строки. Запустите -nrили попробуйте их онлайн .

J , 52 байта

(>,{;^:4~i.10)([#~]*/@e."2((#~3=+/"1)#:i.32)#"_ 1[)]

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

Japt, 21 байт

1e5o ù'0 f@e_XèZË+".*

Попробуй!

1e5o ù'0 f@e_XèZË+".*    # full program

1e5o                     # generate numbers under 100k
     ù'0                 # left pad with 0's
         f@              # filter array
           e_            # check every element of input array
             Xè          # X is the number to be tested.
                         # test it against a regex.
               ZË+".*    # the regex is an element from the input array
                         # with wildcards injected between each character

-2 байта благодаря @Shaggy!

C # (интерактивный компилятор Visual C #) , 116 байт

x=>{for(int i=0;i<1e5;){var s=$"{i++:D5}";if(x.All(t=>t.Aggregate(-6,(a,c)=>s.IndexOf(c,a<0?a+6:a+1))>0))Print(s);}}

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

// x: input list of strings
x=>{
  // generate all numbers under 100k
  for(int i=0;i<1e5;){
    // convert the current number to
    // a 5 digit string padded with 0's
    var s=$"{i++:D5}";
    // test all inputs against the 5 digit
    // string using an aggregate.
    // each step of the aggregate gets
    // the index of the next occurrence
    // of the current character starting
    // at the previously found character.
    // a negative index indicates error.
    if(x.All(t=>t
             .Aggregate(-6,(a,c)=>
               s.IndexOf(c,a<0?a+6:a+1)
             )>0))
      // output to STDOUT
      Print(s);
  }
}

РЕДАКТИРОВАТЬ: исправлена ​​ошибка, когда один и тот же символ был посчитан более одного раза. Например, если 000было зарегистрировано, функция используется для возврата всех паролей, содержащих один 0.

Чисто , 113 байт

import StdEnv,Data.List
$l=[s\\s<-iter 5(\p=[[c:e]\\e<-p,c<-['0'..'9']])[[]]|all(flip any(subsequences s)o(==))l]

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

К 67 байт

{n@&{&/y in\:x@/:&:'a@&3=+/'a:(5#2)\:'!32}[;x]'n:{"0"^-5$$x}'!_1e5}

У K есть (очень) примитивная возможность регулярных выражений, поэтому я попробовал другой подход.

{...} определяет лямбду. Пример использования:{...}("320";"723";"730")

возвращается ("37230";"72320";"73203";"73230")

• n список целых чисел в диапазоне 0..9999 в виде строк с 0 дополнениями

  • _1e5 применяет слово к числу с плавающей точкой 1e5 (научное обозначение) -> генерирует целое число 100000

  • !_1e5 генерирует целочисленный список 0..99999

  • {..}'!_1e5 применяет лямбду к каждому значению в 0..99999

  • $x преобразовать аргумент x (неявный аргумент) в строку

  • -5$$xОтрегулируйте правую строку $ x в поле размером 5 (например, -5$$12генерирует" 12"

  • "0"^stringзаменяет пробелы символом "0", поэтому "0"^-5$$12генерирует"00012"

• a список целых чисел в диапазоне 0..31 в виде 5-битных значений

  • !32 генерировать значения 0..31

  • (5#2) повторить 2 пять раз (список 2 2 2 2 2)

  • (5#2)\:'!32 генерирует 5-битные значения (2-базовые пять раз) для каждого значения в диапазоне 0..31

• мы отфильтровываем значения с ровно 3. Это значение все комбинации (места) , где рисунок может быть расположены по адресу: 11100 11010 11001 10110 10101 10011 01110 01101 01011 00111. Ex. для шаблона "abc" мы имеем эквивалентность с регулярными выражениямиabc?? ab?c? ab??c a?bc? a?b?c a??bc ?abc? ?ab?c ?a?bc ??abc?

  • +\'a вычисляет сумму каждого двоичного представления (количество единиц)

  • 3=+\'a генерирует список логических значений (если каждое значение в a имеет ровно 3)

  • a@&3=+\'a читается как «а, где 3 = + \ 'истинно"

• создать список индексов для предыдущих мест: (0 1 2; 0 1 3; 0 1 4; 0 2 3; 0 2 4; 0 3 4; 1 2 3; 1 2 4; 1 3 4; 2 3 4)и возможные введенные значения для пароля (x)

  • &:' читается как «где каждый», относится к списку двоично-целых чисел и вычисляет индексы каждого 1-битного

  • x@/: применяет пароль x к каждому элементу списка индексов (генерирует все возможные введенные значения)

• Определяет, находятся ли все шаблоны в списке всех возможных введенных значений.

  • y это арг, который представляет список шаблонов

  • y in\: читается как каждое значение у в списке справа

  • &/"и окончен". &/y in\:..возвращает true, если все шаблоны в y находятся в списке ..

• наконец, возвращайте каждую строку в n в каждом индексе, который делает лямбду истинной

  • n@&{..} читается как "n там, где лямбда {..} возвращает true"

C (GCC) 222 байта

#define C(p)*f-p?:++f;
#define I(x,y)x<10?:++y,x%=10;
a,b,c,d,e;f(int**H){for(;a<10;){int**h=H,*f,g=0;for(h=H;*h;){f=*h;C(a)C(b)C(c)C(d)C(e)f>*h+++2?:(g=1);}g?:printf("%d%d%d%d%d,",a,b,c,d,e);++e;I(e,d)I(d,c)I(c,b)I(b,a)}}

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

Телефонный код

int main() {
  int hint1[5] = {9,9,7,-1,-1};
  int hint2[5] = {8,0,7,-1,-1};
  int* hints[3] = {hint1,hint2,0};
  f(hints);
}

Выход

80997,89097,89907,98097,98907,99807,