Generar la secuencia del horizonte del templo

39

Considere el siguiente proceso:

  1. Tome un número entero no negativo N.

    por ejemplo, N = 571

  2. Exprésalo en binario sin ceros a la izquierda. (Cero en sí mismo es la única excepción, convirtiéndose 0)

    eg 571= 1000111011en binario

  3. Separe series consecutivas de unos y ceros en esta representación binaria.

    por ejemplo, 10001110111, 000, 111, 0,11

  4. Ordena las carreras de la más larga a la más corta.

    por ejemplo 1, 000, 111, 0, 11000, 111, 11, 1,0

  5. Sobrescriba todos los dígitos en cada ejecución alternando 1'sy 0' s, siempre comenzando con 1's.

    por ejemplo 000, 111, 11, 1, 0111, 000, 11, 0,1

  6. Concatena el resultado para obtener un nuevo número binario.

    por ejemplo 111, 000, 11, 0, 11110001101= 909en decimal

Cuando traza los valores producidos por este proceso, obtiene un gráfico bastante ordenado:

Trama del horizonte del templo a 1024

Y es de esperar que sea evidente por qué llamo a la secuencia resultante la secuencia Temple Skyline :

Skyline del templo

Reto

Escriba un programa o función que tome un número entero no negativo N e imprima o devuelva el número de secuencia correspondiente de Temple Skyline. Su entrada y salida deben estar en decimal.

Por ejemplo, si la entrada es 571la salida debería ser 909.

El código más corto en bytes gana.

Como referencia, aquí están los términos en la secuencia de N = 0 a 20:

0   1
1   1
2   2
3   3
4   6
5   5
6   6
7   7
8   14
9   13
10  10
11  13
12  12
13  13
14  14
15  15
16  30
17  29
18  26
19  25
20  26

Aquí están los términos del 0 al 1023.

Pasatiempos de Calvin
fuente

Respuestas:

4

Pyth, 20 19 bytes

ACr.BQ8|is*V_SGH2 1

1 byte guardado por Jakube

Banco de pruebas

Utiliza el hecho de que después de la codificación de longitud de ejecución, las ejecuciones son las ejecuciones deseadas en la salida.

Perdió 3 bytes de la carcasa especial 0.

isaacg
fuente
14

CJam, 25 23 22 bytes

ri1e>2be`z($W%a\+ze~2b

Solo un poco de codificación de longitud de ejecución. -1 gracias a @ MartinBüttner.

Pruébelo en línea / Test suite .

Explicación

ri        Read n from input as int
1e>       Take max with 1 (special case for n = 0)
2b        Convert n to binary
e`        Run length encode
z         Zip, giving a pair [<counts> <10101.. array>]
($W%      Drop the counts array and sort decending
a\+z      Add it back to the 10101.. array and re-zip
e~        Run length decode
2b        Convert from binary
Sp3000
fuente
11

Pyth - 21 20 bytes

¡Gracias a @sok por salvarme un byte!

is.em%hk2hb_Sr.BQ8 2

Pruébalo aquí en línea .

Maltysen
fuente
Puede usar en .BQlugar de jQ2, lo que significa que puede perder el espacio entre el 8y el precedente 2.
Sok
is*R`s=!Z_ShMr.BQ8 2Es una solución interesante de la misma longitud. Principalmente publicando porque realmente no esperaba que la asignación en un argumento de mapa funcionara.
FryAmTheEggman
1
@FryAmTheEggman Reemplazar `scon ]. Guarda un byte.
Jakube
6

Python 2, 121 bytes 125

121: ¡Gracias a Sp3000 por reducir 4 bytes!

import re;print int("".join(n*`~i%2`for i,n in enumerate(sorted(map(len,re.split('(1*|0+)',bin(input())[2:])))[::-1])),2)

125

import re;print int("".join("10"[i%2]*n for i,n in enumerate(sorted(map(len,re.split('(1*|0+)',bin(input())[2:])))[::-1])),2)
enpenax
fuente
1
¡Agradable! Creo que también puedes hacerlo en n*`~i%2`forlugar de"10"[i%2]*n for
Sp3000
Gracias por editar! Tuve que apresurarme rápidamente pero quería presentarme porque pensé que este era un desafío hermoso y bueno para la primera presentación. ¡Revisaré tu presentación en breve!
enpenax
Creo que puedes guardar algunos bytes usando en sorted(...,key=len)lugar de usarmap(len,... pero no entiendo completamente su programa en este momento, así que no estoy seguro de que eso lo beneficie.
cole
Hola @Cole, estoy mapeando lenporque esa es la única información que necesito para replicar la cantidad de 1 y 0. Probé su sugerencia y agrega 2 bytes, ya que tendré que usarla lendos veces, ¡pero gracias por la sugerencia!
enpenax
5

JavaScript ES6, 110 bytes 113 116 119 120

Guardado 3 bytes gracias a @intrepidcoder

Guardado 3 bytes gracias a @NinjaBearMonkey

n=>+('0b'+n.toString(2).split(/(0+)/).sort((b,a)=>a.length-b.length).map((l,i)=>l.replace(/./g,i-1&1)).join``)

Enfoque directo hacia adelante. No me gusta la longitud de la función de clasificación, pero no puedo pensar en una forma de jugar golf.

Downgoat
fuente
Creo que puedes usar un en +lugar de eval.
intrepidcoder
@intrepidcoder gracias, ¡eso ahorró 3 bytes!
Downgoat
No puedo probar esto, pero split(/(0+)/g)debería poder reemplazarlo match(/(.)\1*/g).
NinjaBearMonkey
@NinjaBearMonkey gracias, ¡eso ahorró 3 bytes!
Downgoat
Guardar un byte: +(s=0, ... .map(l=>l.replace(/./g,s^=1))...)
Espero poder ayudar
5

C ++, 535 527 bytes

(Gracias Zereges por recortar algunos bytes).

Ahora que nos hemos librado de esos bytes, el programa ahora es competitivo;)

