Ta konstrukcja jest sposobem reprezentacji liczb naturalnych.

W tej reprezentacji 0 jest zdefiniowane jako pusty zbiór, a dla wszystkich innych liczb n oznacza połączenie {0} i {n-1}.

Na przykład, aby zbudować 3, możemy zastosować algorytm:

3 =
{ø, 2} =
{ø, {ø, 1}} =
{ø, {ø, {ø}}}

Zadanie

Jak można się domyślać, Twoim zadaniem jest przyjęcie liczby naturalnej (w tym zero) i wygenerowanie jej konstrukcji.

Możesz wyprowadzać dane jako ciąg znaków lub jako obiekt zestawu, jeśli wybrany język obsługuje takie obiekty.

Jeśli wybierzesz wyjście jako ciąg, powinieneś reprezentować zestaw z nawiasami klamrowymi ( {}). Opcjonalnie możesz reprezentować pusty zestaw jako ø(w przeciwnym razie powinien to być zestaw bez wpisów {}). Możesz także dodać przecinki i białe znaki między wpisami w zestawie i po nim.

Kolejność nie jest ważna, jednak możesz nie mieć powtarzających się elementów w zestawach, które wysyłasz (np. {ø,ø})

To jest golf golfowy, więc celem jest jak najmniej bajtów

Przypadki testowe

Oto kilka przypadków testowych z przykładowymi danymi wyjściowymi.

0 -> {}
1 -> {{}}
2 -> {{}{{}}}
3 -> {{}{{}{{}}}}
4 -> {{}{{}{{}{{}}}}}

Python , 28 bajtów

lambda x:"{{}"*x+x*"}"or"{}"

Wypróbuj online!

Jest to dość nijakie rozwiązanie problemu. W przypadku liczb większych niż zero można uzyskać reprezentację za pomocą formuły ciągów "{{}"*x+"}"*x. Jednak to nie działa dla zera, gdy jest to pusty ciąg. Możemy wykorzystać ten fakt do zwarcia i orzwrócenia pustego zestawu.

Chciałem użyć obiektów wbudowanych w Pythona, aby rozwiązać ten problem, ale niestety:

TypeError: unhashable type: 'set'

Nie możesz umieszczać zestawów w zestawach w Pythonie.

Haskell , 37 bajtów

f 0="{}"
f n=([1..n]>>)=<<["{{}","}"]

Wypróbuj online!

Jeszcze 10 minut temu taka odpowiedź nie miałaby dla mnie żadnego sensu. Wszystkie kredyty przechodzą do odpowiedzi na te wskazówki .

Zasadniczo używamy >>jako concat $ replicate(ale przekazując mu listę n elementów zamiast po prostu n) i =<<jako concatMap, replikując, a następnie n razy każdy ciąg z listy i łącząc wynik w pojedynczy ciąg.

0Przypadek jest traktowany osobno jako że zwróci pusty ciąg.

JavaScript, 28 bajtów

f=n=>n?--n?[[],f(n)]:[[]]:[]

Reprezentuje zestawy za pomocą tablic. 38-bajtowe rozwiązanie nierekurencyjne:

n=>'{{}'.repeat(n)+'}'.repeat(n)||'{}'

Zwraca przykładowe ciągi wyjściowe.

Mathematica, 27 bajtów

Mam dwa rozwiązania w tej liczbie bajtów:

Nest[{{}}~Union~{#}&,{},#]&
Union//@Nest[{{},#}&,{},#]&

Perl 6 , 37 bajtów

{('{}','{{}}',{q:s'{{}$_}'}...*)[$_]}

Spróbuj

Rozszerzony:

{   # bare block lambda with implicit parameter ｢$_｣

  (
    # generate a sequence

    '{}',   # seed it with the first two values
    '{{}}',

    {   # bare block lambda with implicit parameter ｢$_｣

      q         # quote
      :scalar   # allow scalar values

      '{{}$_}'  # embed the previous value ｢$_｣ in a new string

    }

    ...         # keep using that code block to generate values

    *           # never stop

  )[ $_ ] # get the value at the given position in the sequence
}

05AB1E , 6 5 bajtów

Kod

ƒ)¯sÙ

Wykorzystuje kodowanie CP-1252 . Wypróbuj online! lub Zweryfikuj wszystkie przypadki testowe! .

Wyjaśnienie

ƒ       # For N in range(0, input + 1)..
 )      #   Wrap the entire stack into an array
  ¯     #   Push []
   s    #   Swap the two top elements
    Ù   #   Uniquify the array

