Wygeneruj warkocz Pascala

32

Oto warkocz Pascala:

 1 4  15  56   209   780    2911    10864     40545      151316      564719
1 3 11  41  153   571   2131    7953     29681     110771      413403      1542841
 1 4  15  56   209   780    2911    10864     40545      151316      564719

Całkowicie to wymyśliłem. O ile wiem, Blaise Pascal nie miał warkocza, a jeśli tak, to prawdopodobnie zrobiono go z włosów zamiast cyfr.

Jest zdefiniowane w następujący sposób:

  1. Pierwsza kolumna ma jeden 1w środku.
  2. Druga kolumna ma 1na górze i na dole.
  3. Teraz naprzemiennie umieszczamy liczbę w środku lub dwie kopie liczby na górze i na dole.
  4. Jeśli liczba będzie na górze lub na dole, będzie to suma dwóch sąsiednich liczb (np 56 = 15 + 41.). Jeśli lekko przechylisz głowę, jest to jak krok w trójkącie Pascala.
  5. Jeśli liczba znajdzie się na środku, będzie to suma wszystkich trzech sąsiednich liczb (np 41 = 15 + 11 + 15.).

Twoim zadaniem będzie wydrukowanie (jakiejś części) tego warkocza.

Wkład

Powinieneś napisać program lub funkcję, która otrzyma jedną liczbę całkowitą n, podając indeks ostatniej kolumny, która ma zostać wyprowadzona.

Możesz wybrać, czy pierwsza kolumna (drukująca tylko jeden 1wiersz w środkowej linii) odpowiada n = 0lub n = 1. To musi być spójny wybór dla wszystkich możliwych danych wejściowych.

Wydajność

Wyjmij warkocz Pascala do nkolumny. Biała spacja musi dokładnie odpowiadać powyższemu przykładowemu układowi, z tą różnicą, że można dopełnić krótsze linie do długości dłuższych linii spacjami i opcjonalnie wyprowadzić pojedyncze końcowe podawanie linii.

Innymi słowy, każda kolumna powinna być dokładnie tak szeroka jak liczba (lub para równych liczb) w tej kolumnie, liczby w kolejnych kolumnach nie powinny się pokrywać i między kolumnami nie powinno być spacji.

Możesz wydrukować wynik do STDOUT (lub najbliższej alternatywy), lub jeśli napiszesz funkcję, możesz zwrócić ciąg znaków o tej samej treści lub listę trzech ciągów (po jednym dla każdej linii).

Dalsze szczegóły

Możesz założyć, że nnie będzie to mniej niż indeks pierwszej kolumny (czyli nie mniej niż 0lub w 1zależności od twojego indeksowania). Możesz także założyć, że ostatnia liczba w oplocie jest mniejsza niż 256 lub największa liczba reprezentowana przez rodzimą liczbę całkowitą twojego języka, w zależności od tego, która wartość jest większa . Więc jeśli rodzimy typ liczb całkowitych może przechowywać tylko bajty, możesz założyć, że największy njest 9lub 10(w zależności od tego, czy używasz 0 lub 1 n) i czy może on przechowywać 32-bitowe liczby całkowite ze znakiem, nbędzie co najwyżej 33lub 34.

Obowiązują standardowe zasady . Najkrótszy kod wygrywa.

OEIS

Oto kilka odpowiednich linków OEIS. Oczywiście zawierają one spoilery na różne sposoby generowania liczb w oplocie:

Przypadki testowe

Te przypadki testowe wykorzystują indeksowanie 1-zasadowe. Każdy przypadek testowy składa się z czterech linii, z których pierwsza to dane wejściowe, a pozostałe trzy to dane wyjściowe.

1

1

---
2
 1
1
 1
---
3
 1
1 3
 1
---
5
 1 4
1 3 11
 1 4
---
10
 1 4  15  56   209
1 3 11  41  153
 1 4  15  56   209
---
15
 1 4  15  56   209   780    2911
1 3 11  41  153   571   2131    7953
 1 4  15  56   209   780    2911
---
24
 1 4  15  56   209   780    2911    10864     40545      151316      564719       2107560
