"Ajuster les chiffres"

Sam a une idée "géniale" pour la compression! Pouvez-vous m'aider?

---

Voici un aperçu du schéma de compression de Sam. Prenez d'abord une représentation en base 10 de tout nombre naturel strictement inférieur à 2 ^ 16, et écrivez-le sous la forme d'une chaîne binaire sans zéros non significatifs.

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

Remplacez maintenant tout groupe d'un ou plusieurs zéros par un seul zéro. En effet, le nombre est devenu plus maigre. Votre chaîne binaire ressemblera maintenant à ceci.

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

Maintenant, vous reconvertissez la chaîne binaire en une représentation de base 10, et la sortez dans n'importe quel format acceptable. Voici vos cas de test. Le premier entier représente une entrée et le dernier entier représente une sortie. Notez que certains nombres ne changent pas et peuvent donc être appelés "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 -> 111111111111111111 -> 65535
65000 -> 1111110111101000 -> 11111101111010 -> 16250

---

Vous pouvez utiliser n'importe quelle langue, mais veuillez noter que Sam déteste les failles standard. C'est le code golf donc le code peut être le plus court possible pour faire de la place aux numéros "compressés".

---

Remarque: Ce n'est PAS un schéma de compression acceptable. L'utiliser vous fera rapidement virer.

---

Citation-Needed: Je ne prends pas le crédit de ce concept. Cela vient du blog de @Conor O 'Brien ici voir cet OEIS de numéros d'ajustement. https://oeis.org/A090078

05AB1E , 8 6 octets

b00¬:C

Explication

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

Essayez-le en ligne

Enregistré 2 octets grâce à Adnan

Utilitaires Bash + GNU, 27

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

Entrée lue depuis STDIN.

JavaScript (ES6), 41 octets

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

Méduse , 20 octets

p
d
# S
,1
*
\dbi
 2

Essayez-le en ligne!

Explication

• i est entrée.
• b le convertit en binaire (liste de chiffres)
• \davec des arguments 2et la liste des chiffres s'applique d(chiffres binaires au nombre) à chaque sous-chaîne de longueur 2 de la liste des chiffres.
• * prend le signal des résultats: 00 passe à 0, tout le reste à 1.
• ,1 pointe un 1 jusqu'à la fin, de sorte que le dernier chiffre ne soit pas perdu.
• # Ssélectionne parmi biles chiffres qui ont un 1 sur la liste calculée ci-dessus: ceux qui ne sont pas les moitiés gauches de 00.
• dreconvertit en nombre et pimprime le résultat.

Python 2, 36 octets

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

Une implémentation récursive directe sans intégration de conversion de base ni opérations de chaîne. Moins golfé:

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

Quand nest un multiple de 4, il se termine par deux 0 en binaire, donc nous avons coupé un par étage de division par 2. Dans le cas contraire, nous nous sommes séparés nen (n%2) + 2*(n/2), laissez le dernier chiffre binaire n%2seul, et récursion sur les autres chiffres n/2.

Bash (sed + bc), 60 55 43 octets

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

Éditer:

1. changé sed -E 's/0+en sed 's/00*et changé echo et pipe utilisé pour passer la valeur à bc avec <<<.
2. Brillante suggestion de @Digital Trauma!

exemple:

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

Perl 6 ,  31  27 octets

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

Explication:

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

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

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

Exemple:

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 octets

BFFOZtXB

Cette version ne fonctionne que dans MATLAB car strrepdans MATLAB peut gérer les entrées logiques. Voici une version qui fonctionnera en octave (9 octets) (et donc l'interpréteur en ligne) qui convertit explicitement les entrées logiques en type double.

Essayez-le en ligne

Explication

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

4 octets enregistrés grâce au Sp3000.

Solution assez simple.

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

Javascript (ES6), 40 octets

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

En fait, 14 octets (non concurrents)

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

Essayez-le en ligne!

Cette soumission n'est pas en compétition car un correctif de bogue a Æété fait après la publication de ce défi.

Explication:

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

Rubis, 35 31 octets

-2 octets grâce à @Doorknob

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

Voir sur repl.it: https://repl.it/CnnQ/2

Gelée , 13 7 octets

6 octets merci à Zgarb pour son algorithme .

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

Essayez-le en ligne!

PHP, 53 51 octets

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

Prend un argument de la console.

Grâce à:

@manatwork remplacer "0" par 0

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

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

Nécessite un -pindicateur pour fonctionner (j'ai ajouté un -lindicateur pour le rendre plus lisible, mais ce n'est pas nécessaire autrement):

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

Notez beaucoup de choses à dire sur le code: il convertit le nombre en binaire ( sprintf"%b"), puis remplace les blocs de zéros par un seul zéro, et convertit le résultat en decimal ( oct"0b".).

C #, 112 91 octets

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

-8 octets grâce à TuukkaX

Java, 75

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

Programme de test:

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

PARI / GP , 54 43 octets

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

PowerShell v2 +, 69 octets

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

( fonctionnalité-demande Un moyen plus court de convertir vers / à partir de binaire dans PowerShell )

Prend l'entrée $args[0], utilise le .NET intégré [convert]::ToString(int,base)pour convertir l'entier d'entrée en une chaîne de base binaire. Cela est filtré à travers -replacepour éliminer toutes les séries d'un ou plusieurs zéros 0. Cette chaîne résultante est renvoyée dans l'autre sens via [convert]::ToInt32(string,base)pour transformer le binaire en entier. Cet entier est laissé sur le pipeline et la sortie est implicite.

Cas de test

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

Implémentation de référence dans SILOS "seulement" 417 octets

Golfé

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

Voici l'implémentation de référence totalement non golfée. En bonus, il affiche les étapes nécessaires pour parvenir à une réponse.

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

Sur demande, la transpilation a été supprimée. N'hésitez pas à consulter l'historique des modifications pour le récupérer, sinon rendez-vous sur ce dépôt pour un interprète.

Exemple de sortie pour 65000

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

Pyth, 12

i:.BQ"0+"\02

En ligne.

  .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

Rétine , 30 octets

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

Essayez-le en ligne!

Et là, je pensais que Retina serait parmi les premières réponses ...

Java, 152 143 138 octets

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 octets de moins grâce à @RohanJhunjhunwala. Je préfère le garder comme un programme pleinement fonctionnel avec principal et similaires. Cependant, bien sûr, il peut être joué plus autrement.
• 5 octets de moins grâce aux suggestions de @ LeakyNun.

Dyalog APL , 19 octets

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

TryAPL en ligne!

Cette fonction est vraiment un "sommet" de deux fonctions, la première fonction est:

2∘⊥⍣¯1l' inverse de la conversion binaire en décimal, c'est-à-dire que la conversion binaire de -décimal
 deux 2 est lié ∘ à -à-décimal ⊥
 répéter l'opération ⍣ négative une fois¯1 (c'est-à-dire une fois, mais inversée)

Dans la deuxième fonction, le résultat binaire ci-dessus est représenté par ⍵:

{2⊥⍵/⍨~0 0⍷⍵}
 0 0⍷⍵Booléen pour où {0, 0} commence dans ⍵ Négation
 ~booléenne, donc maintenant nous avons ᴛʀᴜᴇ partout, mais aux non-premiers zéros dans les exécutions nulles,
 ⍵/⍨utilisez-le pour filtrer ⍵, ce qui supprime nos zéros indésirables
 2⊥convertissant le binaire en décimal

TSQL, 143 octets

Ne pas utiliser de build ins pour convertir depuis et vers binaire.

Golfé:

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

Non golfé:

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

Violon

CJam, 16 ans

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

Essayez-le en ligne

C'est assez long en raison du manque de regex.

Explication:

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 octets

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

Programme de test

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 octets

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

Essayez-le en ligne!

Explication

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

Rubis, 37 35 octets

Sauvegardé deux octets grâce à la manœuvre.

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

L'approche naïve. (:

C, 37 octets

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