License Plates

May 16, 2017

There are lots of ways to store the set of license plate numbers. Since 26 × 26 × 27 = 17576 isn’t a particularly big number, we decide to create an array of 17576 lists; the array is indexed from AAA = 0 to ZZZ = 17575, and the lists are unsorted, which is sufficient because the average list will have only about six items. Here is our interface to the license plate set:

(define licenses (make-vector 17576 (list)))
(define (hash license)
  (define (c->i c)
    (- (char->integer (char-upcase c)) 65))
  (let loop ((cs (string->list license))
             (e 2) (s 0))
    (if (negative? e) s
      (loop (cdr cs) (- e 1)
            (+ (* 26 s) (c->i (car cs)))))))
(define (adjoin license)
  (when (not (license? license))
    (vector-set! licenses (hash license)
      (cons (substring license 3 6)
            (vector-ref licenses (hash license))))))
(define (license? license)
  (member (substring license 3 6)
          (vector-ref licenses (hash license))))
(define (start-list half-license)
  (sort string<? (vector-ref licenses (hash half-license))))

For testing and demonstration, here is a function that clears the licenses table, generates a hundred thousand random license plates, and inserts them in the license plate set:

(define (create-random-data n)
  (define (i->c i) (integer->char (+ i 65)))
  (define (i->d i) (integer->char (+ i 48)))
  (set! licenses (make-vector 17576 (list)))
  (do ((n n (- n 1))) ((zero? n))
    (adjoin (list->string
      (cons (i->c (randint 26))
        (cons (i->c (randint 26))
          (cons (i->c (randint 26))
            (cons (i->d (randint 10))
              (cons (i->d (randint 10))
                (list (i->d (randint 10))))))))))))

And here are the answers to the three questions in the exercise, for our random set of license plates:

> (license? "PLB123")
#f
> (length (start-list "PLB"))
2
> (start-list "PLB")
("287" "345")

The longest list has 19 elements, there are 68 unused license plate starters, and our random generator created 272 duplicate license plate numbers:

> (apply max (map length (vector->list licenses)))
19
> (length (filter zero? (map length (vector->list licenses))))
68
> (apply + (map length (vector->list licenses)))
99728

You can run the program at https://programmingpraxis.com/2017/05/16/license-plates/3/.

There are many other ways to write the requested program. You could write the list of license plate numbers to a file, then use grep to search. You could use hash tables or tries. A ternary search trie might be the best solution, as it works extremely well on string data and admits sorted searches on the data.

Advertisements

Pages: 1 2 3

