ASCII Cayley Graph

26

2

While doing some research for a different challenge I'm formulating, I came across a Cayley graph, specifically this one. Since I'm one of the top challenge writers, of course I had to make an ASCII art challenge for this.

Your challenge is to produce this ASCII art depiction of a Cayley graph of the free group on two generators as follows:

                                               +                                               
                                              +++                                              
                                             + | +                                             
                                            ++-+-++                                            
                                             + | +                                             
                                          +    |    +                                          
                                         +++   |   +++                                         
                                        + |    |    | +                                        
                                       ++-+----+----+-++                                       
                                        + |    |    | +                                        
                                         +++   |   +++                                         
                                          +    |    +                                          
                                   +           |           +                                   
                                  +++          |          +++                                  
                                 + | +         |         + | +                                 
                                ++-+-++        |        ++-+-++                                
                                 + | +         |         + | +                                 
                              +    |           |           |    +                              
                             +++   |           |           |   +++                             
                            + |    |           |           |    | +                            
                           ++-+----+-----------+-----------+----+-++                           
                            + |    |           |           |    | +                            
                             +++   |           |           |   +++                             
                              +    |           |           |    +                              
                                 + | +         |         + | +                                 
                                ++-+-++        |        ++-+-++                                
                                 + | +         |         + | +                                 
                    +             +++          |          +++             +                    
                   +++             +           |           +             +++                   
                  + | +                        |                        + | +                  
                 ++-+-++                       |                       ++-+-++                 
                  + | +                        |                        + | +                  
               +    |    +                     |                     +    |    +               
              +++   |   +++                    |                    +++   |   +++              
             + |    |    | +                   |                   + |    |    | +             
            ++-+----+----+-++                  |                  ++-+----+----+-++            
             + |    |    | +                   |                   + |    |    | +             
              +++   |   +++                    |                    +++   |   +++              
               +    |    +                     |                     +    |    +               
        +           |                          |                          |           +        
       +++          |                          |                          |          +++       
      + | +         |                          |                          |         + | +      
     ++-+-++        |                          |                          |        ++-+-++     
      + | +         |                          |                          |         + | +      
   +    |           |                          |                          |           |    +   
  +++   |           |                          |                          |           |   +++  
 + |    |           |                          |                          |           |    | + 
++-+----+-----------+--------------------------+--------------------------+-----------+----+-++
 + |    |           |                          |                          |           |    | + 
  +++   |           |                          |                          |           |   +++  
   +    |           |                          |                          |           |    +   
      + | +         |                          |                          |         + | +      
     ++-+-++        |                          |                          |        ++-+-++     
      + | +         |                          |                          |         + | +      
       +++          |                          |                          |          +++       
        +           |                          |                          |           +        
               +    |    +                     |                     +    |    +               
              +++   |   +++                    |                    +++   |   +++              
             + |    |    | +                   |                   + |    |    | +             
            ++-+----+----+-++                  |                  ++-+----+----+-++            
             + |    |    | +                   |                   + |    |    | +             
              +++   |   +++                    |                    +++   |   +++              
               +    |    +                     |                     +    |    +               
                  + | +                        |                        + | +                  
                 ++-+-++                       |                       ++-+-++                 
                  + | +                        |                        + | +                  
                   +++             +           |           +             +++                   
                    +             +++          |          +++             +                    
                                 + | +         |         + | +                                 
                                ++-+-++        |        ++-+-++                                
                                 + | +         |         + | +                                 
                              +    |           |           |    +                              
                             +++   |           |           |   +++                             
                            + |    |           |           |    | +                            
                           ++-+----+-----------+-----------+----+-++                           
                            + |    |           |           |    | +                            
                             +++   |           |           |   +++                             
                              +    |           |           |    +                              
                                 + | +         |         + | +                                 
                                ++-+-++        |        ++-+-++                                
                                 + | +         |         + | +                                 
                                  +++          |          +++                                  
                                   +           |           +                                   
                                          +    |    +                                          
                                         +++   |   +++                                         
                                        + |    |    | +                                        
                                       ++-+----+----+-++                                       
                                        + |    |    | +                                        
                                         +++   |   +++                                         
                                          +    |    +                                          
                                             + | +                                             
                                            ++-+-++                                            
                                             + | +                                             
                                              +++                                              
                                               +

Input

No input, unless your language explicitly requires input to run.

Output

The ASCII art representation shown above.

MD5 Hashes

