pengantar

Untuk mencegah keylogger mencuri kata sandi pengguna, sistem rekening bank tertentu telah menerapkan tindakan keamanan berikut: hanya digit tertentu yang diminta untuk dimasukkan setiap kali.

Misalnya, katakan kata sandi target Anda 89097, sistem mungkin meminta mereka untuk memasukkan digit ke-2, ke-4 dan ke-5:

997

Atau mungkin mendorong mereka untuk memasukkan angka 1, 3 dan 5:

807

Yang Anda tahu adalah bahwa target Anda memasukkan angka secara berurutan, tetapi Anda tidak tahu di mana posisi mereka dalam kata sandi yang sebenarnya . Yang Anda tahu ada dua angka 9, yang harus ada sebelum jam 7; dan bahwa 8 muncul sebelum 0, dan 0 sebelum 7. Oleh karena itu, ada enam kata sandi yang mungkin:

80997
89097
89907
98097
98907
99807

Keylogger di komputer target Anda telah mengumpulkan input kata sandi selama berbulan-bulan sekarang, jadi mari masuk!

Tantangan

Diberikan daftar input tiga digit, tampilkan semua kata sandi yang mungkin yang valid untuk semua input. Untuk mengurangi kompleksitas komputasi dan untuk menjaga jumlah hasil yang mungkin rendah, kata sandi dijamin numerik dan memiliki ukuran tetap 5. Digit dalam setiap input berurutan: jika 123, target mengetik 1 terlebih dahulu, lalu 2, lalu 3.

Contoh input / output

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

Aturan

• Input dijamin tidak kosong.
• Angka nol di depan dan di belakang: 01234berbeda dengan 12340, dan 1234tidak memecahkan kata sandi. Pikirkan cara kerja kata sandi nyata!
• Aturan I / O standar berlaku.
• Tidak ada celah standar .
• Ini adalah kode-golf , jadi jawaban tersingkat dalam byte menang. Bahasa non-codegolf dipersilakan!

Python, 100 byte

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

Cobalah online!

Berfungsi di Python 2 dan Python 3.

