Temukan nomor biner 1-sparse berikutnya

27

Bilangan bulat positif N adalah K- sparse jika setidaknya ada K 0 antara dua 1 berturut-turut dalam representasi binernya.

Jadi, angka 1010101 adalah 1-jarang sedangkan 101101 tidak.

Tugas Anda adalah menemukan nomor 1-sparse berikutnya untuk nomor input yang diberikan. Misalnya, jika inputnya 12 ( 0b1100) output harus 16 ( 0b10000) dan jika inputnya 18 ( 0b10010) outputnya harus 20 ( 0b10100).

Program atau fungsi terkecil (dalam byte) menang! Celah standar tidak diijinkan.

articuno
sumber
"Berikutnya" seperti dalam "tertinggi berikutnya" atau seperti "dengan perbedaan paling tidak absolut"?
FUZxxl
"selanjutnya" seperti pada "tertinggi berikutnya".
articuno
Apa kisaran input yang perlu ditangani?
mbomb007
Saya akan menganggap angka negatif tidak perlu.
mbomb007
@articuno Bisakah kita membuat fungsi, atau apakah itu harus program penuh? Fungsinya cukup standar.
mbomb007

Jawaban:

13

Pyth, 9 byte

Upaya pertama saya di Pyth:

f!.&TyThQ

Coba di sini

               implicit: Q = input()            
f      hQ      find the first integer T >= Q + 1, 
               that satisfies the condition:
 !.&TyT        T & (T * 2) is 0
Trauma Digital
sumber
9

CJam, 14 11 byte

3 byte disimpan berkat DigitalTrauma.

l~{)___+&}g

Uji di sini.

Penjelasan

l~          "Read and eval input.";
  {      }g "Do while...";
   )_       "Increment and duplicate (call this x).";
     __+    "Get two more copies and add them to get x and 2x on the stack.";
        &   "Take their bitwise AND. This is non-zero is as long as x's base-2
             representation contains '11'.";

Ini meninggalkan nomor terakhir pada tumpukan yang dicetak secara otomatis di akhir program.

Martin Ender
sumber
8

Python 2, 44 byte

Ini adalah program python lengkap yang bertuliskan n, dan mencetak jawabannya. Saya pikir itu cukup baik dalam sub-kompetisi keterbacaan.

n=input()+1
while'11'in bin(n):n+=1
print n

Hasil tes:

$ echo 12 | python soln.py 
16
$ echo 18 | python soln.py 
20
Ksatria Logika
sumber
6

Pyth, 12 11 byte

f!}`11.BThQ

Cobalah secara online: Pyth Compiler / Executor .

               implicit: Q = input()            
f        hQ    find the first integer T >= Q + 1, 
               that satisfies the condition:
 !}`11.BT         "11" is not in the binary representation of T