Since this is a pretty large output, to check your work here are some MD5 hashes of example forms of output (all are UTF-8 without BOM):

  • Square space padding, CR/LF linefeeds, and trailing newline -- 954B93871DAAE7A9C05CCDF79B00BF3C -- this is the representation used above.
  • Square space padding, CR/LF linefeeds, no trailing newline -- 28405EF91DA305C406BD03F9275A175C
  • Square space padding, LF linefeeds, and trailing newline -- 8CA65FB455DA7EE5A4C10F25CBD49D7E
  • Square space padding, LF linefeeds, no trailing newline -- FDB1547D68023281BB60DBEC82C8D281
  • No trailing spaces, CR/LF linefeeds, and trailing newline -- 77FDE8CE5D7BD1BDD47610BA23264A19
  • No trailing spaces, CR/LF linefeeds, no trailing newline -- EAD390C3EFD37F0FCACE55A84B793AB5
  • No trailing spaces, LF linefeeds, and trailing newline -- 1F6CAB740F87881EB2E65BED65D08C36
  • No trailing spaces, LF linefeeds, no trailing newline -- 7D41CE1E637619FEA9515D090BFA2E9C
  • If there is an additional MD5 you would like for comparison, please let me know and I'll create it and update the challenge.

Rules

  • Leading or trailing newlines or whitespace are all optional, so long as the characters themselves line up correctly.
  • Either a full program or a function are acceptable. If a function, you can return the output rather than printing it.
  • If possible, please include a link to an online testing environment so other people can try out your code!
  • Standard loopholes are forbidden.
  • This is so all usual golfing rules apply, and the shortest code (in bytes) wins.

AdmBorkBork

Posted 2017-03-14T18:19:03.200

Reputation: 41 581

I'm slightly surprised this isn't parametrised in any way - it looks as if it should be the sixth in a sequence. – Neil – 2017-03-14T18:30:38.150

This anarchy golf challenge is very similar.

– James – 2017-03-14T18:33:14.977

@Neil I had considered doing so, but decided against it for fear that it would increase the difficulty too much for little gain. – AdmBorkBork – 2017-03-14T18:33:26.657

Looks like the runs of -/|s follow the formula (2<<n)-n-2 rather than (1<<n)-1 which is what my original guess would have been. – Neil – 2017-03-14T19:25:30.533

@Neil They're actually Eulerian numbers, since that provided the best aesthetic.

– AdmBorkBork – 2017-03-14T19:30:09.750

Why in the "last iteration" it started to overlap ;-; <cries in recursive> – Rod – 2017-03-14T19:57:35.253

Cool highscores listing! I'm 6th in [tag:ascii-art]! I didn't know S.E. had this feature; neato. – Magic Octopus Urn – 2017-03-16T13:52:59.037

Answers

9

JavaScript (ES6), 204 195 188 180 bytes

f=
_=>[...Array(9119)].map((_,i)=>~i%96?g(48+~(i/96),47-i%96,5):`
`,g=(x,y,z,n=(1<<z)-z)=>x|y?(x=x<0?-x:x)+(y=y<0?-y:y)<n?` |-+`[2*!x+!y]:z--?x>y?g(x-n,y,z):g(x,y-n,z):` `:`+`).join``
;document.write(`<pre>`+f())

Square space padding, LF linefeeds, and no trailing newline, although I haven't checked the MD5.

f=
m=>[...Array((w=(4<<m)-m*-~m-2)*~-w)].map((_,i)=>~i%w?g(w/2+~(i/w),w/2-i%w-1,m):`
`,g=(x,y,z,n=(1<<z)-z)=>x|y?(x=x<0?-x:x)+(y=y<0?-y:y)<n?` |-+`[2*!x+!y]:z--?x>y?g(x-n,y,z):g(x,y-n,z):` `:`+`).join``
<input type=number min=0 oninput=o.textContent=f(this.value)><pre id=o>+

Parametrised version for 222 216 207 199 bytes. Explanation: The output size is 9119 ASCII characters, including 46 newlines. (For the parametrised version, the output size is calculated including the trailing newline.) Each character is individually determined, firstly by checking whether a newline is due, otherwise by calling a function on the coordinates relative to the origin in the middle of the final diagram. The function recursively checks the point against the nearest crosses of each size to the point, and returns the appropriate character depending on whether the point is discovered to lie on the centre or axis of a cross.

Neil

Posted 2017-03-14T18:19:03.200

Reputation: 95 035

7

Röda, 284 280 238 234 bytes

{a=[1,-1]t=[]seq 1,95|t+=[" "]*95,_
f={|x,y,i,d|{s=[27,12,5,2,1][i]i++
a|{|j|{seq y,y+s*j|t[_][x]="|"f x,y+s*j,i,2-j}if[d!=2+j]}_
a|{|j|{seq x,x+s*j|t[y][_]="-"f x+s*j,y,i,3-j}if[d!=3+j]}_}if[i<5]
t[y][x]="+"}f 47,47,0,0
t|print _&""}

