Wprowadzenie

Aby zapobiec kradzieży hasła użytkownika przez keyloggery, pewien system kont bankowych wdrożył następujący środek bezpieczeństwa: za każdym razem monituje się o wprowadzenie tylko niektórych cyfr.

Na przykład, powiedzmy, że hasłem twojego celu jest 89097, system może poprosić go o wprowadzenie drugiej, czwartej i piątej cyfry:

997

Lub może poprosić ich o wprowadzenie pierwszej, trzeciej i piątej cyfry:

807

Wiesz tylko, że cel wprowadził cyfry w kolejności, ale nie wiesz, do której pozycji należą w faktycznym haśle . Wiesz tylko, że są dwie 9, które muszą wystąpić przed 7; i że 8 występuje przed 0, a 0 przed 7. Dlatego istnieje sześć możliwych haseł:

80997
89097
89907
98097
98907
99807

Keylogger na twoim komputerze docelowym zbiera hasła od miesięcy, więc włam się!

Wyzwanie

Biorąc pod uwagę listę trzycyfrowych danych wejściowych, wypisz wszystkie możliwe hasła, które są ważne dla wszystkich danych wejściowych. Aby zmniejszyć złożoność obliczeniową i utrzymać niską liczbę możliwych wyników, hasło jest gwarantowane jako numeryczne i ma stały rozmiar 5. Cyfry na każdym wejściu są w porządku: jeśli jest to 123, cel wpisuje 1 jako pierwszy, następnie 2, a następnie 3.

Przykłady wejścia / wyjścia

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

Zasady

• Dane wejściowe są gwarantowane jako niepuste.
• Liczby wiodące i końcowe: 01234są różne 12340i 1234nie łamią żadnego hasła. Pomyśl, jak działają prawdziwe hasła!
• Obowiązują standardowe zasady we / wy .
• Brak standardowych luk .
• To jest golf golfowy , więc wygrywa najkrótsza odpowiedź w bajtach. Mile widziane języki niekodujące do gry w golfa!

Python, 100 bajtów

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

Wypróbuj online!

Działa w Python 2, a także Python 3.

