Em teoria dos conjuntos, os números naturais $\mathbb{N} = \{0, 1, 2, 3, ...\}$ geralmente são codificados como conjuntos puros , ou seja, conjuntos que contêm apenas o conjunto vazio ou outros conjuntos que são puros. No entanto, nem todos os conjuntos puros representam números naturais. Esse desafio é decidir se um determinado conjunto puro representa uma codificação do número natural ou não.

A codificação de números naturais funciona da seguinte maneira ¹ :

• Zero é o conjunto vazio: $Set(0) = \{\}$
• Para um número $n > 0$ : $Set(n) = Set(n-1) \cup \{Set(n-1)\}$

Assim, as codificações dos primeiros números naturais são

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

A tarefa

• Dada uma sequência que representa um conjunto puro, determine se esse conjunto codifica um número natural de acordo com a construção acima.
• Observe, no entanto, que os elementos de um conjunto não são ordenados; portanto, $\{\{\},\{\{\}\},\{\{\},\{\{\}\}\}\}$ não é a única representação válida de $3$ como, por exemplo, $\{\{\{\}\},\{\},\{\{\{\}\},\{\}\}\}$ representa o mesmo conjunto.
• Você pode usar [], ()ou em <>vez de {}.
• Você pode assumir que os conjuntos são fornecidos sem o ,separador as.
• Você pode assumir que não haverá elementos duplicados na entrada, por exemplo, {{},{}}não é uma entrada válida e que a entrada está bem formada, por exemplo {{},, não {,{}}ou similar.

Casos de teste

Verdade:

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

Falso:

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

^{Relacionado: Construção natural (gera a codificação definida de um determinado número natural.)
1 Consulte https://en.wikipedia.org/wiki/Set-theoretic_definition_of_natural_numbers}

JavaScript (Node.js) , 53 48 44 bytes

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

Experimente online! Casos de teste roubados descaradamente da resposta de @ Arnauld. Explicação: Se um conjunto representa um número natural, então o número natural que representa deve ser igual ao tamanho do conjunto e (considerando que os elementos são garantidos distintos), os elementos devem ser as representações dos números naturais menores que ele, e estes devem, portanto, ter comprimentos mais curtos. Isso é trivialmente verdadeiro para o conjunto vazio, é claro. Editar: salvou 5 bytes graças a @Arnauld. Economizou 4 bytes graças a @Cowsquack.

Python 3 , 69 58 44 bytes

11 bytes graças a Erik, o Outgolfer.

14 bytes graças ao Sr. Xcoder.

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

Experimente online!

Wolfram Language (Mathematica) , 60 59 bytes

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

Experimente online!

O núcleo desta solução é a função

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

que converte uma lista do formulário {0,1,2,...,n-1}em qualquer ordem na saída n(em particular, converte {}em 0) e converte qualquer outra coisa no número real E.

Chame esta função f. Dada uma entrada como "{{{}},{}}", fazemos o seguinte:

1. Converta a string em uma expressão do Mathematica.
2. Aplique fem todos os níveis, obtendo f[{f[{f[{}]}], f[{}]}].
3. A avaliação de todos os fitens produzirá um número natural para uma entrada que o representa. Por exemplo, f[{f[{f[{}]}], f[{}]}]= f[{f[{0}], 0}]= f[{1, 0}]= 2. Qualquer outra coisa irá produzir E.
4. Testamos se o resultado é um número natural, verificando se não é E.

Brachylog (v2), 9 bytes

↰ᵐo.t~k|Ė

Experimente online!

Como sempre, para um problema de decisão , este é um programa completo. Entrada da entrada padrão, usando colchetes. Saída para saída padrão como true.versus false..

Explicação

Embora eu tenha dito acima que este é um programa completo, é realmente mais interessante que isso; é tanto um programa completo e uma função. Quando usado como um programa completo, ele imprimetrue. se o conjunto é um número natural ou false.se não é. Quando usado como uma função, "normaliza" um número natural (ou seja, normaliza todos os seus elementos e os classifica em ordem por valor; este programa usa listas internamente, não conjuntos), ou "gera uma exceção" (na verdade uma falha, pois é Prolog) se a entrada não for um número natural.

O comportamento completo do programa é fácil de explicar: é puramente implícito no tratamento do Brachylog de programas completos que não contêm instruções de E / S. O comportamento em questão é "execute a função, obtendo sua entrada da entrada padrão e afirmando que sua saída corresponde à descrição fornecida pelo primeiro argumento da linha de comando; se a asserção falhar ou o programa lançar uma exceção, imprima false., imprima true." . Nesse caso, o argumento da linha de comando está ausente (ou seja, "vale tudo"), portanto, o comportamento de exceção / não exceção da função fornece a saída.

Quanto ao comportamento da função:

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

Um número natural é definido como contendo duas partes: os elementos do número natural abaixo, unidos ao próprio número. Assim, todos os seus elementos também são números naturais. Podemos reconhecer um número natural: a) verificando se todos os seus elementos são números naturais; b) verificando se o maior elemento do conjunto é idêntico ao conjunto sem seu maior elemento.