#include<iostream>
#include<cmath>
int main(){int I,D;std::cin>>I;while(I>int(pow(2,D))){D++;}int L[99];int X=0;int Z=0;int O=0;for(int i=D-1;i>=0;i--){if( int(pow(2,i))&I){if(Z>0){L[X]=Z;Z=0; X++;}O++;}else{if(O>0){L[X] = O;O=0;X++;}Z++;}}if(Z>0){L[X]=Z;Z=0;X++;}if(O>0){L[X]=O;O=0;X++;}int P=0;bool B = true;int W = D-1;for(int j=0;j<X;j++){int K=0;int mX=0;for(int i=0;i<X;i++){if(L[i]>K){K=L[i];mX=i;}}L[mX]=0;if(B){for(int k=0;k<K;k++){P+=int(pow(2,W));W--;}}else{for(int k=0;k<K;k++){W--;}}B^=1;}std::cout<<P;return 0;}

Soy nuevo en el golf, así que por favor dame algunos consejos en los comentarios .

Cosas como "no necesita esos corchetes" o "use printf" son útiles, pero también agradezco los consejos sobre la lógica. ¡Gracias por adelantado!

Para facilitar la lectura, presento la versión sin golf:

#include<iostream>
#include<cmath>
int main()
{
int input,digits;

std::cin>>input;
while(input > int(pow(2,digits))){digits++;}

int list[99];
int index=0;
int zCounter=0;
int oCounter=0;

for(int i=digits;i>0;i--)
{
    if( int(pow(2,i-1))&input)
    {
        if(zCounter>0)
        {
            list[index] = zCounter;
            zCounter=0;
            index++;
        }
        oCounter++;
    }
    else
    {
        if(oCounter>0)
        {
            list[index] = oCounter;
            oCounter=0;
            index++;
        }
        zCounter++;
    }
}
if(zCounter>0)
{
        list[index] = zCounter;
        zCounter=0;
        index++;
}
if(oCounter>0)
{
        list[index] = oCounter;
        oCounter=0;
        index++;
}

int output = 0;
bool ones = true;
int power = digits-1;
for(int j=0;j<index;j++)
{
    int max=0;
    int mIndex=0;
    for(int i=0;i<index;i++)
    {
        if(list[i]>max){max=list[i];mIndex=i;}
    }
    list[mIndex]=0;

    if(ones)
    {
        for(int k=0;k<max;k++)
        {
            output+=int(pow(2,power));
            power--;
        }
    }
    else
    {
        for(int k=0;k<max;k++)
        {
            power--;
        }
    }
    ones^=1;

}
std::cout<<output;
return 0;
}

EDITAR la versión de golf bajó un par de bytes, la versión sin golf no cambió

Liam
fuente
Puedes en lugar de int a; int b;usar int a,b;. También las variables en el ámbito global se inicializan con 0. Además, no tiene que usar llaves cuando solo hay un comando para ejecutar. También ones=!ones;se puede simplificar comoones ^= 1;
Zereges
Ahorré algunos bytes gracias
Liam
Cambia tu primer forciclo 1, es decir, for(int i=D;i;i--)y úsalo pow(2,i-1)dentro del ciclo.
nimi
@LiamNoronha En realidad no guardó lo que le recomendé :)
Zereges
1
@LiamNoronha Mira esto . Todavía hay mucho espacio para mejorar. Por ejemplo, reutilizar variables (guarda la definición), onestambién puede ser int. Tal vez macroing int(pow(i))en P(i). Le recomendaría que lea la discusión aquí
Zereges,
2

Haskell, 132 131 bytes

import Data.List
g 0=[]
g n=mod n 2:g(div n 2)
q=[1]:[0]:q
f=foldl((+).(2*))0.concat.zipWith(<*)q.sortOn((-)0.length).group.g.max 1

Ejemplo de uso:

> map f [0..20]
[1,1,2,3,6,5,6,7,14,13,10,13,12,13,14,15,30,29,26,25,26]

Cómo funciona:

                 max 1         -- fix n=0: f(0) is the same as f(1)
               g               -- turn into binary, i.e. list of 0s and 1s
            group              -- group sequences of equal elements
         sortOn((-)0.length)   -- sort groups on negative length
      zipWith(<*)q             -- map each element in a group to constant 1 or 0 by turns
   concat                      -- flatten all groups into a single list
