Divida-me ao meio

15

Você receberá um número x, onde 0 <= x <= 2^32 - 1.

Você deve gerar uma lista de números em decimal, após a divisão recursiva em formato binário.

Exemplos:

Exemplo 1:

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

A lista atual é justa 255.

A representação binária de 255é 1111 1111. Dividindo, obtemos 1111e 1111, que em decimal são 15e 15.

Nós os adicionamos à lista, então teremos 255 15 15.

Agora os números 15e 15servirão como entradas e esses números serão divididos.

Fazê-lo novamente, obtemos ( 3 3de ambos 15s): 255 15 15 3 3 3 3.

Continuando a lógica, a lista final será 255 15 15 3 3 3 3 1 1 1 1 1 1 1 1. E como 1não pode mais ser dividido, a saída é interrompida.

Exemplo 2:

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

A lista inicial é 225.

A representação binária de 225é 1110 0001. Dividindo, obtemos 1110e 0001, que em decimal são 14e 1.

Adicionando-os à lista, obtemos 225 14 1.

Agora os números 14e 1servirão como entradas e esses números serão divididos.

Como 1não é divisível, a saída será 225 14 1 3 2.

Exemplo 3:

32 -> 32 4 0 1 0

Condições :

  1. Se o número de dígitos binários for ímpar, o primeiro número terá um dígito binário a menos que o próximo. Exemplo, 20 (10100)será dividido como 10e 100, com a saída decimal sendo 2e 4.
  2. Aplicam-se regras de brecha padrão.
  3. 0se 1não se propagam mais.
  4. Falha no programa por tentar exibir muitos números é uma condição de saída válida.
ctrl-shift-esc
fonte
Apenas uma sugestão, mas que tal ter os dígitos binários preenchidos com 0s quando o comprimento é ímpar?
Caird coinheringaahing
1
@ Satan'sSon Se você der um tapinha na frente, isso é equivalente à descrição.
Isaacg 19/05
1
A ordem de saída especificada é necessária ou apenas os valores?
Jonathan Allan
@ Satan'sSon Sem preenchimento com 0s.
ctrl-shift-esc
1
@JonathanAllan A ordem de saída especificada é necessária.
ctrl-shift-esc

Respostas:

13

Pitão, 18 bytes

u+QiR2smc2+0dt#.BM

Suíte de teste

Esse código faz algo muito complicado e inteligente com uo operador de ponto fixo do Pyth.

O corpo da função, que é tudo diferente de u, é bastante direto:

+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

Esse código remove 0s e 1s, divide todos os números e adiciona a entrada na frente.

u executará esta função no resultado anterior da função até que o resultado pare de mudar.

Qual valor inicial uusa? Essa é a parte mais inteligente: o código não especifica qual valor usar, então o padrão é a entrada. Mas a entrada não é uma lista de números - é um número. Pyth implica implicitamente o número no primeiro tempo através do loop até o intervalo do número - [0, 1, ..., Q-1]. Isso não se parece em nada com o resultado que queremos obter. Felizmente, uencontrará o resultado correto, independentemente da entrada inicial - a saída desejada é o único ponto fixo da função e a aplicação repetida sempre o alcançará.

Vejamos os valores intermediários do programa com a entrada 7. Eu destaquei o prefixo do resultado que é garantido como correto, independentemente da entrada inicial:

  1. 7(Implicitamente [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]

Qual é a saída.


Pyth compactado, 16 bytes

Observe que, como o Pyth usa apenas o intervalo 0-127 do ASCII, ele pode ser compactado usando uma codificação de 7 bits em vez de uma codificação de 8 bits. Assim, o programa acima pode ser compactado em 16 bytes. O programa resultante é:

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

hexdump:

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

O intérprete é encontrado aqui . Forneça a entrada como um argumento da linha de comandos.

A página de código desse idioma (Packed Pyth) é o intervalo de 0 a 127 do ASCII, e cada caractere é representado com 7 bits, preenchido no final. Assim, o hexdump ilegível acima representa:

u+QiR2smc2+0dt#.BM

Mas em 16 bytes.

isaacg
fonte
6

05AB1E , 21 20 18 17 bytes

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

Experimente online!

Explicação

,¸[Ž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
fonte
@JonathanAllan Yep o corrigiu agora. Parece ser um problema os exemplos não cobrem, obrigado :)
kalsowerus
ʒ- Esta nova página de códigos ... Desde quando é 05AB1E Jelly? Eu gosto.
Urna de polvo mágico
4

JavaScript (ES6), 99 bytes

Parece um pouco longo. Pode haver uma maneira melhor de obter a ordem correta.

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)

Demo

Arnauld
fonte
4

Geléia , 21 20 bytes

-1 byte, removendo uma cadeia monádica e, em seguida, lidando com a conseqüência de uma lista vazia ser convertida do binário com 0 mais tarde.

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

Um link monádico pegando um número e retornando a lista especificada.

Experimente online!

Quão?

ỊÐḟ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
fonte
Como é que isso funciona?
Caird coinheringaahing
@ Satan'sSon Adicionei uma explicação agora
Jonathan Allan
Você adicionou ao mesmo tempo que eu comentei: D
caird coinheringaahing
@ ØrjanJohansen ambos os sentidos têm o mesmo custo byte
Jonathan Allan
Ah, não vi a resposta Pyth primeiro, que já usava esse truque.
Ø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);}

Manter o pedido original me ferrou muito, caso contrário, seria apenas um princípio fácil de loop e chamada recursiva. Ainda assim, é um desafio divertido de descobrir, mantendo a ordem.

Explicação:

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 do teste:

Experimente aqui.

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));
  }
}

Resultado:

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
fonte
2

Python 2 , 110 bytes

l=[input()];i=1
while i:
 z=0
 for k in l[-i:]:
	if k>1:b=~-len(bin(k))/2;l+=[k>>b,k&2**b-1];z+=2
 i=z
print l

Experimente online!

ovs
fonte
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+
$.&

Experimente online!

Neil
fonte
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);

Experimente online!

Jörg Hülsermann
fonte
Isso não funciona, de acordo com a experimentá-lo sistema on-line nesta página;
Martin Barker
@MartinBarker, o que você quer dizer?
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 )quando não = 255 15 15 3 3 3 3 1 1 1 1 1 1 1 1
Martin Barker
@MartinBarker Você deve alterar a entrada no cabeçalho Versão. Alterar a variável $argnEsta variável estará disponível se você estiver executando o PHP na linha de comando com a -Ropção Aqui está um exemplo para a entrada 255 Experimente online!
Jörg Hülsermann 22/17
Isso é o que eu estava tentando dizer que não funcionava de acordo com o sistema try it online. (link no post)
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]}

Experimente online!

Value Ink
fonte
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)]:[]}]}

Experimente online!

Simplesmente uma otimização básica da resposta do Value Ink : use flat_map em vez de map ... flatten e use

a==[]?a ao invés de a==[]?[]

Jenkar
fonte