Partirme por la mitad

15

Se le dará un número x, donde 0 <= x <= 2^32 - 1.

Debería generar una lista de números en decimal, después de la división recursiva en formato binario.

Ejemplos:

Ejemplo 1:

255 -> 255 15 15 3 3 3 3 1 1 1 1 1 1 1 1

La lista actual es justa 255.

La representación binaria de 255es 1111 1111. Partiéndolo, obtenemos 1111y 1111, que en decimal son 15y 15.

Los agregamos a la lista, así que lo haremos 255 15 15.

Ahora los números 15y 15servirán como entradas y estos números deben dividirse.

Haciendo de nuevo, obtenemos ( 3 3de ambos 15s): 255 15 15 3 3 3 3.

Continuando con la lógica, la lista final será 255 15 15 3 3 3 3 1 1 1 1 1 1 1 1. Y como ya 1no se puede dividir, la salida se detiene.

Ejemplo 2

225 -> 225 14 1 3 2 1 1 1 0

La lista de inicio es 225.

La representación binaria de 225es 1110 0001. Partiéndolo, obtenemos 1110y 0001, que en decimal son 14y 1.

Al agregarlos a la lista, obtenemos 225 14 1.

Ahora los números 14y 1servirán como entradas y estos números deben dividirse.

Como 1no es divisible, la salida será 225 14 1 3 2.

Ejemplo 3

32 -> 32 4 0 1 0

Condiciones :

  1. Si el número de dígitos binarios es impar, el primer número tendrá un dígito binario menos que el siguiente. Ejemplo, 20 (10100)se dividirá como 10y 100, con salida decimal siendo 2y 4.
  2. Se aplican las normas de laguna legal.
  3. 0sys 1no se propagan más.
  4. El bloqueo de programa por intentar mostrar demasiados números es una condición de salida válida.
ctrl-shift-esc
fuente
Solo una sugerencia, pero ¿qué pasa con los dígitos binarios rellenados con 0s cuando la longitud es impar?
caird coinheringaahing
1
@ Satan'sSon Si tocas delante, eso es equivalente a la descripción.
isaacg
1
¿Se requiere el orden de salida especificado o solo los valores?
Jonathan Allan
@ Satan'sSon Sin relleno con 0s.
ctrl-shift-esc
1
@JonathanAllan Se requiere el orden de salida especificado.
ctrl-shift-esc

Respuestas:

13

Pyth, 18 bytes

u+QiR2smc2+0dt#.BM

Banco de pruebas

Este código hace algo muy complicado e inteligente con uel operador de punto fijo de Pyth.

El cuerpo de la función, que es todo lo que no sea el u, es bastante sencillo:

+QiR2smc2+0dt#.BM
+QiR2smc2+0dt#.BMG    Implicit variable
                      G will store the list of numbers from the previous iteration.
              .BMG    Map each number to its binary representation
            t#        Filter out the ones of length 1 (0 and 1)
      m               Map the remaining binary
         +0d          Prefix with a 0
       c2             Chop in half.
                      Since c puts the larger half first, prefixing with a 0
                      makes the chop work out right, and doesn't change the value.
     s                Concatenate
  iR2                 Map back to binary
+Q                    Add the input to the front of the list

Este código elimina 0s y 1s, divide cada número y agrega la entrada al frente.

u ejecutará esta función en el resultado anterior de la función hasta que el resultado deje de cambiar.

¿Qué valor inicial uusa? Esa es la parte más inteligente: el código no especifica qué valor usar, por lo que el valor predeterminado es la entrada. Pero la entrada no es una lista de números, es un número. Pyth coacciona implícitamente el número en el primer tiempo a través del ciclo hasta el rango del número - [0, 1, ..., Q-1]. Eso no se parece en nada a la salida que queremos obtener. Afortunadamente, uencontrará el resultado correcto independientemente de cuál sea la entrada inicial: la salida deseada es el único punto fijo de la función, y la aplicación repetida siempre lo alcanzará.

