Kod Sierpińskiego

47

Napisz prostokątny blok tekstu, który po ułożeniu w dywanie Sierpińskiego , używając bloków o tej samej wielkości dla pustych części, tworzy program, który wyświetla numer iteracji dywanu.

Na przykład, jeśli masz blok tekstowy

TXT
BLK

następnie uruchom program

TXTTXTTXT
BLKBLKBLK
TXT   TXT
BLK   BLK
TXTTXTTXT
BLKBLKBLK

powinien wyjść, 1ponieważ kształt programu reprezentuje pierwszą iterację dywanu Sierpińskiego.

Podobnie działa

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

powinien wypisać 2, ponieważ jest to kształt drugiej iteracji dywanu Sierpińskiego.

Uruchamianie bloku tekstu bez zmian

TXT
BLK

powinien generować, 0ponieważ można to uznać za iterację zerową.

Powinno to działać dla wszystkich dalszych iteracji. (Przynajmniej teoretycznie, zakładając, że komputer ma pamięć i wszystko.)

Detale

  • Programy nie mogą czytać ani uzyskiwać dostępu do informacji o kodzie źródłowym. Traktuj to jak surowe wyzwanie quine.
  • Dane wyjściowe trafiają do standardowej lub podobnej alternatywy. Podaj tylko liczbę i opcjonalny znak nowej linii. Brak danych wejściowych.
  • Blok tekstowy może zawierać dowolne znaki, które nie są uważane za terminatory linii . Blok tekstowy może zawierać spacje.
  • „Pusta przestrzeń” na dywanie musi składać się wyłącznie ze znaków spacji .
  • Opcjonalnie możesz założyć, że wszystkie programy mają końcowy znak nowej linii.

Możesz użyć tego fragmentu stosu do wygenerowania dywanu dla danego bloku tekstu w dowolnej iteracji:

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

Punktacja

Zwycięzcą jest zgłoszenie, którego początkowy blok tekstowy jest najmniejszy pod względem obszaru (szerokość razy wysokość). TXT\nBLKPrzykładem jest 3 od 2 do 6. (wynik w zasadzie najkrótszej wygranych kod, tym samym znacznikiem kod golfa).

Tiebreaker przechodzi do zgłoszenia, w którym w bloku tekstu jest najmniej różnych znaków. Jeśli nadal jest remis, odpowiedź opublikowana jako pierwsza wygrywa.

Hobby Calvina
źródło

Odpowiedzi:

23

CJam, 9 bajtów

Myślę, że można to poprawić, ale na razie chodźmy z tym ...

];U):U8mL

Jak to działa :

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

Wypróbuj online tutaj

Optymalizator
źródło
35

piet - 32 * 6 = 192

wprowadź opis zdjęcia tutaj

Wypełniłem puste miejsce wzorem w kratkę. Myślę, że to sprawia, że ​​Sierpiński jest nieco potrójniejszy.

Oto druga iteracja: wprowadź opis zdjęcia tutaj

oryginał: 32 * 7

wprowadź opis zdjęcia tutaj

captncraig
źródło
19

> <> , 11 * 2 = 22

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

Tutaj przyjmujemy inne podejście, używając funkcji skoku / teleportacji> <>.

Program wykonuje tylko bloki w górnym rzędzie, uruchamiając 1. / 2. blok, a następnie 3. / 4. blok, 9. / 10. blok, 27. / 28 blok itd. (Zwiększenie mocy 3). Ponieważ w górnym rzędzie znajdują się 3^nbloki, tylko nbloki są wykonywane, zanim program wraca do początku, wysyła górę stosu i zatrzymuje się (zgodnie z ninstrukcją umieszczoną przez p).

Program wykorzystuje zasadę „Nie ma danych wejściowych”, ponieważ ipolecenie wypycha -1 na stos, jeśli EOF jest spełniony. Aby to przetestować, musisz umieścić w pustym pliku.


Poprzednie zgłoszenie, 7 * 4 = 28

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

Pierwszy wiersz ciągle przesuwa długość stosu dla każdego bloku i zmienia pierwszy "cytat na strzałkę w dół vza pomocą ppolecenia put. Do czasu zakończenia pierwszego wiersza stos wygląda

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

(Pamiętaj, że inicjał ljest używany dwukrotnie).

Ostatnie trzy wiersze liczą następnie, ile razy musimy podzielić przez 3, zanim trafimy 1 (ponieważ> <> nie ma funkcji dziennika). Dolne zero służy do śledzenia liczby.

