ASCII Cayley Graph

26

Проводя некоторые исследования для другой задачи, которую я формулирую, я наткнулся на график Кейли , в частности, этот . Так как я являюсь одним из лучших авторов тестов для ascii-art , мне, конечно, пришлось сделать ASCII-арт-вызов для этого.

Ваша задача состоит в том, чтобы создать это художественное изображение ASCII графа Кэли свободной группы на двух генераторах следующим образом:

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

вход

Нет ввода, если только ваш язык явно не требует ввода для запуска.

Выход

Художественное представление ASCII показано выше.

MD5 Хеши

Поскольку это довольно большой вывод, для проверки вашей работы приведем несколько хэшей MD5 примеров форм вывода (все это UTF-8 без спецификации):

  • Квадратные пробелы, CR/LFпереводы строки и завершающий перевод строки 954B93871DAAE7A9C05CCDF79B00BF3C- это представление, использованное выше.
  • Квадратные отступы, CR/LFпереводы строки, без новой строки -28405EF91DA305C406BD03F9275A175C
  • Квадратные отступы, LFпереводы строки и завершающий перевод строки -8CA65FB455DA7EE5A4C10F25CBD49D7E
  • Квадратные отступы, LFпереводы строки, без новой строки -FDB1547D68023281BB60DBEC82C8D281
  • Нет завершающих пробелов, CR/LFперевода строки и завершающего перевода строки -77FDE8CE5D7BD1BDD47610BA23264A19
  • Нет завершающих пробелов, CR/LFперевода строки, нет завершающего перевода строки -EAD390C3EFD37F0FCACE55A84B793AB5
  • Нет завершающих пробелов, LFперевода строки и завершающего перевода строки -1F6CAB740F87881EB2E65BED65D08C36
  • Нет завершающих пробелов, LFперевода строки, нет завершающего перевода строки -7D41CE1E637619FEA9515D090BFA2E9C
  • Если есть дополнительный MD5, который вы хотите сравнить, пожалуйста, дайте мне знать, и я создам его и обновлю задачу.

правила

  • Начальные или завершающие символы новой строки или пробелы являются необязательными, при условии, что сами символы выстроены правильно.
  • Допустимы либо полная программа, либо функция. Если функция, вы можете вернуть вывод, а не распечатать его.
  • Если возможно, укажите ссылку на среду онлайн-тестирования, чтобы другие люди могли опробовать ваш код!
  • Стандартные лазейки запрещены.
  • Это код-гольф, поэтому применяются все обычные правила игры в гольф, и выигрывает самый короткий код (в байтах).
code-golf ascii-art kolmogorov-complexity fractal AdmBorkBork
источник
Я немного удивлен, что это никак не параметризуется - похоже, он должен быть шестым в последовательности.
Нил
Эта проблема анархии в гольф очень похожа.
DJMcMayhem
@Neil Я думал об этом, но решил не делать этого, опасаясь, что это увеличит сложность слишком сильно и мало что даст.
AdmBorkBork
Похоже, прогоны -/ |s следуют формуле, (2<<n)-n-2а не (1<<n)-1тому, что было бы моим первоначальным предположением.
Нил
@Neil Это на самом деле эйлеровы числа , поскольку это дало лучшую эстетику.
AdmBorkBork

Ответы:

9

JavaScript (ES6), 204 195 188 180 байт

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())
Развернуть фрагмент

Квадратные отступы, LF переводы строк и отсутствие завершающего перевода строки, хотя я не проверял 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>+
Развернуть фрагмент

Параметризованная версия для 222 216 207 199 байтов. Объяснение: Выходной размер составляет 9119 символов ASCII, включая 46 символов новой строки. (Для параметризованной версии выходной размер рассчитывается с учетом завершающей новой строки.) Каждый символ определяется индивидуально, во-первых, проверяя, следует ли вводить новую строку, в противном случае вызывая функцию с координатами относительно начала координат в середине финальной строки. диаграмма. Функция рекурсивно проверяет точку по ближайшим крестикам каждого размера к точке и возвращает соответствующий символ в зависимости от того, обнаружена ли точка, лежащая на центре или оси креста.

