Let's begin with some terminology. Let n be the number of pins, d be the possible depths, and h be the MACS. For the sake of example, consider a 5 pin system with 10 depths and a MACS of 7. It's easy to bound the solution with [h^n, d^n], but we want an exact answer. We also want something that can be computed as quickly as possible, so even if we have 10,000 pins with 3,000 depths, we can still solve the problem (not practical, but this is math). While I don't know if there's a solution in terms of n, d, and h, we can reduce the amount of time to count the solution pretty far.
Our first case is the code written by user geekmug here. The code is copied below.
- Code: Select all
DEPTHS = 10
MAC = 7
PINS = 6
def is_valid_mac(key):
for i in range(PINS - 1):
if abs(key[i] - key[i + 1]) > MAC:
return False
return True
def main():
valid = 0
key = [0] * PINS
is_not_done = True
while is_not_done:
if is_valid_mac(key):
valid += 1
for i in range(PINS):
key[i] += 1
if key[i] >= DEPTHS:
key[i] = 0
if i == PINS - 1 :
is_not_done = False
continue
else:
break
print("Valid: %d" % (valid,))
if __name__ == '__main__':
main()
Essentially, the code is creating every possible bitting, and only counting those which do not violate the MACS. That means we are creating d^n keys, and checking up to n-1 chambers for a violation of the MACS. In terms of computational complexity, this solution is O(nd^n), or exponential with respect to n. In other words, this solution is fine for small n (which was the use for this script anyway), but as you increase the number of pins, solving the problem begins to take exponentially longer.
Luckily, we can speed up the solution even more. Let's start by counting all the 5 pin bittings of the form 0----. Then we can count all the 5 pin bittings of the form 1----, 2----, etc. and add them all up at the end. When we're counting the bittings of the form 0----, we can just add up the 4 pin bittings that don't violate the MACS. That is, add up the number of bittings of the form 0---,1---,2---,...,7--- (since we can't have a biting that's 08--- or 09---). Now when we count the bittings of the form 1----, we can just add up the number of bittings of the form 0--- through 8---. However, since we already counted most of these in the previous step, we can save time by remembering the answers we've already computed. In computer science, these concepts are known as recursion and memoization. Here's the code:
- Code: Select all
DEPTHS = 10
MAC = 7
PINS = 6
def main():
combos = [1] * DEPTHS
for i in range(1,PINS):
combos2 = [0] * DEPTHS
for j in range(DEPTHS):
for k in filter(lambda x: 0<=x<DEPTHS, range(j-MAC,j+MAC+1)):
combos2[j] += combos[k]
combos = combos2
print("Valid: %d" % sum(combos))
if __name__ == '__main__':
main()
Already you can see it runs slightly faster than the first script. What's the complexity? O(n*d*h). That means it can handle large n, d, and h, without much problem.
We can actually do a little bit better still. If you look at the second piece of code, you'll see that the outermost for loop is doing the equivalent of a matrix multiplication on a vector. If we have
- Code: Select all
[1,1,1,1,1,1,1,1,0,0] [1]
[1,1,1,1,1,1,1,1,1,0] [1]
[1,1,1,1,1,1,1,1,1,1] [1]
[1,1,1,1,1,1,1,1,1,1] [1]
M = [1,1,1,1,1,1,1,1,1,1] and v=[1]
[1,1,1,1,1,1,1,1,1,1] [1]
[1,1,1,1,1,1,1,1,1,1] [1]
[1,1,1,1,1,1,1,1,1,1] [1]
[0,1,1,1,1,1,1,1,1,1] [1]
[0,0,1,1,1,1,1,1,1,1] [1]
where M is a dxd matrix constructed based on h, the total number of valid combinations for a system of n pins is given by v^T * M^(n-1) * v. In Mathematica,
- Code: Select all
DEPTHS = 10
MAC = 7
PINS = 6
mat = Table[If[Abs[i - j] <= MAC, 1, 0],{i,DEPTHS},{j,DEPTHS}]
vec = Table[1, {DEPTHS}]
vec.MatrixPower[mat, PINS-1].vec
Finally, what is the complexity of this solution? Taking the matrix to a power turns out to be the computationally most expensive, and is at most O(d^3*log n). For a fixed d, this is significantly faster than our previous algorithm, and we may even be able to acheive faster results by taking advantage of the Jordan Normal form of our matrix. In this case we could even get an equation in terms of n.
Computing the total number of differs is a highly interesting mathematical problem. Even though keying systems with this many pins is impractical, this exercise should demonstrate an efficient, algorithmic way to compute the total number of differs. I skipped over most of the important details to avoid this from being too long, but if any of you have an interest in computer science or linear algebra, I hope this post has given you something to think about.
-xylac