46
\$\begingroup\$

Write a rectangular block of text that when arranged into a Sierpinski carpet, using same-sized blocks of spaces for the empty portions, creates a program that outputs the iteration number of the carpet.

For example, if your text block is

TXT
BLK

then running the program

TXTTXTTXT
BLKBLKBLK
TXT   TXT
BLK   BLK
TXTTXTTXT
BLKBLKBLK

should output 1 because the shape of the program represents the first iteration of the Sierpinski carpet.

Similarly, running

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

should output 2 because this is the shape of the second Sierpinski carpet iteration.

Running the text block as is

TXT
BLK

should output 0 because it can be considered the zeroth iteration.

This should work for all further iterations. (At least theoretically, assuming the computer has the memory and all.)

Details

  • Programs may not read or access information about their source code. Treat this like a strict quine challenge.
  • Output goes to stdout or similar alternative. Only output the number and an optional trailing newline. There is no input.
  • The text block may contain any characters that are not considered line terminators. The text block may contain spaces.
  • The "empty space" in the carpet must consist entirely of space characters.
  • You may optionally assume all the programs have a trailing newline.

You can use this stack snippet to generate a carpet for a given text block at any iteration:

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

Scoring

The submission whose initial text block is smallest by area (width times height) is the winner. The TXT\nBLK example is 3 by 2 for a score of 6. (Basically the shortest code wins, hence the code-golf tag.)

Tiebreaker goes to the submission that uses the fewest distinct characters in their text block. If still tied, answer posted first wins.

\$\endgroup\$

16 Answers 16

23
\$\begingroup\$

CJam, 9 bytes

I think this can be improved, but for now, lets go with it...

];U):U8mL

How it works:

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

Try it online here

\$\endgroup\$
35
\$\begingroup\$

piet - 32*6 = 192

enter image description here

I filled the empty space with the checker pattern. I think it makes the Sierpinski a bit trippier.

Here is the second iteration: enter image description here

original : 32*7

enter image description here

\$\endgroup\$
19
\$\begingroup\$

><>, 11 * 2 = 22

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

Here we take a different approach by using ><>'s jump/teleport functionality.

The program only executes blocks in the top row, running the 1st/2nd block, then the 3rd/4th blocks, 9th/10th blocks, 27th/28th blocks, etc. (going up in powers of 3). As the top row has 3^n blocks, only n blocks are executed before the program wraps back to the start, outputs the top of the stack and halts (due to the n instruction placed via p).

The program exploits the rule "There is no input.", as the i command pushes -1 onto the stack if EOF is met. So to test this you'll need to pipe in an empty file.


Previous submission, 7 * 4 = 28

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

The first line continuously pushes the length of the stack for every block, and changes the first " quote to a down arrow v using the p put command. By the time the first line is over, the stack looks like

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

(Note that the initial l is used twice.)

The last three lines then count how many times we need to divide by 3 before we hit 1 (since ><> doesn't have a log function). The bottom zero is used to keep track of the count.

\$\endgroup\$
13
\$\begingroup\$

Perl, 26

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

This uses the harmonic series to approximate the base 3 logarithm. I think it works, but I've only tried it for small numbers. Thanks to squeamish ossifrage for the idea of using die.

Old version (34):

$n--or$n=3**$s++;
print$s-1if!$o++;
\$\endgroup\$
10
\$\begingroup\$

Perl, 30 (15×2)

First of all, I'm going to claim that 10 iterations is a reasonable limit, not 232. After 10 iterations, a program consisting of N bytes will have expanded to (N × 320) bytes (plus line breaks), which is over 3 gigabytes even for N=1. A 32-bit architecture would be completely unable to handle 11 iterations. (And obviously there aren't enough particles in the universe for 232 iterations).

So here's my solution:

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

This works by incrementing the variable $n in the first line and calculating its logarithm at each step. The second line prints the integer part of this logarithm and quits.

A simple logarithm to base e (2.718..) is close enough to give correct results for the first 10 iterations.

\$\endgroup\$
  • 2
    \$\begingroup\$ According to the OP, it should theoretically work for all iterations. \$\endgroup\$ – Nathan Merrill Feb 25 '15 at 14:39
  • 2
    \$\begingroup\$ @NathanMerrill Well, OK. But to comply with the original spec it would also have had to work in alternate universes. The question has been edited since then. \$\endgroup\$ – squeamish ossifrage Feb 25 '15 at 15:11
  • \$\begingroup\$ I changed the question because of the good points made here. I agree that using natural log is rather a gray area, but honestly I'm not too concerned since this isn't winning. \$\endgroup\$ – Calvin's Hobbies Feb 25 '15 at 15:46
  • \$\begingroup\$ Most of these submissions keep control only in the top row of 3^n x 1 tiles. If you just generate that segment of the carpet, you can scale quite a bit further. Almost certainly to where rounding errors will break you. \$\endgroup\$ – captncraig Feb 25 '15 at 17:13
  • 1
    \$\begingroup\$ As I mentioned already, the original question asked for code that could scale to a "reasonable" number of iterations (up to 2^32). If you do the maths, you'll find that even a single byte would expand to in excess of 10^4098440370 bytes after that many iterations. I proposed an answer that I thought was a bit more reasonable, but since then the word "reasonable" has disappeared from the question :-/. Look, I'm done here. Just downvote this answer if you don't like it. \$\endgroup\$ – squeamish ossifrage Feb 25 '15 at 20:26
9
\$\begingroup\$

Golfscript, 9 * 2 = 18

