Use T-SQL to Generate a Sequence

I recently received an inquiry from a reader asking about various tasks concerning vehicle license plates: specifically, how to generate a sequence of license plates, how to identify ranges of existing license plates (islands), and how to identify ranges of missing license plates (gaps). While working on these tasks, I found them to be interesting T-SQL exercises and therefore decided to present them as reader challenges. In this article, I focus on the first task: generating a sequence of license plates. I’ll leave the other tasks for you to try on your own.

The Challenge

Our challenge for this article involves generating a sequence of license plates between two input license plate numbers, for an input license plate type. By type, I’m referring to the fact that in different locations (e.g., different states in the United States), as well as in certain locations in different time periods, the rules can be different. For example, currently the license plate system in Washington state uses the form AAANNNN (A = alpha, N = numeral), whereas the current system in New Jersey uses the form ANN-AAA. Some systems have a straightforward right-to-left significance order (from least to most) for the characters (e.g., in Washington state, the order is 7654321, where 1 represents the least significant character). Other systems have a more specialized order (e.g., in New Jersey, the order is 321-654). Also, some systems don’t use certain letters in certain character positions. As an example, see the Wikipedia article “Vehicle registration plates of New Jersey” at en.wikipedia.org/wiki/Vehicle_registration_plates_of_New_Jersey. Note that the New Jersey license plate system that was first issued in 2007 didn’t use the letters D, T, or X in the first position or the letters I, O, or Q in any position.

The specifics of the challenge are that you need to develop a solution that allows storing in the database the different rules for each license plate system that you need to support. You also need to develop a table function that returns a sequence of license plates between two input plates, based on an input plate type.

For the purposes of this challenge, we’ll keep things simple. Suppose that you need to support two plate system types called WA2009 and NJ2010. The system type WA2009 has the following rules:

So, for example, the range AAA0000 through AAA9999 is followed by the range AAB0000 through AAB9999.

The system type NJ2010 has the following rules:

So, for example, the sequence starts with the range A00-AAA through Z99-AAA, and this range is followed by A00-AAB. Also, with the character restrictions, C99-AAA, for example, is followed by E00-AAA, because D isn’t used in the first position.

To test your solution, you can use the following code to request a sequence of WA2009 plates:

SELECT plateFROM dbo.GetPlatesRange('AAA0000', 'AAZ9999', 'WA2009') AS P;

You should get a sequence with 260,000 plates, shown in abbreviated form in Figure 1.

Figure 1: Sequence of WA2009 Plates

You can use the following code to request a sequence of NJ2010 plates:

SELECT plateFROM dbo.GetPlatesRange('A00-AAA', 'Z99-AAZ', 'NJ2010') AS P;

You should get a sequence of 46,000 plates, shown in abbreviated form in Figure 2.

Figure 2: Sequence of NJ2010 Plates

I suggest that you try to come up with your own solution before looking at mine.

The Solution

The approach I used in my solution is to create two mapping functions: one (call it PlateToValue) that maps a license plate to an integer value that reflects the position of the current license plate in the entire sequence, and another (call it ValueToPlate) that maps an integer value to the license plate that it represents. I created a table called PlateChars in which I stored the plate system rules, and I used this table in the functions.

Use the code in Listing 1 to create and populate the PlateChars table. The platetype attribute represents the plate system type (e.g., 'WA2009', 'NJ2010'); charpos represents the position of the character in the string (1 is leftmost); validchars holds a string representing the valid symbols in the current character position; charvalue is the multiplier of the digit (0-based ordinal) that the symbol in the current character position represents.

