Output "Fit" numbers

Question

"Fit Numbers"

Sam has a "brilliant" idea for compression! Can you help?

---

Here is a rundown of Sam's compression scheme. First take in a base 10 representation of any natural number strictly smaller than 2^16, and write it as a binary string without any leading zeros.

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

Now replace any group of one or more zeros with a single zero. This is because the number has gotten leaner. Your binary string now will look like this.

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

Now you convert the binary string back to a base 10 representation, and output it in any acceptable format. Here are your test cases. The first integer represents an input, and the last integer represents an output. Note that some numbers do not change, and thus can be called "fit"

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

---

You may use any language, but please note that Sam hates standard loopholes. This is code golf so the code can be as short as possible to make room for the "compressed" numbers".

---

Note:This is NOT an acceptable compression scheme. Using this will promptly get you fired.

---

Citation-Needed: I do not take credit for this concept. This comes from @Conor O' Brien's blog here see this OEIS of fit numbers. https://oeis.org/A090078

Answer 1

Bash + GNU utilities, 27

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

Input read from STDIN.

Answer 2

05AB1E, 8 6 bytes

b00¬:C

Explanation

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

Try it online

Saved 2 bytes thanks to Adnan

Answer 3

JavaScript (ES6), 41 bytes

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

Answer 4

Jellyfish, 20 bytes

p
d
# S
,1
*
\dbi
 2

Try it online!

Explanation

• i is input.
• b converts it to binary (list of digits)
• \d with arguments 2 and the digit list applies d (binary digits to number) to every length-2 substring of the digit list.
• * takes signum of the results: 00 goes to 0, everything else to 1.
• ,1 tacks a 1 to the end, so the last digit is not lost.
• # S selects from bi those digits which have a 1 on the list computed above: those that are not the left halves of 00.
• d converts back to number, and p prints the result.

Answer 5

Python 2, 36 bytes

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

A direct recursive implementation with no base conversion built-ins or string operations. Less golfed:

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

When n is a multiple of 4, it ends in two 0's in binary, so we cut one by floor-dividing by 2. Otherwise, we split n into (n%2) + 2*(n/2), leave the last binary digit n%2 alone, and recurse on the other digits n/2.

Answer 6

Bash (sed + bc), 60 55 43 bytes

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

edit:

1. changed sed -E 's/0+ to sed 's/00* and changed echo and pipe used to pass the value to bc with <<<.
2. Brilliant suggestion by @Digital Trauma!

example:

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

Answer 7

Perl 6,  31  27 bytes

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

Explanation:

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

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

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

Example:

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

Answer 8

MATL, 11 9 8 bytes

BFFOZtXB

This version works only in MATLAB since strrep in MATLAB can handle logical inputs. Here is a version that will work in Octave (9 bytes) (and thus the online interpreter) which explicitly casts the logical inputs to type double.

Try it online

Explanation

    % 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

Answer 9

Python 3, 55, 50 bytes.

Saved 4 bytes thanks to Sp3000.

Pretty straightforward solution.

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

Answer 10

Ruby, 35 31 bytes

-2 bytes thanks to @Doorknob

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

See it on repl.it: https://repl.it/CnnQ/2

Answer 11

Javascript (ES6), 40 bytes

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

Answer 12

Actually, 14 bytes

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

Try it online!

Explanation:

├`'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

Answer 13

Jelly, 13 7 bytes

6 bytes thanks to Zgarb for his algorithm.

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

Try it online!

Answer 14

PHP, 53 51 Bytes

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

Takes an argument from the console.

Thanks to:

@manatwork replace "0" with 0

Answer 15

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

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

Needs -p flag to run (I added -l flag to make it more readable, but it's not needed otherwise) :

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

Note much to say about the code : it converts the number into binary (sprintf"%b"), then replaces blocs of zeros by just one zero, and converts the result into decimal (oct"0b".).

Answer 16

C#, 112 91 bytes

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

-8 bytes thanks to TuukkaX

Answer 17

Java, 75

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

Test program:

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

Answer 18

PARI/GP, 54 43 bytes

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

Answer 19

C, 37 bytes

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

Answer 20

PowerShell v2+, 69 bytes

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

(feature-requestA shorter way to convert to/from binary in PowerShell)

Takes input $args[0], uses the .NET built-in [convert]::ToString(int,base) to convert the input integer into a binary base string. That's filtered through the -replace to strip out any runs of one-or-more-zeros to just 0. That resultant string is sent back through the other direction via [convert]::ToInt32(string,base) to turn the binary back into an integer. That integer is left on the pipeline and output is implicit.

Test Cases

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

Answer 21

Reference Implementation in S.I.L.O.S "only" 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

Here is the reference implementation fully ungolfed. As a bonus feature it outputs the steps needed to come to an answer.

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

By request the transpilation has been deleted. Feel free to view the edit history to recover it, otherwise go to this repo for an interpreter.

Sample output for 65000

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

Answer 22

Pyth, 12

i:.BQ"0+"\02

Online.

  .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

Answer 23

Retina, 30 bytes

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

Try it online!

And here I thought Retina would be amongst the first answers...

Answer 24

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 less thanks to @RohanJhunjhunwala. I prefer to keep it as a fully functioning program with main and the like. However, of course it can be golfed more otherwise.
• 5 bytes less thanks to @LeakyNun's suggestions.

Answer 25

Dyalog APL, 19 bytes

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

TryAPL online!

This function is really an "atop" of two functions, the first function is:

2∘⊥⍣¯1 the inverse of binary-to-decimal conversion, i.e. binary-from-decimal conversion
 two 2 is bound ∘ to -to-decimal ⊥
 repeat the operation ⍣ negative one time ¯1 (i.e. once, but inverted)

In the second function, the above's binary result is represented by ⍵:

{2⊥⍵/⍨~0 0⍷⍵}
 0 0⍷⍵ Boolean for where {0, 0} begins in ⍵
 ~ Boolean negation, so now we have ᴛʀᴜᴇ everywhere but at non-first zeros in zero-runs
 ⍵/⍨ use that to filter ⍵, so this removes our unwanted zeros
 2⊥ convert binary-to-decimal

Answer 26

TSQL, 143 bytes

Not using build ins to convert from and to binary.

Golfed:

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

Fiddle

Answer 27

CJam, 16

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

Try it online

It's quite long due to lack of regex.

Explanation:

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

Answer 28

Java, 64 bytes

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

Test Program

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
}

Answer 29

CJam, 23 bytes

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

Try it online!

Explanation

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

Answer 30

Ruby, 37 35 bytes

Saved two bytes thanks to manatwork.

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

The naive approach. (: