Einführung

Um zu verhindern, dass Keylogger das Passwort eines Benutzers stehlen, hat ein bestimmtes Bankkontosystem die folgende Sicherheitsmaßnahme implementiert: Bei jeder Eingabe werden nur bestimmte Ziffern abgefragt.

Angenommen, das Passwort Ihres Ziels lautet 89097: Das System fordert Sie möglicherweise auf, die 2., 4. und 5. Ziffer einzugeben:

997

Oder sie werden aufgefordert, die 1., 3. und 5. Ziffer einzugeben:

807

Sie wissen nur, dass Ihr Ziel die Ziffern der Reihe nach eingegeben hat, aber Sie wissen nicht, zu welcher Position sie im aktuellen Passwort gehören . Alles, was Sie wissen, ist, dass es zwei Neunen gibt, die vor sieben kommen müssen. und dass 8 vor 0 und 0 vor 7 kommt. Daher gibt es sechs mögliche Passwörter:

80997
89097
89907
98097
98907
99807

Der Keylogger auf dem Computer Ihres Ziels sammelt seit Monaten Passworteingaben, also lasst uns einsteigen!

Herausforderung

Geben Sie bei einer Liste dreistelliger Eingaben alle möglichen Passwörter aus, die für alle Eingaben gültig sind. Um die Komplexität der Berechnungen zu verringern und die Anzahl der möglichen Ergebnisse gering zu halten, ist das Kennwort garantiert numerisch und hat eine feste Größe von 5. Die Ziffern in jeder Eingabe sind in der richtigen Reihenfolge: Wenn es 123 ist, gibt das Ziel zuerst 1 ein. dann 2, dann 3.

Ein- / Ausgabebeispiele

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

Regeln

• Die Eingabe ist garantiert nicht leer.
• Führende und nachfolgende Nullen sind wichtig: Sie 01234unterscheiden sich von den Kennwörtern 12340und 1234knacken sie nicht. Überlegen Sie, wie echte Passwörter funktionieren!
• Es gelten die Standard-E / A-Regeln .
• Keine Standardlücken .
• Das ist Code-Golf , also gewinnt die kürzeste Antwort in Bytes. Nicht-Codegolf-Sprachen sind willkommen!

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

Probieren Sie es online!

Funktioniert sowohl in Python 2 als auch in Python 3.

( 97 Bytes in 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

Probieren Sie es online!

Erläuterung

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

Druckt die Ergebnisse mit alert().

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

Probieren Sie es online!

Kommentiert

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]

Der offensichtliche Brute-Force-Ansatz in Haskell: Erstellen Sie eine Liste aller möglichen Kennwörter und behalten Sie diejenigen bei, bei denen sich alle Elemente aus der Eingabeliste in der jeweiligen Liste der Teilsequenzen befinden.

Probieren Sie es online!

Edit: -1 Byte dank @xnor, -2 -4 Byte dank @ H.PWiz

Jelly , 11 Bytes

9Żṗ5ŒPiⱮẠɗƇ

Probieren Sie es online!

Pyth, 11 Bytes

f<QyT^s`MT5

Nimmt die Eingabe als eine Reihe von Zeichenfolgen.
Probieren Sie es hier aus

Erläuterung

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

Probieren Sie es online!

Nimmt die Eingabe als Array von Zeichen-Arrays.

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

Probieren Sie es online!

Versucht rekursiv, jede fünfstellige Zahlenfolge einzubauen s, und verfolgt dabei die Teilfolgen, die lnoch getroffen werden müssen. Wenn am Ende alle leer sind, wird das Ergebnis gedruckt.

Python 3.8 (Vorabversion) , 94 Byte

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

Probieren Sie es online!

Siehe die Macht der Zuweisungsausdrücke ! Verwendet die Methode von hier zum Überprüfen von Teilsequenzen.

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

Probieren Sie es online!

Netzhaut , 53 Bytes

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

Probieren Sie es online! Erläuterung:

~(`

Nehmen Sie nach dem Ausführen des Skripts das Ergebnis als neues Skript und führen Sie es ebenfalls aus.

.$*

.*Überall einfügen . Dies führt .*3.*2.*0.*zwar dazu, dass wir nur brauchen 3.*2.*0, aber nicht, dass es darauf ankommt.

m`^
G`

Fügen Sie G`am Anfang jeder Zeile ein. Dies macht es zu einem Retina Grep-Befehl.

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

Stellen Sie zwei weiteren Retina-Befehlen das Präfix voran. Das resultierende Skript sieht daher ungefähr so ​​aus:

K`

Löschen Sie den Puffer (der die ursprüngliche Eingabe enthält).

5+

Wiederholen Sie 5 mal ...