1 3 11  41  153   571   2131    7953     29681     110771      413403      1542841
 1 4  15  56   209   780    2911    10864     40545      151316      564719       2107560
Martin Ender
źródło
Format wydaje mi się trochę kameleonem.
Leaky Nun
3
@LeakyNun Próbowałem tego wyzwania, gdy było w piaskownicy, i spędziłem około połowy bajtów na obliczaniu warkocza, niż na drukowaniu. Wydaje mi się to idealną równowagą dla wyzwania ascii-art .
FryAmTheEggman
4
@LeakyNun Miałem nadzieję, że zarówno generowanie sekwencji, jak i grafika ASCII są ważnymi komponentami wyzwania, ponieważ większość języków prawdopodobnie będzie lepsza w jednym z tych dwóch, więc pomyślałem, że interesujące byłoby ich pomieszanie. I wprowadza dodatkowy komponent, w którym nie jest oczywiste, czy lepiej jest generować osobno górny / dolny i środkowy, czy też generować całość, a następnie rozdzielić bisekcje.
Martin Ender
Numeryczna Pascal Braid ?
Luis Mendo,
Nikt jeszcze nie napisał rozwiązania w Pascal. To mnie smuci.
dynamitereed

Odpowiedzi:

5

Galaretka , 31 30 29 bajtów

Q;S⁹o_
3ḶḂç@⁸СIµa"Ṿ€o⁶z⁶Zµ€Z

To jest łącze monadyczne; akceptuje jako argument indeks kolumny oparty na 0 i zwraca listę ciągów znaków.

Wypróbuj online!

Jak to działa

Q;S⁹o_                  Helper link.
                        Arguments: [k, 0, k] and [0, m, 0] (any order)

Q                       Unique; deduplicate the left argument.
 ;                      Concatenate the result with the right argument.
  S                     Take the sum of the resulting array.
   ⁹o                   Logical OR with the right argument; replaces zeroes in the
                        right argument with the sum.
     _                  Subtract; take the difference with the right argument to
                        remove its values.
                        This maps [k, 0, k], [0, m, 0] to [0, k + m, 0] and
                        [0, m, 0], [k, 0, k] to [m + 2k, 0, m + 2k].


3ḶḂç@⁸СIµa"Ṿ€o⁶z⁶Zµ€Z  Monadic link. Argument: A (array of column indices)

3Ḷ                      Yield [0, 1, 2].
  Ḃ                     Bit; yield [0, 1, 0].
        I               Increments of n; yield [].
      С                Apply...
   ç@                       the helper link with swapped arguments...
     ⁸                      n times, updating the left argument with the return
                            value, and the right argument with the previous value
                            of the left one. Collect all intermediate values of
                            the left argument in an array.
         µ         µ€   Map the chain in between over the intermediate values.
            Ṿ€          Uneval each; turn all integers into strings.
          a"            Vectorized logical AND; replace non-zero integers with
                        their string representation.
              o⁶        Logical OR with space; replace zeroes with spaces.
                z⁶      Zip with fill value space; transpose the resulting 2D
                        array after inserting spaces to make it rectangular.
                  Z     Zip; transpose the result to restore the original shape.
                     Z  Zip; transpose the resulting 3D array.
Dennis
źródło
12

Pyt , 44 bajty

Generowanie liczb zajęło 20 bajtów, a formatowanie zajęło 24 bajty.

jsMC+Led.e.<bkC,J<s.u+B+hNyeNeNQ,1 1Qm*;l`dJ

Wypróbuj online!

jsMC+Led.e.<bkC,J<s.u+B+hNyeNeNQ,1 1Qm*;l`dJ   input as Q
                   .u          Q,1 1           repeat Q times, starting with [1,1],
                                               collecting all intermediate results,
                                               current value as N:
                                               (this will generate
                                                more than enough terms)
                       +hNyeN                  temp <- N[0] + 2*N[-1]
                     +B      eN                temp <- [temp+N[-1], temp]

now, we would have generated [[1, 1], [3, 4], [11, 15], [41, 56], ...]

