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.
Programming Praxis 
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]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-987MUMPS 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-987Using 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 """I used this shell program to generate a list of license plate numbers:
#!/bin/bash
NUM_TIMES=100000
for ((i == 0 ; i < NUM_TIMES ; i++)); do
HEAD=$(head -c 3 < /dev/urandom | tr --complement 'A-Z' 'A-ZA-ZA-ZA-ZA-ZA-ZA-ZA-Z')
TAIL=$(head -c 3 < /dev/urandom | tr --complement '0-9' '0-90-90-90-90-90-90-90-90-90-90-90-90-90-90-90-90-90-90-90-90-90-90-90-9')
echo $HEAD-$TAIL
done
Then I piped it through
sortanduniqto make a list with no duplicates intocleaned.txt.Then I can use this shell program to query in the 3 ways required (membership, prefix count, and prefix listing):
#!/bin/bash
case "$1" in
(member) # membership query #
<cleaned.txt grep --silent '^'"$2"'$'
if test "$?" -eq 0
then
echo "'$2' is a member of this set."
else
echo "'$2' is not a member of this set."
exit 1
fi
;;
(prefix) # prefix count #
COUNT=$(<cleaned.txt grep --count '^'"$2")
if test "$COUNT" -eq 0
then
echo "No license plates begin with '$2'."
exit 1
elif test "$COUNT" -eq 1
then
echo "1 license plate begins with '$2'."
else
echo "$COUNT license plates begin with '$2'."
fi
;;
(list) # prefix list #
<cleaned.txt grep '^'"$2"
if test "$?" -ne 0
then
echo "No license plates begin with '$2'."
exit 1
fi
;;
(*)
echo "unknown command - use 'member', 'prefix', or 'list'."
exit 1
;;
esac
edit of above comment:
#!/bin/bash
NUM_TIMES=100000
for ((i == 0 ; i < NUM_TIMES ; i++)); do
HEAD=$(head -c 3 < /dev/urandom | tr --complement 'A-Z' 'A-ZA-ZA-ZA-ZA-ZA-ZA-ZA-Z')
TAIL=$(head -c 3 < /dev/urandom | tr --complement '0-9' '0-90-90-90-90-90-90-90-90-90-90-90-90-90-90-90-90-90-90-90-90-90-90-90-9')
echo $HEAD-$TAIL
done
—
#!/bin/bash
case "$1" in
(member) # membership query #
<cleaned.txt grep --silent '^'"$2"'$'
if test "$?" -eq 0
then
echo "'$2' is a member of this set."
else
echo "'$2' is not a member of this set."
exit 1
fi
;;
(prefix) # prefix count #
COUNT=$(<cleaned.txt grep --count '^'"$2")
if test "$COUNT" -eq 0
then
echo "No license plates begin with '$2'."
exit 1
elif test "$COUNT" -eq 1
then
echo "1 license plate begins with '$2'."
else
echo "$COUNT license plates begin with '$2'."
fi
;;
(list) # prefix list #
<cleaned.txt grep '^'"$2"
if test "$?" -ne 0
then
echo "No license plates begin with '$2'."
exit 1
fi
;;
(*)
>&2 echo "unknown command - use 'member', 'prefix', or 'list'."
exit 1
;;
esac