# "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

• From @Conor's comic blog: link – Rɪᴋᴇʀ Aug 16 '16 at 20:23
• OEIS A090078 might come in handy. – Adnan Aug 16 '16 at 20:24
• It is I who wrote the comic. <s>I also expect a 35% rep royalty</s> ;) – Conor O'Brien Aug 16 '16 at 20:25
• Would the downvoter please explain the issue? – Rohan Jhunjhunwala Aug 16 '16 at 20:40
• Why is 16 equal to 8? Shouldn't 16 be 10000? – eithed Aug 16 '16 at 22:56

## 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

• You can replace „00'0 by 00¬ :). – Adnan Aug 16 '16 at 20:39
• @Adnan Nice! Didn't think of that. – Emigna Aug 16 '16 at 20:41
• I don't even know why I explicitly pushed them as strings... – Emigna Aug 16 '16 at 20:44
• Yeah, it's a bit counterintuitive, but it works :). – Adnan Aug 16 '16 at 20:48
• This is looking like it will win :D, i'll give it a bit more time before accepting so that more people can participate. – Rohan Jhunjhunwala Aug 17 '16 at 11:59

# Bash + GNU utilities, 27

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


• Nice! I have never used dc :) – Master_ex Aug 16 '16 at 21:43
• The dc man page reads a lot like the docs for some golfing languages. – Jordan Aug 17 '16 at 0:32

n=>+0b${n.toString(2).replace(/0+/g,0)}  ## 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. ## 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. • Isn't n%2 redundant? – xsot Aug 18 '16 at 0:47 • @xsot Not sure what you mean. Doing |n gives wrong results. – xnor Aug 18 '16 at 0:57 • I mean you can replace the whole of (n%4>0)|n%2 with (n%4>0). – xsot Aug 18 '16 at 3:11 • @xsot The precedence goes as (f(n/2)<<(n%4>0)) | n%2. – xnor Aug 18 '16 at 3:22 • Ah, my bad then. I thought shifting has the lowest precedence. – xsot Aug 18 '16 at 3:25 # Bash (sed + bc), 6055 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

• sed + bc was my first thought too. echo "obase=2;$1"|bc|sed 's/00*/0/g;s/^/ibase=2;/'|bc is 2 bytes shorter – Riley Aug 16 '16 at 21:29 • Use pipes and escapes to your advantage: echo$[2#bc<<<obase=2\;$1|sed s/00\*/0/g]. But dc and tr make it way shorter. – Digital Trauma Aug 16 '16 at 21:34 • @DigitalTrauma: Thanks, that's great! @Riley: nice idea, it would be a bit shorter like that: bc<<<"obase=2;$1"|sed 's/00*/0/g;s/^/ibase=2;/'|bc – Master_ex Aug 16 '16 at 21:40
• if you use tr -s 0 instead of sed you can get down to 36 bytes – Riley Aug 16 '16 at 22:10
• @Riley: True, but Digital Trauma already uses it in the other bash answer so I prefer not to use it :) – Master_ex Aug 17 '16 at 6:57

# 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


# MATL, 119 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


# 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)))

• Can you keep the 0b and just eval instead? – Sp3000 Aug 16 '16 at 21:46
• @Sp3000 Certainly can! Thanks for the suggestion! – Morgan Thrapp Aug 17 '16 at 13:15
• Anonymous lambdas are allowed; you can shrink this to 48 bytes by using lambda x:eval(re.sub('0+','0',bin(x))) <insert newline here> import re – MilkyWay90 Apr 8 '19 at 0:51

## Javascript (ES6), 40 bytes

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

• I'm afraid this is a snippet. Unless the challenge description states otherwise, the solutions are expected to be either full programs or functions. – manatwork Aug 17 '16 at 9:48
• What require to be "full program" in Javascript if I don't want to use function? Please advise. – cychoi Aug 17 '16 at 9:57
• For example with Node.js: console.log(+('0b'+parseInt(process.argv[1]).toString(2).replace(/0+/g,0))). – manatwork Aug 17 '16 at 10:15
• Off topic. Your code block has the same problem as @Master_ex. Is it because some popular shell config scripts polluting the terminal? Or SE's fault? – cychoi Aug 17 '16 at 11:02
• The shortest fix would be to prepend N=> which would make it a valid function submission. – Martin Ender Aug 17 '16 at 11:36

## Actually, 14 bytes (non-competing)

├'0;;+(ÆY2@¿


Try it online!

This submission is non-competing because a bugfix for Æ was made after this challenge was posted.

Explanation:

├'0;;+(ÆY2@¿
'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

• Then post a competing version! – Leaky Nun Aug 17 '16 at 13:33

# 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

# Jelly, 13 7 bytes

6 bytes thanks to Zgarb for his algorithm.

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


Try it online!

