Schalte ein paar Bits um und erhalte ein Quadrat

26

Bei einer Ganzzahl müssen Sie die minimale Anzahl von Bits finden, die in N invertiert werden müssen , um sie in eine quadratische Zahl umzuwandeln . Sie dürfen nur Bits unter dem höchstwertigen invertieren .N>3N

Beispiele

  • bereits eine quadratische Zahl ( 2 2 ), daher ist die erwartete Ausgabe 0 .N=4220
  • kann durch Invertieren von 1 Bit in eine quadratische Zahl umgewandelt werden: 11000 1100 1 ( 25 = 5 2 ), sodass die erwartete Ausgabe 1 ist .N=24110001100125=521
  • kann nicht durch Invertieren eines einzelnen Bits in eine quadratische Zahl umgewandelt werden (die möglichen Ergebnisse sind 23 , 20 , 18 und 30 ), sondern durch Invertieren von 2 Bits: 10110 10 0 0 0 ( 16 = 4 2 ) , also die erwartete Ausgabe ist 2 .N=2223201830101101000016=422

Regeln

  • Es ist in Ordnung, wenn Ihr Code zu langsam ist oder einen Fehler für die größeren Testfälle ausgibt, aber er sollte mindestens in weniger als 1 Minute unterstützen.3<N<10000
  • Das ist !

Testfälle

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

Oder im kopier- / einfügefreundlichen Format:

[4,22,24,30,94,831,832,1055,6495,9999,40063,247614,1049310,7361278,100048606]
Arnauld
quelle
Fast die Hälfte der Antworten wird 100048606bei TIO nicht ausgeführt. Ist das ein Problem?
Magic Octopus Urn
@MagicOctopusUrn Danke, ich habe die Regeln aktualisiert, um klarer zu machen, dass die Unterstützung von optional ist. N10000
Arnauld
1
Dies wäre auch eine nette Frage mit dem schnellsten Code (ohne die Beschränkung der Eingabegröße)
qwr
@qwr Ja, wahrscheinlich. Oder wenn Sie hardcore gehen wollen: Wenn , finden Sie das kleinste N, so dass f ( N ) = k . kNf(N)=k
Arnauld

Antworten:

14

Ruby, 74 Bytes

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

Probieren Sie es online!

Dies erzeugt einfach die Sequenz (die weitaus mehr als genug ist), XORs es mit n und nimmt dann entweder die Anzahl von 1s in seiner binären Darstellung, wenn die Anzahl von Bits geringer ist als oder gleich log 2 n oder sonst n . Es dauert dann die minimale Anzahl von Bits umgedreht. Die Rückgabe von n anstelle der Anzahl der umgedrehten Bits, wenn das höchste umgedrehte Bit größer als log 2 n ist, verhindert, dass diese Fälle als Minimum n ausgewählt werden[12,22,,n2]nLog2nnnLog2nn wird immer größer sein als die Anzahl der Bits, die es hat.

Vielen Dank an Piccolo für das Speichern eines Bytes.

Türknauf
quelle
Sie können ein Byte speichern, indem Sie (n^x*x).to_s 2;...anstelle von(n^x*x).to_s(2);...
Piccolo den
@ Piccolo Kann nicht glauben, dass ich das verpasst habe, danke!
Türklinke
6

Gelee , 12 Bytes

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

Probieren Sie es online!

Testen Sie eine Testsuite!

Monadischer Link. Sollte golffähig sein. Aber ich bin zu dumm, um mir einen Weg auszudenken, wie ich das ³s loswerden kann . Es ist meine erste Antwort, bei der ich Filterung / Mapping / Looping im Allgemeinen zusammen mit einer dyadischen Kette erfolgreich verwende.

Erläuterung

², BẈEðƇ² ^ B§Ṃ - Volles Programm / Monadischer Link. Nenne das Argument N.
     ðƇ - Filter-Keep [1 ... N] mit der folgenden dyadischen Kette:
², BẈE - Das Quadrat des aktuellen Elements hat die gleiche Bitlänge wie N.
² - Quadrat.
 , - Paar mit N.
  B - Beide in Binär umwandeln.
   Ẉ - Abrufen ihrer Längen.
    E - Und prüfen Sie, ob sie gleich sind.
       ² ^ - Quadrieren Sie nach dem Filtern die Ergebnisse und XOR sie mit N.
         B - Binäre Darstellung von jedem.
          § - Summe von jedem. Zählt die Anzahl der 1s im Binärformat.
           Ṃ - Minimum.
Mr. Xcoder
quelle
5

Schale , 20 Bytes

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

Probieren Sie es online!

Erläuterung

▼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
ბიმო
quelle
▼mΣfo¬←ṠMz≠ȯfo£İ□ḋπŀ2LḋSpart 2 Bytes. RIP Sie perfekte Punktzahl.
Mr. Xcoder
@ Mr.Xcoder: Schade um die Punktzahl .. Aber ich habe ein paar mehr losgeworden und zielt jetzt auf 16; P
ბიმო
5