4 Responses to “License Plates”

  1. Rutger said

    In Python

    from collections import defaultdict
    
    class license_plates:
            # assumes plates of format ABC-123
    	def __init__(self):
    		self.collection = defaultdict(lambda : defaultdict(lambda : defaultdict(list)))
    
    	def __str__(self):
    		result = "List of plates in license_plate collection:"
    		for l1 in self.collection:
    			for l2 in self.collection[l1]:
    				for l3 in self.collection[l1][l2]:
    					for n in self.collection[l1][l2][l3]:
    						result+= "\n"+ l1+l2+l3+"-"+n
    		return result
    
    
    	def add_plate(self, plate):
    		if len(plate) != 7 and all(plate[i] in string.letters for i in range(3)):
    			raise
    		else:
    			self.collection[plate[0]][plate[1]][plate[2]].append(plate[4:7])
    
    
    	def print_plates_starting_with(self, start_letters):
    		if start_letters and len(start_letters) < 4:
    			d = self.collection
    			for l in start_letters:
    				d = d[l]
    			print("Plates starting with:", start_letters)
    			self.pretty_print_dict(start_letters, d)
    		else:
    			raise
    
    
    	def pretty_print_dict(self, prefix, d):
    		for key in d:
    			# print('\t' * indent + str(key))
    			if isinstance(d[key], dict):
    				self.pretty_print_dict(prefix+key, d[key])
    			else:
    				for n in d[key]:
    					print(prefix + key + '-' + n)
    
    
    lp = license_plates()
    lp.add_plate('ABC-123')
    lp.add_plate('ABH-666')
    lp.add_plate('AQC-987')
    lp.add_plate('DEF-000')
    
    print(lp)
    
    lp.print_plates_starting_with('A')
    lp.print_plates_starting_with('AB')
    lp.print_plates_starting_with('D')
    lp.print_plates_starting_with('X')
    
    # output:
    # List of plates in license_plate collection:
    # DEF-000
    # AQC-987
    # ABH-666
    # ABC-123
    # Plates starting with: A
    # AQC-987
    # ABH-666
    # ABC-123
    # Plates starting with: AB
    # ABH-666
    # ABC-123
    # Plates starting with: D
    # DEF-000
    # Plates starting with: X
    # [Finished in 0.2s]
    
    
  2. Steve said

    MUMPS V1

    
    LICPLATE  ;New routine
             N CT,I,PLATES
             ; Add plates to array
             ;
             F I="PLB-123","PLB-666","PLB-987","PLC-000" D
             . S PLATES(I)=""
             ; Is PLB-123 member of the array?
             W !,"PLB is ",$S($D(PLATES("PLB-123")):"",1:"not"),"a member of the array."
             ;
             ; How many license plates begin with 'PLB'?
             ;
             S I=$O(PLATES("PLB"),-1) ; Start immediately before entries starting with 'PLB'
             F CT=0:1 S I=$O(PLATES(I)) Q:I'?1"PLB".E
             W !!,CT," plate",$S(CT'=1:"s",1:"")," begin with 'PLB'."
             ;
             ; What is the list of license plates that begin with the 'PLB'
             ;
             W !!,"List of license plates that begin with 'PLB':"
             S I=$O(PLATES("PLB"),-1) ; Start immediately before entries starting with 'PLB'
             F  S I=$O(PLATES(I)) Q:I'?1"PLB".E  W !,I
             Q
    
    ---
    
    D ^LICPLATE
    
    PLB is a member of the array.
    
    3 plates begin with 'PLB'.
    
    List of license plates that begin with 'PLB':
    PLB-123
    PLB-666
    PLB-987
    
    
  3. MUMPS V1

    
    Correction
    
    LICPLATE  ;New routine
             N CT,I,PLATES
             ; Add plates to array
             ;
             F I="PLB-123","PLB-666","PLB-987","PLC-000" D
             . S PLATES(I)=""
             ; Is PLB-123 member of the array?
             W !,"PLB-123 is ",$S($D(PLATES("PLB-123")):"",1:"not"),"a member of the array."
             ;
             ; How many license plates begin with 'PLB'?
             ;
             S I=$O(PLATES("PLB"),-1) ; Start immediately before entries starting with 'PLB'
             F CT=0:1 S I=$O(PLATES(I)) Q:I'?1"PLB".E
             W !!,CT," plate",$S(CT'=1:"s",1:"")," begin with 'PLB'."
             ;
             ; What is the list of license plates that begin with the 'PLB'
             ;
             W !!,"List of license plates that begin with 'PLB':"
             S I=$O(PLATES("PLB"),-1) ; Start immediately before entries starting with 'PLB'
             F  S I=$O(PLATES(I)) Q:I'?1"PLB".E  W !,I
             Q
    
    ---
    
    D ^LICPLATE
    
    PLB is a member of the array.
    
    3 plates begin with 'PLB'.
    
    List of license plates that begin with 'PLB':
    PLB-123
    PLB-666
    PLB-987
    
    
  4. Paul said

    Using SQLite.

    import sqlite3 as db
    import random
    import string
    
    def create_random_plates():
        'fill the database with some license plates'
        with db.connect("license2.db") as DB:
            cur = DB.cursor()
            cur.execute('CREATE TABLE LicensePlates(Id INT, Chr TEXT)')
            for i in range(100000):
                c = "".join(random.sample(string.ascii_uppercase, 3))
                n = "".join(random.sample(string.digits, 3))
                cur.execute("""INSERT INTO LicensePlates Values({},
                            "{}-{}")""".format(i+1, c, n))
    
    def find_pattern(pattern):
        'pattern for SQL LIKE'
        with db.connect("license2.db") as DB:
            cur = DB.cursor()
            cur.execute("""SELECT * FROM LicensePlates
                        WHERE Chr LIKE '{}'
                        ORDER BY Chr""".format(pattern))
            return cur.fetchall()
    
    create_random_plates()
    #  find all plates starting with PLB and with 5 in middle of number
    for plate in find_pattern("PLB-_5_"):
        print(plate[1])
    
    """
    PLB-451
    PLB-652
    PLB-756
    PLB-956
    """
    

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: