"Fit Numbers"

Sam hat eine "geniale" Idee für die Komprimierung! Kannst du helfen?

---

Hier ist ein Überblick über Sams Komprimierungsschema. Nehmen Sie zunächst eine Basis 10-Darstellung einer natürlichen Zahl, die streng kleiner als 2 ^ 16 ist, und schreiben Sie sie als Binärzeichenfolge ohne führende Nullen.

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

Ersetzen Sie nun eine Gruppe von einer oder mehreren Nullen durch eine einzelne Null. Dies liegt daran, dass die Zahl magerer geworden ist. Ihre Binärzeichenfolge sieht jetzt so aus.

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

Jetzt konvertieren Sie die Binärzeichenfolge zurück in eine Basis 10-Darstellung und geben sie in einem beliebigen akzeptablen Format aus. Hier sind Ihre Testfälle. Die erste Ganzzahl repräsentiert eine Eingabe und die letzte Ganzzahl repräsentiert eine Ausgabe. Beachten Sie, dass sich einige Zahlen nicht ändern und daher als "fit" bezeichnet werden können.

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 -> 11111111111111 -> 65535
65000 -> 1111110111101000 -> 11111101111010 -> 16250

---

Sie können jede Sprache verwenden, aber bitte beachten Sie, dass Sam Standardlücken hasst. Dies ist Codegolf, damit der Code so kurz wie möglich ist, um Platz für die "komprimierten" Zahlen zu schaffen.

---

Hinweis: Dies ist KEIN akzeptables Komprimierungsschema. Wenn Sie dies verwenden, werden Sie sofort gefeuert.

---

Citation-Needed: Ich kann dieses Konzept nicht würdigen. Das kommt von @Conor O‘Brien Blog hier sehen diese OEIS Passnummern. https://oeis.org/A090078

05AB1E , 8 6 Bytes

b00¬:C

Erläuterung

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

Probieren Sie es online aus

2 Bytes gespart dank Adnan

Bash + GNU-Dienstprogramme, 27

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

Eingang von STDIN gelesen.

JavaScript (ES6), 41 Byte

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

Qualle , 20 Bytes

p
d
# S
,1
*
\dbi
 2

Probieren Sie es online!

Erläuterung

• i eingegeben wird.
• b konvertiert es in binär (Liste der Ziffern)
• \dmit Argumenten 2und die Ziffernliste gilt d(Binärziffern zu Zahl) für jede Teilzeichenfolge der Länge 2 der Ziffernliste.
• * Nimmt ein Zeichen für die Ergebnisse: 00 geht auf 0, alles andere auf 1.
• ,1 setzt eine 1 ans Ende, damit die letzte Ziffer nicht verloren geht.
• # Swählt aus biden Ziffern, die eine 1 in der oben berechneten Liste haben: diejenigen, die nicht die linke Hälfte von 00 sind.
• dkonvertiert zurück in Zahl und pdruckt das Ergebnis.

Python 2, 36 Bytes

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

Eine direkte rekursive Implementierung ohne integrierte Basiskonvertierungs- oder Zeichenfolgenoperationen. Weniger golfen:

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

Wenn nes sich um ein Vielfaches von 4 handelt, endet es in zwei binären Nullen , sodass wir eine durch Teilen durch 2 abschneiden. Andernfalls teilen wir uns nauf (n%2) + 2*(n/2), lassen die letzte binäre Ziffer in n%2Ruhe und greifen auf die anderen Ziffern zurück n/2.

Bash (sed + bc), 60 55 43 Bytes

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

bearbeiten:

1. geändert sed -E 's/0+in sed 's/00*und geändert in Echo und Pipe, mit denen der Wert an bc übergeben wird <<<.
2. Genialer Vorschlag von @Digital Trauma!

Beispiel:

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

Erläuterung:

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

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

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

Beispiel:

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

Diese Version funktioniert nur in MATLAB, da strrepin MATLAB logische Eingaben verarbeitet werden können. Hier ist eine Version, die in Octave (9 Bytes) (und damit im Online-Interpreter) funktioniert und die logischen Eingaben explizit in type umsetzt double.

Probieren Sie es online aus

Erläuterung

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

4 Bytes gespart dank Sp3000.

Ziemlich einfache Lösung.

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

Javascript (ES6), 40 Byte

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

Eigentlich 14 Bytes (nicht konkurrierend)

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

Probieren Sie es online!

Diese Einsendung ist nicht konkurrierend, da ein Bugfix für gemacht Æwurde, nachdem diese Herausforderung veröffentlicht wurde.

Erläuterung:

├`'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 dank @Doorknob

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

Siehe es auf repl.it: https://repl.it/CnnQ/2

Jelly , 13 7 Bytes

6 Bytes danke an Zgarb für seinen Algorithmus .

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

Probieren Sie es online!

PHP, 53 51 Bytes

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

Übernimmt ein Argument von der Konsole.

Dank an:

@manatwork "0" durch 0 ersetzen

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

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

Needs -pflag to run (Ich habe -lflag hinzugefügt , um es lesbarer zu machen, aber es wird sonst nicht benötigt):

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

Zu dem Code gibt es viel zu sagen: Er konvertiert die Zahl in binary ( sprintf"%b"), ersetzt dann Blöcke mit Nullen durch nur eine Null und konvertiert das Ergebnis in 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 dank TuukkaX

Java, 75

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

Testprogramm:

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

Dyalog APL , 19 Bytes

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

TryAPL online!

Diese Funktion ist wirklich eine "Spitze" von zwei Funktionen, die erste Funktion ist:

2∘⊥⍣¯1das inverse von binary- zu -decimal Umwandlung, dh binary- aus -decimal Umwandlung
 zwei 2 gebunden ist ∘ an -bis-dezimalen ⊥
 Wiederholen der Operation ⍣ negativ Zeit ¯1(dh einmal, aber invertiert)

In der zweiten Funktion wird das obige binäre Ergebnis dargestellt durch ⍵:

{2⊥⍵/⍨~0 0⍷⍵}
 0 0⍷⍵Boolesch für den
 ~Punkt, an dem {0, 0} in in Boolescher Negation beginnt. Jetzt haben wir ᴛʀᴜᴇ überall, aber bei Nullen in
 ⍵/⍨Nullläufen wird dies zum Filtern von ⍵ verwendet. Dadurch werden unsere unerwünschten Nullen entfernt
 2⊥, die die Binärzahl in die Dezimalzahl umwandeln

TSQL, 143 Bytes

Keine Verwendung von Build-Ins zum Konvertieren von und nach Binär.

Golf gespielt:

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

Geige

CJam, 16

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

Probieren Sie es online aus

Es ist ziemlich lang, weil es an Regex mangelt.

Erläuterung:

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

Testprogramm

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

Probieren Sie es online!

Erläuterung

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

Zwei Bytes dank Handarbeit gespart.

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

Der naive Ansatz. (:

C 37 Bytes

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