"Números aptos"

¡Sam tiene una idea "brillante" para la compresión! ¿Puede usted ayudar?

---

Aquí hay un resumen del esquema de compresión de Sam. Primero tome una representación de base 10 de cualquier número natural estrictamente menor que 2 ^ 16, y escríbala como una cadena binaria sin ceros a la izquierda.

1 -> 1
9 -> 1001
15 -> 1111
13 -> 1101
16 -> 10000
17 -> 10001
65535 -> 111111111111111

Ahora reemplace cualquier grupo de uno o más ceros con un solo cero. Esto se debe a que el número se ha vuelto más delgado. Su cadena binaria ahora se verá así.

1 -> 1 -> 1
9 -> 1001 -> 101
15 -> 1111 -> 1111
13 -> 1101 -> 1101
16 -> 10000 -> 10
17 -> 10001 -> 101
65535 -> 111111111111111 -> 111111111111111

Ahora convierte la cadena binaria de nuevo a una representación de base 10 y la genera en cualquier formato aceptable. Aquí están tus casos de prueba. El primer entero representa una entrada, y el último entero representa una salida. Tenga en cuenta que algunos números no cambian y, por lo tanto, pueden denominarse "ajuste"

1 -> 1 -> 1 -> 1
9 -> 1001 -> 101 -> 5
15 -> 1111 -> 1111 -> 15
13 -> 1101 -> 1101 -> 13
16 -> 10000 -> 10 -> 2
17 -> 10001 -> 101 -> 5
65535 -> 1111111111111111 -> 1111111111111111 -> 65535
65000 -> 1111110111101000 -> 11111101111010 -> 16250

---

Puede usar cualquier idioma, pero tenga en cuenta que Sam odia las lagunas estándar. Este es el código de golf, por lo que el código puede ser lo más corto posible para dejar espacio para los números "comprimidos".

---

Nota: Este NO es un esquema de compresión aceptable. Usar esto lo despedirá rápidamente.

---

Cita requerida: No tomo crédito por este concepto. Esto viene del blog de @Conor O 'Brien aquí, vea este OEIS de números de ajuste. https://oeis.org/A090078

05AB1E , 8 6 bytes

b00¬:C

Explicación

b        # convert input to binary
 00¬:    # replace 00 with 0 while possible
     C   # convert to int

Pruébalo en línea

Guardado 2 bytes gracias a Adnan

Bash + GNU utilidades, 27

dc -e2o?p|tr -s 0|dc -e2i?p

Entrada leída desde STDIN.

JavaScript (ES6), 41 bytes

n=>+`0b${n.toString(2).replace(/0+/g,0)}`

Medusa , 20 bytes

p
d
# S
,1
*
\dbi
 2

Pruébalo en línea!

Explicación

• i es entrada.
• b lo convierte a binario (lista de dígitos)
• \dcon argumentos 2y la lista de dígitos se aplica d(dígitos binarios al número) a cada subcadena de longitud 2 de la lista de dígitos.
• * toma el signo de los resultados: 00 va a 0, todo lo demás a 1.
• ,1 agrega un 1 al final, por lo que el último dígito no se pierde.
• # Sselecciona de biesos dígitos que tienen un 1 en la lista calculada anteriormente: aquellos que no son las mitades izquierdas de 00.
• dconvierte de nuevo a número e pimprime el resultado.

Python 2, 36 bytes

f=lambda n:n and f(n/2)<<(n%4>0)|n%2

Una implementación recursiva directa sin operaciones integradas de conversión de base u operaciones de cadena. Menos golfizado:

f=lambda n:n and[f(n/2),n%2+2*f(n/2)][n%4>0]

Cuando nes un múltiplo de 4, termina en dos ceros en binario, por lo que cortamos uno dividiendo el piso por 2. De lo contrario, nos dividimos nen (n%2) + 2*(n/2), dejamos solo el último dígito binario n%2y volvemos a los otros dígitos n/2.

Bash (sed + bc), 60 55 43 bytes