Sp3000
źródło
13

Perl, 26

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

Wykorzystuje szereg harmonicznych do przybliżenia logarytmu podstawowego 3. Myślę, że to działa, ale próbowałem tylko dla małych liczb. Dzięki wrażliwemu kostwieniu za pomysł użycia die.

Stara wersja (34):

$n--or$n=3**$s++;
print$s-1if!$o++;
grc
źródło
To bardzo miłe!
skrzypliwy kostrzew
10

Perl, 30 (15 × 2)

Przede wszystkim zamierzam twierdzić, że 10 iteracji to rozsądny limit, a nie 2 32 . Po 10 iteracjach program składający się z N bajtów zostanie rozszerzony do ( N × 3 20 ) bajtów (plus podział wiersza), co stanowi ponad 3 gigabajty nawet dla N = 1. Architektura 32-bitowa byłaby całkowicie niezdolna do obsługi 11 iteracji. (I oczywiście nie ma wystarczającej liczby cząstek we wszechświecie dla 2 32 iteracji).

Oto moje rozwiązanie:

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

Działa to poprzez inkrementację zmiennej $nw pierwszym wierszu i obliczanie jej logarytmu na każdym kroku. Drugi wiersz wypisuje całkowitą część tego logarytmu i kończy pracę.

Prosty logarytm do podstawy e (2.718 ..) jest wystarczająco blisko, aby dać poprawne wyniki dla pierwszych 10 iteracji.

piskliwy kostuch
źródło
2
Według PO powinien teoretycznie działać dla wszystkich iteracji.
Nathan Merrill,
2
@NathanMerrill Cóż, OK. Ale aby zachować zgodność z oryginalną specyfikacją, musiałby również działać w alternatywnych wszechświatach. Pytanie zostało zredagowane od tego czasu.
piskliwy kosteczek kostnych
Zmieniłem pytanie ze względu na dobre uwagi tutaj. Zgadzam się, że używanie naturalnego logu to raczej szara strefa, ale szczerze mówiąc, nie martwię się zbytnio, ponieważ to nie wygrywa.
Calvin's Hobbies,
Większość tych zgłoszeń zachowuje kontrolę tylko w górnym rzędzie 3 ^ nx 1 kafelków. Jeśli po prostu wygenerujesz ten segment dywanu, możesz skalować nieco dalej. Niemal na pewno tam, gdzie złamią cię zaokrąglenia.
captncraig
1
Jak już wspomniałem, pierwotne pytanie dotyczyło kodu, który można skalować do „rozsądnej” liczby iteracji (do 2 ^ 32) . Jeśli wykonasz matematykę, przekonasz się, że nawet jeden bajt po tylu iteracjach przekroczy 10 ^ 4098440370 bajtów. Zaproponowałem odpowiedź, która moim zdaniem była nieco bardziej rozsądna, ale od tego czasu słowo „rozsądny” zniknęło z pytania: - /. Słuchaj, skończyłem tutaj. Po prostu zanotuj tę odpowiedź, jeśli Ci się nie podoba.
piskliwy kosteczek kostnych
9

Golfscript, 9 * 2 = 18

0+       
,3base,(}

(Zauważ, że pierwsza linia ma końcowe spacje, aby była prostokątna)

Nie mogłem znaleźć funkcji dziennika dla Golfscript, więc basemusiałem to zrobić.

Golfscript zaczyna się od pustego łańcucha, więc 0+po prostu zwiększa długość łańcucha o 1 (przez skręcenie). Zanim skończy się pierwsza linia, stos będzie miał ciąg długości 3^n, który przyjmujemy logarytmiczną podstawę 3 przed super komentarzem. njest następnie automatycznie drukowany.

Sp3000
źródło
Możesz zapisać 2 znaki, używając liczby całkowitej zamiast łańcucha, a tym samym zapisując ,drugą linię. Pierwsza linia 0or):; druga linia 3base,(}. Drugim oczywistym celem jest (druga linia. Jest to trudniejsze, ale można je również usunąć, zastępując pierwszą linię 1+~abs(prostokątem 7 * 2.
Peter Taylor
8

C, 12 x 8 = 96

Zainspirowany przez @ciamej, zmniejszyłem go. Wykorzystuje dzielenie przez 3 lewę, a także świadomość, że dywan skutecznie przekształca pętlę if w pętlę while.

Kod został przetestowany na gcc / Ubuntu dla iteracji do 3.

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

Poprzednie rozwiązanie: C, 11x12

Nie jest zwycięzcą, ale hej, to C.

Znajduje log2 liczby bloków poprzez przesunięcie bitów, a następnie używa magicznych liczb i obcięcia do oszacowania log3. Matematyka powinna działać do 26 iteracji (liczba 42-bitowa).

#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
źródło
Witam, opublikowałem skróconą wersję twojego rozwiązania.
ciamej
Niezła sztuczka z tym, jeśli! ;)
ciamej
6

CJam, 9 bajtów

Pomysł użycia ]pochodzi z Optymalizatora, ale używa zupełnie innej metody liczenia.