Jakube
sumber
1
Anda dapat menyimpan karakter dengan mengubahnya "11"menjadi `11.
orlp
@ Atau Terima kasih, seharusnya memperhatikan ini.
Jakube
5

Mathematica, 41 30 byte

Disimpan 11 byte berkat Martin Büttner.

#+1//.i_/;BitAnd[i,2i]>0:>i+1&
alephalpha
sumber
3
Bisakah Anda menambahkan deskripsi?
mbomb007
4

Perl, 31

#!perl -p
sprintf("%b",++$_)=~/11/&&redo

Atau dari baris perintah:

 perl -pe'sprintf("%b",++$_)=~/11/&&redo' <<<"18"
nutki
sumber
4

APL, 18 byte

1∘+⍣{~∨/2∧/⍺⊤⍨⍺⍴2}

Ini mengevaluasi ke fungsi monadik. Coba di sini. Pemakaian:

   1∘+⍣{~∨/2∧/⍺⊤⍨⍺⍴2} 12
16

Penjelasan

1∘+                    ⍝ Increment the input ⍺
   ⍣{            }     ⍝ until
     ~∨/               ⍝ none of
        2∧/            ⍝ the adjacent coordinates contain 1 1 in
           ⍺⊤⍨⍺⍴2      ⍝ the length-⍺ binary representation of ⍺.
Zgarb
sumber
4

J, 20 karakter

Kata kerja monadik. Tetap mematuhi aturan.

(+1 1+./@E.#:)^:_@>:

Penjelasan

Pertama, ini adalah kata kerja dengan spasi dan kemudian sedikit kurang golf:

(+ 1 1 +./@E. #:)^:_@>:
[: (] + [: +./ 1 1 E. #:)^:_ >:

Baca baca:

    ]                             The argument
      +                           plus
        [: +./                    the or-reduction of
               1 1 E.             the 1 1 interval membership in
                      #:          the base-2 representation of the argument,
[: (                    )^:_      that to the power limit of
                             >:   the incremented argument

Argumen plus atau-reduksi 1 1keanggotaan interval dalam representasi basis-2 argumen, bahwa untuk batas daya diterapkan pada argumen yang bertambah.

Saya pada dasarnya menghitung jika 1 1terjadi dalam representasi basis-2 dari input. Jika ya, saya menambah input. Ini diletakkan di bawah batas daya, yang berarti diterapkan hingga hasilnya tidak berubah lagi.

FUZxxl
sumber
Algoritma yang bagus! Ini memiliki panjang yang sama di APL: {⍵+∨/2∧/⍵⊤⍨⍵⍴2}⍣=.
Zgarb
@randomra Ah, begitu.
FUZxxl
4

Javascript, 25 19

Menggunakan fakta bahwa, untuk bilangan biner 1-jarang, x&2*x == 0:

f=x=>x++&2*x?f(x):x
Nick
sumber
3

JavaScript (ES6), 39 43

Tanpa regexp, tanpa string, rekursif:

R=(n,x=3)=>x%4>2?R(++n,n):x?R(n,x>>1):n

Versi berulang:

F=n=>{for(x=3;x%4>2?x=++n:x>>=1;);return n}

Ini sangat sederhana, hanya menggunakan shift kanan untuk menemukan urutan 11. Ketika saya menemukannya, lewati ke nomor berikutnya. Versi rekursif langsung berasal dari versi berulang.

Tidak terseret dan lebih jelas. Untuk bermain golf, bagian tersulit adalah menggabungkan loop bagian dalam dan bagian luar (harus init x ke 3 di awal)

F = n=>{
  do {
    ++n; // next number
    for(x = n; x != 0; x >>= 1) {
      // loop to find 11 in any position
      if ((x & 3) == 3) { // least 2 bits == 11
        break;
      }
    }
  } while (x != 0) // if 11 was found,early exit from inner loop and x != 0
  return n
}
edc65
sumber
Ini %4>2terlihat seperti sihir dari Number Theory, bisakah kamu jelaskan || berikan tautan?
Yakub
@ Jacob (x% 4> 2) sederhananya ((x & 3) == 3), tetapi dengan operator yang diutamakan adalah JS Anda menghindari 2 tanda kurung
edc65
Sederhana dari yang saya kira. Sekarang dengan versi yang tidak diserang jelas. Terima kasih!
Yakub
3

Python 2, 37 byte

f=input()+1
while f&2*f:f+=1
print f

Digunakan logika x & 2*x == 0untuk angka 1-jarang.
Terima kasih kepada @Nick dan @CarpetPython.

ShinMigami13
sumber
Mengapa downvote? Ini berfungsi dengan baik, dan golf juga.
ETHproductions
Selamat datang di PPCG, btw, dan jawaban pertama yang bagus! Saya mendorong Anda untuk terus menjawab tantangan di situs :-)
ETHproductions
2

JavaScript, 75 66 62 byte

Terima kasih kepada Martin Büttner karena telah menghemat 9 byte dan Pietu1998 untuk 4 byte!

function n(a){for(a++;/11/.test(a.toString(2));a++);return a;}

Cara kerjanya: menjalankan forloop mulai dari a + 1selama jumlah saat ini tidak 1-jarang, dan jika ya, loop terputus dan mengembalikan nomor saat ini. Untuk memeriksa apakah angka 1-jarang, itu mengubahnya menjadi biner dan memeriksa apakah tidak mengandung 11.

Hapus kode golf:

function nextOneSparseNumber(num) {
    for (num++; /11/.test(num.toString(2)); num++);
    return num;
}
ProgramFOX
sumber
2

Julia, 40 byte

n->(while contains(bin(n+=1),"11")end;n)

Ini menciptakan fungsi anonim yang menerima integer tunggal sebagai input dan mengembalikan integer 1-sparse tertinggi berikutnya. Untuk menyebutnya, berikan nama, misalnya f=n->..., dan lakukan f(12).

Penjelasan + tidak dikumpulkan:

function f(n)

    # While the string representation of n+1 in binary contains "11",
    # increment n. Once it doesn't, we've got the answer!

    while contains(bin(n += 1), "11")
    end

    return(n)
end

Contoh:

julia> f(12)
16

julia> f(16)
20

Saran dan / atau pertanyaan diterima seperti biasa!

Alex A.
sumber
2

> <> (Ikan) , 31 + 3 = 34 byte

1+:>:  4%:3(?v~~
;n~^?-1:,2-%2<

Pemakaian:

>python fish.py onesparse.fish -v 12
16

3 byte ditambahkan untuk -vbendera.

randomra
sumber
1

JavaScript (ECMAScript 6), 40

Dengan rekursi:

g=x=>/11/.test((++x).toString(2))?g(x):x

JavaScript, 56

Sama tanpa fungsi panah.

function f(x){return/11/.test((++x).toString(2))?f(x):x}
nutki
sumber
1

Scala, 65 byte

(n:Int)=>{var m=n+1;while(m.toBinaryString.contains("11"))m+=1;m}

(jika fungsi bernama diperlukan, solusi akan menjadi 69 byte)

Yakub
sumber
1

Python, 39 33 byte

Cobalah di sini: http://repl.it/gpu/2

Dalam bentuk lambda (terima kasih kepada xnor untuk bermain golf):

f=lambda x:1+x&x/2and f(x+1)or-~x

Sintaks fungsi standar ternyata lebih pendek dari lambda untuk sekali!

def f(x):x+=1;return x*(x&x*2<1)or f(x)
mbomb007
sumber
Anda dapat mempersingkat satu lambda untuk 33 byte: f=lambda x:1+x&x/2and f(x+1)or-~x. Ternyata Anda menggeser sedikit ke kanan daripada ke kiri, Anda dapat menggunakan x/2alih-alih (x+1)/2karena perbedaan selalu dalam nol bit x+1. Namun spec meminta program.
xnor
Saya bertanya dan dia bilang kita bisa melakukan fungsi. Sebagian besar jawabannya sudah.
mbomb007
1

Java, 33 byte.

Menggunakan metode dalam jawaban ini

n->{for(;(n++&2*n)>0;);return n;}

TIO

Benjamin Urquhart
sumber
0

Ruby, 44

->(i){loop{i+=1;break if i.to_s(2)!~/11/};i}

Cukup mendasar. Lambda dengan infinite loop dan regexp untuk menguji representasi biner. Saya berharap itu loopmenghasilkan dan nomor indeks.

Maks
sumber
@ mbomb007 selesai. terima kasih atas tipnya.
Maks.
0

Matlab ( 77 74 bytes)

m=input('');for N=m+1:2*m
if ~any(regexp(dec2bin(N),'11'))
break
end
end
N

Catatan:

  • Itu sudah cukup untuk nomor tes m+1untuk 2*m, di mana madalah input.
  • ~any(x)adalah truejika xberisi semua nol atau jika xkosong
Luis Mendo
sumber
0

C (32 byte)

f(int x){return 2*++x&x?f(x):x;}

Implementasi rekursif dari algoritma yang sama dengan jawaban lainnya.

Ahli alkimia
sumber
0

Perl, 16 byte

Menggabungkan x&2*xdari berbagai jawaban (saya pikir yang pertama Nick ) dengan hasil nutki redo :

perl -pe'++$_&2*$_&&redo'

Diuji dalam Strawberry 5.26.

msh210
sumber
0

Jelly , 7 byte

‘&Ḥ¬Ɗ1#

Program lengkap yang menerima bilangan bulat tunggal, non-negatif yang mencetak bilangan bulat positif (sebagai tautan monadik ia menghasilkan daftar yang berisi bilangan bulat positif tunggal).

Cobalah online!

Bagaimana?

Mulai dari v=n+1, dan bertambah, dobel vuntuk menggeser setiap bit ke atas satu tempat dan sedikit bijaksana DAN dengan vdan kemudian lakukan logika TIDAK untuk menguji apakah v1-jarang hingga satu angka tersebut ditemukan.

‘&Ḥ¬Ɗ1# - Main Link: n   e.g. 12
‘       - increment           13
     1# - 1-find (start with that as v and increment until 1 match is found) using:
    Ɗ   -   last three links as a dyad:
  Ḥ     -   double v
 &      -   (v) bit-wise AND (with that)
   ¬    -   logical NOT (0->1 else 1)
        - implicit print (a single item list prints as just the item would)
Jonathan Allan
sumber
0

Stax , 5 byte

╦>ù╤x

Jalankan dan debug itu

Ini bekerja menggunakan prosedur ini. Input dimulai di atas tumpukan.

  • Tambahkan dan salin dua kali.
  • Membagi dua bagian atas tumpukan.
  • Bitwise - dan dua elemen teratas di stack.
  • Jika hasilnya benar (tidak nol) ulangi seluruh program.
rekursif
sumber