Construye los números naturales con conjuntos

17

Esta construcción es una forma de representar los números naturales.

En esta representación, 0 se define como el conjunto vacío y para todos los demás números, n es la unión de {0} y {n-1}.

Por ejemplo, para construir 3 podemos seguir el algoritmo:

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

Tarea

Como habrás adivinado, tu tarea es tomar un número natural (incluido cero) y generar su construcción.

Puede mostrar como una cadena o como un conjunto de objetos si su idioma de elección admite dichos objetos.

Si elige generar como una cadena, debe representar un conjunto con llaves ( {}). Opcionalmente, puede representar el conjunto vacío como ø(de lo contrario, debe ser un conjunto sin entradas {}). También puede optar por agregar comas y espacios en blanco entre y después de las entradas en el conjunto.

El orden no es importante, sin embargo, es posible que no tenga elementos repetidos en los conjuntos que genera (por ejemplo {ø,ø})

Este es el por lo que el objetivo es tener la menor cantidad de bytes

Casos de prueba

Aquí hay algunos casos de prueba con algunos resultados de ejemplo.

0 -> {}
1 -> {{}}
2 -> {{}{{}}}
3 -> {{}{{}{{}}}}
4 -> {{}{{}{{}{{}}}}}
Post Rock Garf Hunter
fuente
44
@ mbomb007 No importa si la definición es "incorrecta" o no. Sigue siendo un buen desafío (y uno diferente).
Martin Ender
44
@ mbomb007 Los casos de prueba y la definición dada en este desafío coinciden, y son diferentes del otro desafío. En todo caso, el enlace podría mejorarse, pero no creo que el enlace sea relevante para el desafío en sí.
Martin Ender
Sin embargo, lo llamó la construcción de Von Neumann, y ese no es el desafío. Eso es lo que es el dup. Se deduce que cada número natural es igual al conjunto de todos los números naturales menores que él
mbomb007
1
¿Podemos devolver un objeto similar a un conjunto, como una lista de listas de una función o imprimir la representación de nuestro lenguaje en STDOUT?
Dennis

Respuestas:

12

Python , 28 bytes

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

Pruébalo en línea!

Esta es una solución bastante suave para el problema. Para números mayores que cero, puede obtener la representación con la fórmula de cadena "{{}"*x+"}"*x. Sin embargo, esto no funciona para cero donde esta es la cadena vacía. Podemos usar este hecho para cortocircuitar ory devolver el conjunto vacío.

Quería usar los objetos integrados de Python para resolver este problema, pero desafortunadamente:

TypeError: unhashable type: 'set'

No puede poner conjuntos dentro de conjuntos en python.

Post Rock Garf Hunter
fuente
2
Puede mover el xpara "{{}"*x+x*"}"orguardar un byte
Rod
1
f=podría ser eliminado
Yytsi
Hay frozenset, pero no hay nadie tiene bytes por eso ...
Esolanging Fruit
9

Haskell , 37 bytes

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

Pruébalo en línea!

Hasta hace 10 minutos, una respuesta como esta no tendría sentido para mí. Todos los créditos van a esta respuesta de consejos .

Básicamente, usamos >>como concat $ replicate(pero pasándole una lista de n elementos en lugar de simplemente n), y =<<como concatMap, replicando entonces n veces cada una de las cadenas de la lista y concatenando el resultado en una sola cadena.

El 0caso se trata por separado, ya que devolvería una cadena vacía.

León
fuente
@Laikoni También probé algo así, pero también necesitarías un caso especial f 1para que funcione correctamente
Leo
En efecto. Entonces me gusta tu versión aún más.
Laikoni
6

JavaScript, 28 bytes

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

Representa conjuntos usando matrices. Solución no recursiva de 38 bytes:

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

Devuelve las cadenas de salida de ejemplo.

Neil
fuente
6

Mathematica, 27 bytes

Tengo dos soluciones en este recuento de bytes:

