# "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 Aug 16, 2016 at 20:23
• OEIS A090078 might come in handy. Aug 16, 2016 at 20:24
• It is I who wrote the comic. <s>I also expect a 35% rep royalty</s> ;) Aug 16, 2016 at 20:25
• Would the downvoter please explain the issue? Aug 16, 2016 at 20:40
• Why is 16 equal to 8? Shouldn't 16 be 10000? Aug 16, 2016 at 22:56

# Bash + GNU utilities, 27

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


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

## 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¬ :). Aug 16, 2016 at 20:39
• @Adnan Nice! Didn't think of that. Aug 16, 2016 at 20:41
• I don't even know why I explicitly pushed them as strings... Aug 16, 2016 at 20:44
• Yeah, it's a bit counterintuitive, but it works :). Aug 16, 2016 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. Aug 17, 2016 at 11:59

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, 2016 at 0:47 • @xsot Not sure what you mean. Doing |n gives wrong results. – xnor Aug 18, 2016 at 0:57 • I mean you can replace the whole of (n%4>0)|n%2 with (n%4>0). – xsot Aug 18, 2016 at 3:11 • @xsot The precedence goes as (f(n/2)<<(n%4>0)) | n%2. – xnor Aug 18, 2016 at 3:22 • Ah, my bad then. I thought shifting has the lowest precedence. – xsot Aug 18, 2016 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 Aug 16, 2016 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. Aug 16, 2016 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 Aug 16, 2016 at 21:40
• if you use tr -s 0 instead of sed you can get down to 36 bytes Aug 16, 2016 at 22:10
• @Riley: True, but Digital Trauma already uses it in the other bash answer so I prefer not to use it :) Aug 17, 2016 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  (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? Aug 16, 2016 at 21:46
• @Sp3000 Certainly can! Thanks for the suggestion! Aug 17, 2016 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 Apr 8, 2019 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. Aug 17, 2016 at 9:48
• What require to be "full program" in Javascript if I don't want to use function? Please advise. Aug 17, 2016 at 9:57
• For example with Node.js: console.log(+('0b'+parseInt(process.argv).toString(2).replace(/0+/g,0))). Aug 17, 2016 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? Aug 17, 2016 at 11:02
• The shortest fix would be to prepend N=> which would make it a valid function submission. Aug 17, 2016 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! Aug 17, 2016 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)));  Takes an argument from the console. ## Thanks to: @manatwork replace "0" with 0 • Mostly "0" and 0 are handled in the same way. Aug 17, 2016 at 7:17 • @manatwork Thanks. That was a pretty obvious one I should have seen myself. Aug 17, 2016 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...? Aug 17, 2016 at 10:59 • int f(int x){return Convert.ToInt32(Regex.Replace(Convert.ToString(x,2),"0+","0"),2);} 86 bytes. Aug 17, 2016 at 11:04 • i dont know how you are counting bytes, i use this mothereff.in/byte-counter Aug 17, 2016 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. Aug 17, 2016 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. Aug 17, 2016 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 Aug 17, 2016 at 12:27 • int f(Integer x){return x.parseInt(x.toString(x,2).replaceAll("0+","0"));} for a couple fewer bytes Aug 17, 2016 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. Aug 17, 2016 at 12:36 • oh ok, the other java answer uses the same technique Aug 17, 2016 at 12:40 • codegolf.stackexchange.com/a/90085/46918 Aug 17, 2016 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,2)-replace'0+',0),2)


(A shorter way to convert to/from binary in PowerShell)

Takes input $args, 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, 2016 at 20:27 • Ok, I'll golf it. Aug 16, 2016 at 20:28 • I didn't want to bloat up the challenge body with this @Mego Aug 16, 2016 at 20:28 • @TimmyD one second I'm golfing it down now Aug 16, 2016 at 20:44 • @Mego I have golfed it now Aug 16, 2016 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 Aug 17, 2016 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 Aug 17, 2016 at 11:53
• @RohanJhunjhunwala: Yes, it is Aug 19, 2016 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. Aug 19, 2016 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),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)).replaceAll("0+","0"),2));}} for 8 bytes of saving Aug 16, 2016 at 21:38
• wrap it in a lambda expression for even more saving and remove class definitions, and your set. Aug 16, 2016 at 21:38
• @RohanJhunjhunwala:Ah! The Integer i; part is simple and fantastic! Aug 16, 2016 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. Aug 16, 2016 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. Aug 16, 2016 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? Aug 17, 2016 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. Aug 17, 2016 at 12:11
• ok amkes sense - Aug 17, 2016 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 Aug 17, 2016 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. Aug 17, 2016 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 , dropping empty pieces; only chunks of 1s are left
0a*    join by 
);     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. Aug 17, 2016 at 16:39

# C, 37 bytes

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