jsMC+Led.e.<bkC,J<s                 Qm*;l`dJ
                  s                            flatten
                 <                  Q          first Q items
                J                              store in J
                                     m    dJ   for each item in J:
                                         `     convert to string
                                        l      length
                                      *;       repeat " " that many times

jsMC+Led.e.<bkC,
              C,     transpose, yielding:
[[1, ' '], [1, ' '], [3, ' '], [4, ' '], [11, '  '], ...]
(each element with as many spaces as its length.)
        .e            for each sub-array (index as k, sub-array as b):
          .<bk            rotate b as many times as k

[[1, ' '], [' ', 1], [3, ' '], [' ', 4], [11, '  '], ...]

jsMC+Led
    +Led              add to each sub-array on the left, the end of each sub-array
   C                  transpose
 sM                   sum of each sub-array (reduced concatenation)
j                     join by new-lines
Leaky Nun
źródło
7
To największy program Pyth, jaki kiedykolwiek widziałem.
imallett,
7

Python 2, 120 bajtów

a=1,1,3,4
n=input()
y=0
exec"y+=1;t='';x=0;%sprint t;"%(n*"a+=a[-2]*4-a[-4],;v=`a[x]`;t+=[v,len(v)*' '][x+y&1];x+=1;")*3

Wypróbuj na Ideone.

Lynn
źródło
7

MATL , 38 bajtów

1ti:"yy@oQ*+]vG:)!"@Vt~oX@o?w]&v]&hZ}y

Wypróbuj online!

Obliczenie tablicy z (unikalnymi) liczbami zajmuje pierwsze 17 bajtów. Formatowanie zajmuje pozostałe 21 bajtów.

Wyjaśnienie

Część 1: generowanie liczb

To generuje tablicę liczb z pierwszych i drugich rzędów rosnące: [1; 1; 3; 4; 11; 15; ...]. Zaczyna się 1, 1. Każdy nowy numer jest iteracyjnie uzyskiwany z poprzednich dwóch. Z nich drugi jest mnożony przez 1lub2 indeks iteracji zależny od niego, a następnie sumowany do pierwszego w celu uzyskania nowej liczby.

Liczba iteracji jest równa wartości wejściowej n. Oznacza to, że n+2liczby są generowane. Po wygenerowaniu tablica musi zostać przycięta, aby zachować tylko pierwsze nwpisy.

1t      % Push 1 twice
i:      % Take input n. Generage array [1 2 ... n]
"       % For each
  yy    %   Duplicate the two most recent numbers
  @o    %   Parity of the iteration index (0 or 1)
  Q     %   Add 1: gives 1 for even iteration index, 2 for odd
  *+    %   Multiply this 1 or 2 by the most recent number in the sequence, and add
       %    to the second most recent. This produces a new number in the sequence
]       % End for each
v       % Concatenate all numbers in a vertical array
G:)     % Keep only the first n entries

Część 2: sformatuj wyjście

Dla każdej liczby w uzyskanej tablicy generowane są dwa ciągi: ciąg reprezentujący liczbę oraz ciąg o tej samej długości składający się ze znaku 0 powtarzanego (znak 0 jest wyświetlany jako spacja w MATL). Nawet w przypadku iteracji te dwa ciągi są zamieniane.

Dwa łańcuchy są następnie łączone w pionie. Tak więc ntablice ·znaków 2D są tworzone w następujący sposób (przy użyciu do reprezentowania znaku 0):

·
1

1
·

· 
3

4
·

·· 
11

15
··

Te tablice są następnie łączone poziomo w celu wytworzenia

·1·4··15
1·3·11··

Wreszcie, ta tablica znaków 2D jest podzielona na dwa rzędy, a pierwszy jest powielany na górze stosu. Trzy ciągi znaków są wyświetlane w kolejności, każdy w innym wierszu, tworząc pożądany wynik

!       % Transpose into a horizontal array [1 1 3 4 11 15 ...]
"       % For each
  @V    %   Push current number and convert to string
  t~o   %   Duplicate, negate, convert to double: string of the same length consisting 
        %   of character 0 repeated
  X@o   %   Parity of the iteration index (1 or 0)
  ?     %   If index is odd
    w   %     Swap
  ]     %   End if
  &v    %   Concatenate the two strings vertically. Gives a 2D char array representing
        %   a "numeric column" of the output (actually several columns of characters)
]       % End for
&h      % Concatenate all 2D char arrays horizontally. Gives a 2D char array with the
        % top two rows of the output
