Teoretycznie zadanej liczby naturalne $\mathbb{N} = \{0, 1, 2, 3, ...\}$ są zwykle kodowane jako czyste zestawy , czyli zestawy zawierające tylko pusty zestaw lub inne zestawy, które są czyste. Jednak nie wszystkie czyste zbiory reprezentują liczby naturalne. Wyzwanie polega na podjęciu decyzji, czy dany czysty zestaw reprezentuje kodowanie liczby naturalnej, czy nie.

Kodowanie liczb naturalnych działa w następujący sposób ¹ :

• Zero to pusty zbiór: $Set(0) = \{\}$
• Dla liczby $n > 0$ : $Set(n) = Set(n-1) \cup \{Set(n-1)\}$

Tak więc kodowanie pierwszych kilku liczb naturalnych jest

• $0 \leadsto \{\}$
• $1 \leadsto \{0\} \leadsto \{\{\}\}$
• $2 \leadsto \{0,1\} \leadsto \{\{\},\{\{\}\}\}$
• $3 \leadsto \{0,1,2\} \leadsto \{\{\},\{\{\}\},\{\{\},\{\{\}\}\}\}$
• $4 \leadsto \{0,1,2,3\} \leadsto \{\{\},\{\{\}\},\{\{\},\{\{\}\}\},\{\{\},\{\{\}\},\{\{\},\{\{\}\}\}\}\}$

Zadanie