Siatkówka , 22 bajty

.+
$*
\`.
{{}
{

^$
{}

Wypróbuj online!

Wyjaśnienie

.+
$*

Przekształć dane wejściowe w jednoargumentowe.

\`.
{{}

Zastąp każdą pojedynczą cyfrę {{}znakiem i wydrukuj wynik bez końcowego linefeed ( \).

{

Usuń otwory {s, aby pozostałe }były dokładnie tymi, które wciąż musimy wydrukować, aby zamknąć wszystkie zestawy. Jednak powyższa procedura kończy się niepowodzeniem w przypadku danych wejściowych 0, w których niczego nie drukujemy. Więc...

^$
{}

Jeśli ciąg jest pusty, zastąp go pustym zestawem.

Brain-Flak , 135 bajtów

Obejmuje +1 dla -A

(({}())<{({}[()]<((((((()()()()()){}){}){}())()){}{})>)}{}({}[()()])>)(({})<{({}[()]<(((({}()())[()()])))>)}{}>[()]){(<{}{}{}>)}{}{}{}

Wypróbuj online!

(({}())<                 # Replace Input with input + 1 and save for later
  {({}[()]<              # For input .. 0
    (...)                # Push '}'
  >)}{}                  # End for and pop counter
  ({}[()()])             # change the top '}' to '{'. This helps the next stage
                         # and removes the extra '}' that we got from incrementing input
>)                       # Put the input back on

(({})<                   # Save input
  {({}[()]<              # For input .. 0
    (((({}()())[()()]))) # Replace the top '{' with "{{{}"
  >)}{}                  # end for and pop the counter
>[()])                   # Put down input - 1
{(<{}{}{}>)}             # If not 0, remove the extra "{{}"
{}{}{}                   # remove some more extras

Röda , 37 bajtów

f n{[[[],f(n-1)]]if[n>1]else[[[]]*n]}

CJam , 11 bajtów

Lri{]La|}*p

Drukuje obiekt podobny do zestawu składający się z list list. CJam drukuje puste listy jako puste ciągi, ponieważ listy i ciągi są prawie wymienne.

Wypróbuj online!

Wyjaśnienie

L            Push an empty array 
 ri          Read an integer from input
   {    }*   Run this block that many times:
    ]          Wrap the entire stack in an array
     La        Wrap an empty list in an array, i.e. [[]]
       |       Set union of the two arrays
          p  Print the result

Stara odpowiedź, 21 18 bajtów

Było to przed potwierdzeniem, że wydrukowanie struktury listy zagnieżdżonej jest w porządku. Wykorzystuje algorytm powtarzania łańcucha.

Zaoszczędzono 3 bajty dzięki Martinowi Enderowi!

ri{{}}`3/f*~_{{}}|

Wyjaśnienie