Z}      % Split this array into its two rows
y       % Push a copy of the first row. Implicitly display
Luis Mendo
źródło
6

Haskell, 101 bajtów

a=1:1:t
t=3:4:zipWith((-).(4*))t a
g(i,x)=min(cycle" 9"!!i)<$>show x
f n=[zip[y..y+n]a>>=g|y<-[0..2]]

Definiuje funkcję f :: Int → [String].

  • Michael Klein przypomniał mi, że nie musiałem sprawdzać unlineswyniku, oszczędzając 7 bajtów. Dzięki!

  • Zapisałem bajt, zastępując " 9"!!mod i 2go cycle" 9"!!i.

  • Jeszcze trzy bajty, pisząc dwie listy corecursive zamiast używać drop.

  • Moja dziewczyna zauważyła, że ​​mogę zaoszczędzić jeszcze dwa bajty, rozpoczynając odpowiedzi od 0zamiast 1.

Lynn
źródło
3

C 183 177 176 bajtów

#define F for(i=0;i<c;i++)
int i,c,a[35],t[9];p(r){F printf("%*s",sprintf(t,"%d",a[i]),r-i&1?t:" ");putchar(10);}b(n){c=n;F a[i]=i<2?1:a[i-2]+a[i-1]*(i&1?1:2);p(0);p(1);p(0);}

Wyjaśnienie

C nigdy nie wygra żadnych nagród za zwięzłość w stosunku do języka wyższego poziomu, ale ćwiczenie to jest interesujące i dobre praktyki.

Makro F goli sześć bajtów kosztem czytelności. Zmienne są deklarowane globalnie, aby uniknąć wielokrotnych deklaracji. Potrzebowałem bufora znaków dla sprintf, ale ponieważ K&R jest luźny w sprawdzaniu typów, sprintf i printf mogą interpretować t [9] jako wskaźnik do bufora 36-bajtowego. Zapisuje to osobną deklarację.

#define F for(i=0;i<c;i++)
int i,c,a[35],t[9];

Ładna funkcja drukowania, gdzie r jest numerem wiersza. Sprintf formatuje liczbę i oblicza szerokość kolumny. Aby zaoszczędzić miejsce, po prostu wywołujemy to trzy razy, po jednym dla każdego wiersza wyniku; wyrażenie ri i 1 filtruje to, co zostanie wydrukowane.

p(r) {
    F
        printf("%*s", sprintf(t, "%d", a[i]), r-i&1 ? t
                                                    : " ");
    putchar(10);
}

Funkcja punktu wejścia, argument to liczba kolumn. Oblicza tablicę a wartości kolumn a [], a następnie wywołuje funkcję drukowania p jeden raz dla każdego wiersza wyniku.

b(n) {
    c=n;
    F
        a[i] = i<2 ? 1
                   : a[i-2] + a[i-1]*(i&1 ? 1
                                          : 2);
    p(0);
    p(1);
    p(0);
}

Przykładowe wywołanie (nieuwzględnione w odpowiedzi i liczbie bajtów):

main(c,v) char**v;
{
    b(atoi(v[1]));
}

Zaktualizowano

Zawarte w linii sugestii sprintf z Tomsmeding. To zmniejszyło liczbę z 183 do 177 znaków. Pozwala to również na usunięcie nawiasów klamrowych wokół bloku printf (sprintf ()), ponieważ jest to teraz tylko jedna instrukcja, ale zapisano tylko jeden znak, ponieważ nadal wymaga spacji jako separatora. A więc do 176.

maharvey67
źródło
Nie możesz wstawić definicji tego, wgdzie jest używany? Wydaje się, że używasz go tylko raz.
tomsmeding
Nie możesz użyć itoazamiast sprintf?
Giacomo Garabello,
Rozważałem itoa, ale nie ma go w moim systemie i używam wartości zwracanej przez sprintf do ustawiania szerokości pola.
maharvey67
2