0+       
,3base,(}

(Note that the first line has trailing spaces to make it rectangular)

I couldn't find a log function for Golfscript, so base had to do.

Golfscript starts off with an empty string, so 0+ just increases the length of the string by 1 (by coersion). By the time the first line is over, the stack will have a string of length 3^n, which we take the log base 3 of before we super comment. n is then automatically printed.

\$\endgroup\$
  • \$\begingroup\$ You could save 2 chars by using an integer instead of a string and hence saving the , on the second line. First line: 0or); second line 3base,(}. The other obvious target is the ( on the second line. This is trickier, but can also be removed by replacing the first line with 1+~abs( for a 7*2 rectangle. \$\endgroup\$ – Peter Taylor Feb 26 '15 at 16:31
8
\$\begingroup\$

C, 12x8 = 96

Inspired by @ciamej, I've reduced it. It uses that divide by 3 trick, plus the realization that the carpet effectively converts an if into a while loop.

The code was tested on gcc/Ubuntu for iterations up to 3.

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

Previous Solution: C, 11x12

Not a size winner, but hey, it's C.

It finds log2 of the blockcount by bitshifting, then uses some magic numbers and int truncation to estimate log3. The math should work up to 26 iterations (a 42 bit number).

#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//__
\$\endgroup\$
  • \$\begingroup\$ Hi, I've posted a shortened version of your solution. \$\endgroup\$ – ciamej Feb 26 '15 at 19:55
  • \$\begingroup\$ Nice trick with that if! ;) \$\endgroup\$ – ciamej Feb 27 '15 at 1:51
6
\$\begingroup\$

CJam, 9 bytes

The idea of using ] is from Optimizer, but it uses a very different method to count.

X~]:X,8mL

Try it online

How it works:

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

Two other 9 byte solutions

]X+:X,8mL

],X+:X8mL
\$\endgroup\$
  • \$\begingroup\$ This actually ties Optimizer, even with the tiebreaker. :P Tiebreakerbreaker: earlier post wins. \$\endgroup\$ – Calvin's Hobbies Feb 26 '15 at 2:54
  • \$\begingroup\$ I think it's a good solution regardless. I haven't been able to beat 9 chars. \$\endgroup\$ – PhiNotPi Feb 26 '15 at 2:57
  • \$\begingroup\$ I think the general approach is same only (and which is the only approach which makes sense) - Have a variable, increment it by 1 somehow. \$\endgroup\$ – Optimizer Feb 27 '15 at 14:25
4
\$\begingroup\$

Python 2, 15 * 3 = 45

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

Another implementation of the count-first-row-then-log-three-and-exit idea. Can probably still be golfed a fair bit more.

\$\endgroup\$
2
\$\begingroup\$

bc, 2*16+1 = 33

The extra +1 in the score is because the -l bc option is required:

a+=1;          
l(a)/l(3);halt;
\$\endgroup\$
2
\$\begingroup\$

Golfscript, 7 * 2 = 14

1+~abs(
3base,}

This is inspired by Sp3000's answer, and in particular by the desire to optimise the long second line. 3base, is as short as a base-3 logarithm will get in GS, and the super-comment } is clearly optimal.

What's required for the first line is to map the empty string '' from the initial stdin to 0, and then to map each non-negative integer to its successor. In this way we end the first line with 3^n - 1 on the stack, and 3base, doesn't require any decrement.

\$\endgroup\$
2
\$\begingroup\$

C, 13x8

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

Perl, 76

I know there's probably not much point in posting this since it's already been thoroughly beaten, but here's my current solution anyways.

$_++;                                 
if(not$_&$_-1){print log()/log 8;$_--}
\$\endgroup\$
  • \$\begingroup\$ @Alex That doesn't seem to work, even at the 1st iteration. \$\endgroup\$ – PhiNotPi Feb 26 '15 at 1:26
  • \$\begingroup\$ Yes, it works as it stands. Have you tested your method? \$\endgroup\$ – PhiNotPi Feb 26 '15 at 2:20
  • \$\begingroup\$ Mine works on ideone: ideone.com/othumP. \$\endgroup\$ – PhiNotPi Feb 26 '15 at 3:26
  • \$\begingroup\$ Gotcha. I missed an important detail that kept it from working before. You're right, my suggestion is incorrect. \$\endgroup\$ – Alex A. Feb 26 '15 at 3:37
1
\$\begingroup\$

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

A more straightforward ><> solution:

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

We first run the top row of the top blocks. 'v'00p puts v at the very first position of the whole program directing the program pointer downwards when it gets back to the start after reaching the end of the line. Before that every block pushes 0 and the length of the stack + 1 onto it. (stack will be 0 2 0 4 0 6 ...)

On the first half of the second and third we count how many times we can divide the top stack element before we get 2 (we store this in the second to top element).

At the end we output the second to top element of the stack.

\$\endgroup\$
1
\$\begingroup\$

Lua, 3 * 17 = 51

Same strategy as most people:

x=(x or 0)+1;    
y=math.log(x,3)  
print(y)os.exit()
\$\endgroup\$
1
\$\begingroup\$

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

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

Just another take on count-log3-out. Not very small, but my first golf ;)

\$\endgroup\$
  • \$\begingroup\$ On PCG.SE like everywhere else, please check the documentation before posting :) . \$\endgroup\$ – Blackhole Mar 1 '15 at 18:44
  • \$\begingroup\$ @Blackhole Good catch! Thanks \$\endgroup\$ – Lars Ebert Mar 2 '15 at 8:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.