Code Sierpinskified

47

Écrivez un bloc de texte rectangulaire qui, lorsqu'il est disposé dans un tapis de Sierpinski , en utilisant des blocs d'espaces de même taille pour les parties vides, crée un programme qui affiche le numéro d'itération du tapis.

Par exemple, si votre bloc de texte est

TXT
BLK

puis lancer le programme

TXTTXTTXT
BLKBLKBLK
TXT   TXT
BLK   BLK
TXTTXTTXT
BLKBLKBLK

devrait sortir 1car la forme du programme représente la première itération du tapis de Sierpinski.

De même, en cours d'exécution

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

devrait produire 2 car il s’agit de la deuxième itération du tapis de Sierpinski.

Exécuter le bloc de texte tel quel

TXT
BLK

devrait sortir 0car il peut être considéré comme l'itération zéro.

Cela devrait fonctionner pour toutes les itérations ultérieures. (Du moins théoriquement, en supposant que l'ordinateur ait la mémoire et tout.)

Détails

  • Les programmes ne peuvent pas lire ou accéder aux informations concernant leur code source. Traitez cela comme un défi quine strict.
  • La sortie passe à stdout ou à une alternative similaire. N'affiche que le numéro et une nouvelle ligne de fin optionnelle. Il n'y a pas d'entrée.
  • Le bloc de texte peut contenir des caractères qui ne sont pas considérés comme des fins de ligne . Le bloc de texte peut contenir des espaces.
  • "L'espace vide" dans le tapis doit être entièrement composé de caractères d'espace .
  • Vous pouvez éventuellement supposer que tous les programmes ont une nouvelle ligne.

Vous pouvez utiliser cet extrait de pile pour générer un tapis pour un bloc de texte donné à n'importe quelle itération:

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

Notation

La soumission dont le bloc de texte initial est le plus petit par zone (largeur multipliée par la hauteur) est le gagnant. L' TXT\nBLKexemple est 3 par 2 pour un score de 6. (Fondamentalement, le code le plus court gagne, d'où le tag code-golf.)

Tiebreaker va à la soumission qui utilise le moins de caractères distincts dans son bloc de texte. S'il y a toujours égalité, répondez posté en premier gagne.

Les passe-temps de Calvin
la source

Réponses:

23

CJam, 9 octets

Je pense que cela peut être amélioré, mais pour l'instant, allons-y avec ...

];U):U8mL

Comment ça marche :

];             "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";

Essayez-le en ligne ici

Optimiseur
la source
35

piet - 32 * 6 = 192

entrez la description de l'image ici

J'ai rempli l'espace vide avec le motif en damier. Je pense que cela rend le Sierpinski un peu trippier.

Voici la deuxième itération: entrez la description de l'image ici

original: 32 * 7

entrez la description de l'image ici

captncraig
la source
19

> <> , 11 * 2 = 22

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

Ici, nous adoptons une approche différente en utilisant la fonctionnalité de saut / téléportation de> <>.

Le programme exécute uniquement les blocs de la rangée supérieure, en exécutant le 1er / 2ème bloc, puis les 3ème / 4ème blocs, les 9ème / 10ème blocs, les 27ème / 28ème blocs, etc. (augmentant avec une puissance de 3). Comme la rangée supérieure contient des 3^nblocs, seuls ceux-ci nsont exécutés avant que le programme ne revienne au début, affiche le haut de la pile et s’arrête (en raison de l’ ninstruction placée via p).

Le programme exploite la règle "Il n'y a pas d'entrée.", Car la icommande envoie -1 dans la pile si EOF est rencontré. Donc, pour tester cela, vous devrez canaliser un fichier vide.


Soumission précédente, 7 * 4 = 28

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

La première ligne pousse continuellement la longueur de la pile pour chaque bloc et remplace le premier "guillemet par une flèche vers le bas và l'aide de la pcommande put. Au moment où la première ligne est terminée, la pile ressemble à

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

