Beralih beberapa bit dan dapatkan kotak

26

Dengan bilangan bulat , Anda harus menemukan jumlah bit minimum yang perlu dibalik dalam untuk mengubahnya menjadi angka kuadrat . Anda hanya diperbolehkan membalikkan bit di bawah yang paling signifikan .NN>3N

Contohnya

  • 2 2 0N=4 sudah merupakan angka kuadrat ( ), sehingga output yang diharapkan adalah .220
  • 11000 1100 1 25 = 5 2 1N=24 dapat diubah menjadi angka kuadrat dengan membalik 1 bit: ( ), sehingga output yang diharapkan adalah .110001100125=521
  • 23 20 18 30 10110 10 0 0 0 16 = 4 2 2N=22 tidak dapat diubah menjadi angka kuadrat dengan membalikkan bit tunggal (hasil yang mungkin adalah , , dan ) tetapi dapat dilakukan dengan membalik 2 bit: ( ), jadi output yang diharapkan adalah .23201830101101000016=422

Aturan

  • Tidak apa-apa jika kode Anda terlalu lambat atau melempar kesalahan untuk kasus uji yang lebih besar, tetapi setidaknya mendukung dalam waktu kurang dari 1 menit.3<N<10000
  • Ini !

Uji kasus

    Input | Output
----------+--------
        4 | 0
       22 | 2
       24 | 1
       30 | 3
       94 | 4
      831 | 5
      832 | 1
     1055 | 4
     6495 | 6
     9999 | 4
    40063 | 6
   247614 | 7        (smallest N for which the answer is 7)
  1049310 | 7        (clear them all!)
  7361278 | 8        (smallest N for which the answer is 8)
100048606 | 8        (a bigger "8")

Atau dalam format salin / tempel ramah:

[4,22,24,30,94,831,832,1055,6495,9999,40063,247614,1049310,7361278,100048606]
Arnauld
sumber
Hampir setengah dari jawaban tidak dieksekusi 100048606pada TIO, apakah itu masalah?
Magic Octopus Urn
@ MagicOctopusUrn Terima kasih, saya telah memperbarui aturan untuk membuatnya lebih jelas bahwa mendukung adalah opsional. N10000
Arnauld
1
Ini akan menjadi pertanyaan kode tercepat yang bagus juga (tanpa batasan ukuran input)
qwr
@ qr Ya, mungkin. Atau jika Anda ingin menjadi hardcore: diberikan , cari terkecil sehingga . N f ( N ) = kkNf(N)=k
Arnauld

Jawaban:

14

Ruby, 74 byte

->n{(1..n).map{|x|a=(n^x*x).to_s 2;a.size>Math.log2(n)?n:a.count(?1)}.min}

Cobalah online!

Ini hanya menghasilkan urutan (yang jauh lebih dari cukup), XOR dengan , dan kemudian mengambil jumlah 1s dalam binernya representasi jika jumlah bit kurang dari atau sama dengan , atau sebaliknya. Kemudian dibutuhkan jumlah bit minimum yang dibalik. Mengembalikan sebagai ganti jumlah bit yang dibalik ketika bit tertinggi yang dibalik lebih besar dari mencegah kasus-kasus ini dipilih sebagai minimum, karena akan selalu lebih besar dari jumlah bit yang dimilikinya. n log 2 nnn log 2 nn[12,22,,n2]nlog2nnnlog2nn

Terima kasih kepada Piccolo untuk menghemat satu byte.

Gagang pintu
sumber
Anda dapat menyimpan byte dengan menggunakan (n^x*x).to_s 2;...bukannya(n^x*x).to_s(2);...
Piccolo
@Piccolo Tidak percaya saya melewatkan itu, terima kasih!
Gagang Pintu
6

Jelly , 12 byte

²,BẈEðƇ²^B§Ṃ

Cobalah online!

Lihatlah suite tes!

Tautan monadik. Harus golf. Tapi saya terlalu bodoh untuk memikirkan cara untuk menyingkirkan ³. Ini jawaban pertama saya di mana saya berhasil menggunakan penyaringan / pemetaan / perulangan secara umum bersama dengan rantai diad \ o /