Perl 6 , 65 Bytes

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

Probieren Sie es online!

Ich fühle mich ein wenig schmutzig, wenn ich nach einem perfekten Quadrat suche, indem ich nach einem Punkt in der Zeichenfolgendarstellung der Quadratwurzel der Zahl Ausschau halte, aber ... irgendetwas, um Bytes zu entfernen.

Sean
quelle
4

05AB1E , 20 15 Bytes

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

-5 Bytes dank @ Mr.Xcoder , der einen Port seiner Jelly-Antwort verwendet .

Probieren Sie es online aus oder überprüfen Sie alle Testfälle (die drei größten Testfälle werden entfernt, weil nach 60 Sekunden eine Zeitüberschreitung eintritt; bei den anderen Testfällen dauert dies noch ca. 35-45 Sekunden).

Erläuterung:

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
quelle
1
Okay , dann ein gültiger 15-byter: Lnʒ‚b€gË}^b€SOß. Es bricht leider Ihre Testsuite
Mr. Xcoder
1
@ Mr.Xcoder Danke! Und meine Testsuite bricht fast immer, nachdem ich etwas golfen habe. XD Aber es ist jetzt auch behoben.
Kevin Cruijssen
Ich denke, ich bin nicht gut darin, Testsuiten in 05AB1E zu schreiben ¯ \ _ (ツ) _ / ¯, es ist schön, dass Sie es behoben haben :)
Mr. 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;}

Probieren Sie es online!

Olivier Grégoire
quelle
1
Sie können 1 Byte speichern, indem Sie bitweise und &anstelle von logischen und&&
kirbyquerby
3

Gaia , 18 Bytes

Near-Port meiner Gelee-Antwort .

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

Probieren Sie es online!

Nervenzusammenbruch

s¦⟪, b¦l¦y⟫⟫ ⟪^ bΣ⟫¦⌋ - Volles Programm. Nennen wir den Eingang N.
s¦ - Quadrieren Sie jede ganze Zahl im Bereich [1 ... N].
  ⟪⟫⁇ - Wählen Sie diejenigen aus, die beim Durchlaufen eine bestimmte Bedingung erfüllen
                     ein dyadischer Block. Die Verwendung eines dyadischen Blocks spart ein Byte, weil der
                     Die Eingabe N wird implizit als weiteres Argument verwendet.
   , - Das aktuelle Element und N in einer Liste koppeln.
    b - Konvertieren Sie sie in Binärdateien.
      L ... - Holen Sie sich ihre Längen.
        y - Dann prüfen Sie, ob sie gleich sind.
           ⟪⟫¦ - Führen Sie alle gültigen ganzen Zahlen durch einen dyadischen Block.
            ^ - XOR jeweils mit N.
             bΣ - Konvertiere in binär und summiere (zähle die 1s in binär)
                 ⌋ - Minimum.
Mr. Xcoder
quelle
2

Brachylog , 56 41 Bytes

Es wird keine Rekorde brechen, aber ich dachte, ich würde es trotzdem posten

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

Probieren Sie es online!

Kroppeb
quelle
Gerade erkannt, dass das Zippen eine Sache ist. Ich werde es verkürzen, nachdem ich vom Abendessen zurückgekommen
bin
1
@Arnauld Ja, das Hauptproblem war, dass ich für jedes i im Bereich (0, n + 1) den Bereich neu berechnet, quadriert und auf binär gesetzt habe. Wenn Sie das Ganze nach draußen bringen, werden ein paar Bytes mehr benötigt, aber es ist jetzt viel schneller
Kroppeb
2

x86-64-Assembly, 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

Dies berechnet sogar das höchste Beispiel in weniger als einer Sekunde.

Herzstück des Algorithmus ist wie gewohnt xor / popcount.

    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
quelle
Vorschlagen mindestens Ersetzen eines Ihrer movs mit einemxchg
ceilingcat
Soweit ich das mov %ecx,%eaxbeurteilen kann, gibt es nur einen, der ein Byte ( ) speichern würde, und ich kann% ecx dort nicht sterben lassen.
ObsequiousNewt
1

Kohle , 31 Bytes

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

Probieren Sie es online! Link ist eine ausführliche Version des Codes. Erläuterung:

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
quelle
1

Japt -g , 20 Bytes

Hier kann man Golf spielen.

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

Probieren Sie es online!

Luis Felipe De Jesus Munoz
quelle
1

C (GCC) ,  93  91 Bytes

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

Probieren Sie es online!


Bearbeiten: Ich denke, meine ursprüngliche Lösung ( Online ausprobieren! ) Ist ungültig, da eine der Variablen, die mglobal ist, um ein paar Bytes zu sparen, indem kein Typ angegeben wurde, außerhalb von initialisiert wurde f(n)und daher zwischen den Aufrufen neu initialisiert werden musste


Ungolfed und kommentierter Code:

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

Bearbeitungen:

  • 2 Bytes dank ceilingcat gespart
Annyo
quelle