Re: PIN card

From: Peter Pearson (ppearson_at_nowhere.invalid)
Date: 10/17/05

Date: Mon, 17 Oct 2005 14:39:55 -0700

Mike Amling wrote:

> Let's say we have an alphabet of d distinct symbols. What's the
> smallest (area) rectangular array of such symbols such that every
> n-symbol sequence of such symbols is present in the array somewhere if
> we allow reading sequences in straight lines in any of the 8 directions
> N, S, E, W, NW, NE, SW, SE?

This Python program tells you whether an n_rows
by n_cols rectangular array of digits 0..d-1
"might" suffice to hold all sequences of pin_length
digits. A returned value of False guarantees that no
array of that size can hold all possible PINs.

def might_suffice( d, pin_length, n_rows, n_cols ):
  def places( pin_length, n_rows, n_cols ):
    mc = max(0,n_cols+1-pin_length)
    mr = max(0,n_rows+1-pin_length)
    return 2*n_rows*mc + 2*n_cols*mr + 4*mr*mc
  def places_needed( d, pin_length ):
    if pin_length % 2 == 0: palindromes = d**(pin_length/2)
    else: palindromes = d**((pin_length+1)/2)
    return d**pin_length + palindromes
  return places_needed( d, pin_length ) <= \
         places( pin_length, n_rows, n_cols )

For 4-digit decimal PINs, the smallest sufficient square
array is 38 x 38. Arrays of this size filled with random
decimal digits tend to contain around 6250 distinct 4-digit
PINs out of the 10,000 possible.

Peter Pearson
To get my email address, substitute:
nowhere -> spamcop, invalid -> net