Mapeie a sequência para a curva de Hilbert

27

Vamos mapear algumas strings para o espaço 2D, estilo fractal. Sua tarefa é calcular uma curva de Hilbert e colocar uma corda ao longo dela.

A curva de Hilbert, iterações 1 a 8

Tarefa

A tarefa é pegar a sequência de entrada de linha única e colocá-la ao longo de uma curva de Hilbert grande o suficiente para contê-la, mas não maior. Tente fazer com que o byte conte o mais baixo possível; afinal, isso é !

Condições

  • Quaisquer espaços a serem preenchidos com espaço em branco, mas o preenchimento não é necessário no final das linhas.
  • O início da linha deve estar no canto superior esquerdo e o final no canto inferior esquerdo.
  • Você pode criar um programa ou função.
  • Pode haver alguns novos casos de teste aparecendo, portanto, não codifique nada!

Bônus

Nota: Os bônus se acumulam assim: -50% & -20% on 100B= -20% on 50Bou -50% on 80B= 40B.

  • -50% Se a entrada for uma sequência de várias linhas, inverta o processo para criar a entrada original. Casos de teste para o bônus: basta usar os existentes (incluindo os casos de teste de bônus!)
  • -20% Se você retirar todo o espaço em branco desnecessário da saída (por exemplo, no final de uma linha).
  • -5% Se você não poluir o espaço para nome global (você entende o que eu quero dizer!)

Casos de teste

abcdefghijklmn

adef
bchg
 nij
 mlk


The quick brown fox jumps over the lazy dog.

Thn f ju
 ewooxpm
qckr rs 
ui btevo
    hlaz
    e  y
      do
      .g

E para o bônus de remoção de espaço em branco:

No  hitespac  her 

Noher

hesc
itpa

Entre os melhores

Para garantir que sua resposta seja exibida, inicie-a com um título, usando o seguinte modelo de remarcação:

# Language Name, N bytes

onde Nestá o tamanho do seu envio. Se você melhorar sua pontuação, poderá manter as pontuações antigas no título, identificando-as. Por exemplo:

# Ruby, <s>104</s> <s>101</s> 96 bytes

Se você quiser incluir vários números no cabeçalho (por exemplo, porque sua pontuação é a soma de dois arquivos ou você deseja listar as penalidades do sinalizador de intérpretes separadamente), verifique se a pontuação real é o último número no cabeçalho:

# Perl, 43 + 2 (-p flag) = 45 bytes

Você também pode transformar o nome do idioma em um link que será exibido no snippet da tabela de classificação:

# [><>](http://esolangs.org/wiki/Fish), 121 bytes
wizzwizz4
fonte
Se alguém puder fazer mais alguns casos de teste, isso seria apreciado.
wizzwizz4
Portanto, os caracteres devem ser representados por vértices da curva?
flawr
No..hitespac..her.onde os pontos são espaços, seria um caso de teste melhor para o bônus. (E atualmente, o caso de teste está faltando .)
Martin Ender
Se você estiver adotando a abordagem do sistema L, também poderá tentar http: // codegolf / questions / 48697 / ascii-l-system-renderer . Pode ajudá-lo a jogar suas respostas.
wizzwizz4

Respostas:

7

CJam, 119 117 113 112 109 * 0,5 * 0,8 = 43,6 bytes

Agradecemos a Dennis por economizar 1 byte.

Aqui está um começo ...

{+e`W<e~}:F;q_N-,4mLm]0aa{4\#4e!1=f*\:G[zGGW%zW%G].ff+2/{~.+~}%}@:L/\_N&{N/]z:z:~$1f>sS}{4L#' e]f{f=SF}N*N}?F

Teste a transformação direta . Teste a transformação inversa.

Tenho certeza de que há uma maneira mais curta de gerar a curva ...

Explicação

Primeiro, defino uma função para aparar algum elemento do final de uma matriz, porque preciso disso em vários lugares. Espera que a matriz e o elemento (dentro de uma matriz separada) estejam no topo da pilha.

{
  +  e# Append the element to the array.
  e` e# Run-length encode.
  W< e# Discard last run.
  e~ e# Run-length decode.
}:F; e# Store in F and discard.

