Construire les nombres naturels avec des ensembles

17

Cette construction est une façon de représenter les nombres naturels.

Dans cette représentation, 0 est défini comme l'ensemble vide et pour tous les autres nombres, n est l'union de {0} et {n-1}.

Par exemple, pour construire 3, nous pouvons suivre l'algorithme:

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

Tâche

Comme vous l'avez peut-être deviné, votre tâche consiste à saisir un nombre naturel (y compris zéro) et à générer sa construction.

Vous pouvez sortir sous forme de chaîne ou d'objet set si la langue de votre choix prend en charge ces objets.

Si vous choisissez de sortir sous forme de chaîne, vous devez représenter un ensemble avec des accolades ( {}). Vous pouvez éventuellement représenter l'ensemble vide comme ø(sinon il doit s'agir d'un ensemble sans entrées {}). Vous pouvez également choisir d'ajouter des virgules et des espaces entre et après les entrées dans l'ensemble.

L'ordre n'est pas important, mais vous ne pouvez pas avoir d'éléments répétés dans les ensembles que vous produisez (par exemple {ø,ø})

C'est du donc le but est d'avoir le moins d'octets

Cas de test

Voici quelques cas de test avec quelques exemples de sorties.

0 -> {}
1 -> {{}}
2 -> {{}{{}}}
3 -> {{}{{}{{}}}}
4 -> {{}{{}{{}{{}}}}}
Post Rock Garf Hunter
la source
4
@ mbomb007 Peu importe que la définition soit "fausse" ou non. C'est toujours un beau défi (et différent).
Martin Ender
Étroitement liés.
Martin Ender
4
@ mbomb007 Les cas de test et la définition donnée dans ce défi correspondent et sont différents de l'autre défi. Si quoi que ce soit, le lien pourrait être amélioré, mais je ne pense pas que le lien soit pertinent pour le défi lui-même.
Martin Ender
Il l'a appelé la construction de Von Neumann, cependant, et ce n'est pas ce que ce défi est. C'est ça le dup. Il s'ensuit que chaque nombre naturel est égal à l'ensemble de tous les nombres naturels inférieur à lui
mbomb007
1
Pouvons-nous renvoyer un objet de type ensemble tel qu'une liste de listes à partir d'une fonction ou imprimer la représentation de notre langage sur STDOUT?
Dennis

Réponses:

12

Python , 28 octets

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

Essayez-le en ligne!

C'est une solution assez fade au problème. Pour les nombres supérieurs à zéro, vous pouvez obtenir la représentation avec la formule de chaîne "{{}"*x+"}"*x. Cependant, cela ne fonctionne pas pour zéro où il s'agit de la chaîne vide. Nous pouvons utiliser ce fait pour court-circuiter oret retourner l'ensemble vide.

Je voulais utiliser les objets set intégrés de python pour résoudre ce problème mais malheureusement:

TypeError: unhashable type: 'set'

Vous ne pouvez pas mettre d'ensembles à l'intérieur d'ensembles en python.

Post Rock Garf Hunter
la source
2
Vous pouvez déplacer le xà "{{}"*x+x*"}"orsauver un octet
Rod
1
f=pourrait être supprimé.
Yytsi
Il n'y a frozensetque personne pour ça ...
Esolanging Fruit
9

Haskell , 37 octets

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

Essayez-le en ligne!

Jusqu'à il y a 10 minutes, une réponse comme celle-ci n'aurait pas eu de sens pour moi. Tous les crédits vont à cette réponse de conseils .

Fondamentalement, nous utilisons >>as concat $ replicate(mais en lui passant une liste de n éléments au lieu de simplement n), et =<<as concatMap, répliquant ensuite n fois chacune des chaînes de la liste et concaténant le résultat en une seule chaîne.

Le 0cas est traité séparément car il retournerait une chaîne vide.

Leo
la source
@Laikoni J'ai aussi essayé quelque chose comme ça, mais il faudrait aussi un cas spécial f 1pour le faire fonctionner correctement
Leo
En effet. Ensuite, j'aime encore plus votre version.
Laikoni
6

JavaScript, 28 octets

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

Représente les ensembles à l'aide de tableaux. Solution non récursive de 38 octets:

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

Renvoie les exemples de chaînes de sortie.

Neil
la source
6

Mathematica, 27 octets

J'ai deux solutions à ce nombre d'octets:

Nest[{{}}~Union~{#}&,{},#]&
Union//@Nest[{{},#}&,{},#]&
Martin Ender
la source
1
Quasi - octets à 32: #//.{1->{{}},x_/;x>1->{{},x-1}}&. Bien que je suppose que cela gâche l'entrée 0
Greg Martin
5

Perl 6 , 37 octets

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

Essayez-le

Étendu:

{   # 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
}
Brad Gilbert b2gills
la source
Vous manquez un terminateur de devis :ou est-ce quelque chose de nouveau pour Perl 6?
CraigR8806
@ CraigR8806 Vous ne pouvez pas utiliser de deux-points pour délimiter les constructions entre guillemets en Perl 6 car elles sont utilisées pour les adverbes. (regardez la version étendue)
Brad Gilbert b2gills
5

05AB1E , 6 5 octets

Code

ƒ)¯sÙ

Utilise l' encodage CP-1252 . Essayez-le en ligne!ou Vérifiez tous les cas de test! .

Explication

ƒ       # For N in range(0, input + 1)..
 )      #   Wrap the entire stack into an array
  ¯     #   Push []
   s    #   Swap the two top elements
    Ù   #   Uniquify the array