%`$

... an jede Zeile anhängen ...

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

... die Ziffer 0, dann eine Kopie der Zeile, dann die Ziffer 1usw. bis 9. Dies bedeutet, dass Sie nach nSchleifen alle nZiffern haben.

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

Filtern Sie die möglichen Zahlen basierend auf der Eingabe heraus.

R , 80 82 Bytes

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

Hier ist eine Basis-R-Lösung mit Regex. Durch das Schreiben dieser verschachtelten Reihe von Funktionen wurde mir klar, wie sehr ich gelernt habe, das Paket magrittr zu schätzen!

Hatte anfangs keine Regeln für die Eingabe gelesen, liest jetzt also von stdin (danke @KirillL).

Probieren Sie es online!

Ruby , 79 77 Bytes

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

Probieren Sie es online!

Die Eingabe ist ein Array von Zeichenfolgen.

Hier ist eine besser lesbare Version desselben Codes:

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;

oder

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;

Eingabe von Befehlszeilenargumenten. Laufen Sie mit -nroder probieren Sie sie online aus .

J , 52 Bytes

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

Probieren Sie es online!

Japt, 21 Bytes

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

Versuch es!

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 dank @Shaggy!

C # (Visual C # Interactive Compiler) , 116 Byte

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

Probieren Sie es 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);
  }
}

BEARBEITEN: Ein Fehler wurde behoben, durch den dasselbe Zeichen mehr als einmal gezählt wurde. Wenn beispielsweise 000protokolliert wurde, gibt die Funktion alle Kennwörter zurück, die ein einzelnes enthalten 0.

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

Probieren Sie es online!

K 67 Bytes

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

K hat eine (sehr) primitive Regex-Fähigkeit, also habe ich einen anderen Ansatz ausprobiert.

{...} definiert ein Lambda. Anwendungsbeispiel:{...}("320";"723";"730")

kehrt zurück ("37230";"72320";"73203";"73230")

• n ist die Liste der Ganzzahlen im Bereich 0..9999 als mit 0 aufgefüllte Zeichenfolgen

  • _1e5 Wendet Floor auf Float 1e5 an (wissenschaftliche Notation) -> generiert eine Ganzzahl von 100000

  • !_1e5 Erzeugt Integer-Liste 0..99999

  • {..}'!_1e5 Wendet Lambda auf jeden Wert in 0..99999 an

  • $x transformiere das Argument x (implizites Argument) in einen String

  • -5$$xrechts stell die Zeichenkette $ x auf ein Feld der Größe 5 (zB -5$$12erzeugt" 12"

  • "0"^stringErsetzt Leerzeichen durch "0", "0"^-5$$12erzeugt also"00012"

• a ist die Liste der Ganzzahlen im Bereich 0..31 als 5-Bit-Werte

  • !32 Werte generieren 0..31

  • (5#2) wiederhole 2 fünf mal (liste 2 2 2 2 2)

  • (5#2)\:'!32 generiert 5-Bit-Werte (2-Basis-Fünffach) für jeden Wert im Bereich 0..31

• Wir filtern die Werte von a mit genau drei. Dass Werte sind alle Kombinationen (Plätze) , wo Muster angeordnet werden können: 11100 11010 11001 10110 10101 10011 01110 01101 01011 00111. Ex. für "abc" Muster haben wir Äquivalenz mit regulären Ausdrückenabc?? ab?c? ab??c a?bc? a?b?c a??bc ?abc? ?ab?c ?a?bc ??abc?

  • +\'a berechnet die Summe jeder binären Darstellung (Anzahl von Einsen)

  • 3=+\'a Erzeugt eine Liste von Booleschen Werten (wenn jeder Wert in a genau drei hat)

  • a@&3=+\'a liest als "a an wo 3 = + 'a ist wahr"

• Liste der Indizes für frühere Orte generieren: (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)und die möglichen eingegebenen Werte für ein Passwort (x)

  • &:' Liest als "where each", gilt für die Liste der binär codierten Ganzzahlen und berechnet die Indizes für jedes 1-Bit

  • x@/: Wendet das Passwort x auf jedes Element der Indexliste an (generiert alle möglichen eingegebenen Werte)

• Bestimmt, ob sich alle Muster in der Liste aller möglichen eingegebenen Werte befinden

  • y ist das Argument, das eine Liste von Mustern darstellt

  • y in\: Liest als jeden Wert von y in der Liste auf der rechten Seite

  • &/ist "und vorbei". &/y in\:..Gibt true zurück, wenn sich alle Muster in y in der Liste befinden.

• Geben Sie abschließend bei jedem Index, der Lambda wahr macht, jeden String in n zurück

  • n@&{..} liest als "n an, wo Lambda {..} wahr zurückgibt"

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

Probieren Sie es online aus

Vorwahl

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

Ausgabe

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