Try it online!

This is an anonymous function. I used newlines instead of semicolons so it is very nicely formatted!

The recursive function f creates the graph in a two-dimensional array t, which is then printed at the last line.

I didn't find a way to calculate 27,12,5,2,1 in few bytes, so they are hard-coded.

fergusq

Posted 2017-03-14T18:19:03.200

Reputation: 4 867

Is there no way to calculate powers of 2? – Neil – 2017-03-14T22:33:51.177

@Neil A b_shiftl operator exists, but it's too long to be used in this program, I think. – fergusq – 2017-03-15T18:17:33.390

Only thing I can think of is maybe base-3? Dunno how good Roda is at base conversion though... 10000110001200020001 -> 1168671727 doubt you can convert and split with less than 2 bytes though heh... – Magic Octopus Urn – 2017-03-16T13:56:14.017

3

Charcoal, 50 43 bytes

Ｆ³²⁴«Ｐ++↷ＡＥ…¹¦⁵∧¬﹪ιＸ³κ⁻Ｘ²⁺κ¹⁺κ²εＦ⁺ε⮌ε¿κ«+κ↶

Try it online! Link is to verbose version of code. I originally tried various reflections and rotations but they either didn't do what I want or in some cases were buggy. I then tried a nested loop approach but I've now switched to this iterative method which works by drawing a number of lines between each inner cross depending on how many powers of 3 the step number is divisible by. It can even be readily modified to accept a size parameter at a cost of only 4 bytes:

ＮβＦ×⁴Ｘ³β«Ｐ++↷ＡＥ…·¹β∧¬﹪ιＸ³κ⁻Ｘ²⁺κ¹⁺κ²εＦ⁺ε⮌ε¿κ«+κ↶

Edit: I've since worked out how to use RotateShutterOverlap to achieve this task, but annoyingly it takes me 44 bytes:

Ａ⁰ηＦ⁶«ＡηγＡ⁻⁺Ｘ²ιηιηＪη⁰Ｐ-γ+¿γ⟲ＳＯ²⁶⁻×²γ¹»‖⟲ＳＯ⁹⁵

If RotateShutterOverlap accepted a variable rotations integer, that would reduce it to 40 bytes:

Ａ⁰ηＦ⁶«Ａ∨η¹γＡ⁻⁺Ｘ²ιηιηＪη⁰Ｐ+γ+⟲ＳＯ⎇‹ι⁵Ｌβ²⁴⁶γ

As it is, using a rotations list parameter takes 45 bytes:

Ａ⁰ηＦ⁶«Ａ∨η¹γＡ⁻⁺Ｘ²ιηιηＪη⁰Ｐ+γ+⟲ＳＯ⟦⁶ײ⁺¹⁼⁵ι⟧⁻ײγ¹

Neil

Posted 2017-03-14T18:19:03.200

Reputation: 95 035

This feels like cheating to me. :P – HyperNeutrino – 2017-05-26T01:08:54.760

@HyperNeutrino Slightly less hardcoded version: Try it online! Or is that not what you meant?

– Neil – 2017-05-26T20:04:09.647

:P I meant this is way too short and way too easy for Charcoal :P – HyperNeutrino – 2017-05-26T20:05:18.660

@Neil :O This is amazing! I'm wondering if you could give an example of a buggy reflection/rotation so I can fix it – ASCII-only – 2017-05-30T10:38:08.833

@ASCII-only In the case of a buggy reflection, I think only one of the diagonal reflections was working, but I can't remember which. I think the error was an undefined variable (probably too much copypasta). – Neil – 2017-05-30T10:41:32.873

@Neil Would you mind trying to reproduce the bug? I have testcases for reflection but it appears that I don't have enough – ASCII-only – 2017-05-30T10:43:18.353

@ASCII-only It was ReflectMirror. I don't know about Reflect...Overlap, I can't work out how to get them to parse. – Neil – 2017-05-30T11:20:26.593

@Neil For the ...Overlap commands you need to specify the amount of overlap after the rest of the arguments – ASCII-only – 2017-05-30T11:25:42.250

@ASCII-only I was trying ReflectOverlapOverlap([:UpLeft, :UpRight, :DownLeft, :DownRight], 0); but I don't even get a parse error, although I do for for (InputString()) Cast(Equals(i, "0")); for some reason... – Neil – 2017-05-31T08:00:08.857