ri                  Read an integer from input
  {{}}`             Push the string "{{}}"
       3/           Split it into length-3 subtrings, gives ["{{}" "}"]
         f*         Repeat each element of that array a number of times equal to the input
           ~_       Dump the array on the stack, duplicate the second element
             {{}}|  Pop the top element, if it's false, push an empty block, which gets 
                      printed as "{}". An input of 0 gives two empty strings on the 
                      repetition step. Since empty strings are falsy, we can correct the 
                      special case of 0 with this step.

Galaretka , 6 bajtów

⁸,⁸Q$¡

Jest to link zerowy, który odczytuje liczbę całkowitą ze STDIN i zwraca niewyrównaną tablicę.

Wypróbuj online!

Jak to działa

⁸,⁸Q$¡  Niladic link.

⁸       Set the return value to [].
    $   Combine the three links to the left into a monadic chain.
 ,⁸     Pair the previous return value with the empty array.
   Q    Unique; deduplicate the result.
     ¡  Read an integer n from STDIN and call the chain to the left n times.

Python 3 , 32 bajty

f=lambda n:[[],n and f(n-1)][:n]

Nie najkrótsza droga, ale musiałem to zrobić z rekurencją.

Wypróbuj online!

Kardynał , 51 50 bajtów

%:#>"{"#? v
x  ^?-"}{"<
v <8/ ?<
>  8\
v"}"<
>?-?^

Wypróbuj online!

Wyjaśnienie

%:#
x

Odbierz dane wejściowe i wyślij w dół i w lewo od #

   >"{" ? v
   ^?-"}{"<

Wydrukuj „{” jeden raz, a następnie wydrukuj „{} {” n-1 razy, jeśli n> 1, a następnie wydrukuj „{}”, jeśli n> 0

       #

v <8/ ?<
>  8\

Trzymaj wartość wejściową, aż pierwsza pętla się zakończy

v"}"<
>?-?^

Wydrukuj „}” raz, a następnie powtórz n-1 razy, jeśli n> 1

AHK, 55 bajtów

IfEqual,1,0
s={{}{}}
Loop,%1%
s={{ 2}{}}%s%{}}
Send,%s%

To nie jest najkrótsza odpowiedź, ale podobało mi się to, ponieważ osobliwości AutoHotkey sprawiają, że ta metoda rekurencji wygląda bardzo źle. Ifa Loopinstrukcje zakładają, że następny wiersz jest jedyną zawartą pozycją, jeśli nawiasy nie są używane. Nawiasy klamrowe to znaki specjalne, więc musisz użyć innych nawiasów klamrowych, aby użyć ich jako tekstu. Również zmienna1 jest również pierwszym przekazywanym argumentem. Kiedy czytam kod, nie znając tych ciekawostek, logika wygląda następująco:

• Jeśli 1 = 0, ustaw wartość srówną błędnej odpowiedzi
• Zapętlaj i dodaj za każdym razem kilka nawiasów klamrowych i kilka na końcu
• Wróć, wysyłając wynikowy ciąg do bieżącego okna

Bez wszystkich znaków otwierających nawiasy wyglądałoby to tak:

IfEqual,1,0
   s={}
Loop,%1%
   s={{}%s%}
Send,%s%

JavaScript 50 bajtów

g=n=>n==0?"":"{{}"+g(n-1)+"}"
z=m=>m==0?"{}":g(m)

tinylisp , 52 bajty

(d f(q((n)(i n(i(e n 1)(c()())(c()(c(f(s n 1))())))(

Wypróbuj online! (uprząż testowa).

Wyjaśnienie

Zauważ, że w (cons x (cons y nil))ten sposób budujesz listę zawierającą xi yw Lisp.

(d f           Define f to be
 (q(           a quoted list of two items (which acts as a function):
  (n)           Arglist is a single argument n
  (i n          Function body: if n is truthy (i.e. nonzero)
   (i(e n 1)     then if n equals 1
    (c()())       then cons nil to nil, resulting in (())
    (c            else (if n > 1) cons
     ()            nil to
     (c            cons
      (f(s n 1))    (recursive call with n-1) to
      ())))         nil
   ()))))        else (if n is 0) nil

C (gcc) , 52 bajty

n(i){putchar(123);i>1&&n(0);i&&n(i-1);putchar(125);}

Wykorzystując pewną ocenę zwarcia i rekurencję.

Wypróbuj online!

Pure Bash , 49 48 41 bajtów

for((;k++<$1;)){ s={{}$s};};echo ${s-{\}}

Wypróbuj online!

dc , 46 bajtów

[[{}]]sx256?^dd3^8d^1-/8092541**r255/BF*+d0=xP

Wypróbuj online!

Wejście na stdin, wyjście na stdout.

Działa to poprzez obliczenie formuły dla pożądanego wyniku jako liczby podstawowej-256. Komenda P w dc jest następnie używana do wypisania liczby base-256 jako łańcucha.

Dalsze wyjaśnienia:

Niech n będzie wejściem n. Program dc oblicza sumę

A = piętro (256 ^ n / 255) * 125 (BF jest interpretowane przez dc jako 11 * 10 + 15 = 125)

i

B = podłoga ((256 ^ n) ^ 3 / (8 ^ 8-1)) * 8092541 * (256 ^ n).

Dla:

Zauważ, że 1 + 256 + 256 ^ 2 + ... + 256 ^ (n-1) równa się (256 ^ n-1) / 255 według wzoru dla postępu geometrycznego, a to równa się podłodze (256 ^ n / 255 ). Jest to więc liczba składająca się z n 1 w bazie 256.

Po pomnożeniu go przez 125, aby uzyskać A, wynikiem jest liczba składająca się z n 125 w podstawie 256 (oczywiście 125 jest pojedynczą cyfrą w podstawie 256). Prawdopodobnie lepiej jest zapisać cyfry w bazie 256 jako liczby szesnastkowe; 125 jest szesnastkowym 7D, więc A jest liczbą podstawową-256 składającą się z n 7D z rzędu.

B jest podobny:

Tym razem zauważ, że 1 + 16777216 + 16777216 ^ 2 + ... + 16777216 ^ (n-1) równa się (16777216 ^ n - 1) / 16777215, a to równa się podłodze (16777216 ^ n / 16777215).

Teraz 256 ^ 3 = 16777216 i 8 ^ 8-1 = 16777215, więc to właśnie obliczamy jako floor ((256 ^ n) ^ 3 / (8 ^ 8-1)).

Z reprezentacji szeregów geometrycznych liczba ta w podstawie 256 wynosi 100100100 ... 1001, gdzie n cyfr to 1, a pozostałe cyfry to 0.

Mnożymy to przez 8092541, czyli 7B7B7D w systemie szesnastkowym. W bazie 256 jest to trzycyfrowa liczba składająca się z cyfr 7B, 7B i 7D (dla wygody zapisuje te cyfry szesnastkowo).

Wynika z tego, że produkt zapisany w bazie 256 jest liczbą 3n cyfr składającą się z 3 cyfr 7B 7B 7D powtórzonych n razy.

Mnoży się to przez 256 ^ n, co daje 4n-cyfrową liczbę podstawową-256, składającą się z 3 cyfr 7B 7B 7D powtórzonych n razy, po których następuje n 0. To jest B.

Dodanie A + B daje teraz 4n-cyfrową liczbę podstawową-256 składającą się z 3 cyfr 7B 7B 7D powtórzonych n razy, a następnie n 7D. Ponieważ 7B i 7D są odpowiednio kodami ASCII {i }jest to ciąg składający się z n kopii, {{}a następnie n kopii }, co jest dokładnie tym, czego chcemy dla n> 0. Polecenie P w dc wypisuje liczbę podstawową 256 jako ciąg, tak jak potrzebujemy.

Niestety n = 0 należy traktować jako szczególny przypadek. Powyższe obliczenia dają wynik 0 dla n = 0; w takim razie właśnie zakodowałem wydruk napisu {}.

Java 7, 61 bajtów

String p(int p){return p<1?"{}":p<2?"{{}}":"{{}"+p(p-1)+"}";}

Wypróbuj online!

Partia, 88 bajtów

@set s={}
@if %1 gtr 0 set s=&for /l %%i in (1,1,%1)do @call set s={{}%%s%%}
@echo %s%

Brainf *** , 99 bajtów

>+>+>+>+<[>[-<+++++>]<-<]>--[->+>+<<]
>[-<+>]>++<,[[->>+>+<<<]>>[-<<<..>>.>]>[-<<.>>]+[]]<.>>.

(nowa linia dla estetyki) Ponieważ jest to mózg ***, przyjmuje dane jako kody znaków ascii (wejście „a” odpowiada 96)

Braineasy, 60 bajtów

Ponadto, w moim niestandardowym języku (na podstawie brainf **, tłumacz tutaj ):

#123#[->+>+<<]>++<,[[-<+<+>>]<[->>>..<.<<]<[->>>.<<<]!]>>.<.

Musisz na stałe zakodować wejście programu do interpretera, ponieważ jestem leniwy.

05AB1E , 5 3 bajty

F¯)

Wypróbuj online!

Ta wersja jest po tym, jak wyjaśnił, że zestawy są w porządku.

F   # From 1 to input...
 ¯  # Push global array (default value is []).
  ) # Wrap stack to array.

Stara wersja (wykorzystująca ø):

05AB1E , 5 4 bajtów

FX¸)

Wypróbuj online!

Gdzie 1jest równoważne z ø.

F    # From 1 to input...
 X   # Push value in register X (default is 1).
  ¸  # Wrap pushed value into an array.
   ) # Wrap whole stack into an array.
     # Implicit loop end (-1 byte).
     # Implicit return.