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

Relevant Pages

  • Idle curiosity (ieee bitorder)
    ... >> Where this becomes a problem is the byte array is LITTLE ENDIAN. ... The GCM specification has no concept beyond bit sequences. ... Without naming bits in some way and carefully specifying what we mean by ...
    (sci.crypt)
  • Re: Perl script to mimic uniq
    ... > There is a list of number sequences. ... I want to sort through the list, ... to arrays of IDs. ... There is nothing for "that array" to refer to in the previous ...
    (comp.lang.perl)
  • Re: Treetop parser (or PEG in general?) questions
    ... then it could build an array of thing, ... sequences, ... parser) would be a parser command that skips ALL node creation, ... language support) any time soon, well, I have another project ...
    (comp.lang.ruby)
  • Re: Unshuffle algorithm
    ... I have an array of numbers made up of two sequences that ... extract separate arrays made up of these sequences. ... that had been converted to flat images without metadata. ... algorithm, but thanks very much for your interest. ...
    (comp.soft-sys.matlab)
  • Re: VT100 standards
    ... I remember a similar set of sequences writing in DIBOL and Synergy DBL. ... array of pointers and an index. ... spaces, allocated memory for the text, stuffed the text in that memory, ...
    (comp.os.vms)