Editor's Note: Send your experts-only T-SQL tips to Itzik Ben-Gan at firstname.lastname@example.org. If we use your tip in the magazine, you'll receive $100 and an exclusive T-SQL Black Belt shirt.
In "Wake Up to T-SQL," April 2002, InstantDoc ID 24139, I showed how you can use T-SQL for the unusual purpose of drawing a smiley face. Last month's drawing was more or less realistic; this time, I look at how to use T-SQL for abstract drawing. Mike Labosh, a fellow Microsoft Certified Trainer (MCT), posted a very cool puzzle in a private SQL Server MCT newsgroup. I had a lot of fun working on it and found the output interesting. With Labosh's permission, I'm going to share his puzzle and my solution with you.
As always, I urge you to try to come up with your own solution. A tip: Use stored procedures and user-defined functions (UDFs) where appropriate to make the solution modular and easy to follow and maintain.
The September 1986 issue of Byte magazine featured a cool article titled "Abstract Mathematical Art," which described a cellular automation algorithm related to John H. Conway's "Game of Life." (The "game" Conway invented is actually an algorithm with a set of rules governing the birth, death, and survival of organisms through generations. This algorithm is commonly used in software-development demos.) Those were the days of line-numbered BASIC, and the algorithm immediately caught Labosh's attention. He now uses the algorithm as a way to test his skills whenever he wants to try a new language or push the limits on one that he knows.
The automation string is a series of 80 single-digit numeric values (so they fit nicely in a line of screen output). Each digit can be either 0, 1, 2, or 3. The automation string can be stored as an array of integers or as a string of single digits—varchar(80). The algorithm generates multiple automation strings, where the first string's state changes according to the algorithm's rules. Each digit of the first automation state must be randomly generated. For more aesthetically pleasing output, you can make sure that the first and last values in the string (or array) are always 0. Doing this produces "borders," keeps the math from changing all the string's digits on every generation, and keeps the output from looking like a mess.
Part of the algorithm is a replication rule that defines how each successive automation state will be generated. The replication rule contains 10 single-digit values, in which each digit is also either 0, 1, 2, or 3. The rule can also be stored as an array of integers or as a string of 10 digits such as char(10). You can design the rule arbitrarily, or you can use replication rules that are known to produce interesting graphical formations. For example, the replication rule "0102030201" generates particularly interesting output that's more visually appealing than some arbitrary replication rules you might choose.
To calculate the next automation state, the algorithm loops across the values in the 80-digit state, starting at the second digit and ending at the 79th digit. (Make sure the first and last values are set to 0.) The algorithm calculates the next state for any given value, say the nth digit position, by following these steps:
- It calculates the sum of n-1's value, n's value, and n+1's value, then adds 1.
- The algorithm uses that sum—I'll call it m—to point at the mth digit of the replication rule.
- Whatever value appears at that position of the rule is the next state value for the nth digit of the automation string.
You can begin testing your solution by randomly generating the first state and storing it in a table or using the PRINT command to print it. For example, suppose you randomly generated the following (abbreviated) first state: 002222030011...0. You'd generate the next state by using the algorithm above (Steps 1, 2, and 3), then store or PRINT the values of that state. Using the replication rule "0102030201," here's how you'd calculate the first few digits of the next state:
- Set first digit to 0 manually
- Step 1: m=0+0+2+1=3; Step 2: third digit of replication rule is 0; Step 3: second digit in new state is 0
- Step 1: m=0+2+2+1=5; Step 2: fifth digit of replication rule is 0; Step 3: third digit in new state is 0
- Step 1: m=2+2+2+1=7; Step 2: seventh digit of replication rule is 0; Step 3: fourth digit in new state is 0
- Step 1: m=2+2+2+1=7; Step 2: seventh digit of replication rule is 0; Step 3: fifth digit in new state is 0
- Step 1: m=2+2+0+1=5; Step 2: fifth digit of replication rule is 0; Step 3: sixth digit in new state is 0
- Step 1: m=2+0+3+1=6; Step 2: sixth digit of replication rule is 3; Step 3: seventh digit in new state is 3
- Step 1: m=0+3+0+1=4; Step 2: fourth digit of replication rule is 2; Step 3: eighth digit in new state is 2
- Step 1: m=3+0+0+1=4; Step 2: fourth digit of replication rule is 2; Step 3: ninth digit in new state is 2
- Step 1: m=0+0+1+1=2; Step 2: second digit of replication rule is 1; Step 3: tenth digit in new state is 1
- Step 1: m=0+1+1+1=3; Step 2: third digit of replication rule is 0; Step 3: eleventh digit in new state is 0
- Perform the same calculation for all digits through the 79th digit
- Set 80th digit to 0 manually
As a result of running the process, the next state (abbreviated) is 00000032210...0.
Run the automation through, say, 25 generations (this size is convenient because most screens can show 80 characters * 25 rows), and you'll see an interesting abstract pattern in the output. Applications with a UI can represent each value as a colored pixel, and you can generate patterned wallpaper. Figure 1 contains some abbreviated sample output; note the interesting pattern. After you achieve an output similar to Figure 1's sample output, you might want to replace the digits 0, 1, 2, and 3 with other symbols to make it look like a drawing. Later in the article, I provide an example of how to achieve this effect.
Now let's implement the algorithm in T-SQL to test our T-SQL skills. Because T-SQL is a relational environment, you'd probably prefer to store the automation states in a table, then use a query to return the results in an ordered fashion, rather than just using variables and PRINT statements as you would in most programming environments. I envisioned a table with two columns. One column, a key column called num_step, determines the generation number that you use in the ORDER BY clause of a query that produces the desired output. The other column, step, holds the string of digits that you generated. Because each run of the algorithm generates a different output, I thought that writing a table-valued UDF that returns the table I envisioned would be a better idea than creating a real table. Using such a UDF would make the code that generates the output shorter and cleaner than creating, querying, then dropping a real table. By using a UDF, you could get the desired output by performing a SELECT query against the function as follows:
SELECT state FROM fn_get_automation_states(<input_arguments>) ORDER BY num_step
Initially, I thought that the replication rule and the number of desired automation steps would be the only parameters that the function fn_get_automation_states() would require. However, one of the puzzle's requirements is that each digit of the first state of the automation be randomly generated. This requirement means that you need to use the RAND() function to generate random values. The RAND() function, when invoked with no arguments, is by definition nondeterministic—that is, on different invocations, it returns different results. However, nondeterministic functions aren't allowed within UDFs, so you need to somehow produce the first automation state outside the UDF (by using a stored procedure, for example) and pass it to the UDF as an argument.
After you have all the input and output parameters for the fn_get_automation_states() function, you need to implement the function's algorithm, which is fairly simple. Beginning with this information
- Input: first_automation_state, rule, num_steps
- Output: steps table with columns num_step and state
you can write code based on the following pseudocode to implement the function's algorithm:
insert first_automation_state into the steps table while not handled all steps begin calculate next_automation_state insert next_automation_state into the steps table end
As I suggested earlier, using a modular approach here is advisable. You could calculate the next automation state inside the fn_get_automation_states() function. However, to keep things simple, you can write a scalar UDF called fn_next_automation_state(), which accepts an automation state and a replication rule as arguments and returns the next automation state. You now have all the information you need to write the fn_get_automation_states() function. Listing 1 shows the version of the fn_get_automation_states() function that I came up with.
Now you have to write the usp_first_automation_state stored procedure, which generates the first automation state as a string of 80 random digits, and the fn_next_automation_state() function, which generates the next automation state. Let's start with the stored procedure. The code constructs the first automation state in a loop. In each iteration, the loop calculates a random digit in the range 0 to 3 and concatenates it to the output parameter. Remember that the puzzle requires that each automation state starts and ends with a 0. Run the code that Listing 2, page 23, shows to create the usp_first_automation_state stored procedure.
The last step is to write the fn_next_automation_state() scalar function, which implements the kernel of the puzzle's algorithm. The function accepts an automation state as a string of 80 digits in the range 0 to 3 and a replication rule as a string of 10 digits in the range 0 to 3. Remember that the first and last digits of a step are always 0. The function forms a loop to handle digits 2 though 79. The algorithm calculates each digit in the resulting automation state, as I outlined in Steps 1 through 3 earlier.
The following T-SQL code is a translation of the main algorithm that the fn_next_automation_state() function implements:
SUBSTRING( @rule, CAST(SUBSTRING(@state, @pos - 1, 1) AS int) + CAST(SUBSTRING(@state, @pos, 1) AS int) + CAST(SUBSTRING(@state, @pos + 1, 1) AS int) + 1, 1),
In this code, @state is the input automation state, @rule is the automation rule, and @pos is the current digit's position. You can run the script that Listing 3, page 23, shows to create the fn_next_automation_state() function.
You can now use the code that Listing 4, page 23, shows to invoke the usp_first_automation_state stored procedure to generate the first automation state, then invoke the fn_get_automation_states() function to generate the required output. (Run the code in Query Analyzer text mode.) To make the output look more like a drawing, I used the code that Listing 5, page 23, shows to replace the digits 0, 1, 2, and 3 with space, dot, lowercase o, and uppercase O characters, respectively.
Figure 2 and Figure 3 show a couple of drawings (abbreviated to fit in print) that my example code produced. Note that the first automation state is generated randomly, so you get a different drawing each time you run the code.
I hope that you've enjoyed drawing with T-SQL. In case you were wondering, I won't cover surreal drawings in my next column. However, I'll stay in the area of graphical and geometrical problems and discuss a scenario that will put your knowledge of geometry to the test.