Código qualificado Sierpins

47

Escreva um bloco de texto retangular que, quando organizado em um tapete Sierpinski , usando espaços do mesmo tamanho para as partes vazias, cria um programa que gera o número de iteração do tapete.

Por exemplo, se o seu bloco de texto for

TXT
BLK

então executando o programa

TXTTXTTXT
BLKBLKBLK
TXT   TXT
BLK   BLK
TXTTXTTXT
BLKBLKBLK

deve sair 1porque a forma do programa representa a primeira iteração do tapete Sierpinski.

Da mesma forma, executando

TXTTXTTXTTXTTXTTXTTXTTXTTXT
BLKBLKBLKBLKBLKBLKBLKBLKBLK
TXT   TXTTXT   TXTTXT   TXT
BLK   BLKBLK   BLKBLK   BLK
TXTTXTTXTTXTTXTTXTTXTTXTTXT
BLKBLKBLKBLKBLKBLKBLKBLKBLK
TXTTXTTXT         TXTTXTTXT
BLKBLKBLK         BLKBLKBLK
TXT   TXT         TXT   TXT
BLK   BLK         BLK   BLK
TXTTXTTXT         TXTTXTTXT
BLKBLKBLK         BLKBLKBLK
TXTTXTTXTTXTTXTTXTTXTTXTTXT
BLKBLKBLKBLKBLKBLKBLKBLKBLK
TXT   TXTTXT   TXTTXT   TXT
BLK   BLKBLK   BLKBLK   BLK
TXTTXTTXTTXTTXTTXTTXTTXTTXT
BLKBLKBLKBLKBLKBLKBLKBLKBLK

deve gerar 2 porque esse é o formato da segunda iteração do tapete de Sierpinski.

Executando o bloco de texto como está

TXT
BLK

deve sair 0porque pode ser considerada a iteração zero.

Isso deve funcionar para todas as iterações adicionais. (Pelo menos teoricamente, supondo que o computador tenha memória e tudo.)

Detalhes

  • Os programas podem não ler ou acessar informações sobre seu código-fonte. Trate isso como um desafio estrito à questão.
  • A saída vai para stdout ou alternativa semelhante. Somente imprima o número e uma nova linha opcional à direita. Não há entrada.
  • O bloco de texto pode conter caracteres que não sejam considerados terminadores de linha . O bloco de texto pode conter espaços.
  • O "espaço vazio" no tapete deve consistir inteiramente em caracteres de espaço .
  • Opcionalmente, você pode assumir que todos os programas têm uma nova linha à direita.

Você pode usar esse snippet de pilha para gerar um tapete para um determinado bloco de texto em qualquer iteração:

<style>#o,#i{font-family:monospace;}</style><script>function c(e){e=e.split("\n");for(var n=new Array(3*e.length),t=0;t<n.length;t++){var l=t%e.length;n[t]=e[l]+(t>=e.length&&t<2*e.length?e[l].replace(/./g," "):e[l])+e[l]}return n.join("\n")}function f(){for(i=document.getElementById("i").value,n=parseInt(document.getElementById("n").value);n>0;)i=c(i),n--;document.getElementById("o").value=i}</script><textarea id='i'placeholder='code block...'rows='8'cols='32'></textarea><br>Iterations <input id='n'type='text' value='1'><br><br><button type='button'onclick='f()'>Generate</button><br><br><textarea id='o'placeholder='output...'rows='8'cols='32'style='background-color:#eee'readonly></textarea>

Pontuação

O envio cujo bloco de texto inicial é menor por área (largura x altura) é o vencedor. O TXT\nBLKexemplo é 3 por 2 para uma pontuação de 6. (Basicamente, o código mais curto vence, daí a tag code-golf.)

O desempatador vai para o envio que usa o menor número de caracteres distintos em seu bloco de texto. Se ainda estiver empatado, responda as primeiras vitórias postadas.

Passatempos de Calvin
fonte

Respostas:

23

CJam, 9 bytes

Eu acho que isso pode ser melhorado, mas por enquanto, vamos em frente ...

];U):U8mL

Como funciona :

];             "Wrap everything on stack in an array and discard it";
               "Before this point, the only thing on array can be the log 8 result of";
               "last updated value of U, or nothing, if its the first code";
  U):U         "Increment by 1 and update the value of U (which is pre initialized to 0)";
      8mL      "Take log base 8 of U. This is the property of Sierpinski carpet that";
               "the occurrence of the code is 8 to the power iteration count, indexed 0";

Experimente online aqui

Optimizer
fonte
35

piet - 32 * 6 = 192

insira a descrição da imagem aqui

Enchi o espaço vazio com o padrão de xadrez. Eu acho que isso torna o Sierpinski um pouco mais desonesto.

Aqui está a segunda iteração: insira a descrição da imagem aqui

original: 32 * 7

insira a descrição da imagem aqui

captncraig
fonte
19

> <> , 11 * 2 = 22

";n"00pbi1v
+$3*:@3-0.>

Aqui, adotamos uma abordagem diferente usando a funcionalidade de salto / teleporte de> <>.