• Biorąc pod uwagę ciąg reprezentujący czysty zestaw, określ, czy ten zestaw koduje liczbę naturalną zgodnie z powyższą konstrukcją.
• Pamiętaj jednak, że elementy zestawu nie są uporządkowane, więc $\{\{\},\{\{\}\},\{\{\},\{\{\}\}\}\}$ nie jest jedyną prawidłową reprezentacją $3$ np. $\{\{\{\}\},\{\},\{\{\{\}\},\{\}\}\}$ reprezentuje ten sam zestaw.
• Można użyć [], ()lub <>zamiast {}.
• Możesz założyć, że zestawy są podane bez ,separatora.
• Można założyć, że nie będzie żadnych zduplikowanych elementów w wejściu, na przykład {{},{}}nie jest poprawnym wejście, a wejście jest dobrze uformowane, na przykład brak {{},, {,{}}lub podobny.

Przypadki testowe

Prawdziwe:

{}
{{}}
{{},{{}}}
{{{}},{}}
{{},{{}},{{},{{}}}}
{{{},{{}}},{},{{}}}
{{{{}},{}},{{}},{}}
{{},{{}},{{},{{}}},{{},{{}},{{},{{}}}}}
{{{{{}},{}},{{}},{}},{{}},{},{{},{{}}}}
{{},{{}},{{},{{}},{{},{{}}},{{},{{}},{{},{{}}}}},{{{}},{}},{{},{{}},{{},{{}}}}}
{{{{{{{{}},{}},{{}},{}},{{{}},{}},{{}},{}},{{{{}},{}},{{}},{}},{{{}},{}},{{}},{}},{{{{{}},{}},{{}},{}},{{{}},{}},{{}},{}},{{{{}},{}},{{}},{}},{{{}},{}},{{}},{}},{{{{{{}},{}},{{}},{}},{{{}},{}},{{}},{}},{{{{}},{}},{{}},{}},{{{}},{}},{{}},{}},{{{{{}},{}},{{}},{}},{{{}},{}},{{}},{}},{{{{}},{}},{{}},{}},{{{}},{}},{{}},{}}

Fałszywe:

{{{}}}
{{{{}}}}
{{{{}},{}}}
{{},{{}},{{{}}}}
{{{},{{}}},{{}}}
{{{{{}}},{}},{{}},{}}
{{},{{}},{{},{{}}},{{},{{}},{{{}}}}}
{{{{{}},{}},{{{}}},{}},{{}},{},{{},{{}}}}
{{{{{{{{}},{}},{{}},{}},{{{}},{}},{{}},{}},{{{{}},{}},{{}},{}},{{{}},{}},{{}},{}},{{{{{}},{}},{{}},{}},{{{}},{}},{{}},{}},{{{{}},{}},{{}},{}},{{{}},{}},{{}},{}},{{{{{{}},{}},{{}},{}},{{{}},{}},{{}},{}},{{{{}},{}},{{}},{}},{{{}},{}},{{}},{}},{{{{{}},{}},{{}},{}},{{{}},{}},{{}}},{{{{}},{}},{{}},{}},{{{}},{}},{{}},{}}

^{Powiązane: Konstrukcja naturalna (Wyjście kodowania zestawu podanej liczby naturalnej.)
1 Patrz https://en.wikipedia.org/wiki/Set-theoretic_definition_of_natural_numbers}

JavaScript (Node.js) , 53 48 44 bajtów

f=a=>(a=eval(a)).every(e=>a[e.length]&&f(e))

Wypróbuj online! Przypadki testowe w większości bezwstydnie skradzione z odpowiedzi @ Arnauld. Objaśnienie: Jeśli zbiór reprezentuje liczbę naturalną, wówczas liczba naturalna, którą reprezentuje, musi być równa wielkości zbioru, a (biorąc pod uwagę, że elementy są gwarantowane odrębne), elementy muszą być reprezentacjami liczb naturalnych mniejszych od niego, i dlatego muszą mieć krótsze długości. Jest to oczywiście prawda dotycząca pustego zestawu. Edycja: Zapisano 5 bajtów dzięki @Arnauld. Zaoszczędź 4 bajty dzięki @Cowsquack.

Python 3 , 69 58 44 bajtów

11 bajtów dzięki Erikowi Outgolfer.

14 bajtów dzięki Mr. Xcoder.

f=lambda s:all(len(e)<len(s)*f(e)for e in s)

Wypróbuj online!

Wolfram Language (Mathematica) , 60 59 bajtów

E!=(If[Sort@#===Range[t=Tr[1^#]]-1,t,E]&//@ToExpression@#)&

Wypróbuj online!

Rdzeniem tego rozwiązania jest funkcja

If[Sort@#===Range[t=Tr[1^#]]-1,t,E]&

która konwertuje listę formularza {0,1,2,...,n-1}w dowolnej kolejności na wynik n(w szczególności konwertuje {}na 0) i konwertuje cokolwiek innego na liczbę rzeczywistą E.

Wywołaj tę funkcję f. Biorąc pod uwagę dane wejściowe takie jak "{{{}},{}}", wykonujemy następujące czynności:

1. Przekształć ciąg w wyrażenie matematyczne.
2. Aplikuj fna każdym poziomie, otrzymując f[{f[{f[{}]}], f[{}]}].
3. Ocena wszystkich fspowoduje utworzenie liczby naturalnej dla reprezentującego ją wkładu. Na przykład f[{f[{f[{}]}], f[{}]}]= f[{f[{0}], 0}]= f[{1, 0}]= 2. Wszystko inne będzie produkować E.
4. Sprawdzamy, czy wynikiem jest liczba naturalna, sprawdzając, czy nie jest E.

Brachylog (v2), 9 bajtów

↰ᵐo.t~k|Ė

Wypróbuj online!

Jak zwykle w przypadku problemu decyzyjnego , jest to pełny program. Wprowadzanie ze standardowego wejścia za pomocą nawiasów kwadratowych. Wyjście na standardowe wyjście w true.porównaniu do false..

Wyjaśnienie

Chociaż powiedziałem powyżej, że jest to pełny program, jest tak naprawdę bardziej interesujący; to zarówno pełny program, jak i funkcja. Gdy jest używany jako pełny program, drukuje, true.jeśli zestaw jest liczbą naturalną, lubfalse. nie. Gdy jest używany jako funkcja, „normalizuje” liczbę naturalną (tj. Normalizuje wszystkie jej elementy i sortuje je w kolejności według wartości; ten program używa list wewnętrznie, a nie ustawia), lub „zgłasza wyjątek” (w rzeczywistości awarię, ponieważ to Prolog), jeśli dane wejściowe nie są liczbą naturalną.

Pełne zachowanie programu jest wystarczająco łatwe do wyjaśnienia: jest ono całkowicie ukryte w traktowaniu przez Brachylog pełnych programów, które nie zawierają instrukcji We / Wy. Zachowanie, o którym mowa, to „uruchom funkcję, pobierając dane wejściowe ze standardowego wejścia i upewniając się, że dane wyjściowe są zgodne z opisem podanym w pierwszym argumencie wiersza poleceń; jeśli asercja nie powiedzie się lub program zgłosi wyjątek, wydrukuj false., w przeciwnym razie wydrukuj true.” . W takim przypadku brakuje argumentu wiersza polecenia (tzn. „Wszystko idzie”), więc zachowanie funkcji wyjątek / brak wyjątku daje wynik.

Jeśli chodzi o zachowanie funkcji:

↰ᵐo.t~k|Ė
↰ᵐ          Map a recursive call to this function over the list
  o         Sort the list
   .   |    Assert that the following operation need not change the list:
    t         Take the last (i.e. greatest) element of the list
     ~k       Append an arbitrary element to the resulting list
   .   |    Output the unchanged list
       |    Exception handler: if the above threw an exception,
        Ė     Assert that the input is empty, and output an empty list

Liczba naturalna jest zdefiniowana jako zawierająca dwie części: elementy liczby naturalnej poniżej, zjednoczone z samą liczbą. Zatem wszystkie jego elementy są również liczbami naturalnymi. Możemy rozpoznać liczbę naturalną poprzez a) sprawdzenie, czy wszystkie jej elementy są liczbami naturalnymi, b) sprawdzenie, czy największy element zbioru jest identyczny z zestawem bez jego największego elementu.

Kiedy używamy list zamiast zestawów (a więc nawiasów kwadratowych), musimy uporządkować je w spójnej kolejności, aby porównania równości działały (w tym przypadku posortowane według „wartości”). Domyślna kolejność sortowania Brachylog posortuje prefiks listy przed samą listą, co dogodnie oznacza, że ​​posortuje liczby naturalne według wartości liczbowej. Możemy więc po prostu rekurencyjnie sortować wszystkie nasze liczby, aby uzyskać spójną kolejność. W rzeczywistości za pomocą funkcji, którą definiujemy rekurencyjnie, możemy osiągnąć oba wyniki jednocześnie: rekurencyjne sortowanie elementów liczby i sprawdzanie, czy jest to liczba naturalna.

Funkcja składa się zatem z czterech głównych części. ↰ᵐto wywołanie rekurencyjne, zapewniające, że każdy element jest liczbą naturalną, i przekształcające go w każdy znormalizowany formularz. onormalizuje samą liczbę (jej elementy są już znormalizowane, więc wszystko, co musimy zrobić, to ją posortować). Następnie .t~k|upewnia się, że mamy pożądaną strukturę, sprawdzając, czy największy element i inne elementy są takie same. Pusta lista (tj. 0) nie ma ostatniego elementu, więc wystąpi błąd asercji za pomocą t; |Ėobsługuje ten przypadek, poprzez dając wyraźny krok wstecz w przypadku, gdy lista wejściowy jest pusty.

K (ngn / k) , 26 24 27 bajtów

~^{$[#(!#x)^o'x;0N;#x]}@`j@

Wypróbuj online!

input to parsowany ciąg json `j@(składnia specyficzna dla ngn / k)

{ }jest funkcją rekurencyjną z argumentem x. zwraca liczbę naturalną reprezentowaną przez zestaw xlub null ( 0N), jeśli nie reprezentuje żadnej.

$[ ; ; ]jest jeśli-to-jeszcze. 0 oznacza falsey, inne liczby całkowite są zgodne z prawdą

!#xliczby całkowite od 0 (włącznie) do długości x(wyłączne)

^ bez

o'xrecursion ( o) na każdym ( ') elemenciex

# długość

^ jest zerowy?

~ nie

@działa jako manekina ostatniej czasownika, tak że ~i ^się składa ze { }zamiast do niego stosować

Galareta , 10 bajtów

ẈṢ‘⁼Jȧ@ßƇƑ

Wypróbuj online!

Japt , 9 bajtów

Rozwiązanie JS Port of Neil . Głosuj za tym, jeśli to głosujesz.

e@Ê>XÊ©ßX

Wypróbuj lub uruchom wszystkie przypadki testowe

              :Implicit input of array U
e             :Does every element in U return true
 @            :When passed through the following function as X
  Ê           :Length of U
   >          :Greater than
    XÊ        :Length of X
      ©       :Logical AND with
       ßX     :A recursive call of the programme with X passed as the new value of U

Czerwony , 81 bajtów

func[a][p: 1 foreach e to-block a[p: p *(pick[1 0](length? e)< length? a)* f e]p]

Wypróbuj online!

Podobne do odpowiedzi Python 3 Leaky Nun

Galaretka , 8 bajtów

߀Ṣ
ÇṖƤƑ

Ponieważ dane wejściowe muszą być ciągiem, przesyłanie jest ważne tylko jako pełny program.

Wypróbuj online! lubzweryfikuj wszystkie przypadki testowe

Jak to działa

߀Ṣ   Helper link. Argument: A (array)

߀    Recursively map the helper link over A.
  Ṣ   Sort the result.

Daje to kanoniczną reprezentację danych wejściowych, składającą się wyłącznie z posortowanych tablic.

ÇṖƤƑ  Main link. Argument: A (array)

Ç     Call the helper link to canonicalize the array.
   Ƒ  Fixed; call the link to the left and test if it returns its argument unchanged.
 ṖƤ       Pop prefix; for each non-empty prefix of the result, remove its last element.

Galaretka , 7 bajtów

Ẉ<La߀Ạ

To jest port odpowiedzi Pythona Dziurawej Zakonnicy .

Ponieważ dane wejściowe muszą być ciągiem, przesyłanie jest ważne tylko jako pełny program.

Wypróbuj online! lub zweryfikuj wszystkie przypadki testowe

Jak to działa

Ẉ<La߀Ạ  Main link. Argument: A (array)

Ẉ        Width; compute the length of A's elements.
  L      Yield the length of A.
 <       Compare them, yielding an array of Booleans.
    ߀   Recursively map the main link over A.
   a     Take the logical AND of the Booleans and the results of the map.
      Ạ  All; yield 1 if and only if all ANDs yielded 1.

Wolfram Language (Mathematica) , 52 bajty

If[Max[#0/@#]<(l=2Length@#),l]&@*ToExpression/*EvenQ

Wypróbuj online!