echo $[2#`bc<<<obase=2\;$1|sed s/00\*/0/g`]

editar:

1. cambiado sed -E 's/0+a sed 's/00*y modificado echo y pipe utilizado para pasar el valor a bc con <<<.
2. ¡Brillante sugerencia de @Digital Trauma!

ejemplo:

$ bash script.sh 65000
16250
$ bash script.sh 15
15
$ bash script.sh 9
5

Perl 6 ,  31  27 bytes

{:2(.base(2).subst(:g,/0+/,0))}
{:2(.base(2)~~{S:g/0+/0/})}

Explicación:

-> $_ {
  # convert from base 2
  :2(

    # convert to base 2
    $_.base(2)

    # substitute
    .subst(
      :global,
      / 0+ /,  # all substrings made of 0s
      '0'      # with one 0
    )
  )
}

Ejemplo:

my &fit-compress = {:2(.base(2)~~{S:g/0+/0/})}
say fit-compress 1;     # 1
say fit-compress 9;     # 5
say fit-compress 15;    # 15
say fit-compress 13;    # 13
say fit-compress 16;    # 2
say fit-compress 17;    # 5
say fit-compress 65535; # 65535
say fit-compress 65000; # 16250

# number created with ｢:2( [~] <0 1>.roll: 256 )｣
say fit-compress 80794946326210692074631955353531749442835289622757526957697718534769445507500
# 4240335298301026395935723255481812004519990428936918

MATL 11 9 8 bytes

BFFOZtXB

Esta versión funciona solo en MATLAB ya que strrepen MATLAB puede manejar entradas lógicas. Aquí hay una versión que funcionará en Octave (9 bytes) (y, por lo tanto, el intérprete en línea) que explícitamente emite las entradas lógicas para escribir double.

Pruébalo en línea

Explicación

    % Implicitly grab input
B   % Convert decimal to binary
FF  % Create the array [0 0]
O   % Number literal
Zt  % Replaces all [0 0] with [0] (will replace any number of 0's with 0)
XB  % Convert binary to decimal
    % Implicitly display

Python 3, 55 , 50 bytes.

Guardado 4 bytes gracias a Sp3000.

Solución bastante sencilla.

import re
f=lambda x:eval(re.sub('0+','0',bin(x)))

Javascript (ES6), 40 bytes

n=>'0b'+n.toString(2).replace(/0+/g,0)-0

En realidad, 14 bytes (no competitivos)

├`'0;;+(Æ`Y2@¿

Pruébalo en línea!

Esta presentación no es competitiva porque se realizó una corrección de errores Ædespués de que se publicó este desafío.

Explicación:

├`'0;;+(Æ`Y2@¿
├               bin(input) (automatically discards leading zeroes)
 `'0;;+(Æ`Y     call this function until the output stops changing:
  '0;;+           push "0", "00"
       (Æ         replace "00" with "0" in binary string
           2@¿  convert from binary to decimal

Ruby, 35 31 bytes

-2 bytes gracias a @Doorknob

->n{eval ("0b%b"%n).squeeze ?0}

Véalo en repl.it: https://repl.it/CnnQ/2

Jalea , 13 7 bytes

6 bytes gracias a Zgarb por su algoritmo .

BŒgµL * x @ Ḣµ € FḄ
BŒgḄBFḄ

Pruébalo en línea!

PHP, 53 51 bytes

<?=bindec(preg_replace("/0+/",0,decbin($argv[1])));

Toma un argumento de la consola.

Gracias a:

@manatwork reemplaza "0" con 0

Perl, 38 + 1 ( -p) = 39 bytes

$_=oct"0b".sprintf("%b",$_)=~s/0+/0/gr

Necesita -pque se ejecute el indicador (agregué el -lindicador para hacerlo más legible, pero de lo contrario no es necesario):

perl -plE '$_=oct"0b".sprintf("%b",$_)=~s/0+/0/gr' <<< "1
9
15
13
16
17
65535
65000"

Tenga en cuenta mucho que decir sobre el código: convierte el número en binario ( sprintf"%b"), luego reemplaza los bloques de ceros por solo un cero y convierte el resultado en decimal ( oct"0b".).

C #, 112 91 bytes

int x(int x)=>Convert.ToInt32(Rege‌​x.Replace(Convert.ToS‌​tring(x,2),"0+","0"),2);

-8 bytes gracias a TuukkaX

Java, 75

int f(Integer x){return x.valueOf(x.toString(x,2).replaceAll("0+","0"),2);}

Programa de prueba:

public class Fit {
    int f(Integer x){return x.valueOf(x.toString(x,2).replaceAll("0+","0"),2);}

    public static void main(final String... args) {
        final Fit x = new Fit();
        System.out.println(x.f(65000));
    }
}

PARI / GP , 54 43 bytes

n->fold((a,b)->a+if(b,a+1,a%2,a),binary(n))

PowerShell v2 +, 69 bytes

[convert]::ToInt32(([convert]::ToString($args[0],2)-replace'0+',0),2)

( solicitud de características Una forma más corta de convertir a / desde binario en PowerShell )

Toma entrada $args[0], usa el .NET incorporado [convert]::ToString(int,base)para convertir el entero de entrada en una cadena base binaria. Eso se filtra a través del -replacepara eliminar cualquier ejecución de uno o más ceros a solo 0. Esa cadena resultante se envía de vuelta a través de la otra dirección [convert]::ToInt32(string,base)para convertir el binario en un entero. Ese entero se deja en la tubería y la salida es implícita.

Casos de prueba

PS C:\Tools\Scripts\golfing> 1,9,15,13,16,17,65535,65000|%{"$_ -> " +(.\output-fit-number.ps1 $_)}
1 -> 1
9 -> 5
15 -> 15
13 -> 13
16 -> 2
17 -> 5
65535 -> 65535
65000 -> 16250

Implementación de referencia en SILOS "solo" 417 bytes

Golfed

readIO :
i + 1
I = i
z = 1 
n = 32
b = n
z = 1
n = b
lbla
n - 1
GOSUB p
j = i
j - p
if j b
if z c
z = 1
GOTO e
lblc
b - 1
if n a
GOTO f
lblb
z = 0
A = a
A + 1000
set A 1
i - p
lble
a + 1
if n a
lblf
q = 1000
e = q
e + b
i = 0
lbl>
d = q
d - e
if d ?
n = b
n - i
GOSUB p
g = get q
g * p
o + g
i + 1
q + 1
GOTO >
lbl?
o / 2
printInt o
GOTO z
funcp
p = 1
Z = n
lblQ
if Z C
GOTO D
lblC
Z - 1
p * 2
GOTO Q
lblD
return
lblz

Aquí está la implementación de referencia totalmente sin golf. Como característica adicional, muestra los pasos necesarios para llegar a una respuesta.

/**
*Reference Implementation in the high quality S.I.L.O.S language.
*/
readIO Enter a number to "compress"
//some declarations
i + 1
I = i
z = 1 
//the above is a flag which shows whether or not a zero was last outputted
n = 32
b = n
//maximum number of input bits
printLine Original Binary



lblbinLoop
n - 1
GOSUB pow
j = I
j - p
if j printOne
if z ENDLOOP
print 0
GOTO ENDLOOP
lblprintOne
z = 0
print 1
I - p
lblENDLOOP
if n binLoop




printLine  
printLine Binary "Compressed"


z = 1
n = b


lbltopA
n - 1
GOSUB pow
j = i
j - p
if j printAOne
if z DontPrint
z = 1
print 0
GOTO ENDLOOPA
lblDontPrint
b - 1
if n topA
GOTO endOfBin
lblprintAOne
z = 0
print 1
A = a
A + 1000
set A 1
i - p
lblENDLOOPA
a + 1
if n topA

lblendOfBin

printLine  
printLine -----------
printLine Base 10 Output
print Out Bits:
printInt b

q = 1000
e = q
e + b
i = 0
lblOutputDec
d = q
d - e
if d DONE
n = b
n - i
GOSUB pow
g = get q
g * p
o + g
i + 1
q + 1
GOTO OutputDec
lblDONE
printLine
printLine ---------
o / 2
printInt o

GOTO funcs
//function declarations must be wrapped in gotoes to avoid the interpreter from complaining (breaking)

/**
*This will store the nth power of two in the "p" variable
*/
funcpow
p = 1
Z = n
lbltop
if Z continue
GOTO end
lblcontinue
Z - 1
p * 2
GOTO top
lblend
return

lblfuncs

Por solicitud, la transpilación ha sido eliminada. Siéntase libre de ver el historial de edición para recuperarlo, de lo contrario vaya a este repositorio para obtener un intérprete.

Salida de muestra para 65000

Enter a number to "compress"
65000
Original Binary
1111110111101000 
Binary "Compressed"
11111101111010 
-----------
Base 10 Output
Out Bits:14
---------
16250

Pyth, 12

i:.BQ"0+"\02

En línea.

  .BQ            # Convert input from base 10 to base 2
 :   "0+"\0      # Replace multiple zeroes with single zero
i          2     # Convert back from base 2 to base 10

Retina , 30 bytes

.+
$*1;
+`(1+)\1
$1;
1;
1
;+
0

Pruébalo en línea!

Y aquí pensé que Retina estaría entre las primeras respuestas ...

Java, 152 143 138 bytes

interface C{static void main(String[]b){Integer i=0;System.out.print(i.parseInt(i.toString(i.parseInt(b[0]),2).replaceAll("0+","0"),2));}}

• 9 bytes menos gracias a @RohanJhunjhunwala. Prefiero mantenerlo como un programa completamente funcional con main y similares. Sin embargo, por supuesto, se puede jugar más al golf de lo contrario.
• 5 bytes menos gracias a las sugerencias de @ LeakyNun.

Dyalog APL , 19 bytes

{2⊥⍵/⍨~0 0⍷⍵}2∘⊥⍣¯1

TryAPL en línea!

Esta función es realmente una "cima" de dos funciones, la primera función es:

2∘⊥⍣¯1la inversa de binary- a conversión -decimal, es decir binary- de conversión -decimal
 dos 2 está obligado ∘ a -to-decimal ⊥
 de repetición de la operación ⍣ uno negativo tiempo ¯1(es decir, una vez, pero invertida)

En la segunda función, el resultado binario anterior está representado por ⍵:

{2⊥⍵/⍨~0 0⍷⍵}
 0 0⍷⍵Booleano para donde {0, 0} comienza en ⍵ Negación
 ~booleana, por lo que ahora tenemos ᴛʀᴜᴇ en todas partes, pero en los primeros ceros en las ejecuciones cero,
 ⍵/⍨use eso para filtrar ⍵, por lo que esto elimina nuestros ceros no deseados
 2⊥convertir binario a decimal

TSQL, 143 bytes

No usar build ins para convertir desde y hacia binario.

Golfizado:

DECLARE @i INT=65000

,@ CHAR(99)=''WHILE @i>0SELECT @=REPLACE(LEFT(@i%2,1)+@,'00',0),@i/=2WHILE @>''SELECT @i+=LEFT(@,1)*POWER(2,LEN(@)-1),@=STUFF(@,1,1,'')PRINT @i

Sin golf:

DECLARE @i INT=65000

,@ CHAR(99)=''
WHILE @i>0
  SELECT @=REPLACE(LEFT(@i%2,1)+@,'00',0),@i/=2

WHILE @>''
  SELECT @i+=LEFT(@,1)*POWER(2,LEN(@)-1),@=STUFF(@,1,1,'')

PRINT @i

Violín

CJam, 16

q~2b1+0a%0a*);2b

Pruébalo en línea

Es bastante largo debido a la falta de expresiones regulares.

Explicación:

q~     read and evaluate the input number
2b     convert to base 2 (array of 1s and 0s)
1+     append a 1 to deal with trailing zeros
0a%    split by [0], dropping empty pieces; only chunks of 1s are left
0a*    join by [0]
);     discard the 1 we appended before
2b     convert back from base 2

Java, 64 bytes

i->{return i.parseInt(i.toString(i,2).replaceAll("0+","0"),2);};

Programa de prueba

public static void main(String[] args) {
    Function<Integer, Integer> function = i -> {
        return i.parseInt(i.toString(i, 2).replaceAll("0+", "0"), 2);
    };

    System.out.println(function.apply(1)); // 1
    System.out.println(function.apply(9)); // 5
    System.out.println(function.apply(15)); // 15
    System.out.println(function.apply(13)); // 13
    System.out.println(function.apply(16)); // 2
    System.out.println(function.apply(17)); // 5
    System.out.println(function.apply(65535)); // 65535
}

CJam , 23 bytes

ri2be`{_:g:>{:g}&}%e~2b

Pruébalo en línea!

Explicación

ri          e# Read input as an integer
2b          e# Convert to binary
e`          e# Run-length encoding. Gives a nested (2D) array with run-lengths 
            e# and binary digits
{           e# This block is mapped over the outer array, i.e. is applied to
            e# each inner array
   _        e#   Duplicate the inner array
  :g        e#   Signum of each element of inner array
  :>        e#   This gives true if second element (digit) is false and first
            e#   element (run-length) is not zero. If so, we need to set that
            e#   run-length to 1
  {:g}&     e#   If that's the case, apply signum to original copy of inner
            e#   array, to make run-length 1
}%          e# End block which is mapped over the outer array
e~          e# Run-length decoding
2b          e# Convert from binary. Implicitly display

Ruby, 37 35 bytes

Guardado dos bytes gracias a manatwork.

->a{a.to_s(2).gsub(/0+/,?0).to_i 2}

El enfoque ingenuo. (:

C, 37 bytes

f(x){return x?f(x/2)<<!!(x%4)|x&1:0;}