Let us continue this discussion in chat.

– ASCII-only – 2017-05-31T08:06:15.723

2

05AB1E, 620 bytes

•1dOœ˜‘Av–Qs†ƒFã&äuÌʹÝ2býádÙI’´Ëœ¼)Y»+™ß›[Vg“Ò¢Jù1no<V<*Ét*-¢&â-ßBÆ×090`11-øsµ–¶1VÛ==ü:¼÷ØûÍZ„æ¹=#ùÞV«¡fä&Έ'ëˆÝ=ä^‰¤?Êçù!ØèØr-3îÛ+êò‚û¢½°BéG¦U”Ü1žˆr6S‹“ŽKRK°A¹ª¿â9]}×u¬]ž„Îï›V¦Â¶4Ãï¢v£×é´Ü2Äžiqô>§17F*ÎañníÆ4]s8mÏ›HSÏ771í´‰d3´Þ|À]Uà{þñýqø’e„XÿF4–:Yl&uqžÍÒÿ¾u9¤jóHP‰çêoÒNŠX-°xpÒÿ*ejÏD0Ë+GnÊ-/§3ÜJÙˆƒÌ=ŒÒOX‰|O%wæ[n‹ã4)ôF+~´Ö{aÄ$(Þí¼”÷u–qÿBòfÂíÜìTó–xÝwû¾])<§O«\‚e°‡¾‹K…ZDPô;µ!ò&Ô¼¨1gŠ—Ÿ¦©zW¢¾×4K±ÔÄ_ìûÄ‚3¶Ñ>‚bùn±œ×)ÙCâRö裶”ˆ1ßÑֱͮ[ZéRïyÓxÓE¨cW˜{Ã’ùoE›¥ÚvA¨‹êÆýÑY½RÎ5´‘Ê™uåÄr"ãYð÷I!0¤)å‡ëž”>úèWò}é€@.ØñÈQ€ñ{Á„‘Ü’‰~Çñ=…|“ڃĬcóÇkþÛÇ–š;{¡¦½ÕrÎé–àTz€Kì2à^|¢èˆÎxž“å$œ2ô»EidœþFrSS¥ÝÜ—X¡á~îþQ˜NÜGñ¥Q)aè•4B"1230"" +-|"‡48ôû€û»

Try it online!

All I did was cut the pattern into fourths, converted the symbols to base-4, compressed 1/4 of the pattern into base-214 and then flipped it over the lines of symmetry. I'm working on something smarter using the actual algorithm, but until I finish that this is what'll be here for me.

Magic Octopus Urn

Posted 2017-03-14T18:19:03.200

Reputation: 19 422

4That's by far the largest 05AB1E answer I have seen. xD Usually it's close to 6.20 instead of 620 with answers in this language. ;) – Kevin Cruijssen – 2017-03-15T08:25:21.107

@KevinCruijssen if it was asking for iteration 4 it would've been much-much smaller haha. Still working on the actual algorithm in 05AB1E... Bit harder than I thought. – Magic Octopus Urn – 2017-03-16T13:51:10.453

2

Python 3, 264 bytes

def F(g,p,d,k):
 for c in'-|'[d.real!=0]*(2**k-k-1):g[p]=c;p+=d
 P(g,p,k-1)
def P(g,p,k):
 if'+'==g.setdefault(p,'+')and k:
  for d in[1,1j,-1,-1j]:F(g,p+d,d,k)
g={}
P(g,0j,5)
print('\n'.join(''.join(g.get(r+c*1j,' ')for c in range(-47,48))for r in range(-47,48)))

Uses a pair of mutually recursive functions. F draws the lines and P inserts the '+'s. Can be golfed more, but out of time for now.

RootTwo

Posted 2017-03-14T18:19:03.200

Reputation: 1 749

1

C, 236 bytes

char t[95][95],i=95;f(x,y,s,n,m){if(t[y][x]<33){m=~s+(1<<s);for(n=~m;n++<m;)t[y][x+n]='-',t[y+n][x]=n==0?'+':'|';if(s--)f(x+n,y,s),f(x-n,y,s),f(x,y+n,s),f(x,y-n,s);}}main(){memset(t,32,9025);f(47,47,5);while(i--)printf("%.95s\n",t[i]);}

Just building the character table recursively before displaying it.

Try it online!

Thanks @Neil for making me realize that the length of the branches follow an actual rule.

dim lost faith in SE

Posted 2017-03-14T18:19:03.200

Reputation: 7 018

Asked: 2017-03-14T18:19:03.200

Viewed: 702 times

Active: 2017-06-18T11:04:18.917