SET NOCOUNT ON;USE tempdb;IF OBJECT_ID('dbo.PlateChars', 'U') IS NOT NULL DROP TABLE dbo.PlateChars;CREATE TABLE dbo.PlateChars(  platetype  VARCHAR(10)  NOT NULL,  charpos    INT      NOT NULL,  validchars VARCHAR(100) NOT NULL,  charvalue  BIGINT       NOT NULL,  CONSTRAINT PK_PlateChars PRIMARY KEY(platetype, charpos));GOINSERT INTO dbo.PlateChars(platetype, charpos, validchars, charvalue) VALUES  ('WA2009', 1, 'ABCDEFGHIJKLMNOPQRSTUVWXYZ', 6760000),  ('WA2009', 2, 'ABCDEFGHIJKLMNOPQRSTUVWXYZ',  260000),  ('WA2009', 3, 'ABCDEFGHIJKLMNOPQRSTUVWXYZ',   10000),  ('WA2009', 4, '0123456789'        ,    1000),  ('WA2009', 5, '0123456789'        ,     100),  ('WA2009', 6, '0123456789'        ,      10),  ('WA2009', 7, '0123456789'        ,       1),  ('NJ2010', 1, 'ABCEFGHJKLMNPRSUVWYZ'      ,     100), -- no DTX, no IOQ  ('NJ2010', 2, '0123456789'        ,      10),  ('NJ2010', 3, '0123456789'        ,       1),  ('NJ2010', 4, '-'             ,       1),  ('NJ2010', 5, 'ABCDEFGHJKLMNPRSTUVWXYZ'   , 1058000), -- no IOQ  ('NJ2010', 6, 'ABCDEFGHJKLMNPRSTUVWXYZ'   ,   46000), -- no IOQ  ('NJ2010', 7, 'ABCDEFGHJKLMNPRSTUVWXYZ'   ,    2000); -- no IOQGO

The last two attributes probably deserve further explanation. The validchars attribute holds a string with the valid symbols for the current character position in the order that the symbols are supposed to advance. For example, a character position that’s supposed to support the characters 0 through 9 will have a validchars string '0123456789'. A character position that’s supposed to support the characters A through Z, excluding D, T, X, I, O, and Q, will have the validchars string 'ABCEFGHJKLMNPRSUVWYZ'. Think of the symbols in a validchars string with a length n as representing in left-to-right order digits in base n. So, for example, in the last string A is digit 0 and Z is digit 20 in a base-20 system. You can think of a license plate system as a mix of characters, each representing a digit of its own base, using its own sequence of symbols.

Another issue is how you address the fact that the significance order of the character positions isn’t necessarily a simple right-to-left order, like we’re used to in a decimal system, for example. The solution lies in the charvalue attribute. In a simple decimal system, a number can be expressed as a sum of products of the different digits by their respective multipliers. For example, the value 1,759 is the sum: 9 × 1 + 5 × 10 + 7 × 100 + 1 × 1,000. In a similar way, you can compute the right multiplier for each character position in the license plate system and store it in the charvalue attribute. Each multiplier simply represents the number of possible arrangements of the different symbols in the less significant character positions. For example, character position 2 in the plate system type WA2009 has multiplier 260,000 because there are 260,000 possible arrangements in the character positions that are less significant.

The digit that the current symbol represents (e.g., in an earlier example, recall symbol A was digit 0 and symbol Z was digit 20) is computed as the character position of the current symbol in the validchars string minus 1. So, to map a license plate to an integer value, you sum the products × charvalue for each character position. Listing 2 has the definition of the function PlateToValue implementing this logic.

IF OBJECT_ID('dbo.PlateToValue', 'IF') IS NOT NULL DROP FUNCTION dbo.PlateToValue;GOCREATE FUNCTION dbo.PlateToValue(@myplate AS VARCHAR(20), @platetype AS VARCHAR(10)) RETURNS TABLEASRETURN  SELECT SUM((CHARINDEX(SUBSTRING(@myplate, charpos, 1), validchars) - 1) * charvalue) AS value  FROM dbo.PlateChars  WHERE platetype = @platetype;GO

Note that the function is implemented as an inline table-valued function and not a scalar one, because of performance reasons. To test the function, run the following code:

SELECT value FROM dbo.PlateToValue('ABC1234', 'WA2009')

This code returns the value 281234.

Listing 3 has the definition of the ValueToPlate function, which maps an integer value to the license plate that it represents.

IF OBJECT_ID('dbo.ValueToPlate', 'IF') IS NOT NULL DROP FUNCTION dbo.ValueToPlate;GOCREATE FUNCTION dbo.ValueToPlate(@value AS BIGINT, @platetype AS VARCHAR(10)) RETURNS TABLEASRETURN  SELECT CAST(    (SELECT SUBSTRING(validchars, @value % (charvalue * LEN(validchars)) / charvalue + 1, 1) AS [text()]     FROM dbo.PlateChars     WHERE platetype = @platetype     ORDER BY charpos     FOR XML PATH('')) AS VARCHAR(20)) AS plate;GO