O programa executa apenas blocos na linha superior, executando o 1º / 2º bloco, depois os 3º / 4º blocos, 9º / 10º blocos, 27º / 28º blocos, etc. (subindo em potências de 3). Como a linha superior possui 3^nblocos, apenas os nblocos são executados antes que o programa volte ao início, produza a parte superior da pilha e pare (devido à ninstrução colocada via p).

O programa explora a regra "Não há entrada", pois o icomando envia -1 para a pilha se o EOF for atendido. Portanto, para testar isso, você precisará inserir um arquivo vazio.


Submissão anterior, 7 * 4 = 28

l"v"10p
v>:1=?v
3  ;n{<
<^}+1{,

A primeira linha empurra continuamente o comprimento da pilha para cada bloco e altera a primeira "cotação para uma seta para baixo vusando o pcomando put. Quando a primeira linha termina, a pilha parece

[0, 1, 2, .., 3^n]

(Observe que a inicial lé usada duas vezes.)

As últimas três linhas contam quantas vezes precisamos dividir por 3 antes de atingirmos 1 (já que> <> não possui uma função de log). O zero inferior é usado para acompanhar a contagem.

Sp3000
fonte
13

Perl, 26

$_+=.91/++$n;
die int."\n";

Isso usa a série harmônica para aproximar o logaritmo da base 3. Eu acho que funciona, mas eu só tentei por números pequenos. Obrigado ao ossifrage melindroso pela idéia de usar die.

Versão antiga (34):

$n--or$n=3**$s++;
print$s-1if!$o++;
grc
fonte
Isso é muito legal!
Ossifrage melindroso
10

Perl, 30 (15 × 2)

Primeiro de tudo, vou afirmar que 10 iterações são um limite razoável, não 2 32 . Após 10 iterações, um programa que consiste em N bytes será expandido para ( N × 3 20 ) bytes (mais quebras de linha), com mais de 3 gigabytes, mesmo para N = 1. Uma arquitetura de 32 bits seria completamente incapaz de lidar com 11 iterações. (E, obviamente, não há partículas suficientes no universo para 2 32 iterações).

Então aqui está a minha solução:

$n++; $_=log$n;
print int;exit;

Isso funciona incrementando a variável $nna primeira linha e calculando seu logaritmo em cada etapa. A segunda linha imprime a parte inteira deste logaritmo e sai.

Um logaritmo simples para basear e (2.718 ..) está próximo o suficiente para fornecer resultados corretos para as 10 primeiras iterações.

ossifrage melindroso
fonte
2
De acordo com o OP, ele teoricamente deve funcionar para todas as iterações.
Nathan Merrill
2
@NathanMerrill Bem, OK. Mas, para cumprir com as especificações originais, também teria que trabalhar em universos alternativos. A pergunta foi editada desde então.
Ossifrage melindroso
Mudei de questão por causa dos bons pontos apresentados aqui. Concordo que o uso do log natural é uma área cinzenta, mas sinceramente não estou muito preocupado, pois isso não está ganhando.
Hobbies de Calvin
A maioria desses envios mantém o controle apenas na linha superior de 3 ^ nx 1 blocos. Se você acabou de gerar esse segmento do tapete, poderá escalar um pouco mais. Quase certamente até onde os erros de arredondamento o quebrarão.
captncraig
1
Como já mencionei, a pergunta original solicitava código que pudesse ser dimensionado para um número "razoável" de iterações (até 2 ^ 32) . Se você fizer as contas, verá que mesmo um único byte se expandirá para mais de 10 ^ 4098440370 bytes depois de muitas iterações. Propus uma resposta que achei um pouco mais razoável, mas desde então a palavra "razoável" desapareceu da pergunta: - /. Olha, eu terminei aqui. Apenas vote esta resposta se você não gostar.
ossifrage melindroso
9

Golfscript, 9 * 2 = 18

0+       
,3base,(}

(Observe que a primeira linha possui espaços à direita para torná-la retangular)

Não consegui encontrar uma função de log para o Golfscript, então basetive que fazer.

Golfscript começa com uma string vazia, portanto, 0+apenas aumenta o comprimento da string em 1 (por coerção). Quando a primeira linha terminar, a pilha terá uma sequência de comprimento 3^n, da qual utilizamos a base de log 3 antes de comentar demais. né então impresso automaticamente.

Sp3000
fonte
Você pode salvar 2 caracteres usando um número inteiro em vez de uma sequência e, portanto, salvando o ,na segunda linha. Primeira linha 0or):; segunda linha 3base,(}. O outro alvo óbvio é o (da segunda linha. Isso é mais complicado, mas também pode ser removido substituindo a primeira linha 1+~abs(por um retângulo 7 * 2.
Peter Taylor
8

C, 12x8 = 96

Inspirado por @ciamej, reduzi-o. Ele usa essa divisão por três truques, além da percepção de que o tapete efetivamente converte um if em um loop while.

O código foi testado no gcc / Ubuntu para iterações de até 3.

#ifndef A //
#define A //
x;main(a){//
a++;/*    */
if(a/=3)x++;
printf(   //
"%d",x);} //
#endif    //

Solução anterior: C, 11x12

Não é um vencedor de tamanho, mas ei, é C.

Ele encontra o log2 da contagem de blocos por deslocamento de bits e, em seguida, usa alguns números mágicos e o truncamento int para estimar o log3. A matemática deve trabalhar com até 26 iterações (um número de 42 bits).

#ifndef A//
#define A//
int n=0;//_
int main//_
(v,c){//___
n+=1;/*..*/
while(n//__
>>=1)v++;//
n=.3+.62*v;
printf(//__
"%d",n);}//
#endif//__
AShelly
fonte
Olá, Publiquei uma versão abreviada da sua solução.
C26515
Bom truque com isso se! ;)
ciamej
6

CJam, 9 bytes

A idéia de usar ]é do Optimizer, mas usa um método muito diferente para contar.

