O que é a sequência de palitos de dente?

De acordo com a Wikipedia

Na geometria, a sequência de palitos de dentes é uma sequência de padrões bidimensionais que podem ser formados adicionando repetidamente segmentos de linha ("palitos de dentes") ao padrão anterior na sequência.

A primeira etapa do design é um único "palito" ou segmento de linha. Cada estágio após o primeiro é formado pelo desenho anterior e, para cada extremidade do palito exposto, colocando outro palito centrado em ângulo reto nessa extremidade.

Esse processo resulta em um padrão de crescimento no qual o número de segmentos no estágio n oscila com um padrão fractal entre 0,45n2 e 0,67n2. Se T (n) denota o número de segmentos no estágio n, os valores de n para os quais T (n) / n2 está próximo de seu máximo ocorrem quando n está próximo de uma potência de dois, enquanto os valores para os quais está próximo de seu mínimo ocorrem perto de números que são aproximadamente 1,43 vezes a potência de dois. A estrutura dos estágios na sequência do palito de dentes geralmente se assemelha ao fractal do quadrado T, ou ao arranjo de células no autômato celular Ulam – Warburton.

Todas as regiões delimitadas cercadas por palitos no padrão, mas não elas mesmas atravessadas por palitos, devem ser quadrados ou retângulos. Foi conjeturado que todo retângulo aberto no padrão de palito (ou seja, um retângulo que é completamente cercado por palitos, mas não tem palito cruzando seu interior) tem comprimentos laterais e áreas com potências de dois, com um dos comprimentos laterais sendo no máximo duas.

Tarefa

Você deve criar um programa ou função que receba entrada de STDIN, argumento de função ou argumento de linha de comando e criar um fractal de palpite nesse estágio. A nova linha inicial e final é proibida, exceto se for inevitável. A caixa delimitadora deve estar no mínimo, incluindo espaço à esquerda e à direita. Para a linha inicial, fazemos duas \diagonais no espaço. A entrada é garantida em menos de dois mil. Pelo menos uma linha tem um caractere não espacial. Espaço à direita é permitido.

Casos de teste

1
\ 
 \     

5
    \     
    /\    
   /\     
  / /\   
\/\/\ \ \ 
 \ \ \/\/\
    \/ /  
     \/   
    \/    
     \    

CJam, 99 93 bytes

Isso ficou bastante longo ...

