Introdução

Para impedir que keyloggers roubem a senha de um usuário, um determinado sistema de conta bancária implementou a seguinte medida de segurança: somente determinados dígitos são solicitados a serem inseridos a cada vez.

Por exemplo, digamos que a senha do seu alvo seja 89097, o sistema pode solicitar que ele insira o segundo, quarto e quinto dígitos:

997

Ou pode solicitar que eles digitem o primeiro, terceiro e quinto dígitos:

807

Tudo o que você sabe é que seu destino inseriu os dígitos em ordem, mas você não sabe a que posição eles pertencem na senha real . Tudo que você sabe é que existem dois 9s, que devem vir antes das 7; e que 8 vem antes de 0 e 0 antes de 7. Portanto, existem seis senhas possíveis:

80997
89097
89907
98097
98907
99807

O keylogger no computador do seu alvo está coletando entradas de senha há meses, então vamos entrar!

Desafio

Dada uma lista de entradas de três dígitos, produza todas as senhas possíveis válidas para todas as entradas. Para reduzir a complexidade computacional e manter a quantidade de resultados possíveis baixa, a senha é garantida numérica e tem um tamanho fixo de 5. Os dígitos em todas as entradas estão em ordem: se for 123, o destino digitou 1 primeiro, depois 2, depois 3.

Exemplos de entrada / saída

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

Regras

• A entrada é garantida como não vazia.
• Os zeros à esquerda e à esquerda são importantes: 01234são diferentes 12340e 1234não decifram nenhuma senha. Pense em como as senhas reais funcionam!
• Aplicam- se as regras de E / S padrão .
• Sem brechas padrão .
• Isso é código-golfe , então a resposta mais curta em bytes vence. Idiomas não codegolfing são bem-vindos!

Python, 100 bytes

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

Experimente online!

Funciona em Python 2 e também em Python 3.

