# 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 , so the shortest answer in bytes wins. Non-codegolfing languages are welcome!
• Are the digits always in order? Based on the test cases I assume they are, but I couldn't see it mentioned in the rules unless I read past it. – Kevin Cruijssen Feb 22 at 14:44
• Welcome to PPCG! This is a nice, well-structured, and neatly formatted first challenge. You've clearly done your homework as far as getting that all down. I'm looking forward to answering it (if someone doesn't answer it in R first!). In the future, we suggest using the sandbox to get feedback before posting to main. Hope you enjoy your time on PPCG! – Giuseppe Feb 22 at 15:04
• @Giuseppe thanks! I've been anonymously reading the questions on this site for years, and I've been writing and tweaking and actually solving this specific problem for a couple months: I liked it enough to skip the sandbox. I'll post there first next time! – cefel Feb 22 at 15:07
• @Arnauld Well, if your password is 01234 or 12340 you shouldn't be able to log in by typing 1234. Passwords are more a string than a number even if composed by numbers, at least in that sense. So yes, leading and trailing zeros are mandatory. – cefel Feb 22 at 15:15
• The final test case appears to be missing 22123... unless I'm misunderstanding something? – Jonah Feb 23 at 5:46

# 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

• This is a lovely solution... – Jonah Feb 22 at 16:18
• Your non-3.8 code can do the "poor-man's assignment expression" of aliasing the string '%05d'. – xnor Feb 26 at 6:24

# 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


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


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 • Looks like you can compute the subseqs yourself a little shorter. – xnor Feb 24 at 2:01 • concat.words<$>mapM(:" ")p is shorter – H.PWiz Feb 24 at 10:51
• use p<-mapM(:['1'..'9'])"00000" to save 2 more bytes – H.PWiz Feb 24 at 23:28

# Jelly, 11 bytes

9Żṗ5ŒPiⱮẠɗƇ


Try it online!

# Pyth, 11 bytes

f<QyT^sMT5


Takes input as a set of strings.
Try it here

### Explanation

f<QyT^sMT5
sMT      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*'.*'}/}}}


Try it online!

Takes input as an arrray of character arrays.

• Well done! You beat me by 25 bytes. Should I delete my answer? – Eric Duminil Feb 22 at 20:58
• No, as long as you have a valid answer, there's no need to delete it. – Kirill L. Feb 23 at 10:23

# 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.

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! • $t+=/$b/ instead of /$b/&&$t++ – Nahuel Fouilleul Feb 22 at 21:35 # 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. # 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! • @digEmAll it says it’s 82 bytes doesn’t it? You can’t use integers because of potential for leading zeroes in the input. – Nick Kennedy Feb 23 at 13:02 • Sorry, I read the title and unconsciously I picked the minimum number without noticing that it was strikedthrough... and yes, sorry again you're right about the string input ;) – digEmAll Feb 23 at 14:06 # 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  • BTW, your approach can also be made shorter by switching to char array input, as in my version, and -2 more bytes by formatting the upper value as 1e5, like this – Kirill L. Feb 23 at 10:33 • @KirillL. Thanks for the -2 bytes. I won't change the input format because my answer would look too much like yours. Cheers! – Eric Duminil Feb 23 at 11:24 # J, 52 bytes (>,{;^:4~i.10)([#~]*/@e."2((#~3=+/"1)#:i.32)#"_ 1[)]  Try it online! # 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! • less useless variables: 1e5o ù'0 fA{Ue@AèX®+".* :P – ASCII-only Feb 25 at 4:25 • also 23: 1e5o ù'0 fA{Ue@AèX¬q".* – ASCII-only Feb 25 at 4:54 • 21 bytes – Shaggy Feb 25 at 9:57 • Interesting... I didn't realize return X,Y,Z would pick the last term. Thanks for the tips :) – dana Feb 25 at 12:52 • @dana; Yup, that's a feature of JavaScript: tio.run/##y0osSyxOLsosKNHNy09J/Z9m@1@jQqdS09auuii1pLQoTwHIq/… – Shaggy Feb 25 at 15:28 # 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. # 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.

# 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! ## 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"

# 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,
`