"\ "_W%]{{Sf+W%z}4*2ew{2fewz{_sa"\//\\"4S**4/^_,3={:.e>W%2/\}&;}%z{\)[email protected]>+}:Ff*}%{F}*}q~(*N*

Teste aqui. Se você quiser testar entradas maiores, como a 89 da Wikipedia, o TryItOnline de Dennis usa o interpretador Java muito mais rápido e pode lidar com entradas como essa em alguns segundos.

Tenho certeza de que há muito espaço para melhorias e adicionarei uma explicação assim que estiver mais feliz com a pontuação ...

Aqui está a saída para N = 13:

            \             
            /\            
           /\             
          / /\            
        \/\/\ \ \         
         \ \/\/\/\        
           /\/\/          
          / /\ \          
    \    /\/\ \     \     
    /\  /  \/\/\    /\    
   /\  /\  /\/  \ \/\     
  / /\/ /\/ /\  /\ \/\    
\/\/\/\/\/\/\ \/\ \/\ \ \ 
 \ \ \/\ \/\ \/\/\/\/\/\/\
    \/\ \/  \/ /\/ /\/ /  
     \/\ \  /\/  \/  \/   
    \/    \/\/\  /  \/    
     \     \ \/\/    \    
          \ \/ /          
          /\/\/           
        \/\/\/\ \         
         \ \ \/\/\        
            \/ /          
             \/           
            \/            
             \            

Para minha própria referência ao jogar isso ainda mais, algumas outras idéias:

"\ "_W%]{{Sf+W%z}4*2few2ew::.{+_a"\//\\"4S**4/^_,3={:.e>W%\}&;2/}:z{\)[email protected]>+}ff*{\)[email protected]>+}*}ri(*N*

"\ "_W%]{{Sf+W%z}4*2ew{2fewz{_sa"\//\\"4S**4/^_,3={:.e>W%2/\}&;}%{.{\)[email protected]>+}}*}%{\)[email protected]>+}*}q~(*N*

JavaScript (ES6), 263 bytes

n=>(o=(o=[..." ".repeat(n*2)]).map(_=>o.map(_=>s=c=" ")),(g=a=>s++<n&&g(q=[],a.map(p=>o[p[4]][p[3]]==c&&(o[y=p[1]][x=p[0]]=o[y-1][(b=+p[2])?x-1:x+1]="/\\"[b],q.push([x,++y,!b,b?x+1:x-1,y],[b?x-=2:x+=2,y-2,!b,x,y-3])))))([[n,n,1,n,n]]),o.map(r=>r.join``).join`
`)

Explicação

n=>(                           // n = desired stage

  o=                           // o = output grid
                               //     [ [ "\\", " " ], [ " ", "\\" ], etc... ]
    (o=[..." ".repeat(n*2)])   // create an array the size of the grid
    .map(_=>o.map(_=>          // loop over it and return the output grid
      s=                       // s = current stage (" " acts the same as 0)
        c=                     // c = blank character
          " "                  // initialise each element to " "
    )),

  (g=                          // g = compute stage function
    a=>                        // a = positions to place toothpicks
                               //     [ x, y, isBackslash, checkX, checkY ]
      s++<n&&                  // do nothing if we have reached the desired stage
      g(q=[],                  // q = positions for the next stage's toothpicks
        a.map(p=>              // p = current potential toothpick position
          o[p[4]][p[3]]==c&&(  // check the position to make sure it is clear

            o[y=p[1]][x=p[0]]= // place bottom toothpick, x/y = position x/y
            o[y-1][            // place top toothpick
              (b=+p[2])        // b = isBackslash
              ?x-1:x+1         // top toothpick x depends on direction
            ]="/\\"[b],        // set the location to the appropriate character

            // Add the next toothpick positions
            q.push([x,++y,!b,b?x+1:x-1,y],
              [b?x-=2:x+=2,y-2,!b,x,y-3])
          )
        )
      )
  )([[n,n,1,n,n]]),            // place the initial toothpicks
  o.map(r=>r.join``).join`
` // return the grid converted to a string
)

Teste

Stages: <input type="number" oninput='result.innerHTML=(

n=>(o=(o=[..." ".repeat(n*2)]).map(_=>o.map(_=>s=c=" ")),(g=a=>s++<n&&g(q=[],a.map(p=>o[p[4]][p[3]]==c&&(o[y=p[1]][x=p[0]]=o[y-1][(b=+p[2])?x-1:x+1]="/\\"[b],q.push([x,++y,!b,b?x+1:x-1,y],[b?x-=2:x+=2,y-2,!b,x,y-3])))))([[n,n,1,n,n]]),o.map(r=>r.join``).join`
`)

)(+this.value)' /><pre id="result"></pre>

Ruby, 151 bytes

A versão Golfed usa apenas um loop,, jcom ie kcalculado em tempo real.

->n{m=n*2
s=(' '*m+$/)*m
l=m*m+m
s[l/2+n]=s[l/2-n-2]=?\\
(n*l-l).times{|j|(s[i=j%l]+s[i-m-2+2*k=j/l%2]).sum==124-k*45&&s[i-m-1]=s[i-1+2*k]="/\\"[k]}
s}

Ungolfed in program program

Esta versão usa 2 loops aninhados.

Um builtin raramente usado é o sumque retorna uma soma de verificação bruta adicionando todos os bytes de uma string ascii.

f=->n{
  m=n*2                                       #calculate grid height / width            
  s=(' '*m+$/)*m                              #fill grid with spaces, separated by newlines
  l=m*m+m                                     #calculate length of string s
  s[l/2+n]=s[l/2-n-2]=?\\                     #draw the first toothpick
  (n-1).times{|j|                             #iterate n-1 times
    l.times{|i|                               #for each character in the string
      (s[i]+s[i-m-2+2*k=j%2]).sum==124-k*45&& #if checksum of current character + character diagonally above indicates the end of a toothpick
         s[i-m-1]=s[i-1+2*k]="/\\"[k]         #draw another toothpick at the end
    }                                         
  }
s}                                            #return value = s


puts f[gets.to_i]