Introducción

Para evitar que los keyloggers roben la contraseña de un usuario, cierto sistema de cuenta bancaria ha implementado la siguiente medida de seguridad: solo se solicita ingresar ciertos dígitos cada vez.

Por ejemplo, supongamos que la contraseña de su objetivo es 89097, el sistema puede solicitarles que ingresen el segundo, cuarto y quinto dígitos:

997

O podría pedirles que ingresen el 1er, 3er y 5to dígito:

807

Todo lo que sabe es que su objetivo ingresó los dígitos en orden, pero no sabe a qué posición pertenecen en la contraseña real . Todo lo que sabes es que hay dos 9, que deben venir antes del 7; y ese 8 viene antes que 0, y 0 antes que 7. Por lo tanto, hay seis posibles contraseñas:

80997
89097
89907
98097
98907
99807

El keylogger en la computadora de su objetivo ha estado recolectando entradas de contraseña durante meses, ¡así que hablemos!

Desafío

Dada una lista de entradas de tres dígitos, envíe todas las contraseñas posibles que sean válidas para todas las entradas. Para reducir la complejidad computacional y mantener baja la cantidad de resultados posibles, se garantiza que la contraseña sea numérica y tenga un tamaño fijo de 5. Los dígitos en cada entrada están en orden: si es 123, el objetivo escribió 1 primero, luego 2, luego 3.

Ejemplos de entrada / salida

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

Reglas

• La entrada está garantizada no vacía.
• Los ceros iniciales y finales importan: 01234es diferente 12340y 1234no descifra ninguna contraseña. ¡Piensa en cómo funcionan las contraseñas reales!
• Se aplican las reglas estándar de E / S.
• No hay lagunas estándar .
• Este es el código de golf , por lo que gana la respuesta más corta en bytes. ¡Los idiomas no codegolfing son bienvenidos!

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

Pruébalo en línea!

Funciona en Python 2 y Python 3.

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

Pruébalo en línea!

Explicación

ž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 los resultados con alert().

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

Pruébalo en línea!

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]

El enfoque obvio de la fuerza bruta en Haskell: construyó una lista de todas las contraseñas posibles y mantiene aquellas donde todos los elementos de la lista de entrada están en la lista respectiva de subsecuencias.

Pruébalo en línea!

Editar: -1 bytes gracias a @xnor, -2 -4 bytes gracias a @ H.PWiz

Jalea , 11 bytes

9Żṗ5ŒPiⱮẠɗƇ

Pruébalo en línea!

Pyth, 11 bytes

f<QyT^s`MT5

Toma la entrada como un conjunto de cadenas.
Pruébalo aquí

Explicación

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*'.*'}/}}}

Pruébalo en línea!

Toma la entrada como una matriz de matrices 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']

Pruébalo en línea!

Intenta recursivamente construir cada cadena de números de cinco dígitos s, rastreando las subsecuencias que laún quedan por tocar. Si todos están vacíos al final, imprime el resultado.

Python 3.8 (prelanzamiento) , 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)]

Pruébalo en línea!

¡Mira el poder de las expresiones de asignación ! Utiliza el método desde aquí para verificar subsecuencias.

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

Pruébalo en línea!

Retina , 53 bytes

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

Pruébalo en línea! Explicación:

~(`

Después de ejecutar el script, tome el resultado como un nuevo script y ejecútelo también.

.$*

Insertar en .*todas partes. Esto se traduce en que .*3.*2.*0.*aunque solo necesitamos 3.*2.*0, no es que importe.

m`^
G`

Inserte un G`al comienzo de cada línea. Esto lo convierte en un comando Retina Grep.

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

Prefije dos comandos Retina más. La secuencia de comandos resultante se verá así:

K`

Borre el búfer (que contiene la entrada original).

5+

Repite 5 veces ...