Agora, a maioria do código determina o tamanho da curva de Hilbert necessária e a constrói como uma matriz 2D, onde os elementos são índices ao longo da curva. Eu construo isso com base na seguinte observação:

Considere a curva Hilbert 2x2:

01
32

A curva 4x4 Hilbert é:

0345
1276
ed89
fcba

Se subtrairmos o valor mínimo de cada quadrante (e os separarmos um pouco para maior clareza visual), obtemos:

03 01
12 32

21 01
30 32

Esse padrão é válido para qualquer tamanho. Isso significa que podemos construir o próximo nível a partir do atual, usando como os quatro quadrantes: a) a transposição do nível atual, b) o próprio nível atual, c) a transposição ao longo da anti-diagonal, d) novamente o nível atual em si. E então os compensamos 0, 1, 3, 2 vezes o tamanho do nível atual, respectivamente.

q           e# Read input.
_N-         e# Make a copy and remove all linefeeds.
,4mLm]      e# Take that string's length's logarithm with base 4, rounded up.
            e# This is the Hilbert curve level we need.
0aa         e# Push [[0]] as the level-0 Hilbert curve.
{           e# Store the Hilbert curve level in L. Then for each i from 0 to L-1...
  4\#       e#   Compute 4^i. This is the offset of the four quadrants.
  4e!1=     e#   Get [0 1 3 2] as the second permutation returned by 4e!.
  f*        e#   Multiply each of them by the offset.
  \:G       e#   Swap with the Hilbert curve so far and call it G.
  [         e#   Create an array with...
    z       e#     The transpose of G.
    G       e#     G itself.
    GW%zW%  e#     The anti-diagonal transpose of G.
    G       e#     G itself.
  ]
  .ff+      e#   Add the appropriate offsets to the indices in each of the four quadrants.
  2/        e# Split into a 2x2 grid.
  {         e# Map this onto each pair of quadrants...
    ~       e#   Dump both quadrants on the stack.
    .+      e#   Concatenate them line by line.
    ~       e#   Dump the lines on the stack.
  }%        e# Since this is a map, the lines will automatically be collected in an array.
}@:L/

Por fim, usamos essa curva de índices de Hilbert para aplicar a transformação apropriada à entrada:

\_        e# Swap the curve with the input and make another copy.
N&{       e# If the input contains linefeeds, execute the first block, else the second...
  N/      e#   Split the input into lines. The stack now has a grid of indices and a grid
          e#   of characters.
  ]z:z:~  e#   This is some weird transposition magic which zips up the indices with the
          e#   corresponding characters from both grids, and finally flattens the grid
          e#   into a linear list of index/character pairs. Those cells that don't have
          e#   characters due to trimmed whitespace in the input will be turned into
          e#   arrays containing only an index.
  $       e#   Sort the pairs (which sorts them by indices).
  1f>     e#   Discard the indices.
  s       e#   Flatten the result into a single string.
  S       e#   Leave a space on the stack to be trim trailing spaces later.
}{        e# or...
  4L#     e#   Compute the size of the Hilbert curve.
  ' e]    e#   Pad the input to that size with spaces.
  f{      e#   Map this block over lines of the curve, passing the padding input as an
          e#   additional parameter...
    f=    e#     For each index in the current line, select the appropriate character
          e#     from the padded input.
    SF    e#     Trim spaces from the end of the line.
  }
  N*      e#   Join the lines with linefeed characters.
  N       e#   Leave a linefeed on the stack to be trim trailing linefeeds later.
}?
F         e# We left either a space or a linefeed on stack... trim that character from
          e# the end of the string.
Martin Ender
fonte
3

Python 3, 467 434 423 457 451 426 386 374 342 291 304 * 80% * 95% = 231,04 bytes

A maneira como isso funciona é que eu faço a curva de Hilbert usando um sistema Lindenmayer e sigo as instruções esquerda, direita e frente ao longo de uma série de strings. Provavelmente, existem muitas maneiras de jogar golfe melhor; especialmente nas condicionais e na criação da matriz de strings. (Tentei, [" "*p for i in range(p)]mas as strings não suportam a atribuição de itens (aparentemente). Se eu conseguisse fazer isso funcionar, também poderia me livrar da junção)

Edit: Golfed alguns dos condicionais com graças a Dennis . E eu jogava golfe na série de cordas. E uma mudança sem byte, porque os resultados foram transpostos em comparação com os exemplos acima.