foldl((+).(2*))0               -- convert back to decimal
nimi
fuente
2

J - 30 bytes

Función que toma un entero a la derecha. Maneja correctamente 0.

(\:~#2|#\)@(#;.1~1,2~:/\])&.#:
  • #: - Tomar la representación binaria.
  • 1,2~:/\]- Entre cada dígito, informe Verdadero si son diferentes. Anteponga un Verdadero para que la lista tenga Verdadero al comienzo de cada "ejecución".
  • (#;.1~...) - Usando el vector booleano anterior, tome la longitud de cada ejecución.
  • \:~ - Ordene estas longitudes de mayor a menor.
  • 2|#\- Tome una lista de alternar 1 0 1 0 ...tanto como la lista de longitudes.
  • (...#...) - Para cada número a la izquierda (longitudes ordenadas), tome la mayor cantidad de elementos correspondientes a la derecha (alternando 1 y 0)
  • &. - Convierta esta nueva representación binaria a un número.

Ejemplos:

   (\:~#2|#\)@(#;.1~1,2~:/\])&.#: 571
909
   i.21   NB. zero to twenty
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
   (\:~#2|#\)@(#;.1~1,2~:/\])&.#: every i.21   NB. apply separately to every number
1 1 2 3 6 5 6 7 14 13 10 13 12 13 14 15 30 29 26 25 26
Algoritmo de tiburón
fuente
2

Perl 5.10, 121 101

say oct"0b".join'',map{$|=1-$|;$_=~s/./$|/gr}sort{length$b<=>length$a}(sprintf"%b",shift)=~/(0*|1*)/g

Creo que la parte de clasificación puede ser más corta.

Editar: -20 bytes, gracias a symbabque!

Laposhasú Acsa
fuente
Puede deshacerse de \n, y mno es necesario para la coincidencia de expresiones regulares. En su sustitución, simplemente use en .lugar del grupo char.
simbabque
No hay necesidad de la grepparte tampoco. El octes limpio aunque :)
simbabque
Gracias, accidentalmente dejé esas partes del código original.
Laposhasú Acsa
1

Python 3, 146136 bytes

import re;print(int(''.join(len(j)*'01'[i%2<1]for i,j in enumerate(sorted(re.findall('1+|0+',bin(int(input()))[2:]),key=len)[::-1])),2))
Puertas de Zach
fuente
En lugar de mapcon un lambda, ¿sería mejor hacerlo ''.join(... for ... in ...)?
Sp3000
1

Mathematica, 83 bytes

Flatten[0#+(d=1-d)&/@SortBy[d=0;Split[#~IntegerDigits~2],-Length@#&]]~FromDigits~2&

Esto define una función sin nombre.

Martin Ender
fuente
0

Ruby, 107 104 102 bytes

(guardado 3 bytes gracias a nimi )

No voy a vencer a los gustos de CJam, pero lo tengo bastante pequeño para un lenguaje sensato.

p gets.to_i.to_s(2).scan(/((.)\2*)/).map{|e|e[i=0].size}.sort.reverse.map{|e|"#{i=1-i}"*e}.join.to_i 2
Restablecer a Monica iamnotmaynard
fuente
Unos pocos bytes para guardar: (i+=1)%2es i=1-i.
nimi
@nimi Ah, gracias. Estaba tratando de descubrir cómo acortar eso.
Reinstale a Monica iamnotmaynard el
0

Java 8, 179 176 bytes

(x)->{int g[]=new int[32],h=0,i=highestOneBit(x);g[0]=1;while(i>1)g[((x&i)>0)^((x&(i>>=1))>0)?++h:h]++;sort(g);for(i=32,h=0;g[--i]>0;)while(g[i]-->0)h=h<<1|i%2;return x<1?1:h;}

Usé dos importaciones estáticas: java.util.Integer.highestOneBityjava.util.Arrays.sort .

Para facilitar la lectura, aquí está el código sin golf:

java.util.function.ToIntFunction<Integer> f = (x) -> {
  int g[] = new int[32], h = 0, i = java.util.Integer.highestOneBit(x);
  g[0] = 1;
  while (i > 1) {
    g[((x & i) > 0) ^ ((x & (i >>= 1)) > 0) ? ++h : h]++;
  }
  java.util.Arrays.sort(g);
  for (i = 32, h = 0; g[--i] > 0;) {
    while (g[i]-- > 0) {
      h = h << 1 | i % 2;
    }
  }
  return x < 1 ? 1 : h; // handle zero
};
Olivier Grégoire
fuente
-1

Python 2, 170 bytes

def t(n):
  from itertools import groupby;lst=sorted([''.join(g) for n,g in groupby(bin(n)[2:])],key=len)[::-1];s=''
  for i in lst:s+=str(i)
  return int(s,2)
Tristan Batchler
fuente
44
Bienvenido a PPCG! Desafortunadamente, creo que esto da los valores incorrectos para algunos números, por ejemplo, t(0) = 0cuándo 1se espera y t(4) = 1cuándo se espera 6
Sp3000