( 97 bytes em 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 bytes

žh5ãʒæIåP

Experimente online!

Explicação

ž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 bytes

Imprime os resultados com alert().

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

Experimente online!

Comentado

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 bytes

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

A abordagem óbvia da força bruta em Haskell: construiu uma lista de todas as senhas possíveis e mantém aquelas em que todos os elementos da lista de entrada estão na respectiva lista de subsequências.

Experimente online!

Edit: -1 byte graças a @xnor, -2 -4 bytes graças a @ H.PWiz

Gelatina , 11 bytes

9Żṗ5ŒPiⱮẠɗƇ

Experimente online!

Pitão, 11 bytes

f<QyT^s`MT5

Recebe a entrada como um conjunto de strings.
Experimente aqui

Explicação

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.

Ruby , 54 bytes

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

Experimente online!

Recebe a entrada como uma matriz de matrizes de caracteres.

Python 3 , 98 bytes

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']

Experimente online!

Recursivamente tenta criar cada string de número de cinco dígitos s, rastreando as subsequências que lainda restam para serem atingidas. Se tudo estiver vazio no final, imprime o resultado.

Python 3.8 (pré-lançamento) , 94 bytes

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)]

Experimente online!

Veja o poder das expressões de atribuição ! Usa o método daqui para verificar subseqüências.

Perl 5 -a , 80 bytes

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

Experimente online!

Retina , 53 bytes

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

Experimente online! Explicação:

~(`

Depois de executar o script, pegue o resultado como um novo script e execute-o também.

.$*

Insira em .*todos os lugares. Isso resulta em .*3.*2.*0.*que apenas precisamos 3.*2.*0, não que isso importe.

m`^
G`

Insira a G`no início de cada linha. Isso o transforma em um comando Retina Grep.

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

Prefixe mais dois comandos Retina. O script resultante será, portanto, mais ou menos assim:

K`

Limpe o buffer (que contém a entrada original).

5+

Repita 5 vezes ...

%`$

... anexa a cada linha ...

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

... o dígito 0, depois uma cópia da linha, o dígito 1, etc. até 9. Isso significa que, após os nloops, você terá todosn números de dígitos.

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

Filtre os números possíveis com base na entrada.

R , 80 bytes 82

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

Aqui está uma solução R básica usando regex. Escrever essa série aninhada de funções me fez perceber o quanto aprendi a apreciar o pacote magrittr!

Inicialmente não tinha lido as regras de entrada, então agora lê a partir de stdin (obrigado @KirillL).

Experimente online!

Ruby , 79 77 bytes

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

Experimente online!

Entrada é uma matriz de seqüências de caracteres.

Aqui está uma versão mais legível do mesmo código:

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 bytes

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;

ou

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;

receba entrada dos argumentos da linha de comando. Corra com -nrou experimente-os online .

J , 52 bytes

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

Experimente online!

Japonês, 21 bytes

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

Tente!

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 bytes graças a @Shaggy!

C # (compilador interativo do Visual C #) , 116 bytes

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);}}

Experimente online!

// 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);
  }
}

EDIT: corrigido um bug em que o mesmo personagem era contado mais de uma vez. Por exemplo, se 000foi registrada, a função usada para retornar todas as senhas que contêm uma única 0.

Limpo , 113 bytes

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

Experimente online!

K 67 bytes

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

K tem uma capacidade regex (muito) primitiva, então tentei uma abordagem diferente.

{...} define uma lambda. Use exemplo:{...}("320";"723";"730")

retorna ("37230";"72320";"73203";"73230")

• n é a lista de números inteiros no intervalo 0..9999 como cadeias de caracteres preenchidas com 0

  • _1e5 aplica o piso ao flutuador 1e5 (notação científica) -> gera o número inteiro 100000

  • !_1e5 gera lista inteira 0..99999

  • {..}'!_1e5 aplica lambda a cada valor em 0..99999

  • $x transformar argumento x (arg implícito) em string

  • -5$$xajuste à direita a string $ x para um campo de tamanho 5 (por exemplo, -5$$12gera" 12"

  • "0"^stringsubstitui espaços em branco pelo caractere "0" e "0"^-5$$12gera"00012"

• a é a lista de números inteiros no intervalo 0..31 como valores de 5 bits

  • !32 gerar valores 0..31

  • (5#2) repita 2 cinco vezes (lista 2 2 2 2 2)

  • (5#2)\:'!32 gera valores de 5 bits (duas bases de cinco vezes) para cada valor no intervalo 0..31

• filtramos os valores de a com exatamente 3. Que os valores são todas as combinações (lugares), onde padrão pode ser localizados: 11100 11010 11001 10110 10101 10011 01110 01101 01011 00111. Ex. para o padrão "abc", temos equivalência com regexsabc?? ab?c? ab??c a?bc? a?b?c a??bc ?abc? ?ab?c ?a?bc ??abc?

  • +\'a calcula a soma de cada representação binária (número de unidades)

  • 3=+\'a gera lista de booleanos (se cada valor em um tiver exatamente 3)

  • a@&3=+\'a lê como "a em que 3 = + \ 'a é verdadeiro"

• gerar lista de índices para locais anteriores: (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)e os possíveis valores inseridos para uma senha (x)

  • &:' lê como "where each", aplica-se à lista de números inteiros codificados em binário e calcula índices de cada bit de 1 bit

  • x@/: aplica a senha x a cada elem da lista de índices (gera todos os possíveis valores inseridos)

• Determina se todos os padrões estão localizados na lista de todos os possíveis valores inseridos

  • y é o argumento que representa a lista de padrões

  • y in\: lê como cada valor de y na lista à direita

  • &/é "e acabou". &/y in\:..retorna true se todos os padrões em y estiverem localizados na lista.

• finalmente, retorne cada string em n em todo índice que torne o lambda verdadeiro

  • n@&{..} lê como "n em onde lambda {..} retorna true"

C (GCC) 222 bytes

#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)}}

Experimente online

Código de chamada

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);
}

Resultado

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