Edit: Implementado o bônus de remoção de espaço em branco.

Edit: Corrigido um erro no meu código de remoção de espaço em branco por mais seis bytes

Edit: Como essa resposta não polui o espaço para nome global, recebo o bônus de 5%, de acordo com o wizzwizz4 aqui .

Editar: Alterado como gé incrementado e decrementado. Agora usando eval()e str.translate.

Editar: Esta resposta agora é um programa em vez de uma função.

Editar: Corrigidos alguns erros do golfe anterior.

s=input();m=(len(bin(len(s)-1))-1)//2;t=eval("[' ']*2**m,"*2**m);t[0][0],*s=s;x=y=g=0;b="A";exec("b=b.translate({65:'-BF+AFA+FB-',66:'+AF-BFB-FA+'});"*m)
while s:
 c,*b=b;g+=(c<"-")-(c=="-")
 if"B"<c:x,y=[[x+1-g%4,y],[x,y+g%4-2]][g%2];t[x][y],*s=s
print("\n".join(''.join(i).rstrip()for i in t).rstrip())

Ungolfed:

# hilbert(it) is now implemented in the code with exec("b=b.translate")

def hilbert(it):
    s="A"
    n=""
    for i in range(it):
        for c in s:
            if c == "A":
                n += "-BF+AFA+FB-"
            elif c == "B":
                n += "+AF-BFB-FA+"
            else:
                n += c
        s=n;n=""
    return s

def string_to_hilbert(string):
    length = len(string)
    it = (len(bin(length-1))-1)//2
    hil = hilbert(it)
    pow_2 = 2**it
    # we use eval("[' ']*pow_2,"*pow_2) in the code, but the following is equivalent
    output = [[" "for j in range(pow_2)] for i in range(pow_2)]
    output[0][0] = string[0]
    x = 0
    y = 0
    heading = 0
    while string: # while there are still characters in string
        char, *hil = hil
        if char == "-": heading = heading - 1
        elif char == "+": heading = heading + 1
        elif char == "F":
            if heading % 4 == 3: y += 1
            elif heading % 4 == 2: x -= 1
            elif heading % 4 == 1: y -= 1
            else: x += 1
            output[x][y], *string = string
    array = [''.join(i).rstrip()for i in output]
    array = "\n".join(array).rstrip()
    print(array)
    return
Sherlock9
fonte
Curioso sobre o bônus de 5%. As variáveis ​​são automaticamente locais no Python?
Edc65
@ edc65 Perguntei ao escritor do desafio uma coisa semelhante aqui: chat.stackexchange.com/transcript/240?m=28529277#28529277 . Espero que isso ajude um pouco. Caso contrário, podemos continuar a discussão no chat.
Sherlock9
2

Ruby, 358 356 344 322 319 * 80% * 95% = 242,44 bytes

Este é o meu código Python transpilado para Ruby. Eu deveria escrever mais respostas em Ruby. É uma linguagem decente para jogar golfe.

Edit: Eu esqueci que as funções não precisam ser nomeadas nesta pergunta.

Edit: Como essa resposta não polui o espaço para nome global, recebo o bônus de 5%, de acordo com o wizzwizz4 aqui .

->s{l=s.size;m=((l-1).bit_length+1)/2;x=2**m;t=(1..x).map{[" "]*x};t[0][0]=s[0];x=y=g=z=0;d=1;b=?A;m.times{b=b.split("").map{|c|c==?A?"-BF+AFA+FB-":c==?B?"+AF-BFB-FA+":c}.join("")};(c=b[z];z+=1;g+=c<?-?1:c==?-?-1:0;(g%2>0?y+=g%4-2:x+=1-g%4;t[x][y]=s[d];d+=1)if c>?B)while d<l;puts (t.map{|i|(i*'').rstrip}*"\n").rstrip}

Ungolfed:

