Przełącz kilka bitów i uzyskaj kwadrat

26

Biorąc pod uwagę liczbę całkowitą , musisz znaleźć minimalną liczbę bitów, którą należy odwrócić w aby przekształcić ją w liczbę kwadratową . Dozwolone jest tylko odwracanie bitów poniżej najbardziej znaczącego .N.>3)N.

Przykłady

  • N=4 już jest liczbą kwadratową ( ), więc oczekiwany wynik to . 0220
  • N=24 można zamienić na liczbę kwadratową, odwracając 1 bit: ( ), więc oczekiwany wynik to . 25 = 5 2 1110001100125=52)1
  • 23 20 18 30 10110 10 0 0 0 16 = 4 2 2N.=22 nie można zamienić na liczbę kwadratową poprzez odwrócenie pojedynczego bitu (możliwe wyniki to , , i ), ale można tego dokonać poprzez odwrócenie 2 bitów: ( ), więc oczekiwany wynik to .23201830101101000016=42)2)

Zasady

  • W porządku, jeśli Twój kod jest zbyt wolny lub generuje błąd dla większych przypadków testowych, ale powinien obsługiwać co najmniej w mniej niż 1 minutę.3)<N.<10000
  • To jest !

Przypadki testowe

    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")

Lub w przyjaznym formacie kopiuj / wklej:

[4,22,24,30,94,831,832,1055,6495,9999,40063,247614,1049310,7361278,100048606]
Arnauld
źródło
Prawie połowa odpowiedzi nie jest wykonywana 100048606w TIO, czy to problem?
Magic Octopus Urn
@MagicOctopusUrn Dzięki, zaktualizowałem zasady, aby było bardziej jasne, że obsługa jest opcjonalna. N.10000
Arnauld
1
Byłoby to również miłe pytanie o najszybszym kodzie (bez ograniczenia rozmiaru wejściowego)
qwr
@qwr Tak, prawdopodobnie. Lub jeśli chcesz przejść hardcorowo: biorąc pod uwagę , znajdź najmniejszą taką, że . N f ( N ) = kkN.f(N)=k
Arnauld,

Odpowiedzi:

14

Rubinowy, 74 bajty

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

Wypróbuj online!

To po prostu generuje sekwencję (co jest znacznie więcej niż wystarczające), XORs za pomocą , a następnie przyjmuje liczbę 1s w postaci binarnej reprezentacja, jeśli liczba bitów jest mniejsza lub równa , lub innym przypadku. Następnie zajmuje minimalną liczbę przerzuconych bitów. Zwrócenie zamiast liczby przerzuconych bitów, gdy najwyższy przerzucony bit jest większy niż uniemożliwia tych przypadków jako minimum, ponieważ zawsze będzie większe niż liczba bitów, które ma. n log 2 nnn log 2 nn[12),2)2),,n2)]nlog2)nnnlog2)nn

Dzięki Piccolo za uratowanie bajtu.

Klamka
źródło
Możesz zapisać bajt, używając (n^x*x).to_s 2;...zamiast(n^x*x).to_s(2);...
Piccolo
@Piccolo Nie mogę uwierzyć, że mi tego brakowało, dzięki!
Klamka
6

Galaretka , 12 bajtów

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

Wypróbuj online!

Sprawdź pakiet testowy!

Link monadyczny. Powinien być golfowy. Ale jestem zbyt głupi, aby wymyślić sposób, aby się go pozbyć ³. To moja pierwsza odpowiedź, w której z powodzeniem używam filtrowania / mapowania / zapętlania ogólnie wraz z łańcuchem dynamicznym \ o /

Wyjaśnienie

², BẈEðƇ² ^ B§Ṃ - Pełny program / Łącze monadyczne. Wywołaj argument N.
     ðƇ - Zachowaj filtr [1 ... N] o następującym łańcuchu dyadycznym:
², BẈE - Kwadrat bieżącego elementu ma tę samą długość bitów co N.
² - kwadrat.
 , - Połącz z N.
  B - Konwertuj oba na binarne.
   Ẉ - Odzyskaj ich długości.
    E - I sprawdź, czy się równa.
       ² ^ - Po przefiltrowaniu wyrównaj wyniki i wyrównaj je za pomocą N.
         B - Binarna reprezentacja każdego.
          § - Suma każdego. Liczy liczbę 1 w postaci binarnej.
           Ṃ - minimum.
Pan Xcoder
źródło
5

Łuska , 20 bajtów

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

Wypróbuj online!

Wyjaśnienie

▼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
ბიმო
źródło
▼mΣfo¬←ṠMz≠ȯfo£İ□ḋπŀ2Lḋoszczędza 2 bajty. RIP to idealny wynik kwadratowy.
Pan Xcoder,
@ Mr.Xcoder: Szkoda wynik. Ale pozbyłem się trochę więcej, teraz celuję w 16; P
ბიმო
5

Perl 6 , 65 bajtów

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

