"Nomor yang Cocok"

Sam punya ide "brilian" untuk kompresi! Dapatkah kamu menolong?

---

Berikut ini adalah ikhtisar skema kompresi Sam. Pertama, ambil representasi basis 10 dari bilangan asli mana pun yang benar-benar lebih kecil dari 2 ^ 16, dan tulislah sebagai string biner tanpa nol di depan.

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

Sekarang ganti grup mana pun dari satu nol atau lebih dengan nol tunggal. Ini karena jumlahnya semakin ramping. String biner Anda sekarang akan terlihat seperti ini.

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

Sekarang Anda mengonversi string biner kembali ke representasi basis 10, dan mengeluarkannya dalam format apa pun yang dapat diterima. Berikut ini adalah kasus pengujian Anda. Integer pertama mewakili input, dan integer terakhir mewakili output. Perhatikan bahwa beberapa angka tidak berubah, dan dengan demikian dapat disebut "cocok"

1 -> 1 -> 1 -> 1
9 -> 1001 -> 101 -> 5
15 -> 1111 -> 1111 -> 15
13 -> 1101 -> 1101 -> 13
16 -> 10.000 -> 10 -> 2
17 -> 10001 -> 101 -> 5
65535 -> 1111111111111111 -> 1111111111111111 -> 65535
65000 -> 1111110111101000 -> 11111101111010 -> 16250

---

Anda dapat menggunakan bahasa apa pun, tetapi harap dicatat bahwa Sam membenci celah standar. Ini adalah kode golf sehingga kode dapat sesingkat mungkin untuk memberikan ruang bagi angka "terkompresi".

---

Catatan: Ini BUKAN skema kompresi yang dapat diterima. Menggunakan ini akan segera membuat Anda dipecat.

---

Citation-Needed: Saya tidak menerima pujian untuk konsep ini. Ini berasal dari blog @Conor O 'Brien di sini lihat OEIS nomor yang pas ini. https://oeis.org/A090078

05AB1E , 8 6 byte

b00¬:C

Penjelasan

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

Cobalah online

Disimpan 2 byte berkat Adnan

Utilitas Bash + GNU, 27

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

Masukan dibaca dari STDIN.

JavaScript (ES6), 41 byte

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

Ubur-ubur , 20 byte

p
d
# S
,1
*
\dbi
 2

Cobalah online!

Penjelasan

• i adalah input.
• b mengubahnya menjadi biner (daftar angka)
• \ddengan argumen 2dan daftar digit berlaku d(binary digit ke nomor) untuk setiap panjang-2 substring dari daftar digit.
• * mengambil signum dari hasil: 00 pergi ke 0, yang lainnya ke 1.
• ,1 paku 1 sampai akhir, sehingga digit terakhir tidak hilang.
• # Smenyeleksi dari bimereka digit yang memiliki 1 pada daftar dihitung di atas: mereka yang tidak belahan kiri 00.
• dmengkonversi kembali ke angka, dan pmencetak hasilnya.

Python 2, 36 byte

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

Implementasi rekursif langsung tanpa built-in konversi atau operasi string. Kurang bermain golf:

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

Ketika nkelipatan dari 4, itu berakhir dengan dua 0 dalam biner, jadi kami memotong satu dengan pembagi-lantai dengan 2. Jika tidak, kita membaginya nmenjadi (n%2) + 2*(n/2), meninggalkan digit biner terakhir n%2sendirian, dan berulang pada digit lainnya n/2.

Bash (sed + bc), 60 55 43 byte

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

edit:

1. berubah sed -E 's/0+menjadi sed 's/00*dan mengubah gema dan pipa yang digunakan untuk meneruskan nilai ke bc dengan <<<.
2. Saran cemerlang oleh @Digital Trauma!

contoh:

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

Perl 6 ,  31  27 byte

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

Penjelasan:

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

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

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

Contoh:

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 byte

BFFOZtXB

Versi ini hanya berfungsi di MATLAB karena strrepdi MATLAB dapat menangani input logis. Berikut adalah versi yang akan bekerja dalam Oktaf (9 byte) (dan dengan demikian penerjemah online) yang secara eksplisit melemparkan input logis untuk diketik double.

Cobalah online

Penjelasan

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

Disimpan 4 byte berkat Sp3000.

Solusi yang sangat mudah.

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

