26
\$\begingroup\$

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.
\$\endgroup\$
  • \$\begingroup\$ I'm slightly surprised this isn't parametrised in any way - it looks as if it should be the sixth in a sequence. \$\endgroup\$ – Neil Mar 14 '17 at 18:30
  • \$\begingroup\$ This anarchy golf challenge is very similar. \$\endgroup\$ – DJMcMayhem Mar 14 '17 at 18:33
  • \$\begingroup\$ @Neil I had considered doing so, but decided against it for fear that it would increase the difficulty too much for little gain. \$\endgroup\$ – AdmBorkBork Mar 14 '17 at 18:33
  • \$\begingroup\$ 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. \$\endgroup\$ – Neil Mar 14 '17 at 19:25
  • \$\begingroup\$ @Neil They're actually Eulerian numbers, since that provided the best aesthetic. \$\endgroup\$ – AdmBorkBork Mar 14 '17 at 19:30
9
\$\begingroup\$

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.

\$\endgroup\$
7
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Is there no way to calculate powers of 2? \$\endgroup\$ – Neil Mar 14 '17 at 22:33
  • \$\begingroup\$ @Neil A b_shiftl operator exists, but it's too long to be used in this program, I think. \$\endgroup\$ – fergusq Mar 15 '17 at 18:17
  • \$\begingroup\$ 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... \$\endgroup\$ – Magic Octopus Urn Mar 16 '17 at 13:56
3
\$\begingroup\$

Charcoal, 50 43 bytes

F³²⁴«P++↷AE…¹¦⁵∧¬﹪ιX³κ⁻X²⁺κ¹⁺κ²εF⁺ε⮌ε¿κ«+κ↶

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:

NβF×⁴X³β«P++↷AE…·¹β∧¬﹪ιX³κ⁻X²⁺κ¹⁺κ²εF⁺ε⮌ε¿κ«+κ↶

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

A⁰ηF⁶«AηγA⁻⁺X²ιηιηJη⁰P-γ+¿γ⟲SO²⁶⁻×²γ¹»‖⟲SO⁹⁵

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

A⁰ηF⁶«A∨η¹γA⁻⁺X²ιηιηJη⁰P+γ+⟲SO⎇‹ι⁵Lβ²⁴⁶γ

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

A⁰ηF⁶«A∨η¹γA⁻⁺X²ιηιηJη⁰P+γ+⟲SO⟦⁶ײ⁺¹⁼⁵ι⟧⁻ײγ¹
\$\endgroup\$
  • \$\begingroup\$ This feels like cheating to me. :P \$\endgroup\$ – HyperNeutrino May 26 '17 at 1:08
  • \$\begingroup\$ @HyperNeutrino Slightly less hardcoded version: Try it online! Or is that not what you meant? \$\endgroup\$ – Neil May 26 '17 at 20:04
  • \$\begingroup\$ :P I meant this is way too short and way too easy for Charcoal :P \$\endgroup\$ – HyperNeutrino May 26 '17 at 20:05
  • \$\begingroup\$ @Neil :O This is amazing! I'm wondering if you could give an example of a buggy reflection/rotation so I can fix it \$\endgroup\$ – ASCII-only May 30 '17 at 10:38
  • \$\begingroup\$ @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). \$\endgroup\$ – Neil May 30 '17 at 10:41
2
\$\begingroup\$

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.

\$\endgroup\$
  • 4
    \$\begingroup\$ That'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. ;) \$\endgroup\$ – Kevin Cruijssen Mar 15 '17 at 8:25
  • \$\begingroup\$ @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. \$\endgroup\$ – Magic Octopus Urn Mar 16 '17 at 13:51
2
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.