Wypróbuj online!

Czuję się trochę brudny, jeśli chodzi o testowanie idealnego kwadratu, szukając kropki w reprezentacji ciągu pierwiastka kwadratowego z liczby, ale ... cokolwiek, by zgolić bajty.

Sean
źródło
4

05AB1E , 20 15 bajtów

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

-5 bajtów dzięki @ Mr.Xcoder używający portu swojej odpowiedzi Jelly .

Wypróbuj online lub sprawdź wszystkie przypadki testowe (największe trzy przypadki testowe są usuwane, ponieważ przekroczą limit czasu po 60 sekundach; nadal zajmuje około 35-45 sekund w przypadku innych przypadków testowych).

Wyjaśnienie:

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
źródło
1
Ok wtedy, ważny 15-byter: Lnʒ‚b€gË}^b€SOß. Niestety psuje pakiet testowy
Mr. Xcoder,
1
@ Mr.Xcoder Thanks! A mój pakiet testowy prawie zawsze się psuje po tym, jak coś grałem w golfa .. XD Ale teraz jest to również naprawione.
Kevin Cruijssen,
Chyba nie jestem dobry w pisaniu testów apartamentów w 05AB1E ¯ \ _ (ツ) _ / ¯, miło, że naprawił :)
Pan Xcoder
3

Java (JDK 10) , 110 bajtów

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

Wypróbuj online!

Olivier Grégoire
źródło
1
Możesz zapisać 1 bajt, używając bitowego i &zamiast logicznego i&&
kirbyquerby
3

Gaia , 18 bajtów

Bliski port mojej galaretki .

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

Wypróbuj online!

Awaria

s¦⟪, b¦l¦y⟫⁇ ⟪^ bΣ⟫¦⌋ - Pełny program. Nazwijmy wejście N.
s¦ - Kwadrat każdej liczby całkowitej w zakresie [1 ... N].
  ⟪⟫⁇ - Wybierz te, które spełniają określony warunek po przejściu
                     blokada dyadyczna. Użycie bloku dynamicznego pozwala zaoszczędzić jeden bajt, ponieważ
                     input, N, jest domyślnie używane jako kolejny argument.
   , - Sparuj bieżący element i literę N na liście.
    b¦ - Konwertuj je na binarne.
      l¦ - Zdobądź ich długości.
        y - Następnie sprawdź, czy są równe.
           ⟪⟫¦ - Przeprowadź wszystkie prawidłowe liczby całkowite przez blokadę.
            ^ - XOR każdy z N.
             bΣ - Konwertuj na binarny i sumuj (policz 1 w binarny)
                 ⌋ - minimum.
Pan Xcoder
źródło
2

Brachylog , 56 41 bajtów

Nie pobije żadnych rekordów długości, ale i tak pomyślałem, że to opublikuję

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

Wypróbuj online!

Kroppeb
źródło
Właśnie zrozumiałem, że zipowanie jest rzeczą.
Skrócę
1
@Arnauld Tak, główny problem polegał na tym, że dla każdego i w zakresie (0, n + 1) ponownie obliczyłem zakres, obliczyłem go i binarnie. Umieszczenie tego na zewnątrz wymagało jeszcze kilku bajtów, ale teraz jest o wiele szybsze
Kroppeb,
2

Zestaw x86-64, 37 bajtów

Kod bajtowy:

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

Cóż, to oblicza nawet najwyższy przykład w mniej niż sekundę.

Sercem algorytmu jest xor / popcount jak zwykle.

    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
ObsequiousNewt
źródło
Zaproponuj zastąpienie przynajmniej jednego movz nich xchg
sufitem
O ile mogę stwierdzić, jest tylko jeden, który oszczędziłby bajt ( mov %ecx,%eax) i nie mogę pozwolić, aby% ecx tam umarł.
ObsequiousNewt
1

Wolfram Language (Mathematica) , 67 bajtów

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

Wypróbuj online!

{1,2),,n}BitLengthPickBitXorMinDigitCount1

JungHwan Min
źródło
1

Węgiel drzewny , 31 bajtów

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

Wypróbuj online! Link jest do pełnej wersji kodu. Wyjaśnienie:

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
źródło
1

Japt -g , 20 bajtów

Można to zagrać w golfa.

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

Wypróbuj online!

Luis Felipe De Jesus Munoz
źródło
1

C (gcc) ,  93  91 bajtów

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

Wypróbuj online!


Edycja: Wydaje mi się, że moje oryginalne rozwiązanie ( Wypróbuj online! ) Jest nieprawidłowe, ponieważ jedna ze zmiennych m, globalna w celu zaoszczędzenia kilku bajtów przez nieokreślenie typu, została zainicjowana poza f(n)i dlatego musiała zostać ponownie zainicjowana między wywołaniami


Kod nieposortowany i skomentowany:

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

Edycje:

  • Zaoszczędzono 2 bajty dzięki pułapce cat
Annyo
źródło