21
\$\begingroup\$

"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

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

33 Answers 33

1
2
1
\$\begingroup\$

S.I.L.O.S, 120 bytes

readIO 
p = 1
lbla
m = i
m % 2
M = m
M - 1
M * F
M + 2
p * M
F = 1
F - m
A = p
A * m
r + A
i / 2
if i a
r / 2
printInt r

Try it online!

This is basically a state machine.

  • p for the current power
  • m for the result of the modulo by 2
  • M for the multiplier (to the power); if we are stuck at zeroes, the multiplier would be 1
  • F for the flag, to denote whether the zero is the first zero in the run.
  • r for the result, which is printed at the end.

The conversion between m, M and F is as follows:

  • m=0, F=0 -> F=1, M=2 (first zero, multiply by 2 anyway)
  • m=0, F=1 -> F=1, M=1 (not the first zero, multiply by 1)
  • m=1, F=0 -> F=0, M=2 (it is a one, multiply by 2, reset flag)
  • m=1, F=1 -> F=0, M=2 (it is a one, multiply by 2, reset flag)

Essentially we come up with the following formula:

  • M=((m-1)*F)+2
  • F=1-m
\$\endgroup\$
1
  • \$\begingroup\$ Wow, that golf. So much shorter than the reference \$\endgroup\$ – Rohan Jhunjhunwala Aug 27 '16 at 14:04
1
\$\begingroup\$

Oasis, 25 bytes (non-competing)

n2÷an»»n»4÷xx-p>*nn2÷x-+0

Try it online!

I have not failed my master. \o/

There are many missing features which must be built. For example, there is no conditionals, so the formula I am using would be f(n/2)*[1+(n%4>0)] + n%2.

Actually, there is no modulo either, so n%2 is implemented as n-(n/2*2) where / is integer division.

I did not mention n%4, because there is no > either. The > in the code means +1. So, n%4>0 is built from is_prime(((n+2)%4)+2) where the modulo is generated as above.

\$\endgroup\$
1
\$\begingroup\$

Husk, 11 10 9 bytes

ḋṁS↑o→Σgḋ

Try it online!

-1 byte from H.PWiz.

-1 byte from Jo King.

Alternative 9-byter

ḋṁ?uIΛ¬gḋ

Try it online!

Explanation

ḋṁ?uIΛ≠1gḋ
         ḋ get binary digits
        g  group equal runs of digits
 ṁ         map each group to the following, and concatenate:
  ?  Λ≠1   if all elements are not equal to 1
   u       uniquify the group
    I      else leave it as is
ḋ          convert back to base-10
\$\endgroup\$
0
1
2

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.