Нил
источник
7

Röda , 284 280 238 234 байта

{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 _&""}

Попробуйте онлайн!

Это анонимная функция. Я использовал символы новой строки вместо точек с запятой, так что он очень хорошо отформатирован!

Рекурсивная функция fсоздает график в двумерном массиве t, который затем печатается в последней строке.

Я не нашел способа вычислить 27,12,5,2,1в нескольких байтах, поэтому они жестко запрограммированы.

fergusq
источник
Нет ли способа рассчитать степени 2?
Нил
@Neil b_shiftlОператор существует, но я думаю, он слишком длинный, чтобы использоваться в этой программе.
fergusq
Единственное, о чем я могу думать, это, может быть, база-3? Не знаю, насколько хорош Рода в базовом преобразовании, хотя ... 10000110001200020001-> 1168671727сомневаюсь, что вы можете преобразовать и разделить менее чем на 2 байта, хотя хе ...
Магический Осьминог Урна
3

Древесный уголь , 50 43 байта

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

Попробуйте онлайн! Ссылка на подробную версию кода. Первоначально я пробовал разные отражения и повороты, но они либо не делали то, что я хочу, либо в некоторых случаях глючили. Затем я попробовал подход с вложенным циклом, но теперь я переключился на этот итерационный метод, который работает, рисуя количество линий между каждым внутренним крестом в зависимости от того, на сколько степеней 3 делится число шага. Его можно легко изменить, чтобы он принимал параметр размера по цене всего 4 байта:

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

Изменить: с тех пор я разработал, как использовать RotateShutterOverlapдля достижения этой задачи, но, к сожалению, это занимает у меня 44 байта:

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

Если RotateShutterOverlapбы переменная вращалась целым числом, это уменьшило бы ее до 40 байт:

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

Таким образом, использование параметра списка вращений занимает 45 байтов:

Ａ⁰ηＦ⁶«Ａ∨η¹γＡ⁻⁺Ｘ²ιηιηＪη⁰Ｐ+γ+⟲ＳＯ⟦⁶ײ⁺¹⁼⁵ι⟧⁻ײγ¹
Нил
источник
Это похоже на измену мне. : P
HyperNeutrino
@HyperNeutrino Чуть менее жесткая версия: попробуйте онлайн! Или это не то, что вы имели в виду?
Нил
: PI означало, что это слишком коротко и слишком легко для древесного угля: P
HyperNeutrino
@Neil: O это удивительно! Мне интересно, не могли бы вы привести пример глючного отражения / поворота, чтобы я мог это исправить
только ASCII
@ ASCII-only В случае глючного отражения, я думаю, что работало только одно из диагональных отражений, но я не могу вспомнить, какое именно. Я думаю, что ошибка была неопределенной переменной (вероятно, слишком много copypasta).
Нил
2

05AB1E , 620 байт

•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ôû€û»

Попробуйте онлайн!

Все, что я сделал, это разрезал шаблон на четверти, преобразовал символы в base-4, сжал 1/4 шаблона в base-214 и затем перевернул его по линиям симметрии. Я работаю над чем-то более умным, используя настоящий алгоритм, но пока я не закончу, это то, что будет здесь для меня.

Урна волшебного осьминога
источник
4
Это самый большой 05AB1Eответ, который я видел. xD Обычно это 6,20 вместо 620 с ответами на этом языке. ;)
Кевин Круйссен
@KevinCruijssen, если бы он запрашивал итерацию 4, это было бы намного меньше, ха-ха. Все еще работаю над реальным алгоритмом в 05AB1E ... Немного сложнее, чем я думал.
Волшебный Осьминог Урна
2

Python 3, 264 байта

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)))

Использует пару взаимно рекурсивных функций. F рисует линии, а P вставляет «+». Можно больше играть в гольф, но сейчас не вовремя.

RootTwo
источник
1

C 236 байт

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]);}

Просто рекурсивно строим таблицу символов перед ее отображением.

Попробуйте онлайн!

Спасибо @Neil за то, что я понял, что длина ветвей соответствует действующему правилу.

тусклый
источник