"Ajustar números"

Sam tem uma idéia "brilhante" para compactação! Você pode ajudar?

---

Aqui está um resumo do esquema de compactação de Sam. Primeiro, pegue uma representação da base 10 de qualquer número natural estritamente menor que 2 ^ 16 e escreva-a como uma sequência binária sem zeros à esquerda.

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

Agora substitua qualquer grupo de um ou mais zeros por um único zero. Isso ocorre porque o número ficou menor. Sua string binária agora ficará assim.

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

Agora você converte a string binária de volta para uma representação da base 10 e a produz em qualquer formato aceitável. Aqui estão seus casos de teste. O primeiro número inteiro representa uma entrada e o último número inteiro representa uma saída. Observe que alguns números não mudam e, portanto, podem ser chamados de "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

---

Você pode usar qualquer idioma, mas observe que Sam odeia brechas padrão. Este é o código golf, portanto o código pode ser o mais curto possível para liberar espaço para os números "compactados".

---

Nota: Este NÃO é um esquema de compactação aceitável. Usando isso, você será imediatamente demitido.

---

Necessidade de citação: Não aceito crédito por esse conceito. Isso vem do blog de @Conor O 'Brien aqui, veja este OEIS de números adequados. https://oeis.org/A090078

05AB1E , 8 6 bytes

b00¬:C

Explicação

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

Experimente online

Economizou 2 bytes graças a Adnan

Utilitários Bash + GNU, 27

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

Entrada lida de STDIN.

JavaScript (ES6), 41 bytes

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

Água-viva , 20 bytes

p
d
# S
,1
*
\dbi
 2

Experimente online!

Explicação

• i é entrada.
• b converte-o em binário (lista de dígitos)
• \dcom argumentos 2e a lista de dígitos se aplica d(dígitos binários ao número) a cada substring de comprimento 2 da lista de dígitos.
• * assume signum dos resultados: 00 vai para 0, todo o resto para 1.
• ,1 coloca um 1 no final, para que o último dígito não seja perdido.
• # Sseleciona bios dígitos que têm 1 na lista calculada acima: aqueles que não são as metades esquerdas de 00.
• dconverte novamente em número e pimprime o resultado.

Python 2, 36 bytes

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

Uma implementação recursiva direta sem built-ins de conversão base ou operações de string. Menos golfe:

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

Quando né um múltiplo de 4, termina em dois 0 de em binário, então vamos cortar um por do chão dividindo por 2. Caso contrário, nós dividimos nem (n%2) + 2*(n/2), deixe o último dígito binário n%2sozinho, e recurse em outros dígitos n/2.

Bash (sed + bc), 60 55 43 bytes

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

editar:

1. alterado sed -E 's/0+para sed 's/00*eco alterado e tubo usado para passar o valor para bc com <<<.
2. Sugestão brilhante de @Digital Trauma!

exemplo:

$ 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/})}

Explicação:

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

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

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

Exemplo:

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 versão funciona apenas no MATLAB, pois strrepno MATLAB pode lidar com entradas lógicas. Aqui está uma versão que funcionará em oitava (9 bytes) (e, portanto, o interpretador on-line) que lança explicitamente as entradas lógicas para digitar double.

Experimente online

Explicação

    % 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.

Economizou 4 bytes graças ao Sp3000.

Solução bastante simples.

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

Na verdade, 14 bytes (não concorrentes)

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

Experimente online!

Este envio não é concorrente porque uma correção de bug para Æ foi feita após o lançamento deste desafio.

Explicação:

├`'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 graças a @Doorknob

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

Veja em repl.it: https://repl.it/CnnQ/2

Geléia , 13 7 bytes

6 bytes graças a Zgarb por seu algoritmo .

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

Experimente online!

PHP, 53 51 bytes

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

Leva um argumento do console.

Graças a:

@manatwork substitua "0" por 0

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

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

Precisa de -psinalizador para executar (eu adicionei -lsinalizador para torná-lo mais legível, mas não é necessário caso contrário):

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

Observe muito a dizer sobre o código: ele converte o número em binário (sprintf"%b" ), depois substitui os blocos de zeros por apenas um zero e converte o resultado em 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 graças a TuukkaX

Java, 75

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

Programa de teste:

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)

( solicitação de recurso Uma maneira mais curta de converter de / para binário no PowerShell )

Recebe entrada $args[0], usa o .NET interno [convert]::ToString(int,base)para converter o número inteiro de entrada em uma cadeia de base binária. Isso é filtrado pelo -replacepara remover quaisquer execuções de um ou mais zeros para apenas 0. Essa sequência resultante é enviada de volta pela outra direção via [convert]::ToInt32(string,base)para transformar o binário novamente em um número inteiro. Esse número inteiro é deixado no pipeline e a saída é implícita.

Casos de teste

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

Implementação de referência no SILOS "apenas" 417 bytes

Golfe

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

Aqui está a implementação de referência totalmente desfeita. Como um recurso de bônus, ele exibe as etapas necessárias para obter uma resposta.

/**
*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

A pedido, a transpilação foi excluída. Sinta-se livre para visualizar o histórico de edições para recuperá-lo; caso contrário, acesse este repositório para um intérprete.

Saída de amostra 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

Conectados.

  .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

Experimente online!

E aqui eu pensei que Retina estaria entre as primeiras respostas ...

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 a menos graças a @RohanJhunjhunwala. Prefiro mantê-lo como um programa totalmente funcional com main e similares. No entanto, é claro que pode ser jogado de outra forma.
• 5 bytes a menos, graças às sugestões de @ LeakyNun.

Dyalog APL , 19 bytes

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

TryAPL online!

Esta função é realmente um "topo" de duas funções, a primeira função é:

2∘⊥⍣¯1o inverso da conversão binário em decimal, ou seja, conversão binária de decimal
 dois 2 é vinculado ∘ a decimal para ⊥
 repetir a operação ⍣ negativa uma vez ¯1(ou seja, uma vez, mas invertida)

Na segunda função, o resultado binário do acima é representado por ⍵:

{2⊥⍵/⍨~0 0⍷⍵}
 0 0⍷⍵Booleano para onde {0, 0} começa em neg Negação
 ~booleana, agora temos ᴛʀᴜᴇ em todos os lugares, exceto nos zeros que não são os primeiros em execuções com zero,
 ⍵/⍨usam isso para filtrar ⍵, para remover nossos zeros indesejados e
 2⊥converter o binário em decimal

TSQL, 143 bytes

Não usando build ins para converter de e para binário.

Golfe:

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

Ungolfed:

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

Violino

CJam, 16

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

Experimente online

É bastante longo devido à falta de regex.

Explicação:

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 teste

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

Experimente online!

Explicação

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

Economizou dois bytes graças ao manatwork.

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

A abordagem ingênua. (:

C, 37 bytes

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