Este conjunto representa um número natural?

26

Em teoria dos conjuntos, os números naturais N={0 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 1 :

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

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

  • 0 0{}
  • 1{0 0}{{}}
  • 2{0 0,1}{{},{{}}}
  • 3{0 0,1,2}{{},{{}},{{},{{}}}}
  • 4{0 0,1,2,3}{{},{{}},{{},{{}}},{{},{{}},{{},{{}}}}}

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

Laikoni
fonte
13
Os casos de teste parecido com um programa em um (ainda) esolang unimplemented :)
Galen Ivanov
2
a entrada pode ser uma estrutura de dados (listas aninhadas) em vez de uma sequência?
NGN
3
Eu pensei que era quebra-cabeças por um momento.
Belhenix
5
@ngn Não, a entrada precisa ser uma string.
Laikoni
4
@KirillL. Tecnicamente, essas respostas não eram válidas para começar, pois o desafio sempre dizia "Dada uma sequência que representa um conjunto puro", embora eu entenda que permitir estruturas de dados aninhadas permite oportunidades interessantes de golfe. No entanto, acho difícil decidir onde traçar a linha do que é uma estrutura de dados permitida e o que não é para evitar o abuso de um formato de entrada muito branda, por isso decidi restringir as entradas às seqüências de caracteres por uma questão de simplicidade e inequívoca .
Laikoni

Respostas:

11

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.

Neil
fonte
!e[a.length-1]deve salvar 3 bytes
Arnauld
1
@ Arnauld Ou melhor ainda, a[e.length]&&por 5 bytes!
Neil
@JoKing Ugh, eu apenas copiei Arnauld ... a entrada de string custa 14 bytes :-(
Neil
Certamente, g=(A,a=eval(A))=>a.every(e=>a[e.length]&&g(e))funcionaria?
Kritixi Lithos
@ Cowsquack Ah, bom, isso realmente salva 4 bytes, obrigado!
Neil
6

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!

Freira Furada
fonte
@ Mr.Xcoder done
Leaky Nun
Oh uau, boa melhoria!
Sr. Xcoder
@ Mr.Xcoder e, em seguida, agora eu percebo que é o mesmo que a resposta de Neil ... então techincally Neil derrotado me
Leaky Nun
5

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.
Misha Lavrov
fonte
3

Brachylog (v2), 9 bytes

↰ᵐo.t~k|Ė

Experimente online!

Como sempre, para um , 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.

ais523
fonte
2

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

ngn
fonte
0

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
Shaggy
fonte
0

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

Galen Ivanov
fonte
0

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.
Dennis
fonte
0

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.
Dennis
fonte