Adnan
la source
F¯), ça ne marche pas?
Urne Magic Octopus
@carusocomputing Je ne pense pas que cela fonctionne n=0, car la sortie est vide (pas un ensemble vide).
Adnan
4

Rétine , 22 octets

.+
$*
\`.
{{}
{

^$
{}

Essayez-le en ligne!

Explication

.+
$*

Convertissez l'entrée en unaire.

\`.
{{}

Remplacez chaque chiffre unaire par {{}et imprimez le résultat sans retour à la ligne ( \).

{

Retirez les ouvertures {, afin que les autres }soient exactement ceux que nous devons encore imprimer pour fermer tous les ensembles. Cependant, la procédure ci-dessus échoue pour la saisie 0, où nous n'imprimerions rien. Donc...

^$
{}

Si la chaîne est vide, remplacez-la par l'ensemble vide.

Martin Ender
la source
Je me demandais comment répéter une chaîne de ntemps dans la rétine ...
Neil
4

Brain-Flak , 135 octets

Comprend +1 pour -A

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

Essayez-le en ligne!

(({}())<                 # 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
Riley
la source
4

Röda , 37 octets

f n{[[[],f(n-1)]]if[n>1]else[[[]]*n]}
fergusq
la source
4

CJam , 11 octets

Lri{]La|}*p

Imprime un objet de type ensemble composé de listes de listes. CJam imprime des listes vides sous forme de chaînes vides, car les listes et les chaînes sont presque interchangeables.

Essayez-le en ligne!

Explication

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

Ancienne réponse, 21 18 octets

C'était avant qu'il ne soit confirmé qu'il était correct d'imprimer une structure de liste imbriquée. Utilise l'algorithme de répétition de chaînes.

Sauvegardé 3 octets grâce à Martin Ender!

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

Explication

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.
Chat d'affaires
la source
4

Gelée , 6 octets

⁸,⁸Q$¡

Il s'agit d'un lien niladique qui lit un entier depuis STDIN et renvoie un tableau irrégulier.

Essayez-le en ligne!

Comment ça fonctionne

⁸,⁸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.
Dennis
la source
3

Python 3 , 32 octets

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

Pas le plus court chemin, mais je devais le faire avec récursivité.

Essayez-le en ligne!

Dennis
la source
3

Cardinal , 51 50 octets

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

Essayez-le en ligne!

Explication

%:#
x

Recevez l'entrée et envoyez vers le bas et à gauche du #

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

Imprimer "{" une fois puis imprimer "{} {" n-1 fois si n> 1 puis imprimer "{}" si n> 0

       #

v <8/ ?<
>  8\

Maintenez la valeur d'entrée jusqu'à la fin de la première boucle

v"}"<
>?-?^

Imprimer "}" une fois puis répéter n-1 fois si n> 1

fəˈnɛtɪk
la source
2

AHK, 55 octets

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

Ce n'est pas la réponse la plus courte, mais j'ai apprécié cela parce que les particularités d'AutoHotkey font que cette méthode de récursion a l'air super fausse. Ifet les Loopinstructions supposent que la ligne suivante est la seule chose incluse si les crochets ne sont pas utilisés. Les accolades sont des caractères d'échappement, vous devez donc les échapper avec d'autres accolades pour les utiliser comme texte. De plus, la variable 1est le premier argument passé. Quand je lis le code sans connaître ces petits morceaux, la logique ressemble à ceci:

  • Si 1 = 0, alors définissez ségal à la mauvaise réponse
  • Boucle et ajoute un tas de crochets au début et quelques-uns à la fin à chaque fois
  • Retournez en envoyant la chaîne résultante à la fenêtre courante

Sans tous les caractères d'échappement des crochets, cela ressemblerait à ceci:

IfEqual,1,0
   s={}
Loop,%1%
   s={{}%s%}
Send,%s%
Ingénieur Toast
la source
1

JavaScript 50 octets

g=n=>n==0?"":"{{}"+g(n-1)+"}"
z=m=>m==0?"{}":g(m)
Kemsdale Nickle
la source
quand un nombre est égal à 0, c'est une valeur fausse pour JavaScript. Vous pouvez donc supprimer le == 0 si vous inversez vos expressions ternaires
fəˈnɛtɪk
1

tinylisp , 52 octets

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

Essayez-le en ligne! (test harnais).

Explication

Notez que (cons x (cons y nil))c'est ainsi que vous créez une liste contenant xet yen 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
DLosc
la source
1

Pure Bash , 49 48 41 octets

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

Essayez-le en ligne!

Mitchell Spector
la source
1

dc , 46 octets

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

Essayez-le en ligne!

Entrée sur stdin, sortie sur stdout.

Cela fonctionne en calculant une formule pour la sortie souhaitée sous la forme d'un nombre de base 256. La commande P dans dc est ensuite utilisée pour imprimer le nombre base-256 sous forme de chaîne.


Plus d'explications:

Soit n l'entrée n. Le programme DC calcule la somme de

A = étage (256 ^ n / 255) * 125 (BF est interprété par dc comme 11 * 10 + 15 = 125)

et

B = étage ((256 ^ n) ^ 3 / (8 ^ 8-1)) * 8092541 * (256 ^ n).

 

Pour un:

Observez que 1 + 256 + 256 ^ 2 + ... + 256 ^ (n-1) est égal à (256 ^ n-1) / 255, par la formule d'une progression géométrique, et cela est égal au sol (256 ^ n / 255 ). C'est donc le nombre composé de n 1 en base 256.

Lorsque vous le multipliez par 125 pour obtenir A, le résultat est le nombre composé de n 125 en base 256 (125 est un chiffre unique en base 256, bien sûr). Il est probablement préférable d'écrire les chiffres de la base 256 sous forme de nombres hexadécimaux; 125 est hexadécimal 7D, donc A est le nombre de base 256 composé de n 7D dans une rangée.

 

B est similaire:

Cette fois, observez que 1 + 16777216 + 16777216 ^ 2 + ... + 16777216 ^ (n-1) est égal à (16777216 ^ n - 1) / 16777215, et cela est égal au plancher (16777216 ^ n / 16777215).

Maintenant, 256 ^ 3 = 16777216 et 8 ^ 8-1 = 16777215, c'est donc ce que nous calculons comme étage ((256 ^ n) ^ 3 / (8 ^ 8-1)).

D'après la représentation des séries géométriques, ce nombre dans la base 256 est 100100100 ... 1001 avec n des chiffres étant 1 et le reste des chiffres étant 0.

Ceci est multiplié par 8092541, qui est 7B7B7D en hexadécimal. Dans la base 256, il s'agit d'un nombre à trois chiffres composé des chiffres 7B, 7B et 7D (en écrivant ces chiffres en hexadécimal pour plus de commodité).

Il s'ensuit que le produit écrit en base 256 est un nombre à 3n chiffres composé des 3 chiffres 7B 7B 7D répétés n fois.

Celui-ci est multiplié par 256 ^ n, ce qui donne un nombre de base 256 à 4n chiffres, composé des 3 chiffres 7B 7B 7D répétés n fois, suivis de n 0. C'est B.

 

L'ajout de A + B donne maintenant le nombre de base 256 à 4 chiffres composé des 3 chiffres 7B 7B 7D répétés n fois, suivis de n 7D. Puisque 7B et 7D sont les codes ASCII pour {et }, respectivement, il s'agit de la chaîne composée de n copies de {{}suivi de n copies de} , ce qui est exactement ce que nous voulons pour n> 0. La commande P en dc imprime un nombre en base 256 comme une chaîne, comme nous en avons besoin.

Malheureusement, n = 0 doit être traité comme un cas spécial. Le calcul ci-dessus donne un résultat de 0 pour n = 0; dans ce cas, je viens de coder en dur l'impression de la chaîne {}.

Mitchell Spector
la source
C'est une approche très intéressante utilisant le comportement moins connu de cette commande d'impression. Bien fait! Une explication de la façon dont cela fonctionne améliorerait la réponse.
seshoumara
@seshoumara Merci - J'ai ajouté une explication détaillée.
Mitchell Spector
0

Java 7, 61 octets

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

Essayez-le en ligne!

Poussée
la source
0

Lot, 88 octets

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

Brainf *** , 99 octets

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

(nouvelle ligne pour l'esthétique) Puisque c'est brainf ***, il prend l'entrée en tant que codes de caractères ascii (l'entrée "a" correspond à 96)

Braineasy, 60 octets

Aussi, dans ma langue personnalisée (basée sur brainf **, interprète ici ):

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

Vous devez coder en dur l'entrée du programme dans l'interpréteur parce que je suis paresseux.

internet_user
la source
Bienvenue sur le site! Pourquoi y en a-t-il []? Il semble qu'il pourrait être supprimé
Post Rock Garf Hunter
Si vous ne l'avez pas, il affichera un {} supplémentaire à la fin (il boucle indéfiniment).
internet_user
0

05AB1E , 5 3 octets

F¯)

Essayez-le en ligne!

Cette version est après avoir précisé que les ensembles sont corrects.

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

Ancienne version (qui utilise le ø):

05AB1E , 5 4 octets

FX¸)

Essayez-le en ligne!

1est équivalent à ø.

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.
Urne de poulpe magique
la source