Veamos los valores intermedios del programa con la entrada 7. He resaltado el prefijo del resultado que se garantiza que es correcto, independientemente de la entrada inicial:

  1. 7(Implícitamente [0, 1, 2, 3, 4, 5, 6])

  2. [7,1, 0, 1, 1, 1, 0, 1, 1, 1, 2]

  3. [7, 1, 3,1, 0]

  4. [7, 1, 3, 1, 1]

Cual es la salida.


Pyth empaquetado, 16 bytes

Tenga en cuenta que, dado que Pyth usa solo el rango 0-127 de ASCII, puede comprimirse utilizando una codificación de 7 bits en lugar de una codificación de 8 bits. Por lo tanto, el programa anterior se puede empaquetar en 16 bytes. El programa resultante es:

ꮎ�L����[
    ���4

hexdump:

0000000: eaae 8e9a 4cb9 edc6 c95b 0c9d 11ae 8534  ....L....[.....4

El intérprete se encuentra aquí . Proporcione la entrada como un argumento de línea de comando.

La página de códigos de este lenguaje (Pyth empaquetado) es el rango 0-127 de ASCII, y cada carácter se representa con 7 bits, rellenados al final. Por lo tanto, el hexdump ilegible anterior representa:

u+QiR2smc2+0dt#.BM

Pero en 16 bytes.

isaacg
fuente
6

05AB1E , 21 20 18 17 bytes

,¸[Žrbvy0ì2äCʒ=1›

Pruébalo en línea!

Explicación

,¸[Žrbvy0ì2äCʒ=1›   Argument n
,¸                  Print n and push n as array
  [Ž                Loop until stack is empty
    r               Reverse stack
     b              Convert elements in array to binary
      v             For each y in array
       y0ì2ä        Prepend '0' to y and split it into 2 elements
                    (the first element will take the additional character)
            C       Convert elements to decimal
             ʒ=1›   Keep only elements greater than 1, while printing each element
kalsowerus
fuente
@JonathanAllan Yep lo arregló ahora. Parece ser un problema que los ejemplos no cubren, gracias :)
kalsowerus
ʒ- Esta nueva página de códigos ... ¿Desde cuándo es 05AB1E Jelly? Me gusta.
Magic Octopus Urn
4

JavaScript (ES6), 99 bytes

Esto parece demasiado largo. Puede haber una mejor manera de obtener el orden correcto.

f=(n,p=(a=[],1),i=33-Math.clz32(n)>>1)=>(a[p]=n)>1?f(n>>i,p*=2)&&f(n&(1<<i)-1,p+1):a.filter(n=>1/n)

Manifestación

Arnauld
fuente
4

Jalea , 21 20 bytes

-1 byte eliminando una cadena monádica y luego lidiando con la consecuencia de que una lista vacía se convierta de binario produciendo 0 más tarde.

ỊÐḟBUœs€2UḄF
WÇÐĿṖUF

Un enlace monádico que toma un número y devuelve la lista especificada.

Pruébalo en línea!

¿Cómo?

ỊÐḟBUœs€2UḄF - Link 1, perform an iteration: list of numbers
 Ðḟ          - filter out if:
Ị            -   insignificant (absolute value <= 1 - hence any 0s or 1s)
   B         - convert to a binary list (vectorises)
    U        - upend (reverse each)
     œs€2    - split €ach into 2 equal chunks (the first half is longer if odd ...hence
         U   - upend (reverse each)         ...this upend and the previous one)
          Ḅ  - convert from binary list to number (vectorises, although when the filter
             -                                     removes everything a zero is yielded)
           F - flatten the resulting list of lists to a single list

WÇÐĿṖUF - Main link: number
W       - wrap in a list
  ÐĿ    - loop and collect results until no change occurs:
 Ç      -   call last link (1) as a monad
    Ṗ   - pop (remove the last element - a list containing a single zero which results
        -     from the effect of Ḅ when link 1's input only contained ones and zeros)
     U  - upend (put the iterations into the required order)
      F - flatten to yield a single list
Jonathan Allan
fuente
¿Como funciona esto?
caird coinheringaahing
@ Satan'sSon Agregué una explicación en este momento
Jonathan Allan
Lo agregaste al mismo tiempo que comenté: D
caird coinheringaahing
@ ØrjanJohansen en ambos sentidos tienen el mismo costo de byte
Jonathan Allan,
Oh, no vi la respuesta de Pyth primero, que ya usó ese truco.
Ørjan Johansen
2

Java 7, 541 bytes

import java.util.*;List l=new ArrayList(),L=new ArrayList();String c(int n){l.add(x(n));return a(n+" ",l,n);}String a(String r,List q,Integer n){boolean e=q.equals(l),E=q.equals(L);if(e)L.clear();else l.clear();for(String i:new ArrayList<String>(q)){int s=i.length()/2,a=n.parseInt(i.substring(0,s),2),z=n.parseInt(i.substring(s),2);r+=a+" "+z+" ";if(e&a>1)L.add(x(a));if(e&z>1)L.add(x(z));if(E&a>1)l.add(x(a));if(E&z>1)l.add(x(z));}if(e&L.size()>0)r=a(r,L,n);if(E&l.size()>0)r=a(r,l,n);return r;}String x(Integer n){return n.toString(n,2);}

Mantener el orden original me fastidió a lo grande, de lo contrario sería un bucle fácil y un principio de llamada recursiva. Aún así, es un desafío divertido de resolver mientras retiene el pedido.

Explicación:

import java.util.*;                    // Required import for List and Array List

List l=new ArrayList(),L=new ArrayList(); 
                                       // Two Lists on class-level

String c(int n){                       // Method (1) with integer parameter and String return-type
  l.add(x(n));                         //  Start by adding the binary-String of the input integer to list `l`
  return a(n+" ",l,n);                 //  And let the magic begin in method `a` (2)
}                                      // End of method (1)

String a(String r,List q,Integer n){   // Method (2) with a bunch of parameters and String return-type
  boolean e=q.equals(l),E=q.equals(L); //  Determine which of the two class-level Lists the parameter-List is
  if(e)                                //  If it's `l`:
    L.clear();                         //   Empty `L`
  else                                 //  If it's `L` instead:
    l.clear();                         //   Empty `l`
  for(String i:new ArrayList<String>(q)){
                                       //  Loop over the input list (as new ArrayList to remove the reference)
    int s=i.length()/2,                //   Get the length of the current item in the list divided by 2
                                       //   NOTE: Java automatically floors on integer division,
                                       //   which is exactly what we want for the splitting of odd-length binary-Strings
    a=n.parseInt(i.substring(0,s),2),  //   Split the current binary-String item in halve, and convert the first halve to an integer
    z=n.parseInt(i.substring(s),2);    //   And do the same for the second halve
    r+=a+" "+z+" ";                    //   Append the result-String with these two integers
    if(e&a>1)                          //   If the parameter List is `l` and the first halve integer is not 0:
      L.add(x(a));                     //    Add this integer as binary-String to list `L`
    if(e&z>1)                          //   If the parameter List is `l` and the second halve integer is not 0:
      L.add(x(z));                     //    Add this integer as binary-String to List `L`
    if(E&a>1)                          //   If the parameter List is `L` and the first halve integer is not 0:
      l.add(x(a));                     //    Add this integer as binary-String to List `l`
    if(E&z>1)                          //   If the parameter List is `L` and the second halve integer is not 0:
      l.add(x(z));                     //    Add this integer as binary-String to List `l`
  }                                    //  End of loop
  if(e&L.size()>0)                     //  If the parameter List is `l` and List `L` now contains any items:
    r=a(r,L,n);                        //   Recursive call with List `L` as parameter
  if(E&l.size()>0)                     //  If the parameter List is `L` and List `l` now contains any items:
    r=a(r,l,n);                        //   Recursive call with List `l` as parameter
  return r;                            //  Return the result-String with the now appended numbers
}                                      // End of method (2)

String x(Integer n){                   // Method (3) with Integer parameter and String return-type
  return n.toString(n,2);              //  Convert the integer to its Binary-String
}                                      // End of method (3)

Código de prueba:

Pruébalo aquí.

import java.util.*;
class M{
  List l=new ArrayList(),L=new ArrayList();String c(int n){l.add(x(n));return a(n+" ",l,n);}String a(String r,List q,Integer n){boolean e=q.equals(l),E=q.equals(L);if(e)L.clear();else l.clear();for(String i:new ArrayList<String>(q)){int s=i.length()/2,a=n.parseInt(i.substring(0,s),2),z=n.parseInt(i.substring(s),2);r+=a+" "+z+" ";if(e&a>1)L.add(x(a));if(e&z>1)L.add(x(z));if(E&a>1)l.add(x(a));if(E&z>1)l.add(x(z));}if(e&L.size()>0)r=a(r,L,n);if(E&l.size()>0)r=a(r,l,n);return r;}String x(Integer n){return n.toString(n,2);}

  public static void main(String[] a){
    M m=new M();
    System.out.println(m.c(255));
    m.l.clear();
    m.L.clear();
    System.out.println(m.c(225));
    m.l.clear();
    m.L.clear();
    System.out.println(m.c(32));
  }
}

Salida:

255 15 15 3 3 3 3 1 1 1 1 1 1 1 1 
225 14 1 3 2 1 1 1 0 
32 4 0 1 0 
Kevin Cruijssen
fuente
2

Retina , 142 bytes

.+
$*
+`(1+)\1
${1}0
01
1
{`.+$
$&¶<$&>
+`;(\d*)>
>;<$1>
<.>

{`(\d)>
>$1
}`<(\d)
$1<
<>
;
\b0+\B

}`^;|;\B

¶
;
;;

1
01
+`10
011
0\B

1+
$.&

Pruébalo en línea!

Neil
fuente
2

PHP, 132 bytes

for($r=[$argn];""<$n=$r[+$i++];)$n<2?:[$r[]=bindec(substr($d=decbin($n),0,$p=strlen($d)/2)),$r[]=bindec(substr($d,$p))];print_r($r);

Pruébalo en línea!

Jörg Hülsermann
fuente
Esto no funciona, de acuerdo con el sistema en línea Pruébalo en esta página,
Martin Barker
@MartinBarker, ¿qué quieres decir?
Jörg Hülsermann
tio.run/nexus/… => Array( [0] => 225 [1] => 14 [2] => 1 [3] => 3 [4] => 2 [5] => 1 [6] => 1 [7] => 1 [8] => 0 )cuando no lo hace = 255 15 15 3 3 3 3 1 1 1 1 1 1 1 1
Martin Barker
@MartinBarker Debe cambiar la entrada en la versión del encabezado. Cambiar la variable $argnEsta variable está disponible si ejecuta PHP desde la línea de comandos con la -Ropción. Aquí hay un ejemplo para la entrada 255 ¡ Pruébelo en línea!
Jörg Hülsermann
Eso es lo que estaba tratando de decir que no funcionó de acuerdo con el sistema de prueba en línea. (vinculado en la publicación)
Martin Barker
1

Ruby , 102 bytes

f=->*a{a==[]?[]:a+=f[*a.map{|i|s='%b'%i;i>1?[s[0...h=s.size/2].to_i(2),s[h..-1].to_i(2)]:[]}.flatten]}

Pruébalo en línea!

Tinta de valor
fuente
1

Ruby , 98 bytes

f=->*a{a==[]?a:a+=f[*a.flat_map{|i|s='%b'%i;i>1?[s[0...h=s.size/2].to_i(2),s[h..-1].to_i(2)]:[]}]}

Pruébalo en línea!

Simplemente una optimización básica de la respuesta de Value Ink : use flat_map en lugar de map ... flatten, y use

a==[]?a en lugar de a==[]?[]

Jenkar
fuente