X~]:X,8mL

Wypróbuj online

Jak to działa:

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

Dwa inne 9-bajtowe rozwiązania

]X+:X,8mL

],X+:X8mL
PhiNotPi
źródło
To faktycznie wiąże Optymalizator, nawet z remakiem. : P Tiebreakerbreaker: wcześniejszy post wygrywa.
Calvin's Hobbies
Myślę, że niezależnie od tego jest to dobre rozwiązanie. Nie byłem w stanie pokonać 9 znaków.
PhiNotPi
Myślę, że ogólne podejście jest tylko takie samo (i które jest jedynym podejściem, które ma sens) - Mieć zmienną, w jakiś sposób zwiększać ją o 1.
Optymalizator
4

Python 2, 15 * 3 = 45

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

Kolejna implementacja pomysłu liczenia pierwszego rzędu, a następnie logowania trzy i wyjścia. Prawdopodobnie można jeszcze grać w golfa nieco więcej.

Sp3000
źródło
2

bc, 2 * 16 + 1 = 33

Dodatkowe +1 w wyniku wynika z tego, że -lwymagana jest opcja bc:

a+=1;          
l(a)/l(3);halt;
Cyfrowa trauma
źródło
2

Golfscript, 7 * 2 = 14

1+~abs(
3base,}

To jest inspirowana przez SP3000 za odpowiedź , aw szczególności poprzez dążenie do optymalizacji długą drugą linię. 3base,jest tak krótki, jak logarytm bazowy 3 otrzyma w GS, a super komentarz }jest wyraźnie optymalny.

W pierwszym wierszu wymagane jest odwzorowanie pustego ciągu ''od początkowej wartości standardowej na 0, a następnie odwzorowanie każdej nieujemnej liczby całkowitej na jej następcę. W ten sposób kończymy pierwszą linię 3^n - 1na stosie i 3base,nie wymagamy żadnego zmniejszenia.

Peter Taylor
źródło
2

C, 13 x 8

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

Perl, 76

Wiem, że opublikowanie tego prawdopodobnie nie ma większego sensu, ponieważ zostało już całkowicie pobite, ale oto moje obecne rozwiązanie.

$_++;                                 
if(not$_&$_-1){print log()/log 8;$_--}
PhiNotPi
źródło
@Alex To nie wydaje się działać, nawet przy pierwszej iteracji.
PhiNotPi
Tak, działa bez zmian. Czy przetestowałeś swoją metodę?
PhiNotPi
Mój działa na ideone: ideone.com/othumP .
PhiNotPi
Gotcha Brakowało mi ważnego szczegółu, który uniemożliwiał mu wcześniejsze działanie. Masz rację, moja sugestia jest nieprawidłowa.
Alex A.
1

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

Bardziej proste rozwiązanie> <>:

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

Najpierw uruchamiamy górny rząd górnych bloków. 'v'00pustawia vpierwszą pozycję całego programu, kierując wskaźnik programu w dół, gdy wraca do początku po osiągnięciu końca linii. Wcześniej każdy blok wypycha na niego 0 i długość stosu + 1. (stos będzie 0 2 0 4 0 6 ...)

W pierwszej połowie drugiej i trzeciej policzymy, ile razy możemy podzielić górny element stosu, zanim otrzymamy 2 (przechowujemy to w elemencie od drugiego do górnego).

Na koniec wyprowadzamy element od drugiego do górnego stosu.

randomra
źródło
1

Lua, 3 * 17 = 51

Taka sama strategia jak większość ludzi:

x=(x or 0)+1;    
y=math.log(x,3)  
print(y)os.exit()
Omar
źródło
1

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

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

Kolejne podejście do wylogowania. Niezbyt mały, ale mój pierwszy golf;)

Lars Ebert
źródło
Na PCG.SE, jak wszędzie indziej, sprawdź dokumentację przed opublikowaniem :).
Blackhole
@Blackhole Good catch! Dzięki
Lars Ebert