( 97 bajtów w Pythonie 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 bajtów

žh5ãʒæIåP

Wypróbuj online!

Wyjaśnienie

ž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 bajtów

Drukuje wyniki za pomocą alert().

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

Wypróbuj online!

Skomentował

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 bajtów

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

Oczywiste podejście brutalnej siły w Haskell: zbudował listę wszystkich możliwych haseł i zachowuje te, w których wszystkie elementy z listy wejściowej znajdują się na odpowiedniej liście podsekwencji.

Wypróbuj online!

Edycja -1 bajt dzięki @xnor, -2 -4 bajtów dzięki @ H.PWiz

Galaretka , 11 bajtów

9Żṗ5ŒPiⱮẠɗƇ

Wypróbuj online!

Pyth, 11 bajtów

f<QyT^s`MT5

Pobiera dane wejściowe jako zestaw ciągów znaków.
Wypróbuj tutaj

Wyjaśnienie

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.

Rubinowy , 54 bajty

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

Wypróbuj online!

Pobiera dane wejściowe jako tablicę tablic znaków.

Python 3 , 98 bajtów

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

Wypróbuj online!

Rekurencyjnie próbuje budować każdy pięciocyfrowy ciąg liczbowy s, śledząc podsekwencje, lktóre pozostały do ​​trafienia. Jeśli wszystkie są puste do końca, drukuje wynik.

Python 3.8 (wersja wstępna) , 94 bajty

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

Wypróbuj online!

Oto moc wyrażeń przypisania ! Używa metody z tego miejsca do sprawdzania podciągów.

Perl 5 -a , 80 bajtów

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

Wypróbuj online!

Siatkówka , 53 bajty

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

Wypróbuj online! Wyjaśnienie:

~(`

Po wykonaniu skryptu weź wynik jako nowy skrypt i również go uruchom.

.$*

Wstaw .*wszędzie. To powoduje, .*3.*2.*0.*że chociaż potrzebujemy tylko 3.*2.*0, a nie to ma znaczenie.

m`^
G`

Wstaw a G`na początku każdej linii. To zmienia go w polecenie Retina Grep.

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

Prefiks dwóch kolejnych poleceń Retina. Powstały skrypt będzie więc wyglądał mniej więcej tak:

K`

Wyczyść bufor (który zawiera oryginalne dane wejściowe).

5+

Powtórz 5 razy ...

%`$

... dołącz do każdej linii ...

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

... cyfra 0, następnie kopia linii, następnie cyfra 1itp 9. do . Oznacza to, że po npętlach będziesz mieć wszystkie ncyfry.

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

Odfiltruj możliwe liczby na podstawie danych wejściowych.

R , 80 82 bajtów

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

Oto podstawowe rozwiązanie R z użyciem wyrażenia regularnego. Napisanie tej zagnieżdżonej serii funkcji uświadomiło mi, jak bardzo nauczyłem się doceniać pakiet magrittr!

Początkowo nie czytałem reguł na wejściu, więc teraz czyta ze standardowego wejścia (dzięki @KirillL).

Wypróbuj online!

Rubinowy , 79 77 bajtów

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

Wypróbuj online!

Dane wejściowe to tablica ciągów.

Oto bardziej czytelna wersja tego samego kodu:

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 bajtów

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;

lub

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;

pobrać dane wejściowe z argumentów wiersza poleceń. Uruchom je -nrlub wypróbuj online .

J , 52 bajty

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

Wypróbuj online!

Japt, 21 bajtów

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

Spróbuj!

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 bajty dzięki @Shaggy!

C # (interaktywny kompilator Visual C #) , 116 bajtów

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

Wypróbuj 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);
  }
}

EDYCJA: naprawiono błąd, w którym ta sama postać była liczona więcej niż jeden raz. Na przykład, jeśli 000został zalogowany, funkcja służy do zwrócenia wszystkich haseł zawierających jeden 0.

Czysty , 113 bajtów

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

Wypróbuj online!

K 67 bajtów

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

K ma (bardzo) pierwotną funkcję wyrażania regularnego, więc wypróbowałem inne podejście.

{...} definiuje lambda. Użyj przykładu:{...}("320";"723";"730")

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

• n to lista liczb całkowitych z zakresu 0..9999 jako ciągów 0-dopełnianych

  • _1e5 stosuje floor do float 1e5 (notacja naukowa) -> generuje liczbę całkowitą 100000

  • !_1e5 generuje listę liczb całkowitych 0..99999

  • {..}'!_1e5 stosuje lambda do każdej wartości w 0..99999

  • $x przekształć argument x (domyślny argument) na ciąg

  • -5$$xprawy dopasuj ciąg $ x do pola o rozmiarze 5 (np. -5$$12generuje" 12"

  • "0"^stringzamienia puste znaki na „0”, więc "0"^-5$$12generuje"00012"

• a to lista liczb całkowitych z zakresu 0..31 jako wartości 5-bitowych

  • !32 generować wartości 0..31

  • (5#2) powtórz 2 pięć razy (lista 2 2 2 2 2)

  • (5#2)\:'!32 generuje wartości 5-bitowe (2-zasadowe pięciokrotnie) dla każdej wartości z zakresu 0..31

• filtrujemy wartości z dokładnie 3 z nich. Że wartości są wszystkie kombinacje (miejsc), gdzie wzór może być zlokalizowany: 11100 11010 11001 10110 10101 10011 01110 01101 01011 00111. Dawny. dla wzorca „abc” mamy równoważność z wyrażeniami regularnymiabc?? ab?c? ab??c a?bc? a?b?c a??bc ?abc? ?ab?c ?a?bc ??abc?

  • +\'a oblicza sumę każdej reprezentacji binarnej (liczby)

  • 3=+\'a generuje listę booleanów (jeśli każda wartość w a ma dokładnie 3)

  • a@&3=+\'a czyta się jako „a, gdzie 3 = + \” jest prawdziwe ”

• wygeneruj listę indeksów dla poprzednich miejsc: (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)i możliwe wprowadzone wartości hasła (x)

  • &:' odczytuje jako „gdzie każdy”, stosuje się do listy liczb całkowitych kodowanych binarnie i oblicza indeksy każdego 1-bitowego

  • x@/: stosuje hasło x do każdego elementu listy indeksów (generuje wszystkie możliwe wprowadzone wartości)

• Określa, czy wszystkie wzorce znajdują się na liście wszystkich możliwych wprowadzonych wartości

  • y jest argumentem reprezentującym listę wzorców

  • y in\: odczytuje jak każdą wartość y na liście po prawej stronie

  • &/to „i ponad”. &/y in\:..zwraca true iff wszystkie wzorce y są lokalizowane na liście ..

• na koniec zwracaj każdy ciąg in przy każdym indeksie, który sprawia, że ​​lambda jest prawdą

  • n@&{..} czyta się jako „n, gdzie lambda {..} zwraca true”

C (GCC) 222 bajty

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

Wypróbuj online

Kod telefoniczny

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

Wynik

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