introduction

Afin d'éviter que les enregistreurs de frappe ne volent le mot de passe d'un utilisateur, un système de compte bancaire donné a implémenté la mesure de sécurité suivante: seuls certains chiffres doivent être entrés à chaque fois.

Par exemple, supposons que le mot de passe de votre cible soit 89097, le système peut lui demander de saisir les 2ème, 4ème et 5ème chiffres:

997

Cela pourrait aussi les inciter à entrer les premier, troisième et cinquième chiffres:

807

Tout ce que vous savez, c'est que votre cible a entré les chiffres dans l'ordre, mais vous ne savez pas à quelle position ils appartiennent dans le mot de passe actuel . Tout ce que vous savez, c'est qu'il y a deux 9, qui doivent précéder 7; et que 8 vient avant 0 et 0 avant 7. Il y a donc six mots de passe possibles:

80997
89097
89907
98097
98907
99807

Le keylogger de l'ordinateur de votre cible collecte des mots de passe depuis des mois, alors piratons!

Défi

Avec une liste d'entrées à trois chiffres, indiquez tous les mots de passe possibles valables pour toutes les entrées. Afin de réduire la complexité des calculs et de limiter le nombre de résultats possibles, il est garanti que le mot de passe est numérique et que sa taille est fixée à 5. Les chiffres de chaque entrée sont dans l'ordre: si c'est 123, la cible tapée 1 en premier, puis 2, puis 3.

Exemples d'entrée / sortie

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

Règles

• L'entrée est garantie non vide.
• Les zéros au début et à la fin importent: 01234est différent de 12340, et 1234ne déchiffre aucun mot de passe. Pensez à la façon dont les vrais mots de passe fonctionnent!
• Les règles d'E / S standard s'appliquent.
• Aucune échappatoire standard .
• C'est du code-golf , donc la réponse la plus courte en octets est gagnante. Les langues ne faisant pas partie du code sont les bienvenues!

Python, 100 octets

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

Essayez-le en ligne!

Fonctionne à la fois en Python 2 et en Python 3.