( 97 byte dalam 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 byte

žh5ãʒæIåP

Cobalah online!

Penjelasan

ž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

Mencetak hasilnya dengan alert().

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

Cobalah online!

Berkomentar

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 byte

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

Pendekatan brute force yang jelas di Haskell: membuat daftar semua kata sandi yang mungkin dan menyimpannya di mana semua elemen dari daftar input berada di daftar berikutnya.

Cobalah online!

Sunting: -1 byte berkat @xnor, -2 -4 byte terima kasih kepada @ H.PWiz

Jelly , 11 byte

9Żṗ5ŒPiⱮẠɗƇ

Cobalah online!

Pyth, 11 byte

f<QyT^s`MT5

Mengambil input sebagai satu set string.
Coba di sini

Penjelasan

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 byte

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

Cobalah online!

Mengambil input sebagai array dari array karakter.

Python 3 , 98 byte

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

Cobalah online!

Secara rekursif mencoba membuat setiap string angka lima digit s, melacak urutan yang lmasih tersisa untuk dipukul. Jika semua kosong pada akhirnya, cetak hasilnya.

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

Cobalah online!

Lihatlah kekuatan ekspresi penugasan ! Gunakan metode dari sini untuk memeriksa selanjutnya.

Perl 5 -a , 80 byte

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

Cobalah online!

Retina , 53 byte

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

Cobalah online! Penjelasan:

~(`

Setelah menjalankan skrip, ambil hasilnya sebagai skrip baru, dan jalankan juga.

.$*

Masukkan di .*mana-mana. Ini menghasilkan .*3.*2.*0.*meskipun kita hanya perlu 3.*2.*0, bukan itu yang penting.

m`^
G`

Masukkan a G`di awal setiap baris. Ini mengubahnya menjadi perintah Retina Grep.

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

Awali dua perintah Retina lagi. Karenanya skrip yang dihasilkan akan terlihat seperti ini:

K`

Bersihkan buffer (yang berisi input asli).

5+

Ulangi 5 kali ...

%`$

... tambahkan ke setiap baris ...

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

... digit 0, lalu salinan garis, lalu digit 1, dll 9. hingga . Ini berarti bahwa setelah nloop Anda akan memiliki semua nangka -digit.

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

Saring nomor yang mungkin berdasarkan input.

R , 80 82 byte

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

Inilah solusi dasar R menggunakan regex. Menulis serangkaian fungsi bersarang ini membuat saya menyadari betapa saya telah belajar untuk menghargai paket magrittr!

Awalnya tidak membaca aturan tentang input, jadi sekarang membaca dari stdin (terima kasih @ KirillL).

Cobalah online!

Ruby , 79 77 byte

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

Cobalah online!

Input adalah larik string.

Berikut versi kode yang sama dengan yang dapat dibaca:

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 byte

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;

atau

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;

mengambil input dari argumen baris perintah. Jalankan dengan -nratau coba online .

J , 52 byte

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

Cobalah online!

Japt, 21 byte

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

Cobalah!

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 byte terima kasih kepada @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);}}

Cobalah 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: memperbaiki bug di mana karakter yang sama dihitung lebih dari satu kali. Misalnya, jika 000dicatat, fungsi yang digunakan untuk mengembalikan semua kata sandi yang mengandung satu 0.

Bersihkan , 113 byte

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

Cobalah online!

K 67 byte

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

K memiliki kemampuan regex primitif, jadi saya mencoba pendekatan yang berbeda.

{...} mendefinisikan lambda. Gunakan contoh:{...}("320";"723";"730")

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

• n adalah daftar bilangan bulat di kisaran 0..9999 sebagai string 0-padded

  • _1e5 berlaku floor to float 1e5 (notasi ilmiah) -> menghasilkan integer 100000

  • !_1e5 menghasilkan bilangan bulat daftar 0..99999

  • {..}'!_1e5 berlaku lambda untuk setiap nilai di 0..99999

  • $x mengubah argumen x (argumen implisit) menjadi string

  • -5$$xsesuaikan kanan string $ x ke bidang ukuran 5 (mis. -5$$12menghasilkan" 12"

  • "0"^stringmenggantikan blank dengan char "0", jadi "0"^-5$$12generate"00012"

• a adalah daftar bilangan bulat dalam kisaran 0..31 sebagai nilai 5-bit

  • !32 menghasilkan nilai 0..31

  • (5#2) ulangi 2 lima kali (daftar 2 2 2 2 2)

  • (5#2)\:'!32 menghasilkan nilai 5-bit (2-basis lima kali) untuk setiap nilai dalam kisaran 0..31

• kami memfilter nilai-nilai dengan tepat 3 yang. Bahwa nilai-nilai semua kombinasi (tempat) di mana pola dapat berada: 11100 11010 11001 10110 10101 10011 01110 01101 01011 00111. Ex. untuk pola "abc" kita memiliki persamaan dengan regexabc?? ab?c? ab??c a?bc? a?b?c a??bc ?abc? ?ab?c ?a?bc ??abc?

  • +\'a menghitung jumlah setiap representasi biner (jumlah yang)

  • 3=+\'a menghasilkan daftar booleans (jika setiap nilai dalam memiliki tepat 3 yang)

  • a@&3=+\'a dibaca sebagai "a at where 3 = + \ 'a true"

• menghasilkan daftar indeks untuk tempat-tempat sebelumnya: (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)dan kemungkinan nilai yang dimasukkan untuk kata sandi (x)

  • &:' dibaca sebagai "di mana masing-masing", berlaku untuk daftar bilangan bulat kode-biner, dan menghitung indeks masing-masing 1-bit

  • x@/: menerapkan kata sandi x untuk setiap elem dari daftar indeks (menghasilkan semua nilai yang mungkin dimasukkan)

• Menentukan apakah semua pola berada dalam daftar semua nilai yang dimasukkan mungkin

  • y adalah arg yang mewakili daftar pola

  • y in\: dibaca sebagai setiap nilai y dalam daftar di sebelah kanan

  • &/is "and over". &/y in\:..mengembalikan true iff semua pola dalam y menempatkan di daftar ..

• Akhirnya, kembalikan setiap string dalam n pada setiap indeks yang membuat lambda menjadi benar

  • n@&{..} dibaca sebagai "n di mana lambda {..} mengembalikan true"

C (GCC) 222 byte

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

Cobalah online

Kode panggilan

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

Keluaran

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