(Notez que l'initiale lest utilisée deux fois.)

Les trois dernières lignes comptent alors le nombre de fois que nous devons diviser par 3 avant d’atteindre 1 (puisque> <> n’a pas de fonction de journalisation). Le zéro en bas est utilisé pour garder une trace du compte.

Sp3000
la source
13

Perl, 26 ans

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

Ceci utilise la série des harmoniques pour approximer le logarithme en base 3. Je pense que cela fonctionne, mais je ne l'ai essayé que pour de petits nombres. Merci à ossifrage délirant pour l’idée de l’utiliser die.

Ancienne version (34):

$n--or$n=3**$s++;
print$s-1if!$o++;
grc
la source
C'est très chouette!
ossifrage
10

Perl, 30 (15 × 2)

Tout d’abord, je vais affirmer que 10 itérations est une limite raisonnable, pas 2 32 . Après 10 itérations, un programme composé de N octets aura été étendu à ( N × 3 20 ) octets (plus les sauts de ligne), soit plus de 3 gigaoctets, même pour N = 1. Une architecture 32 bits serait totalement incapable de gérer 11 itérations. (Et évidemment, il n’ya pas assez de particules dans l’univers pour 2 32 itérations).

Alors voici ma solution:

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

Cela fonctionne en incrémentant la variable $ndans la première ligne et en calculant son logarithme à chaque étape. La deuxième ligne affiche la partie entière de ce logarithme et se ferme.

Un simple logarithme à la base e (2,718 ..) est suffisamment proche pour donner des résultats corrects pour les 10 premières itérations.

ossifrage délirant
la source
2
Selon le PO, cela devrait théoriquement fonctionner pour toutes les itérations.
Nathan Merrill
2
@NathanMerrill Eh bien, d'accord. Mais pour se conformer à la spécification d'origine, il aurait également dû fonctionner dans des univers alternatifs. La question a été modifiée depuis.
ossifrage
J'ai changé la question en raison des points positifs soulevés ici. Je suis d'accord pour dire que l'utilisation de bûche naturelle est plutôt une zone grise, mais honnêtement, je ne suis pas trop inquiet car ce n'est pas gagnant.
Les passe-temps de Calvin
La plupart de ces soumissions gardent le contrôle seulement dans la rangée supérieure de 3 ^ nx 1 tuiles. Si vous ne générez que ce segment du tapis, vous pouvez encore évoluer. Presque certainement où des erreurs d'arrondi vont vous briser.
captncraig
1
Comme je l'ai déjà mentionné, la question initiale demandait un code pouvant évoluer vers un nombre "raisonnable" d'itérations (jusqu'à 2 ^ 32) . Si vous faites le calcul, vous constaterez que même un seul octet serait étendu à plus de 10 ^ 4098440370 octets après autant d'itérations. J'ai proposé une réponse qui me semblait un peu plus raisonnable, mais depuis lors, le mot "raisonnable" a disparu de la question: - /. Regardez, j'ai fini ici. Si vous ne l'aimez pas, votez pour cette réponse.
ossifrage
9

Golfscript, 9 * 2 = 18

0+       
,3base,(}

(Notez que la première ligne comporte des espaces pour le rendre rectangulaire)

Je ne pouvais pas trouver de fonction de journalisation pour Golfscript, donc baseje devais le faire.

Golfscript commence par une chaîne vide, il 0+suffit donc d' augmenter la longueur de la chaîne de 1 (par coersion). Au moment où la première ligne est terminée, la pile aura une chaîne de longueur 3^n, que nous prenons la base de journal 3 avant de super comment. nest alors automatiquement imprimé.

Sp3000
la source
Vous pouvez enregistrer 2 caractères en utilisant un entier au lieu d'une chaîne et, par conséquent, en enregistrant le ,sur la deuxième ligne. Première ligne 0or):; deuxième ligne 3base,(}. L'autre cible évidente est (la deuxième ligne. Ceci est plus compliqué, mais peut également être supprimé en remplaçant la première ligne par 1+~abs(un rectangle 7 * 2.
Peter Taylor
8

C, 12x8 = 96

Inspiré par @ciamej, je l'ai réduit. Il utilise cette astuce de division par 3, plus la réalisation que le tapis convertit efficacement une boucle if en une boucle while.

Le code a été testé sur gcc / Ubuntu pour des itérations jusqu’à 3.

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

Solution précédente: C, 11x12

Pas un gagnant de taille, mais bon, c'est C.

Il trouve log2 du nombre de blocs par bitshifting, puis utilise des nombres magiques et une troncature int pour estimer log3. Le calcul devrait fonctionner jusqu'à 26 itérations (un nombre 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
la source
Bonjour, j'ai posté une version abrégée de votre solution.
ciamej
Belle astuce avec ça si! ;)
ciamej
6

CJam, 9 octets

L’idée d’utiliser ]provient d’Optimizer, mais elle utilise une méthode très différente pour compter.

X~]:X,8mL

Essayez-le en ligne

Comment ça fonctionne:

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";

Deux autres solutions à 9 octets

]X+:X,8mL

],X+:X8mL
PhiNotPi
la source
Cela lie en fait l’optimiseur, même avec le tie-break. : P Tiebreakerbreaker: le message précédent l'emporte.
Les passe-temps de Calvin
Je pense que c'est une bonne solution peu importe. Je n'ai pas été capable de battre 9 caractères.
PhiNotPi
Je pense que l'approche générale est la même (et qui est la seule approche qui a du sens) - Avoir une variable, l'incrémenter de 1 en quelque sorte.
Optimiseur
4