( 97 octets 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 octets

žh5ãʒæIåP

Essayez-le en ligne!

Explication

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

Imprime les résultats avec alert().

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

Essayez-le en ligne!

Commenté

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 octets

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

L’approche évidente de la force brute en Haskell: a créé une liste de tous les mots de passe possibles et conserve ceux où tous les éléments de la liste des entrées sont dans la liste respective des sous-séquences.

Essayez-le en ligne!

Edit: -1 octet grâce à @xnor, -2 -4 octets grâce à @ H.PWiz

Gelée , 11 octets

9Żṗ5ŒPiⱮẠɗƇ

Essayez-le en ligne!

Pyth, 11 octets

f<QyT^s`MT5

Prend l'entrée comme un ensemble de chaînes.
Essayez-le ici

Explication

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 octets

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

Essayez-le en ligne!

Prend la saisie comme un tableau de tableaux de caractères.

Python 3 , 98 octets

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

Essayez-le en ligne!

Essaie de manière récursive d’édifier chaque chaîne numérique à cinq chiffres s, en effectuant le suivi des sous-séquences lrestantes. Si tous sont vides à la fin, affiche le résultat.

Python 3.8 (version préliminaire) , 94 octets

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

Essayez-le en ligne!

Voyez le pouvoir des expressions d'affectation ! Utilise la méthode à partir d’ici pour vérifier les sous-séquences.

Perl 5 -a , 80 octets

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

Essayez-le en ligne!

Retina , 53 octets

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

Essayez-le en ligne! Explication:

~(`

Après avoir exécuté le script, prenez le résultat comme un nouveau script et exécutez-le également.

.$*

Insérer .*partout. Il en résulte .*3.*2.*0.*bien que nous ayons seulement besoin 3.*2.*0, pas que cela compte.

m`^
G`

Insérer un G` au début de chaque ligne. Cela le transforme en une commande Retina Grep.

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

Préfixez deux autres commandes Retina. Le script résultant ressemblera donc à ceci:

K`

Efface le tampon (qui contient l’entrée originale).

5+

Répétez 5 fois ...

%`$

... ajouter à chaque ligne ...

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

... le chiffre 0, puis une copie de la ligne, puis le chiffre 1, etc. jusqu'à 9. Cela signifie que, après les nboucles, vous aurez tous les nnuméros à chiffres.

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

Filtrez les nombres possibles en fonction de l'entrée.

R , 80 82 octets

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

Voici une solution de base R utilisant regex. L'écriture de cette série imbriquée de fonctions m'a permis de réaliser à quel point j'ai appris à apprécier le paquet magrittr!

Initialement, je n'avais pas lu les règles sur les entrées, aussi lit-il maintenant à partir de stdin (merci @KirillL).

Essayez-le en ligne!

Ruby , 79 77 octets

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

Essayez-le en ligne!

L'entrée est un tableau de chaînes.

Voici une version plus lisible du même code:

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

128 octets PHP

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;

prendre en compte les arguments de la ligne de commande. Courez avec -nrou essayez-les en ligne .

J , 52 octets

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

Essayez-le en ligne!

Japt, 21 octets

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

Essayez le!

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 octets grâce à @Shaggy!

C # (compilateur interactif Visual C #) , 116 octets

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

Essayez-le en ligne!

// 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: correction d'un bug où le même personnage était compté plus d'une fois. Par exemple, si 000était connecté, la fonction permettait de renvoyer tous les mots de passe contenant un seul 0.

Propre , 113 octets

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

Essayez-le en ligne!

K 67 octets

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

K a une capacité de regex (très) primitive, j'ai donc essayé une approche différente.

{...} définit un lambda. Exemple d'utilisation:{...}("320";"723";"730")

résultats ("37230";"72320";"73203";"73230")

• n est la liste des entiers compris entre 0 et 9999 sous forme de chaînes complétées par 0

  • _1e5 applique floor to float 1e5 (notation scientifique) -> génère un entier 100000

  • !_1e5 génère une liste d'entiers 0..99999

  • {..}'!_1e5 applique lambda à chaque valeur en 0..99999

  • $x transformer l'argument x (arg implicit) en chaîne

  • -5$$xdroit d' ajuster la chaîne x $ à un champ de taille 5 (ex. -5$$12génère" 12"

  • "0"^stringremplace les blancs par "0", donc "0"^-5$$12génère"00012"

• a est la liste des entiers dans la plage 0..31 sous forme de valeurs à 5 bits

  • !32 générer des valeurs 0..31

  • (5#2) répéter 2 cinq fois (lister 2 2 2 2 2)

  • (5#2)\:'!32 génère des valeurs de 5 bits (deux bases cinq fois) pour chaque valeur comprise dans la plage 0..31

• nous filtrons les valeurs de a avec exactement 3 unités. Que les valeurs sont toutes les combinaisons (places) où se trouve modèle: 11100 11010 11001 10110 10101 10011 01110 01101 01011 00111. Ex. pour le modèle "abc" nous avons une équivalence avec les expressions rationnellesabc?? ab?c? ab??c a?bc? a?b?c a??bc ?abc? ?ab?c ?a?bc ??abc?

  • +\'a calcule la somme de chaque représentation binaire (nombre d'unités)

  • 3=+\'a génère une liste de booléens (si chaque valeur de a en a exactement 3)

  • a@&3=+\'a se lit comme "un à où 3 = + \ 'a est vrai"

• générer une liste d'index pour les emplacements précédents: (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)et les valeurs entrées possibles pour un mot de passe (x)

  • &:' se lit comme "où chacun", s'applique à la liste des entiers codés en binaire, et calcule les index de chaque bit

  • x@/: applique le mot de passe x à chaque élément de la liste d'index (génère toutes les valeurs saisies possibles)

• Détermine si tous les modèles sont situés dans la liste de toutes les valeurs possibles entrées

  • y est l'argument qui représente une liste de modèles

  • y in\: se lit comme chaque valeur de y dans la liste à droite

  • &/est "et fini". &/y in\:..retourne vrai si tous les motifs de y sont localisés dans la liste.

• enfin, renvoyez chaque chaîne en n à chaque index rendant lambda vrai

  • n@&{..} se lit comme "n à où lambda {..} retourne vrai"

C (GCC) 222 octets

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

Essayez-le en ligne

Code d'appel

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

Sortie

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