%`$

... anexar a cada línea ...

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

... el dígito 0, luego una copia de la línea, luego el dígito 1, etc. hasta 9. Esto significa que después de los nbucles tendrá todos los nnúmeros de dígitos.

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

Filtre los números posibles según la entrada.

R , 80 82 bytes

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

Aquí hay una solución base R usando regex. ¡Escribir esta serie anidada de funciones me hizo darme cuenta de cuánto aprendí a apreciar el paquete magrittr!

Inicialmente no había leído las reglas de entrada, por lo que ahora lee desde stdin (gracias @KirillL).

Pruébalo en línea!

Ruby , 79 77 bytes

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

Pruébalo en línea!

La entrada es una matriz de cadenas.

Aquí hay una versión más legible del mismo 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;

o

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;

tomar datos de los argumentos de la línea de comandos. Corre con ellos-nr o pruébalos en línea .

J , 52 bytes

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

Pruébalo en línea!

Japt, 21 bytes

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

¡Intentalo!

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 gracias a @Shaggy!

C # (compilador interactivo de 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);}}

Pruébalo en línea!

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

EDITAR: se corrigió un error en el que el mismo personaje se contaba más de una vez. Por ejemplo, si 000se registró, la función utilizada para devolver todas las contraseñas que contengan una sola 0.

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

Pruébalo en línea!

K 67 bytes

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

K tiene una capacidad de expresión regular muy (muy) primitiva, así que probé un enfoque diferente.

{...} define una lambda. Use ejemplo:{...}("320";"723";"730")

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

• n es la lista de enteros en el rango 0..9999 como cadenas con relleno 0

  • _1e5 aplica piso para flotar 1e5 (notación científica) -> genera un entero 100000

  • !_1e5 genera una lista de enteros 0..99999

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

  • $x transforma el argumento x (argumento implícito) en una cadena

  • -5$$xajuste a la derecha la cadena $ x a un campo de tamaño 5 (ej. -5$$12genera" 12"

  • "0"^stringreemplaza espacios en blanco con "0" char, por lo que "0"^-5$$12genera"00012"

• a es la lista de enteros en el rango 0..31 como valores de 5 bits

  • !32 generar valores 0..31

  • (5#2) repetir 2 cinco veces (lista 2 2 2 2 2)

  • (5#2)\:'!32 genera valores de 5 bits (2 bases cinco veces) para cada valor en el rango 0..31

• filtramos los valores de a con exactamente 3 unos. Que los valores son todas las combinaciones (lugares) donde se puede localizar patrón: 11100 11010 11001 10110 10101 10011 01110 01101 01011 00111. Ex. para el patrón "abc" tenemos equivalencia con expresiones regularesabc?? ab?c? ab??c a?bc? a?b?c a??bc ?abc? ?ab?c ?a?bc ??abc?

  • +\'a calcula la suma de cada representación binaria (número de unidades)

  • 3=+\'a genera una lista de booleanos (si cada valor en a tiene exactamente 3 unos)

  • a@&3=+\'a se lee como "a en donde 3 = + \ 'a es verdadero"

• generar una lista de índices para lugares 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)y los posibles valores ingresados ​​para una contraseña (x)

  • &:' se lee como "donde cada", se aplica a la lista de enteros codificados en binario y calcula los índices de cada 1 bit

  • x@/: aplica la contraseña x a cada elemento de la lista de índices (genera todos los valores ingresados ​​posibles)

• Determina si todos los patrones se encuentran en la lista de todos los valores posibles ingresados

  • y es el argumento que representa la lista de patrones

  • y in\: se lee como cada valor de y en la lista de la derecha

  • &/es "y más". &/y in\:..devuelve verdadero si todos los patrones en y se localizan en la lista.

• finalmente, devuelve cada cadena en n en cada índice que hace que lambda sea verdadero

  • n@&{..} se lee como "n en donde lambda {..} devuelve verdadero"

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

Pruébalo en línea

Código de llamada

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

Salida

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