Cet ensemble représente-t-il un nombre naturel?

26

Dans la théorie des ensembles, les nombres naturels N={0,1,2,3,...} sont généralement codés comme des ensembles purs , c'est-à-dire des ensembles qui ne contiennent que l'ensemble vide ou d'autres ensembles purs. Cependant, tous les ensembles purs ne représentent pas des nombres naturels. Ce défi consiste à décider si un ensemble pur donné représente un codage de nombre naturel ou non.

L'encodage des nombres naturels fonctionne de la manière suivante 1 :

  • Zéro est l'ensemble vide: Set(0)={}
  • Pour un nombre n>0 : Set(n)=Set(n1){Set(n1)}

Ainsi, les encodages des premiers nombres naturels sont

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

La tâche

  • Étant donné une chaîne représentant un ensemble pur, déterminez si cet ensemble code pour un nombre naturel selon la construction ci-dessus.
  • Notez cependant que les éléments d'un ensemble ne sont pas ordonnés, donc {{},{{}},{{},{{}}}} n'est pas la seule représentation valide de 3 car par exemple {{{}},{},{{{}},{}}} représente le même ensemble.
  • Vous pouvez utiliser [], ()ou <>au lieu de {}.
  • Vous pouvez supposer que les ensembles sont donnés sans le ,séparateur as.
  • Vous pouvez supposer qu'il n'y aura pas d'éléments en double dans l'entrée, par exemple {{},{}}n'est pas une entrée valide, et que l'entrée est bien formée, par exemple non {{},, {,{}}ou similaire.

Cas de test

Vrai:

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

Faux:

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

Connexes: construction naturelle (sortie de l'encodage d'ensemble d'un nombre naturel donné.)
1 Voir https://en.wikipedia.org/wiki/Set-theoretic_definition_of_natural_numbers

Laikoni
la source
13
Les cas de test ressemblent à un programme dans un esolang (encore) non implémenté :)
Galen Ivanov
2
l'entrée peut-elle être une structure de données (listes imbriquées) au lieu d'une chaîne?
ngn
3
Je pensais que c'était Brain-flak pendant un moment.
Belhenix
5
@ngn Non, l'entrée doit être une chaîne.
Laikoni
4
@KirillL. Techniquement, ces réponses n'étaient pas valables au départ, car le défi indiquait toujours "Étant donné une chaîne représentant un ensemble pur", même si je vois bien que permettre des structures de données imbriquées offre des opportunités de golf intéressantes. Cependant, je trouve difficile de décider où tracer la ligne sur ce qui est une structure de données autorisée et ce qui ne doit pas éviter l'abus d'un format d'entrée trop clément, j'ai donc décidé de restreindre les entrées aux chaînes pour des raisons de simplicité et d'ambiguïté. .
Laikoni

Réponses:

11

JavaScript (Node.js) , 53 48 44 octets

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

Essayez-le en ligne! Des cas de test volés pour la plupart sans vergogne à la réponse de @ Arnauld. Explication: Si un ensemble représente un nombre naturel, le nombre naturel qu'il représente doit être égal à la taille de l'ensemble et (étant donné que les éléments sont garantis distincts), les éléments doivent être les représentations des nombres naturels inférieurs à lui, et ceux-ci doivent donc avoir des longueurs plus courtes. C'est évidemment vrai pour l'ensemble vide bien sûr. Edit: 5 octets enregistrés grâce à @Arnauld. 4 octets enregistrés grâce à @Cowsquack.

Neil
la source
!e[a.length-1]devrait économiser 3 octets
Arnauld
1
@Arnauld Ou mieux encore, a[e.length]&&pour 5 octets!
Neil
@JoKing Ugh, je viens de copier Arnauld ... l'entrée de chaîne coûte 14 octets :-(
Neil
Sûrement, ça g=(A,a=eval(A))=>a.every(e=>a[e.length]&&g(e))marcherait?
Kritixi Lithos
@Cowsquack Ah, sympa, cela économise en fait 4 octets, merci!
Neil
6

Python 3 , 69 58 44 octets

11 octets grâce à Erik l'Outgolfer.

14 octets grâce à M. Xcoder.

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

Essayez-le en ligne!

Leaky Nun
la source
@ Mr.Xcoder fait
Leaky Nun
Oh wow, belle amélioration!
M. Xcoder
@ Mr.Xcoder et maintenant je me rends compte que c'est la même chose que la réponse de Neil ... donc techniquement Neil m'a battu
Leaky Nun
5

Langue Wolfram (Mathematica) , 60 59 octets

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

Essayez-le en ligne!

Le cœur de cette solution est la fonction

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

qui convertit une liste du formulaire {0,1,2,...,n-1}dans n'importe quel ordre en sortie n(en particulier, il convertit {}en 0), et convertit tout le reste en nombre réel E.

Appelez cette fonction f. Étant donné une entrée telle que "{{{}},{}}", nous faisons ce qui suit:

  1. Convertissez la chaîne en une expression Mathematica.
  2. Appliquer fà tous les niveaux, obtenir f[{f[{f[{}]}], f[{}]}].
  3. L'évaluation de tous fproduira un nombre naturel pour une entrée le représentant. Par exemple, f[{f[{f[{}]}], f[{}]}]= f[{f[{0}], 0}]= f[{1, 0}]= 2. Tout le reste produira E.
  4. Nous testons si le résultat est un nombre naturel en vérifiant s'il ne l'est pas E.
Misha Lavrov
la source
3

Brachylog (v2), 9 octets

↰ᵐo.t~k|Ė

Essayez-le en ligne!

Comme d'habitude pour un , il s'agit d'un programme complet. Entrée à partir de l'entrée standard, à l'aide de crochets. Sortie vers sortie standard par true.rapport à false..

Explication

Bien que j'aie dit plus haut qu'il s'agit d'un programme complet, il est en fait plus intéressant que cela; c'est à la fois un programme complet et une fonction. Lorsqu'il est utilisé comme programme complet, il s'imprime true.si l'ensemble est un nombre naturel, ou false.s'il ne l'est pas. Lorsqu'il est utilisé en tant que fonction, il "normalise" un nombre naturel (c'est-à-dire normalise tous ses éléments et les trie par ordre de valeur; ce programme utilise des listes en interne, pas des ensembles), ou "lève une exception" (en fait un échec, car cela est Prolog) si l'entrée n'est pas un nombre naturel.