The function calculates the digit (0-based ordinal) that the symbol in each character position represents; this is achieved with the following expression:

@value % (charvalue * LEN(validchars)) / charvalue

To understand the logic, think of an example from the more familiar decimal system. To isolate the second digit from the left in the value 1,759, you use

1759 % (100 [cur_multiplier] * 10 [num_possible_digits_in_cur_pos]) / 100 [cur_multiplier]

After the digit is computed, you translate it to the symbol that it represents, with the expression

SUBSTRING(validchars,  + 1, 1)

The rest of the logic in the function is concatenating the symbols based on their character positions, using the FOR XML PATH option.

Again, even though the function is supposed to return a scalar value, I implemented it as an inline table-valued function for performance reasons. To test the function, use the following code:

SELECT plate FROM dbo.ValueToPlate(281234, 'WA2009');

You’ll get ABC1234 as the output.

Now that you have the two mapping functions, you can proceed to the next step, which is returning a whole sequence of license plates between two given ones. To achieve this, you first create a table function (call it GetNumsRange) that returns a sequence of integers between two input ones. Listing 4 provides an example for such a function.

IF OBJECT_ID('dbo.GetNumsRange', 'IF') IS NOT NULL DROP FUNCTION dbo.GetNumsRange;GOCREATE FUNCTION dbo.GetNumsRange(@low AS BIGINT, @high AS BIGINT) RETURNS TABLEASRETURN  WITH    L0   AS(SELECT 1 AS c UNION ALL SELECT 1),    L1   AS(SELECT 1 AS c FROM L0 AS A CROSS JOIN L0 AS B),    L2   AS(SELECT 1 AS c FROM L1 AS A CROSS JOIN L1 AS B),    L3   AS(SELECT 1 AS c FROM L2 AS A CROSS JOIN L2 AS B),    L4   AS(SELECT 1 AS c FROM L3 AS A CROSS JOIN L3 AS B),    L5   AS(SELECT 1 AS c FROM L4 AS A CROSS JOIN L4 AS B),    Nums AS(SELECT ROW_NUMBER() OVER(ORDER BY (SELECT NULL)) AS rownum FROM L5)  SELECT TOP (@high - @low + 1) @low + rownum - 1 AS n FROM Nums ORDER BY rownum;GO

The final step is to query GetNumsRange, passing two integers representing the two license plates bounding the desired range. The input integers can be computed with the mapping function PlateToValue. Then you can map the result integer values to license plates using the ValueToPlate function. Listing 5 has the definition of the function GetPlatesRange encapsulating this logic, returning for each entry in the sequence both the license plate and the integer value that it represents. You can use the latter, for example, for sorting purposes.

IF OBJECT_ID('dbo.GetPlatesRange', 'IF') IS NOT NULL DROP FUNCTION dbo.GetPlatesRange;GOCREATE FUNCTION dbo.GetPlatesRange(  @low       AS VARCHAR(20),  @high      AS VARCHAR(20),  @platetype AS VARCHAR(10)) RETURNS TABLEASRETURN  SELECT    (SELECT plate FROM dbo.ValueToPlate(n, @platetype)) AS plate,    n AS platevalue  FROM dbo.GetNumsRange(    (SELECT value FROM dbo.PlateToValue(@low , @platetype)),    (SELECT value FROM dbo.PlateToValue(@high, @platetype)) );GO

The following code uses our new function to return the sequence of WA2009 plates from AAA0000 through AAZ9999:

SELECT plateFROM dbo.GetPlatesRange('AAA0000', 'AAZ9999', 'WA2009') AS PORDER BY platevalue;

Figure 1 shows the output of this code, in abbreviated form.

The following code returns the sequence of NJ2010 plates from A00-AAA through Z99-AAZ:

SELECT plateFROM dbo.GetPlatesRange('A00-AAA', 'Z99-AAZ', 'NJ2010') AS PORDER BY platevalue;

Figure 2 shows the output of this code.

Next Challenge

I hope you found the license plate sequence challenge interesting; I know I did. I’ll leave you with a couple of additional challenges involving license plates. Suppose that you’re given a table called PlatesWA2009 with an attribute called plate, holding a row for each already assigned license plate from the system WA2009. Your tasks are the following:

Good luck!