Penjelasan

², BẈEðƇ² ^ B§Ṃ - Program lengkap / tautan Monadik. Sebut argumen N.
     ðƇ - Filter-keep [1 ... N] dengan rantai diad berikut:
², BẈE - Kuadrat dari item saat ini memiliki panjang bit yang sama dengan N.
² - Kotak.
 , - Pasangkan dengan N.
  B - Konversikan keduanya menjadi biner.
   Ẉ - Ambil panjangnya.
    E - Dan periksa apakah mereka menyamakan.
       ² ^ - Setelah memfilter, beri persegi hasil dan XOR dengan N.
         B - Representasi biner masing-masing.
          § - Jumlah masing-masing. Menghitung jumlah 1 dalam biner.
           Ṃ - Minimum.
Tuan Xcoder
sumber
5

Sekam , 20 byte

▼mΣfo¬→S↑(Mo¤ż≠↔ḋİ□ḋ

Cobalah online!

Penjelasan

▼mΣf(¬→)S↑(M(¤ż≠↔ḋ)İ□ḋ) -- example input n=4
        S↑(           ) -- take n from n applied to (..)
                     ḋ  -- | convert to binary: [1,0,0]
                   İ□   -- | squares: [1,4,9,16,...]
           M(     )     -- | map with argument ([1,0,0]; example with 1)
                 ḋ      -- | | convert to binary: [1]
             ¤  ↔       -- | | reverse both arguments of: [1] [0,0,1]
              ż≠        -- | | | zip with inequality (absolute difference) keeping longer elements: [1,0,1]
                        -- | : [[1,0,1],[0,0,0],[1,0,1,1],[0,0,1,0,1],[1,0,1,1,1],....
                        -- : [[1,0,1],[0,0,0],[1,0,1,1],[0,0,1,0,1]]
    f(  )               -- filter elements where
       →                -- | last element
      ¬                 -- | is zero
                        -- : [[0,0,0]]
 mΣ                     -- sum each: [0]
▼                       -- minimum: 0
ბიმო
sumber
▼mΣfo¬←ṠMz≠ȯfo£İ□ḋπŀ2Lḋmenghemat 2 byte. RIP Anda skor kuadrat sempurna.
Tn. Xcoder
@ Mr.Xcoder: Malu tentang skor .. Tapi saya menyingkirkan lebih banyak lagi, sekarang menargetkan 16; P
ბიმო
5

Perl 6 , 65 byte

{min map {+$^a.base(2).comb(~1) if sqrt($a+^$_)!~~/\./},^2**.msb}

Cobalah online!

Saya merasa sedikit kotor untuk menguji kuadrat sempurna dengan mencari periode dalam representasi string dari akar kuadrat angka, tapi ... apa pun untuk memotong byte.

Sean
sumber
4

05AB1E , 20 15 byte

Lnʒ‚b€gË}^b€SOß

-5 byte terima kasih kepada @ Mr.Xcoder menggunakan port jawaban Jelly-nya .

Cobalah secara online atau verifikasi semua kasus uji (tiga kasus uji terbesar dihapus karena habis waktu setelah 60 detik; masih membutuhkan waktu sekitar 35-45 detik dengan kasus uji lainnya).

Penjelasan:

L            # Create a list in the range [1, input]
             #  i.e. 22 → [0,1,2,...,20,21,22]
 n           # Take the square of each
             #  i.e. [0,1,2,...,20,21,22] → [0,1,4,...,400,441,484]
  ʒ     }    # Filter this list by:
   ,         #  Pair the current value with the input
             #   i.e. 0 and 22 → [0,22]
             #   i.e. 25 and 22 → [25,22]
    b        #  Convert both to binary strings
             #   i.e. [0,22] → ['0','10110']
             #   i.e. [25,22] →  ['10000','11001']
     g      #  Take the length of both
             #   i.e. ['0','10110'] → [1,5]
             #   ['10000','11001'] → [5,5]
       Ë     #  Check if both are equal
             #   i.e. [1,5] → 0 (falsey)
             #   i.e. [5,5] → 1 (truthy)