Quando estamos usando listas em vez de conjuntos (portanto, colchetes), precisamos colocá-los em uma ordem consistente para que as comparações de igualdade funcionem (nesse caso, classificadas por "valor"). A ordem de classificação padrão de Brachylog classificará um prefixo de uma lista antes da própria lista, o que significa convenientemente que classificará números naturais por valor numérico. Assim, podemos classificar recursivamente todos os nossos números para colocá-los em uma ordem consistente. De fato, através da função que definimos recursivamente, podemos alcançar os dois resultados ao mesmo tempo: classificando recursivamente os elementos do número e verificando se é um número natural.

A função tem assim quatro partes principais. ↰ᵐé a chamada recursiva, garantindo que cada elemento seja um número natural e convertendo cada elemento em um formato normalizado. oo normaliza o número em si (seus elementos já estão normalizados, então tudo o que precisamos fazer é classificá-lo). Depois, .t~k|garante que temos a estrutura que queremos, verificando se o maior elemento e outros elementos são os mesmos. Uma lista vazia (ou seja, 0) não possui um último elemento; portanto, ocorrerá uma falha de asserção t; o |Ėmanipula esse caso, fornecendo um fallback explícito no caso em que a lista de entrada está vazia.

K (ngn / k) , 26 24 27 bytes

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

Experimente online!

input é uma string json analisada por `j@(sintaxe específica para ngn / k)

{ }é uma função recursiva com argumento x. retorna o número natural representado pelo conjunto xou null ( 0N) se não representar um.

$[ ; ; ]é if-then-else. 0 é falsey, outros números inteiros são verdadeiros

!#xos números inteiros de 0 (inclusive) até o comprimento de x(exclusivo)

^ sem

o'xrecursion ( o) em cada ( ') elemento dex

# comprimento

^ é nulo?

~ não

@age como um último verbo fictício, de modo que, ~e ^seja composto com, em { }vez de ser aplicado a ele

Gelatina , 10 bytes

ẈṢ‘⁼Jȧ@ßƇƑ

Experimente online!

Japonês , 9 bytes

Solução JS do Port of Neil . Por favor, vote se você está votando isso.

e@Ê>XÊ©ßX

Experimente ou execute todos os casos de teste

              :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

Vermelho , 81 bytes

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

Experimente online!

Semelhante à resposta Python 3 de Leaky Nun

Geléia , 8 bytes

߀Ṣ
ÇṖƤƑ

Como a entrada deve ser uma sequência, esse envio é válido apenas como um programa completo.

Experimente online! ou verifique todos os casos de teste

Como funciona

߀Ṣ   Helper link. Argument: A (array)

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

Isso produz uma representação canônica da entrada, consistindo apenas em matrizes classificadas.

ÇṖƤƑ  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.

Geléia , 7 bytes

Ẉ<La߀Ạ

Esta é uma porta da resposta Python de Leaky Nun .

Como a entrada deve ser uma sequência, esse envio é válido apenas como um programa completo.

Experimente online! ou verifique todos os casos de teste

Como funciona

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

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

Experimente online!