Sebenarnya, 14 byte (tidak bersaing)

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

Cobalah online!

Kiriman ini tidak bersaing karena perbaikan bug Ædilakukan setelah tantangan ini diposting.

Penjelasan:

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

-2 byte terima kasih kepada @Doorknob

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

Lihat di repl.it: https://repl.it/CnnQ/2

Jelly , 13 7 byte

6 byte terima kasih kepada Zgarb untuk algoritme-nya .

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

Cobalah online!

PHP, 53 51 Bytes

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

Mengambil argumen dari konsol.

Terimakasih untuk:

@manatwork ganti "0" dengan 0

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

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

Membutuhkan -pflag untuk dijalankan (saya menambahkan -lflag agar lebih mudah dibaca, tetapi tidak diperlukan sebaliknya):

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

Perhatikan banyak hal tentang kode: ia mengubah angka menjadi biner ( sprintf"%b"), lalu mengganti blok nol dengan hanya satu nol, dan mengubah hasilnya menjadi desimal ( oct"0b".).

C #, 112 91 byte

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

-8 byte berkat TuukkaX

Jawa, 75

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

Program uji:

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 byte

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

PowerShell v2 +, 69 byte

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

( fitur-permintaan Cara yang lebih singkat untuk mengonversi ke / dari biner di PowerShell )

Mengambil input $args[0], menggunakan .NET built-in [convert]::ToString(int,base)untuk mengubah integer input menjadi string basis biner. Itu disaring melalui -replaceuntuk menghapus setiap berjalan satu atau lebih-nol hanya 0. String yang dihasilkan dikirim kembali melalui arah lain via[convert]::ToInt32(string,base) untuk mengubah kembali biner menjadi bilangan bulat. Bilangan bulat itu ditinggalkan di jalur pipa dan hasilnya tersirat.

Uji Kasus

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

Implementasi Referensi dalam SILOS "hanya" 417 byte

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

Berikut ini adalah implementasi referensi sepenuhnya ungolfed. Sebagai fitur bonus menghasilkan langkah-langkah yang diperlukan untuk mendapatkan jawaban.

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

Dengan permintaan, transpilasi telah dihapus. Jangan ragu untuk melihat riwayat edit untuk memulihkannya, jika tidak pergi ke repo ini untuk penerjemah.

Output sampel untuk 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

On line.

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

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

Cobalah online!

Dan di sini saya pikir Retina akan menjadi jawaban pertama ...

Java, 152 143 138 byte

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 byte lebih sedikit berkat @RohanJhunjhunwala. Saya lebih suka menyimpannya sebagai program yang berfungsi penuh dengan utama dan sejenisnya. Namun, tentu saja bisa bermain golf lebih sebaliknya.
• 5 byte lebih sedikit berkat saran dari LeakyNun.

Dyalog APL , 19 byte

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

TryAPL online!

Fungsi ini benar-benar merupakan "puncak" dari dua fungsi, fungsi pertama adalah:

2∘⊥⍣¯1yang terbalik dari binary- untuk konversi -decimal, yaitu binary- dari -decimal konversi
 dua 2 terikat ∘ untuk -untuk-desimal ⊥
 berulang operasi ⍣ negatif satu waktu ¯1(yaitu sekali, tapi terbalik)

Dalam fungsi kedua, hasil biner di atas diwakili oleh ⍵:

{2⊥⍵/⍨~0 0⍷⍵}
 0 0⍷⍵Boolean untuk tempat {0, 0} dimulai pada ⍵
 ~Boolean negasi, jadi sekarang kita memiliki ᴛʀᴜᴇ di mana-mana tetapi di nol pertama di nol-lari
 ⍵/⍨gunakan itu untuk menyaring ⍵, jadi ini menghapus nol yang tidak diinginkan kita
 2⊥mengkonversi biner-ke-desimal

TSQL, 143 byte

Tidak menggunakan build in untuk mengkonversi dari dan ke biner.

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

Tidak Disatukan:

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

Biola

CJam, 16

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

Cobalah online

Cukup lama karena kurangnya regex.

Penjelasan:

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 byte

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

Program Tes

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 byte

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

Cobalah online!

Penjelasan

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 byte

Disimpan dua byte berkat manatwork.

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

Pendekatan naif. (:

C, 37 byte

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