Crack the bank account's password!

Question

Introduction

In order to prevent keyloggers from stealing a user's password, a certain bank account system has implemented the following security measure: only certain digits are prompted to be entered each time.

For example, say your target's password is 89097, the system may prompt them to enter the 2nd, 4th and 5th digit:

997

Or it might prompt them to enter the 1st, 3rd and 5th digit:

807

All you know is that your target entered the digits in order, but you don't know which position they belong to in the actual password. All you know is there are two 9s, which must come before 7; and that 8 comes before 0, and 0 before 7. Therefore, there are six possible passwords:

80997
89097
89907
98097
98907
99807

The keylogger in your target's computer has been collecting password inputs for months now, so let's hack in!

Challenge

Given a list of three-digit inputs, output all the possible passwords that are valid for all inputs. In order to reduce computational complexity and to keep the amount of possible results low, the password is guaranteed to be numerical and have a fixed size of 5. The digits in every input are in order: if it's 123, the target typed 1 first, then 2, then 3.

Input/Output examples

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

---

Rules

• Input is guaranteed non-empty.
• Leading and trailing zeros matter: 01234 is different from 12340, and 1234 doesn't crack either password. Think of how real passwords work!
• Standard I/O rules apply.
• No standard loopholes.
• This is code-golf, so the shortest answer in bytes wins. Non-codegolfing languages are welcome!

Answer 1

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

Try it online!

Works in Python 2 as well as 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

Answer 2

05AB1E, 11 9 bytes

žh5ãʒæIåP

Try it online!

Explanation

ž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

Answer 3

JavaScript (ES6), 88 bytes

Prints the results with alert().

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

Try it online!

Commented

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

Answer 4

Haskell, 81 80 78 76 bytes

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

The obvious brute force approach in Haskell: built a list of all possible passwords and keep those where all elements from the input list are in respective list of subsequences.

Try it online!

Edit: -1 byte thanks to @xnor, -2 -4 bytes thanks to @H.PWiz

Answer 5

Jelly, 11 bytes

9Żṗ5ŒPiⱮẠɗƇ

Try it online!

Answer 6

Pyth, 11 bytes

f<QyT^s`MT5

Takes input as a set of strings.
Try it here

Explanation

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.

Answer 7

Ruby, 54 bytes

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

Try it online!

Takes input as an arrray of character arrays.

Answer 8

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

Try it online!

Recursively tries building every five-digit number string in s, tracking the subsequences in l still remaining to be hit. If all are empty by the end, prints the result.

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

Try it online!

Behold the power of assignment expressions!. Uses the method from here for checking subsequences.

Answer 9

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

Try it online!

Answer 10

Retina, 53 bytes

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

Try it online! Explanation:

~(`

After executing the script, take the result as a new script, and execute that, too.

.$*

Insert .* everywhere. This results in .*3.*2.*0.* although we only need 3.*2.*0, not that it matters.

m`^
G`

Insert a G` at the start of each line. This turns it into a Retina Grep command.

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

Prefix two more Retina commands. The resulting script will therefore look something like this:

K`

Clear the buffer (which contains the original input).

5+

Repeat 5 times...

%`$

... append to each line...

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

... the digit 0, then a copy of the line, then the digit 1, etc. until 9. This means that after n loops you will have all n-digit numbers.

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

Filter out the possible numbers based on the input.

Answer 11

R, 80 82 bytes

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

Here’s a base R solution using regex. Writing this nested series of functions made me realise how much I’ve learned to appreciate the magrittr package!

Initially hadn’t read rules on input, so now reads from stdin (thanks @KirillL).

Try it online!

Answer 12

Ruby, 79 77 bytes

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

Try it online!

Input is an array of strings.

Here's a more readable version of the same 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

Answer 13

J, 52 bytes

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

Try it online!

Answer 14

Japt, 21 bytes

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

Try it!

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 thanks to @Shaggy!

Answer 15

C# (Visual C# Interactive Compiler), 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);}}

Try it 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: fixed a bug where the same character was counted more than once. For example, if 000 was logged, the function used to return all passwords containing a single 0.

Answer 16

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;

or

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;

take input from command line arguments. Run with -nr or try them online.

Answer 17

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

Try it online!

Answer 18

K 67 bytes

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

K has a (very) primitive regex capability, so i tried a different approach.

{...} defines a lambda. Use example: {...}("320";"723";"730")

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

• n is the list of integers in range 0..9999 as 0-padded strings

  • _1e5 applies floor to float 1e5 (scientific notation) -> generates integer 100000

  • !_1e5 generates integer-list 0..99999

  • {..}'!_1e5 applies lambda to each value in 0..99999

  • $x transform argument x (implicit arg) to string

  • -5$$x right adjust string $x to a field of size 5 (ex. -5$$12 generates " 12"

  • "0"^string replaces blanks with "0" char, so "0"^-5$$12 generates "00012"

• a is the list of integers in the range 0..31 as 5-bit values

  • !32 generate values 0..31

  • (5#2) repeat 2 five times (list 2 2 2 2 2)

  • (5#2)\:'!32 generates 5-bit values (2-base five-times) for each value in range 0..31

• we filter the values of a with exactly 3 ones. That values are all the combinations (places) where pattern can be located: 11100 11010 11001 10110 10101 10011 01110 01101 01011 00111. Ex. for "abc" pattern we have equivalence with regexs abc?? ab?c? ab??c a?bc? a?b?c a??bc ?abc? ?ab?c ?a?bc ??abc?

  • +\'a calculates sum of each binary representation (number of ones)

  • 3=+\'a generates list of booleans (if each value in a has exactly 3 ones)

  • a@&3=+\'a reads as "a at where 3=+\'a is true"

• generate list of indexes for previous places: (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) and the possible entered-values for a password (x)

  • &:' reads as "where each", applies to list of binary-coded integers, and calculates indexes of each 1-bit

  • x@/: applies password x to each elem of the list of indexes (generates all possible entered values)

• Determines if all patterns are located in the list of all possible entered values

  • y is the arg that represent list of patterns

  • y in\: reads as each value of y in the list at the right

  • &/ is "and over". &/y in\:.. returns true iff all patterns in y are locates at the list ..

• finally, return each string in n at every index that makes lambda true

  • n@&{..} reads as "n at where lambda {..} returns true"

Answer 19

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

Try it online

Calling code

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

Output

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