<?=bindec(preg_replace("/0+/",0,decbin($argv[1])));  Takes an argument from the console. ## Thanks to: @manatwork replace "0" with 0 • Mostly "0" and 0 are handled in the same way. – manatwork Aug 17 '16 at 7:17 • @manatwork Thanks. That was a pretty obvious one I should have seen myself. – Jeroen Aug 17 '16 at 7:50 ## 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".). ## 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 • int f(int x){var a=Regex.Replace(Convert.ToString(x,2),"0+","0");return Convert.ToInt32(a,2);} - 94 bytes using regex. I've seen a lot of C# solutions not include System.Text.RegularExpressions so maybe it's allowed here too...? – Yytsi Aug 17 '16 at 10:59 • int f(int x){return Convert.ToInt32(Regex.Replace(Convert.ToString(x,2),"0+","0"),2);} 86 bytes. – Yytsi Aug 17 '16 at 11:04 • i dont know how you are counting bytes, i use this mothereff.in/byte-counter – downrep_nation Aug 17 '16 at 11:13 • I use that page too, but it wouldn't work, so I used a different page. You should also mention the required C# version. – Yytsi Aug 17 '16 at 11:17 • mothereff.in/byte-counter calculates 79 bytes for your current solution. I had to type the solution by hand, otherwise it would give me 91. – Yytsi Aug 17 '16 at 17:09 # 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)); } }  • Java 8 convert to lamda x->blah; for fewer bytes – Rohan Jhunjhunwala Aug 17 '16 at 12:27 • int f(Integer x){return x.parseInt(x.toString(x,2).replaceAll("0+","0"));} for a couple fewer bytes – Rohan Jhunjhunwala Aug 17 '16 at 12:29 • @RohanJhunjhunwala That's wrong, it needs to use base 2. As for the lambda, I feel that it's incomplete without the type specification. – aditsu quit because SE is EVIL Aug 17 '16 at 12:36 • oh ok, the other java answer uses the same technique – Rohan Jhunjhunwala Aug 17 '16 at 12:40 • codegolf.stackexchange.com/a/90085/46918 – Rohan Jhunjhunwala Aug 17 '16 at 12:41 # 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)


(A 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  # 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  • Reference implementations should be in the challenge body, not as answers, since they are ungolfed and thus not serious contenders. – user45941 Aug 16 '16 at 20:27 • Ok, I'll golf it. – Rohan Jhunjhunwala Aug 16 '16 at 20:28 • I didn't want to bloat up the challenge body with this @Mego – Rohan Jhunjhunwala Aug 16 '16 at 20:28 • @TimmyD one second I'm golfing it down now – Rohan Jhunjhunwala Aug 16 '16 at 20:44 • @Mego I have golfed it now – Rohan Jhunjhunwala Aug 16 '16 at 21:01 # 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  # Retina, 30 bytes .+$*1;
+(1+)\1
\$1;
1;
1
;+
0


Try it online!

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

• @randomra I'm asking the question OP for clarification – Leaky Nun Aug 17 '16 at 6:45
• Is Retina capable of binary to decimal conversion or binary to unary conversion? I'll except either one so as to not exclude Retina – Rohan Jhunjhunwala Aug 17 '16 at 11:53
• @RohanJhunjhunwala: Yes, it is – Business Cat Aug 19 '16 at 18:41
• Is it possible to make this convert to unary or decimal? Ideally I would like to see decimal, but I will accept either. – Rohan Jhunjhunwala Aug 19 '16 at 20:33

# Java, 152143 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.
• class A{public static void main(String[] a){Integer i;System.out.print(i.parseInt(i.toBinaryString(i.parseInt(a[0])).replaceAll("0+","0"),2));}} for 8 bytes of saving – Rohan Jhunjhunwala Aug 16 '16 at 21:38
• wrap it in a lambda expression for even more saving and remove class definitions, and your set. – Rohan Jhunjhunwala Aug 16 '16 at 21:38
• @RohanJhunjhunwala:Ah! The Integer i; part is simple and fantastic! – Master_ex Aug 16 '16 at 21:45
• It works, but may produce a warning (as opposed to an error) on most sane IDE's. The thing is, you can always call static methods from a non static context, but you can never call a non-static method from a static context. While using this technique is strongly strongly discouraged in production code, it is legal java. – Rohan Jhunjhunwala Aug 16 '16 at 22:11
• codegolf.stackexchange.com/questions/6671/… Is a good read to get more familiar with the lesser known (dare I say shadier) "features" of the java language. – Rohan Jhunjhunwala Aug 16 '16 at 22:13

# 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

# 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

• +1 for not using built ins. My S.I.L.O.S answer (reference implementation) does the same, but it got downvoted as people didn't think it was a serious competitor. Is the new line significant? – Rohan Jhunjhunwala Aug 17 '16 at 11:58
• @RohanJhunjhunwala the new line is not significant. I am counting the characters of the code after the input variable has been defined and assigned a value. – t-clausen.dk Aug 17 '16 at 12:11
• ok amkes sense - – Rohan Jhunjhunwala Aug 17 '16 at 12:14
• @RohanJhunjhunwala I think it is cool that you use an unconversial language to solve Codegolf questions. It does seem you have unnecessary code to add extra information - probably only in your ungolfed version though. You should always try to provide the shortest code possible, cutting corners and abusing language querks(within the scope of the question). If possible you should provide a fiddle, so muggles me can test it – t-clausen.dk Aug 17 '16 at 12:23
• The ungolfed version contains unnecessary code, but the golfed version contains no additional code. I can transpiler it into java if you want me to test it. – Rohan Jhunjhunwala Aug 17 '16 at 12:28

# 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


# 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
}


# 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


### Ruby, 37 35 bytes

Saved two bytes thanks to manatwork.

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


The naive approach. (:

• Regarding "0", see the 2nd point in sepp2k's tip. Regarding .to_i(2), where there is no ambiguity on where a parameter belongs, the parentheses are optional. – manatwork Aug 17 '16 at 16:39

# C, 37 bytes

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