Updated 2015-07-02 17:26:39 by AMG

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.