Nest[{{}}~Union~{#}&,{},#]&
Union//@Nest[{{},#}&,{},#]&
Martin Ender
fuente
1
Falta cercana a los 32 bytes de: #//.{1->{{}},x_/;x>1->{{},x-1}}&. Aunque supongo que arruina la entrada 0
Greg Martin
5

Perl 6 , 37 bytes

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

Intentalo

Expandido:

{   # 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
fuente
¿Te falta un terminador de cotizaciones :o es algo nuevo para Perl 6?
CraigR8806
@ CraigR8806 No puede usar dos puntos para delimitar construcciones de comillas en Perl 6 porque se usan para adverbios. (mira la versión ampliada)
Brad Gilbert b2gills
5

05AB1E , 6 5 bytes

Código

ƒ)¯sÙ

Utiliza la codificación CP-1252 . Pruébalo en línea! o Verifique todos los casos de prueba! .

Explicación

ƒ       # 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
fuente
F¯), eso no funciona?
Magic Octopus Urn
@carusocomputing No creo que funcione n=0, ya que la salida está vacía (no es un conjunto vacío).
Adnan
4

Retina , 22 bytes

.+
$*
\`.
{{}
{

^$
{}

Pruébalo en línea!

Explicación

.+
$*

Convierta la entrada a unario.

\`.
{{}

Reemplace cada dígito unario con {{}e imprima el resultado sin un salto de línea final ( \).

{

Elimine la apertura {s, de modo que el resto }sean exactamente los que aún necesitamos imprimir para cerrar todos los conjuntos. Sin embargo, el procedimiento anterior falla para la entrada 0, donde no imprimiríamos nada. Entonces...

^$
{}

Si la cadena está vacía, reemplácela con el conjunto vacío.

Martin Ender
fuente
Me preguntaba cómo repetir una cuerda nveces en Retina ...
Neil
4

Brain-Flak , 135 bytes

Incluye +1 para -A

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

Pruébalo en línea!

(({}())<                 # 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
fuente
4

Röda , 37 bytes

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

CJam , 11 bytes

Lri{]La|}*p

Imprime un objeto tipo conjunto que consta de listas de listas. CJam imprime listas vacías como cadenas vacías, ya que las listas y las cadenas son casi intercambiables.

Pruébalo en línea!

Explicación

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

Respuesta anterior, 21 18 bytes

Esto fue antes de que se confirmara que estaba bien imprimir una estructura de lista anidada. Utiliza el algoritmo de repetición de cadenas.

¡Guardado 3 bytes gracias a Martin Ender!

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

Explicación

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.
Gato de negocios
fuente
4

Jalea , 6 bytes

⁸,⁸Q$¡

Este es un enlace niládico que lee un número entero de STDIN y devuelve una matriz irregular.

Pruébalo en línea!

Cómo funciona

⁸,⁸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
fuente
3

Cardenal , 51 50 bytes

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

Pruébalo en línea!

Explicación

%:#
x

Recibir entrada y enviar hacia abajo y hacia la izquierda desde el #

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

Imprima "{" una vez y luego imprima "{} {" n-1 veces si n> 1, luego imprima "{}" si n> 0

       #

v <8/ ?<
>  8\

Mantenga el valor de entrada hasta que se complete el primer ciclo

v"}"<
>?-?^

Imprima "}" una vez y luego repita n-1 veces si n> 1

fəˈnɛtɪk
fuente
2

AHK, 55 bytes

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

No es la respuesta más corta, pero disfruté esto porque las idiosincrasias de AutoHotkey hacen que este método de recursión se vea súper mal. Ify las Loopdeclaraciones suponen que la siguiente línea es lo único que se incluye si no se utilizan corchetes. Los corchetes son caracteres de escape, por lo que debe escapar con otros corchetes para usarlos como texto. Además, la variable 1es el primer argumento pasado. Cuando leo el código sin conocer esos datos, la lógica se ve así:

  • Si 1 = 0, entonces establece sigual a la respuesta incorrecta
  • Haga un bucle y agregue un par de corchetes al principio y algunos al final cada vez
  • Regrese enviando la cadena resultante a la ventana actual

Sin todos los caracteres de escape entre paréntesis, se vería así:

IfEqual,1,0
   s={}
Loop,%1%
   s={{}%s%}
Send,%s%
Tostadas de ingeniero
fuente
1

JavaScript 50 bytes

g=n=>n==0?"":"{{}"+g(n-1)+"}"
z=m=>m==0?"{}":g(m)
Kemsdale Nickle
fuente
cuando un número es igual a 0, es un valor falso para JavaScript. Por lo tanto, puede eliminar el == 0 si invierte sus expresiones ternarias
fəˈnɛtɪk
1

tinylisp , 52 bytes

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

Pruébalo en línea!(Arnés de prueba).

Explicación

Tenga en cuenta que así (cons x (cons y nil))es como se crea una lista que contiene xy 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
fuente
1

cc , 46 bytes

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

Pruébalo en línea!

Entrada en stdin, salida en stdout.

Esto funciona calculando una fórmula para la salida deseada como un número base-256. El comando P en dc se usa para imprimir el número base-256 como una cadena.


Explicación adicional:

Sea n la entrada n. El programa de cc calcula la suma de

A = piso (256 ^ n / 255) * 125 (DC interpreta el BF como 11 * 10 + 15 = 125)

y

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

 

Para:

Observe que 1 + 256 + 256 ^ 2 + ... + 256 ^ (n-1) es igual a (256 ^ n-1) / 255, por la fórmula para una progresión geométrica, y esto es igual al piso (256 ^ n / 255 ) Entonces este es el número que consiste en n 1 en la base 256.

Cuando lo multiplica por 125 para obtener A, el resultado es el número que consiste en n 125 en la base 256 (125 es un solo dígito en la base 256, por supuesto). Probablemente sea mejor escribir los dígitos en la base 256 como números hexadecimales; 125 es hexadecimal 7D, por lo que A es el número base 256 que consiste en n 7D en una fila.

 

B es similar:

Esta vez observe que 1 + 16777216 + 16777216 ^ 2 + ... + 16777216 ^ (n-1) es igual a (16777216 ^ n - 1) / 16777215, y esto es igual al piso (16777216 ^ n / 16777215).

Ahora, 256 ^ 3 = 16777216 y 8 ^ 8-1 = 16777215, así que esto es lo que estamos calculando como floor ((256 ^ n) ^ 3 / (8 ^ 8-1)).

A partir de la representación en serie geométrica, este número en la base 256 es 100100100 ... 1001 con n de los dígitos siendo 1 y el resto de los dígitos siendo 0.

Esto se multiplica por 8092541, que es 7B7B7D en hexadecimal. En la base 256, este es un número de tres dígitos que consta de los dígitos 7B, 7B y 7D (escribir esos dígitos en hexadecimal por conveniencia).

Se deduce que el producto escrito en la base 256 es un número de 3 dígitos que consta de los 3 dígitos 7B 7B 7D repetidos n veces.

Esto se multiplica por 256 ^ n, lo que da como resultado un número base-256 de 4 dígitos, que consta de los 3 dígitos 7B 7B 7D repetidos n veces, seguidos de n 0. Eso es B.

 

Agregar A + B ahora produce el número de base 256 de 4 dígitos que consta de los 3 dígitos 7B 7B 7D repetidos n veces, seguidos de n 7D. Dado que 7B y 7D son los códigos ASCII para {y }, respectivamente, esta es la cadena que consta de n copias de {{}seguido de n copias de} , que es exactamente lo que queremos para n> 0. El comando P en dc imprime un número base-256 como una cuerda, tal como la necesitamos.

Desafortunadamente, n = 0 tiene que ser tratado como un caso especial. El cálculo anterior produce un resultado de 0 para n = 0; en ese caso, acabo de codificar la impresión de la cadena {}.

Mitchell Spector
fuente
Ese es un enfoque muy interesante utilizando el comportamiento menos conocido de ese comando de impresión. ¡Bien hecho! Una explicación de cómo funciona esto mejoraría la respuesta.
seshoumara
@seshoumara Gracias, he agregado una explicación detallada.
Mitchell Spector
0

Lote, 88 bytes

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

Brainf *** , 99 bytes

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

(nueva línea para la estética) Dado que es brainf ***, toma la entrada como códigos ascii char (la entrada "a" corresponde a 96)

Braineasy, 60 bytes

Also, in my custom language (brainf** based, interpreter here):

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

You have to hardcode the program input into the interpreter because i'm lazy.

internet_user
fuente
Welcome to the site! Why is there a []? It seems like it could be removed
Post Rock Garf Hunter
Si no tiene eso, generará un {} extra al final (se repite infinitamente).
internet_user
0

05AB1E , 5 3 bytes

F¯)

Pruébalo en línea!

Esta versión es después de que aclaró que los conjuntos están bien.

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

Versión anterior (que hace uso de ø):

05AB1E , 5 4 bytes

FX¸)

Pruébalo en línea!

Donde 1es equivalente a ø.

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.
Urna de pulpo mágico
fuente