PowerShell v2 +, 133 bajty

param($n)$a=1,1;1..$n|%{$a+=$a[$_-1]+$a[$_]*($_%2+1)};$a[0..$n]|%{$z=" "*$l+$_;if($i++%2){$x+=$z}else{$y+=$z}$l="$_".Length};$x;$y;$x

44 bajty do obliczenia wartości, 70 bajtów do sformułowania ASCII

Pobiera dane wejściowe $njako kolumnę o indeksie zerowym. Ustawia początek naszej tablicy sekwencji $a=1,1. Następnie zapętlamy do $nz, 1..$n|%{...}aby zbudować tablicę. Każdej iteracji łączymy sumę (dwa elementy temu) + (poprzedni element) * (niezależnie od tego, czy jesteśmy indeksem nieparzystym, czy parzystym). To wygeneruje $a=1,1,3,4,11...do$n+2 .

Musimy więc pokroić, $aaby wziąć tylko pierwsze 0..$nelementy i przepuścić je przez kolejną pętlę |%{...}. W każdej iteracji ustawiamy helper $zrówny liczbie spacji plus bieżący element jako ciąg. Następnie rozdzielamy, czy to zostanie konkatenowane do $x(górnego i dolnego rzędu) czy $y(środkowego rzędu) przez zwykłe parzyste if/ nieparzyste / else. Następnie obliczamy liczbę spacji $l, biorąc bieżącą liczbę, ustalając ją i biorąc ją .Length.

Wreszcie, umieszczamy $x, $yi $xznowu w potoku, a wyniki są niejawne. Ponieważ domyślnym .ToString()separatorem dla tablicy podczas drukowania do STDOUT jest nowa linia, otrzymujemy to za darmo.

Przykład

PS C:\Tools\Scripts\golfing> .\pascal-braid.ps1 27
 1 4  15  56   209   780    2911    10864     40545      151316      564719       2107560       7865521        29354524
1 3 11  41  153   571   2131    7953     29681     110771      413403      1542841       5757961       21489003
 1 4  15  56   209   780    2911    10864     40545      151316      564719       2107560       7865521        29354524
AdmBorkBork
źródło
0

PHP 265 bajtów

<?php $i=$argv[1];$i=$i?$i:1;$a=[[],[]];$s=['',''];$p='';for($j=0;$j<$i;$j++){$y=($j+1)%2;$x=floor($j/2);$v=$x?$y?2*$a[0][$x-1]+$a[1][$x-1]:$a[0][$x-1]+$a[1][$x]:1;$s[$y].=$p.$v;$a[$y][$x]=$v;$p=str_pad('',strlen($v),' ');}printf("%s\n%s\n%s\n",$s[0],$s[1],$s[0]);

Bez golfa:

$a = [[],[]];
$s = ['',''];

$p = '';

$i=$argv[1];
$i=$i?$i:1;
for($j=0; $j<$i; $j++) {
    $y = ($j+1) % 2;
    $x = floor($j/2);

    if( $x == 0 ) {
        $v = 1;
    } else {
        if( $y ) {
            $v = 2 * $a[0][$x-1] + $a[1][$x-1];
        } else {
            $v = $a[0][$x-1] + $a[1][$x];
        }
    }
    $s[$y] .= $p . $v;
    $a[$y][$x] = $v;
    $p = str_pad('', strlen($v), ' ');
}

printf("%s\n%s\n%s\n", $s[0], $s[1], $s[0]);

Python 278 bajtów

import sys,math;a=[[],[]];s=['',''];p='';i=int(sys.argv[1]);i=1 if i<1 else i;j=0
while j<i:y=(j+1)%2;x=int(math.floor(j/2));v=(2*a[0][x-1]+a[1][x-1] if y else a[0][x-1]+a[1][x]) if x else 1;s[y]+=p+str(v);a[y].append(v);p=' '*len(str(v));j+=1
print ("%s\n"*3)%(s[0],s[1],s[0])
Sammitch
źródło
0

Rubin, 120 bajtów

Zwraca ciąg multilinii.

Wypróbuj online!