X~]:X,8mL

Experimente online

Como funciona:

X~          "push X and dump its contents.  On the zeroth iteration, X is a single number, but later is it an array.";
  ]         "wrap everything into an array.  The stack would contain the contents of X plus the result of the previous instance of the code";
   :X       "store this array back into X.  X is now 1 element longer";
     ,      "take the length of X";
      8mL   "do a base-8 logarithm of it";

Duas outras soluções de 9 bytes

]X+:X,8mL

],X+:X8mL
PhiNotPi
fonte
Na verdade, isso vincula o Optimizer, mesmo com o desempatador. : P Tiebreakerbreaker: post anterior vence.
Hobbies de Calvin
Eu acho que é uma boa solução, independentemente. Não consegui vencer 9 caracteres.
PhiNotPi
Eu acho que a abordagem geral é a mesma (e qual é a única que faz sentido) - Tenha uma variável, aumente-a em 1 de alguma forma.
Optimizer
4

Python 2, 15 * 3 = 45

m=n=0;E=exit  ;
m+=1;n+=m>3**n;
print n;E()   ;

Outra implementação da idéia contar-primeira-linha-depois-registrar-três-e-sair. Provavelmente ainda pode ser jogado um pouco mais.

Sp3000
fonte
2

bc, 2 * 16 + 1 = 33

O +1 extra na pontuação é porque a -lopção bc é necessária:

a+=1;          
l(a)/l(3);halt;
Trauma Digital
fonte
2

Golfscript, 7 * 2 = 14

1+~abs(
3base,}

Isso é inspirado na resposta do Sp3000 e, em particular, no desejo de otimizar a longa segunda linha.3base,é tão curto quanto um logaritmo de base 3 entra no GS, e o super comentário }é claramente ideal.

O que é necessário para a primeira linha é mapear a sequência vazia ''do stdin inicial para 0 e, em seguida, mapear cada número inteiro não negativo para o sucessor. Desta forma, terminamos a primeira linha com 3^n - 1na pilha e 3base,não requer nenhum decremento.

Peter Taylor
fonte
2

C, 13x8

#ifndef A//__
#define A//__
x;a;main(){//
a++;;;;;;;;;;
while(a/=3)//
x++;printf(//
"%d",x);}//__
#endif//_____
ciamej
fonte
1

Perl, 76

Sei que provavelmente não faz muito sentido postar isso, pois ele já foi completamente derrotado, mas aqui está a minha solução atual.

$_++;                                 
if(not$_&$_-1){print log()/log 8;$_--}
PhiNotPi
fonte
@ Alex Isso parece não funcionar, mesmo na 1ª iteração.
PhiNotPi
Sim, funciona como está. Você já testou seu método?
PhiNotPi
A minha trabalha com ideone: ideone.com/othumP .
PhiNotPi
Peguei vocês. Perdi um detalhe importante que o impedia de trabalhar antes. Você está certo, minha sugestão está incorreta.
Alex A.
1

> <> (Peixe), 12 * 3 = 36

Uma solução> <> mais direta:

'v'00p0l1+  
>  :2-?v$1+v
^$+1$,3< ;n<

Primeiro, executamos a linha superior dos blocos superiores. 'v'00pcoloca vna primeira posição de todo o programa, direcionando o ponteiro do programa para baixo quando voltar ao início, após atingir o final da linha. Antes disso, cada bloco empurra 0 e o comprimento da pilha + 1 para ele. (a pilha será 0 2 0 4 0 6 ...)

Na primeira metade do segundo e terceiro contamos quantas vezes podemos dividir o elemento da pilha superior antes de obtermos 2 (nós o armazenamos no segundo ao topo).

No final, produzimos o segundo ao topo do elemento da pilha.

randomra
fonte
1

Lua, 3 * 17 = 51

Mesma estratégia que a maioria das pessoas:

x=(x or 0)+1;    
y=math.log(x,3)  
print(y)os.exit()
Omar
fonte
1

PHP, 22 × 2 = 44 27 × 2 = 54

<?php $i++          ?>
<?php die(log($i,3))?>

Apenas outra opinião sobre count-log3-out. Não é muito pequeno, mas o meu primeiro golfe;)

Lars Ebert
fonte
No PCG.SE, como em qualquer outro lugar, verifique a documentação antes de postar :).
Blackhole
@ Blackhole Boa captura! Obrigado
Lars Ebert /