Python 2, 15 * 3 = 45

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

Une autre implémentation de l'idée de nombre-première-ligne-puis-log-trois-et-sortie. Peut probablement encore être joué au golf un peu plus.

Sp3000
la source
2

bc, 2 * 16 + 1 = 33

Le +1 supplémentaire dans le score est parce que l' -loption bc est requise:

a+=1;          
l(a)/l(3);halt;
Trauma numérique
la source
2

Golfscript, 7 * 2 = 14

1+~abs(
3base,}

Ceci s’inspire de la réponse de Sp3000 , et en particulier de la volonté d’optimiser la longue seconde ligne. 3base,est aussi court qu’un logarithme en base 3 deviendra GS, et le super commentaire }est clairement optimal.

Ce qui est requis pour la première ligne consiste à mapper la chaîne vide ''du stdin initial sur 0, puis à mapper chaque entier non négatif à son successeur. De cette façon, nous terminons la première ligne avec 3^n - 1sur la pile et 3base,ne nécessitons aucune décrémentation.

Peter Taylor
la source
2

C, 13x8

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

Perl, 76

Je sais qu’il n’ya probablement pas beaucoup d’intérêt à publier ceci car il a déjà été complètement battu, mais voici ma solution actuelle de toute façon.

$_++;                                 
if(not$_&$_-1){print log()/log 8;$_--}
PhiNotPi
la source
@ Alex Cela ne semble pas fonctionner, même à la 1ère itération.
PhiNotPi
Oui, cela fonctionne tel quel. Avez-vous testé votre méthode?
PhiNotPi
Le mien fonctionne sur ideone: ideone.com/othumP .
PhiNotPi
Je t'ai eu. J'ai raté un détail important qui l'empêchait de fonctionner auparavant. Vous avez raison, ma suggestion est incorrecte.
Alex A.
1

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

Une solution plus simple> <>:

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

Nous courons d’abord la rangée supérieure des blocs supérieurs. 'v'00pse place và la toute première position de l’ensemble du programme en dirigeant le pointeur du programme vers le bas lorsqu’il revient au début après avoir atteint la fin de la ligne. Avant que chaque bloc pousse 0 et la longueur de la pile + 1 sur elle. (pile sera 0 2 0 4 0 6 ...)

Sur la première moitié de la seconde et de la troisième, nous comptons le nombre de fois où nous pouvons diviser l’élément supérieur de la pile avant d’obtenir 2 (nous le stockons dans l’élément deuxième à supérieur).

À la fin, nous sortons le deuxième au dernier élément de la pile.

randomra
la source
1

Lua, 3 * 17 = 51

Même stratégie que la plupart des gens:

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

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

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

Juste une autre prise sur count-log3-out. Pas très petit, mais mon premier golf;)

Lars Ebert
la source
Sur PCG.SE comme partout ailleurs, veuillez vérifier la documentation avant de poster :).
Blackhole
@ Blackhole Bonne prise! Merci
Lars Ebert