AMG: Here's code to generate an ASCII Sierpiński triangle:
set size 32
set result {}
for {set y [expr {$size - 1}]} {$y >= 0} {incr y -1} {
set line [lrepeat $size " "]
for {set x $y} {$x < $size} {set x [expr {($x + 1) | $y}]} {
lset line $x #
}
lappend result [string range [join $line " "] $y end]
}
puts [join $result \n]And here's the output:
#
# #
# #
# # # #
# #
# # # #
# # # #
# # # # # # # #
# #
# # # #
# # # #
# # # # # # # #
# # # #
# # # # # # # #
# # # # # # # #
# # # # # # # # # # # # # # # #
# #
# # # #
# # # #
# # # # # # # #
# # # #
# # # # # # # #
# # # # # # # #
# # # # # # # # # # # # # # # #
# # # #
# # # # # # # #
# # # # # # # #
# # # # # # # # # # # # # # # #
# # # # # # # #
# # # # # # # # # # # # # # # #
# # # # # # # # # # # # # # # #
# # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # #arjen - 2015-07-02 06:44:46
Amazing! And elegant, even though I confess I have not studied the code in detail.
AMG: I happened across this property while developing an application-specific wildcard matching algorithm.
Let 0 be an exact match, * be a wildcard match, and suppose there are four fields to be matched. 0000 takes precedence over 000* over 00*0 over 00** over 0*00 over 0*0* ... over ****. Substitute 1 for * and treat as binary numbers, then 0 takes precedence over 1 over 2 over ... over 15, a very simple sequence to be sure.
In my application, I need the perhaps unusual property that wildcards only go one way. I can set up a record 0**0 where the *'s match anything, but if I then later search for a record with wildcards in it, those wildcards only match wildcards, e.g. when searching for 0**0 I can match only 0**0, 0***, ***0, or ****.
So what's that last sequence? Using the above conventions, it's 6, 7, 14, 15. The match itself has code 6. Now look to row 6 in this modified view of the above, obtained by prepending $y and outputting $x instead of #.
15 15 14 14 15 13 13 15 12 12 13 14 15 11 11 15 10 10 11 14 15 9 9 11 13 15 8 8 9 10 11 12 13 14 15 7 7 15 6 6 7 14 15 5 5 7 13 15 4 4 5 6 7 12 13 14 15 3 3 7 11 15 2 2 3 6 7 10 11 14 15 1 1 3 5 7 9 11 13 15 0 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
What numbers are found in row 6? 6, 7, 14, 15! This is the collection of all numbers (up to the size limit) which do not have a 0 bit anywhere 6 has a 1 bit.
The math for this couldn't be easier. To get the next number in any of these row sequences, simply increment then bitwise-OR the row number.