^            # After we've filtered, Bitwise-XOR each with the input
             #  i.e. [16,25] and 22 → [6,15]
 b           # Convert each to a binary string again
             #  i.e. [6,15] → ['110','1111']
  S         # Change the binary strings to a list of digits
             #  i.e. ['110','1111'] → [['1','1','0'],['1','1','1','1']]
    O        # Take the sum of each
             #  i.e. [['1','1','0'],['1','1','1','1']] → [2,4]
ß            # And then take the lowest value in the list
             #  i.e. [2,4] → 2
Kevin Cruijssen
sumber
1
Oke kemudian, valid 15-byter: Lnʒ‚b€gË}^b€SOß. Sayangnya, itu merusak test suite Anda
Tn. Xcoder
1
@ Mr.Xcoder Terima kasih! Dan test suite saya hampir selalu rusak setelah saya bermain golf .. XD Tapi sekarang sudah diperbaiki juga.
Kevin Cruijssen
Saya kira saya tidak pandai menulis suite tes di 05AB1E ¯ \ _ (ツ) _ / ¯, senang Anda telah memperbaikinya :)
Tn. Xcoder
3

Java (JDK 10) , 110 byte

n->{int i=1,s=1,b,m=99,h=n.highestOneBit(n);for(;s<h*2;s=++i*i)m=(s^n)<h&&(b=n.bitCount(s^n))<m?b:m;return m;}

Cobalah online!

Olivier Grégoire
sumber
1
Anda dapat menyimpan 1 byte dengan menggunakan bitwise dan &bukannya logis dan&&
kirbyquerby
3

Gaia , 18 byte

Dekat-port jawaban Jelly saya .

s¦⟪,b¦l¦y⟫⁇⟪^bΣ⟫¦⌋

Cobalah online!

Kerusakan

s¦⟪, b¦l¦y⟫⁇ ⟪^ bΣ⟫¦⌋ - Program lengkap. Mari kita panggil input N.
s¦ - Siku setiap integer dalam kisaran [1 ... N].
  ⟪⟫⁇ - Pilih yang memenuhi syarat tertentu, saat dijalankan
                     blok diad. Menggunakan blok diad menghemat satu byte karena
                     input, N, secara implisit digunakan sebagai argumen lain.
   , - Pasangkan elemen saat ini dan N dalam daftar.
    b¦ - Mengubahnya menjadi biner.
      l¦ - Dapatkan panjangnya.
        y - Kemudian periksa apakah keduanya sama.
           ⟪⟫¦ - Jalankan semua bilangan bulat yang valid melalui blok diad.
            ^ - masing-masing XOR dengan N.
             bΣ - Konversi ke biner dan jumlah (hitung angka 1 dalam biner)
                 ⌋ - Minimum.
Tuan Xcoder
sumber
2

Brachylog , 56 41 byte

Itu tidak akan memecahkan catatan panjang tetapi saya pikir saya akan tetap mempostingnya

⟨⟨{⟦^₂ᵐḃᵐ}{h∋Q.l~t?∧}ᶠ{ḃl}⟩zḃᶠ⟩{z{∋≠}ᶜ}ᵐ⌋

Cobalah online!

Kroppeb
sumber
Baru sadar bahwa ritsleting adalah suatu hal. Saya akan mempersingkat setelah saya kembali dari makan malam
Kroppeb
1
@Arnauld Ya, masalah utama adalah bahwa untuk setiap i dalam kisaran (0, n + 1) saya menghitung ulang kisaran, kuadratkan, dan menjadi biner. Menempatkan ini di luar membutuhkan beberapa byte lagi tapi jauh lebih cepat sekarang
Kroppeb
2

perakitan x86-64, 37 byte

Bytecode:

53 89 fb 89 f9 0f bd f7 89 c8 f7 e0 70 12 0f bd
d0 39 f2 75 0b 31 f8 f3 0f b8 c0 39 d8 0f 42 d8
e2 e6 93 5b c3

Baik, ini menghitung bahkan contoh tertinggi dalam waktu kurang dari satu detik.

Inti dari algoritma ini adalah xor / popcount seperti biasa.

    push %rbx
    /* we use ebx as our global accumulator, to see what the lowest bit
     * difference is */
    /* it needs to be initialized to something big enough, fortunately the
     * answer will always be less than the initial argument */
    mov %edi,%ebx
    mov %edi,%ecx
    bsr %edi,%esi
