# Possible numeric codes

This is a question I saw and solved a long time ago, it involves some maths.

There is a keypad

1 2 3

4 5 6

7 8 9

A certain password starts with a 3. Each digit is adjacent (horizontally or vertically) on the keypad to either of the previous two digits of the password. The password length is 10. How many possibilities are there?

For example, 1247879685 is valid but 1234565985 is not (4 is not adjacent to 2 or 3).

Note:
Although a complicated combinatorics solution or a program would also work, I'm looking for one that any common person can understand.

• @Geobits Sorry, I meant either of the last 2 digits. – ghosts_in_the_code Feb 12 '15 at 14:39
• Is 32155 allowed? Is 322 allowed? (My understanding is no, yes respectively but wanting to check I've understood right) – Christopher Feb 12 '15 at 14:57
• @ChristopherFish You're right. – ghosts_in_the_code Feb 12 '15 at 15:01
• Do you have reason to think there's a nice answer? – xnor Feb 13 '15 at 18:12
• @xnor I know a shorter method if a digit has to be adjacent to only the previous digit. I had originally thought the same approach would work, but it doesn't. So I have no idea whether a simple method exists or not. – ghosts_in_the_code Feb 14 '15 at 10:41

I made a small program in lua. this is the code:

n = {
 = {},
 = {=true,=true},
 = {=true,=true,=true},
 = {=true,=true},
 = {=true,=true,=true},
 = {=true,=true,=true,=true},
 = {=true,=true,=true},
 = {=true,=true},
 = {=true,=true,=true},
 = {=true,=true}}

function x(a,b, level)
if level == 10 then
return 1;
end
local newnumbers = {}
for k in pairs(n[a]) do
newnumbers[k] = true
end
for k in pairs(n[b]) do
newnumbers[k] = true
end
local c = 0
for k in pairs(newnumbers) do
c = c + x(b,k,level+1)
end
return c;
end

print(x(0,3,1))


you can test it out at http://www.lua.org/cgi-bin/demo

The result is:

691,950

Not sure if I made any mistake

• Is @SamDickson wrong then? And do you know the simpler approach - no code, very little math? – ghosts_in_the_code Feb 12 '15 at 17:12
• You tell me who is right. You should know. I could have made a mistake. And I don't know the simpler approach. – Ivo Beckers Feb 12 '15 at 17:15
• I just realised my approach was wrong. Sorry. Shall I delete the question or just let it be? – ghosts_in_the_code Feb 12 '15 at 17:28
• But is the answer correct even, shouldn't a and b be removed from newnumbers ? – HKOB Feb 12 '15 at 19:52