Le comportement du programme complet est assez facile à expliquer: il est purement implicite dans le traitement par Brachylog des programmes complets qui ne contiennent pas d'instructions d'E / S. Le comportement en question est «exécuter la fonction, en prenant son entrée à partir de l'entrée standard et en affirmant que sa sortie correspond à la description donnée par le premier argument de ligne de commande; si l'assertion échoue ou que le programme lève une exception, print false., sinon print true.» . Dans ce cas, l'argument de la ligne de commande est manquant (c'est-à-dire "n'importe quoi va"), donc le comportement d'exception / sans exception de la fonction donne la sortie.

Quant au comportement de la fonction:

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

Un nombre naturel est défini comme contenant deux parties: les éléments du nombre naturel ci-dessous, réunis avec le nombre lui-même. Ainsi, tous ses éléments sont également des nombres naturels. Nous pouvons reconnaître un nombre naturel en a) vérifiant que tous ses éléments sont des nombres naturels, b) vérifiant que le plus grand élément de l'ensemble est identique à l'ensemble sans son plus grand élément.

Lorsque nous utilisons des listes plutôt que des ensembles (donc les crochets), nous devons les mettre dans un ordre cohérent pour que les comparaisons d'égalité fonctionnent (dans ce cas, triées par "valeur"). L'ordre de tri par défaut de Brachylog triera le préfixe d'une liste avant la liste elle-même, ce qui signifie commodément qu'il triera les nombres naturels par valeur numérique. Nous pouvons donc trier récursivement tous nos numéros pour les mettre dans un ordre cohérent. En fait, via la fonction que nous définissons récursivement, nous pouvons obtenir les deux résultats en même temps: trier récursivement les éléments du nombre et vérifier qu'il s'agit d'un nombre naturel.

La fonction comprend donc quatre parties principales. ↰ᵐest l'appel récursif, garantissant que chaque élément est un nombre naturel et le convertissant chaque élément en une forme normalisée. ole normalise le nombre lui-même (ses éléments sont déjà normalisés, donc tout ce que nous avons à faire est de le trier). .t~k|S'assure ensuite que nous avons la structure que nous voulons en vérifiant que le plus grand élément et les autres éléments sont identiques. Une liste vide (c.-à-d. 0) n'a pas de dernier élément, donc obtiendra un échec d'assertion avec t; le gère ce cas, en donnant un repli explicite dans le cas où la liste d'entrée est vide.

ais523
la source
2

K (ngn / k) , 26 24 27 octets

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

Essayez-le en ligne!

l'entrée est une chaîne json analysée par `j@(syntaxe spécifique à ngn / k)

{ }est une fonction récursive avec argument x. il renvoie le nombre naturel représenté par l'ensemble x, ou null ( 0N) s'il n'en représente pas un.

$[ ; ; ]est if-then-else. 0 est falsey, les autres entiers sont véridiques

!#xles entiers de 0 (inclus) à la longueur de x(exclusif)

^ sans pour autant

o'xrecursion ( o) sur chaque 'élément ( ) dex

# longueur

^ est nul?

~ ne pas

@agit comme un dernier verbe factice de sorte que ~et ^se compose avec { }au lieu de lui être appliqué

ngn
la source
0

Japt , 9 octets

Port de la solution JS de Neil . Merci de noter que si vous votez pour cela.

e@Ê>XÊ©ßX

Essayez-le ou exécutez tous les cas de test

              :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
Hirsute
la source
0

Rouge , 81 octets

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

Essayez-le en ligne!

Similaire à la réponse de Leaky Nun's Python 3

Galen Ivanov
la source
0

Gelée , 8 octets

߀Ṣ
ÇṖƤƑ

Étant donné que l'entrée doit être une chaîne, cette soumission n'est valide qu'en tant que programme complet.

Essayez-le en ligne! ou vérifier tous les cas de test

Comment ça marche

߀Ṣ   Helper link. Argument: A (array)

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

Cela donne une représentation canonique de l'entrée, composée uniquement de tableaux triés.

ÇṖƤƑ  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
la source
0

Gelée , 7 octets

Ẉ<La߀Ạ

Ceci est un portage de la réponse Python de Leaky Nun .

Étant donné que l'entrée doit être une chaîne, cette soumission n'est valide qu'en tant que programme complet.

Essayez-le en ligne! ou vérifier tous les cas de test

Comment ça marche

Ẉ<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
la source