.L1:
    mov %ecx,%eax
    mul %eax
    jo cont     /* this square doesn't even fit into eax */
    bsr %eax,%edx
    cmp %esi,%edx
    jnz cont    /* can't invert bits higher than esi */
    xor %edi,%eax
    popcnt %eax,%eax
    cmp %ebx,%eax   /* if eax < ebx */
    cmovb %eax,%ebx
cont:
    loop .L1
    xchg %ebx,%eax
    pop %rbx
    retq
ObecessiousNewt
sumber
Sarankan mengganti setidaknya salah satu dari Anda movdenganxchg
ceilingcat
Sejauh yang saya tahu hanya ada satu yang akan menghemat byte ( mov %ecx,%eax) dan saya tidak bisa membiarkan% ecx mati di sana.
ObhiriiousNewt
1

Bahasa Wolfram (Mathematica) , 67 byte

Min@DigitCount[l=BitLength;#~BitXor~Pick[s=Range@#^2,l@s,l@#],2,1]&

Cobalah online!

{1,2,,n}BitLengthPickBitXorMinDigitCount1

JungHwan Min
sumber
1

Arang , 31 byte

NθI⌊EΦEθ↨×ιι²⁼LιL↨θ²ΣE↨責⁼λ§ιμ

Cobalah online! Tautan adalah untuk mengucapkan versi kode. Penjelasan:

Nθ                              Input N
       θ                        N
      E                         Map over implicit range
          ιι                    Current value (twice)
         ×                      Multiply
        ↨   ²                   Convert to base 2
     Φ                          Filter over result
               ι                Current value
                  θ             N
                 ↨ ²            Convert to base 2
              L L               Length
             ⁼                  Equals
    E                           Map over result
                       θ        N
                      ↨ ²       Convert to base 2
                     E          Map over digits
                           λ    Current base 2 digit of N
                             ι  Current base 2 value
                              μ Inner index
                            §   Get digit of value
                          ⁼     Equals
                         ¬      Not (i.e. XOR)
                    Σ           Take the sum
   ⌊                            Take the minimum
  I                             Cast to string
                                Implicitly print
Neil
sumber
1

Jelly , 20 byte

BL’Ø.ṗŻ€©Ḅ^⁸Ʋa§ɼ¹ƇṂ

Cobalah online!

Erik the Outgolfer
sumber
1

Japt -g , 20 byte

Ini bisa di mainkan.

op f_¤Ê¥¢lî^U ¤¬xÃn

Cobalah online!

Luis felipe De jesus Munoz
sumber
1

C (gcc) ,  93  91 byte

g(n){n=n?n%2+g(n/2):0;}m;i;d;f(n){m=99;for(i=0;++i*i<2*n;m=g(d=i*i^n)<m&d<n/2?g(d):m);n=m;}

Cobalah online!


Sunting: Saya pikir solusi asli saya ( Coba online! ) Tidak valid, karena salah satu variabel m,, global untuk menyimpan beberapa byte dengan tidak menentukan jenis, diinisialisasi di luar f(n)dan oleh karena itu harus diinisialisasi ulang di antara panggilan


Kode tidak dikomentari dan dikomentari:

g(n){n=n?n%2+g(n/2):0;} // returns the number of bits equal to 1 in n
m; //miminum hamming distance between n and a square
i; //counter to browse squares
d; //bitwise difference between n and a square
f(n){m=99; //initialize m to 99 > size of int (in bits)
    for(
        i=0;
        ++i*i<2*n; //get the next square number, stop if it's greater than 2*n
        g(d=i*i^n)<m&&d<n/2&&(m=g(d)) //calculate d and hamming distance
//      ^~~~~~~~~~~^ if the hamming distance is less than the minimum
//                    ^~~~^ and the most significant bit of n did not change (the most significant bit contains at least half the value)
//                           ^~~~~~~^ then update m
       );
    n=m;} // output m

Suntingan:

  • Disimpan 2 byte berkat ceilingcat
Annyo
sumber