### 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))
(e 2) (s 0))
(if (negative? e) s
(loop (cdr cs) (- e 1)
(+ (* 26 s) (c->i (car cs)))))))```
```(define (adjoin license)
```(define (license? license)
```(define (start-list 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)))
(do ((n n (- n 1))) ((zero? n))
(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.

Pages: 1 2 3

### 6 Responses to “License Plates”

1. Rutger said

In Python

```from collections import defaultdict

# 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

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)

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
;
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
;
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'
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))
"{}-{}")""".format(i+1, c, n))

def find_pattern(pattern):
'pattern for SQL LIKE'
cur = DB.cursor()
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
"""
```
5. john said

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 `sort` and `uniq` to make a list with no duplicates into `cleaned.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 ```

6. john said

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 ```