def map_string(string)
  len = string.size
  m = ((len-1).bit_length+1)/2
  pow = 2**m
  output = (1..pow).map{[" "]*pow}
  output[0][0] = s[0]
  x = y = heading = char_index = 0
  chars_in_output = 1
  b = ?A
  m.times do |j|
    a = b.split("").map do |char|
      if char == "A"
        "-BF+AFA+FB-"
      else if char == "B"
        "+AF-BFB-FA+"
      else
        char
      end
    end
    b = a.join("")
  end
  while chars_in_output < len
    char = b[char_index]
    char_index += 1
    if char == "-"
      heading += -1
    else if char == "+"
      heading += 1
    else if char == "F"
      if heading % 2 == 0
        y += heading % 4 - 2
      else
        x += 1 - heading % 4
      end
    end
    output[x][y] = string[char_index]
    char_index += 1
  end
  return (output.map{|i|(i*'').rstrip}*"\n").rstrip
Sherlock9
fonte
Esse código tem licença dupla sob uma licença de código? Gostaria de produzir um trabalho derivado lançado sob a GPL (embora qualquer licença compatível com GPL funcione com isso). Atualmente, é lançado sob o CC BY-SA 3.0.
wizzwizz4
@ wizzwizz4 Bate-papo aqui: chat.stackexchange.com/rooms/56405/…
Sherlock9
1

JavaScript (ES6), 227 - 20%: 181,6 bytes

m=>{for(n=1<<((33-Math.clz32(m.length-1))/2),t='',y=0;y<n;y++,t+=`
`)for(x=0;x<n;x++,t+=m[h]||' ')for(u=y,v=x,h=0,s=n;s>>=1;q||(p&&(u=s+~u,v=s+~v),[u,v]=[v,u]))h+=s*s*(3*!!(p=u&s)^!!(q=v&s));return t.replace(/ +$/mg,'').trim()}

Tentando obter o bônus de 5%

m=>{for(var n=1<<((33-Math.clz32(m.length-1))/2),t='',x,y=0;y<n;y++,t+=`
`)for(x=0;x<n;x++,t+=m[h]||' ')for(var p,q,u=y,v=x,h=0,s=n;s>>=1;q||(p&&(u=s+~u,v=s+~v),[u,v]=[v,u]))h+=s*s*(3*!!(p=u&s)^!!(q=v&s));return t.replace(/ +$/mg,'').trim()}

241 * 0.8 * 0.95: 183.16 maior

Menos golfe

m=>
{
  // calc the size of the bounding square, clz32 is a bit shorter than ceil(log2()
  n = 1<<( (33-Math.clz32(m.length-1)) / 2); 
  t = '';
  for(y = 0; y < n; y++) 
  {
    for(x = 0 ; x < n; x++)
    {
      // for each position x,y inside the square
      // get the index postion in the hilbert curve
      // see https://en.wikipedia.org/wiki/Hilbert_curve (convert x,y to d)
      for(u=y, v=x, h=0, s=n; s >>= 1; )
      {
        h += s*s*(3 * !!(p = u & s) ^ !!(q = v & s));
        q || (p && (u = s+~u, v = s+~v),[u,v]=[v,u])
      }
      // add char at given index to output  
      t += m[h]||' '; // blank if beyond the length of m
    }
    t += '\n'; // add newline add end line
  }
  return t.replace(/ +$/mg,'').trim() // to get the 20% bonus
}  

Teste

F=m=>{for(n=1<<((33-Math.clz32(m.length-1))/2),t='',y=0;y<n;y++,t+=`
`)for(x=0;x<n;x++,t+=m[h]||' ')for(u=y,v=x,h=0,s=n;s>>=1;q||(p&&(u=s+~u,v=s+~v),[u,v]=[v,u]))h+=s*s*(3*!!(p=u&s)^!!(q=v&s));return t.replace(/ +$/mg,'').trim()}

function Test() { O.textContent = F(I.value) }

Test()
#I { width: 90% }
#O { border: 1px solid #ccc}
<input id=I oninput='Test()' value='The quick brown fox jumps over the lazy dog.'>
<pre id=O></pre>

edc65
fonte
Valeria a pena adicionar vars para obter o bônus de 5%?
Wizzwizz4
var s,x,y,u,v,t,p,q,n,hnão, não vale a pena @ wizzwizz4
edc65
Você pode colocar varantes do primeiro uso de cada um ... Oh, isso é ainda pior.
Wizzwizz4
@ wizzwizz4 apesar de tudo, talvez você tenha razão ... estou tentando ... não. Muito ruim
edc65 06/04