->n{a=[1,1];(n-2).times{|i|a<<(2-i%2)*a[-1]+a[-2]}
z=->c{a.map{|e|c+=1;c%2>0?' '*e.to_s.size: e}*''}
[s=z[0],z[1],s]*$/}
Wartość tuszu
źródło
0

Matlab, 223 znaki, 226 bajtów

function[]=p(n)
r=[1;1];e={(' 1 ')',('1 1')'}
for i=3:n;r(i)=sum((mod(i,2)+1)*r(i-1)+r(i-2));s=num2str(r(i));b=blanks(floor(log10(r(i)))+1);if mod(i,2);e{i}=[b;s;b];else e{i}=[s;b;s];end;end
reshape(sprintf('%s',e{:}),3,[])

Nie golfił i skomentował:

function[]=p(n) 
r=[1;1];                                    % start with first two 
e={(' 1 ')',('1 1')'}                       % initialize string output as columns of blank, 1, blank and 1, blank, 1.
for i=3:n;                                  % for n=3 and up! 
    r(i)=sum((mod(i,2)+1)*r(i-1)+r(i-2));   % get the next number by 1 if even, 2 if odd times previous plus two steps back
    s=num2str(r(i));                        % define that number as a string
    b=blanks(floor(log10(r(i)))+1);         % get a number of space characters for that number of digits
    if mod(i,2);                            % for odds
        e{i}=[b;s;b];                       % spaces, number, spaces
    else                                    % for evens
        e{i}=[s;b;s];                       % number, spaces, number
    end;
end
reshape(sprintf('%s',e{:}),3,[])            % print the cell array of strings and reshape it so it's 3 lines high
sintax
źródło
0

PHP, 135 124 123 120 bajtów

<?while($i<$argv[1]){${s.$x=!$x}.=${v.$x}=$a=$i++<2?:$v1+$v+$x*$v;${s.!$x}.=str_repeat(' ',strlen($a));}echo"$s
$s1
$s";

wykorzystując niejawne typecasty i zmienne zmienne
jedna trzecia kodu (37 bajtów) trafia do spacji, a 64 bajty w całości są wykorzystywane na wyjście

awaria

$i=0; $x=false; $v=$v1=1; $s=$s1='';    // unnecessary variable initializations
for($i=0;$i<$argv[1];$i++)  // $i is column number -1
{
    $x=!$x; // $x = current row: true (1) for inner, false (empty string or 0) for outer
    // calculate value
    $a=
        $i<2?               // first or second column: value 1
        :$v1+(1+$x)*$v      // inner-val + (inner row: 1+1=2, outer row: 1+0=1)*outer-val
    ;
    ${s.$x}.=${v.$x}=$a;    // replace target value, append to current row
    ${s.!$x}.=str_repeat(' ',strlen($a));    // append spaces to other row
}
// output
echo "$s\n$s1\n$s";
Tytus
źródło
0

Partia, 250 bajtów

@echo off
set s=
set d=
set/ai=n=0,j=m=1
:l
set/ai+=1,j^^=3,l=m+n*j,m=n,n=l
set t=%s%%l%
for /l %%j in (0,1,9)do call set l=%%l:%%j= %%
set s=%d%%l%
set d=%t%
if not %i%==%1 goto l
if %j%==1 echo %d%
echo %s%
echo %d%
if %j%==2 echo %s%

Ponieważ pierwsza i trzecia linia są takie same, musimy tylko zbudować dwa ciągi. Tutaj dreprezentuje ciąg, który kończy się ostatnim wpisem i sreprezentuje ciąg, który kończy się spacjami; ostatnie cztery wiersze zapewniają, że zostaną wydrukowane w odpowiedniej kolejności. ijest tylko licznikiem pętli (jest nieco tańszy niż odliczanie od %1). jto przełączanie między podwojeniem poprzedniego numeru przed dodaniem go do bieżącego numeru, aby uzyskać następny numer. mi nzawierają te liczby. l, oprócz tego, że jest tymczasowo używany do obliczenia następnej liczby, zastępuje się również cyframi spacjami s; si dsą wymieniane za każdym razem za pośrednictwem zmiennej pośredniej t.

Neil
źródło