Sierpiński triangle

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.