Essays/ConnectedFigures

Anton Sherwood writes in his blog http://bendwavy.org/wp/?p=1986

Takana

I had the idea to design a fantasy script from combinations of a small number of features: namely, sets of six of these twelve segments:

    _ _
   |_|_|
   |_|_|

 Using a fixed number of segments gives some built-in error-detection. There are 924 such subsets; discarding those that form disconnected graphs leaves 306, more than enough for a syllabary. (Nearly all scripts are descended from syllabaries, but syllabaries are underrepresented in fantasy.)

I set off to verify the number 306. After a wrong try, I could indeed generate all connected glyphs like the above.

Here's the code cleaned up a bit. The connected glyphs are in the good array, and each glyph can be drawn by the fmt verb.

   frame =: _4]\0 1 1 0 1 1 1 1 1 1 1 1 0 1 1 0
   #poss =: ($frame)$"1(,frame)#^:_1"1(#~6=+/"1)>,{12$<0 1
924
   neigh =: ((2|+/~i.4){_2]\"1]0 0 _1 0 1 0 0 _1 0 1,"_ 1]_1 _1 1 1,:_1 1 1 _1)
   #good =: ( #~ ( ] -: ] ([*.[:+./[:,/neigh*])^:_ (($frame)$[:(i.@:#=i.&1),) )"2 ) poss
306
   #bad =: poss-.good
618
   fmt =: [:{."1 (_4]\'?/\?/\/\\/\/?\/?')#~"0"2 {&(0j1 1)
   <"2 ({~10?#) fmt good NB. example of connected glyphs
+----+----+----+----+----+----+----+----+----+----+
|    |    |  \ |  \ |    |  \ | /\ |    |  \ |    |
|  / |   \| \/\|  /\|  /\|   \| \ \|/\  |/\/ |/   |
|\/\/|\/ /| /  |\/ /|\/\/|  \/| / /| /\/|\ \ |\/\/|
|  / | \/ | \  |    |    | \/ |    | \  |    |  / |
+----+----+----+----+----+----+----+----+----+----+
   <"2 ({~10?#) fmt bad NB. examples of non-connected figures
+----+----+----+----+----+----+----+----+----+----+
|    | /  |  \ |    |  \ | /  |  \ | /  |  \ |    |
|/ /\| \/ |/ / |/\ \| \ \|/  \|   \|/  \| \ \|/\ \|
| / /|\/ /| /\ |\  /|\ \ |\ \ |\/\ |\/  |  \/|   /|
| \  |    |  / |  / |  / |  / |  / |  / | \  | \/ |
+----+----+----+----+----+----+----+----+----+----+
   NB. to write all results to files:
   NB. 1!:2&(<'a2') ([:,/"2,&(10{a.)"1)^:2 ": ': ',"1 fmt good
   NB. 1!:2&(<'a1') ([:,/"2,&(10{a.)"1)^:2 ": ': ',"1 fmt bad

Each figure is represented by a 4x4 boolean matrix with those elements true where the corresponding element is drawn in the figure. The array frame is the mask of all possible segments.

The code that finds out if a figure is connected is an iteration. It starts from a boolean array with 1 only at exactly one segment of the figure, then repeatedly sets the neighbours of each segment where the corresponding element is true and intersects the results with the figure. The neighbours of each segment are precomputed in neigh. This iteration converges to a connected component of the figure, so we just have to compare this with the figure to see if it covers all of it.