Finden Sie die nächste 1-sparse-Binärzahl

27

Eine positive ganze Zahl N ist K -sparsam, wenn zwischen zwei aufeinanderfolgenden Einsen in ihrer binären Darstellung mindestens K 0s liegen.

Die Nummer 1010101 ist also 1-dünn, 101101 dagegen nicht.

Ihre Aufgabe ist es, die nächste 1-sparse-Nummer für die angegebene Eingangsnummer zu finden. Wenn der Eingang beispielsweise 12 ( 0b1100) ist, sollte der Ausgang 16 ( 0b10000) sein, und wenn der Eingang 18 ( 0b10010) ist, sollte der Ausgang 20 ( 0b10100) sein.

Das kleinste Programm oder die kleinste Funktion (in Bytes) gewinnt! Standardlücken sind nicht erlaubt.

articuno
quelle
"Weiter" wie "nächsthöher" oder wie "mit geringstem absoluten Unterschied"?
FUZxxl
"next" wie in "next highest".
Articuno
Welcher Eingabebereich muss bearbeitet werden?
mbomb007
Ich gehe davon aus, dass negative Zahlen nicht sein müssen.
mbomb007
@articuno Können wir eine Funktion erstellen oder muss es ein vollständiges Programm sein? Funktionen sind ziemlich Standard.
mbomb007

Antworten:

9

CJam, 14 11 Bytes

3 Bytes gespart dank DigitalTrauma.

l~{)___+&}g

Teste es hier.

Erläuterung

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'.";

Dadurch bleibt die letzte Nummer auf dem Stapel, die am Ende des Programms automatisch gedruckt wird.

Martin Ender
quelle
8

Python 2, 44 Bytes

Dies ist ein vollständiges Python-Programm, das n einliest und die Antwort ausgibt. Ich denke, dass es im Teilwettbewerb zur Lesbarkeit ganz gut läuft.

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

Die Testergebnisse:

$ echo 12 | python soln.py 
16
$ echo 18 | python soln.py 
20
Logik-Ritter
quelle
6

Pyth, 12 11 Bytes

f!}`11.BThQ

Probieren Sie es online aus: 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
quelle
1
Sie können einen Charakter speichern, indem Sie sich "11"in verwandeln `11.
Orlp
@orlp Danke, hätte das merken sollen.
Jakube
5

Mathematica, 41-30 Bytes

11 Bytes gespart dank Martin Büttner.

#+1//.i_/;BitAnd[i,2i]>0:>i+1&
Alephalpha
quelle
3
Könnten Sie bitte eine Beschreibung hinzufügen?
mbomb007
4

Perl, 31

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

Oder von der Kommandozeile:

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

APL, 18 Bytes

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

Dies ergibt eine monadische Funktion. Probieren Sie es hier aus. Verwendung:

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

Erläuterung

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

J, 20 Zeichen

Ein monadisches Verb. Es wurde behoben, dass die Regeln eingehalten wurden.

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

Erläuterung

Zuerst ist dies das Verb mit Leerzeichen und dann etwas weniger golfen:

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

Lesen:

    ]                             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

Das Argument plus die oder-Verkleinerung der 1 1Intervallzugehörigkeit in der Basis-2-Darstellung des Arguments, das sich auf die Leistungsgrenze bezieht, die auf das inkrementierte Argument angewendet wird.

Ich berechne grundsätzlich, ob 1 1in der Basis-2-Darstellung der Eingang auftritt. In diesem Fall erhöhe ich die Eingabe. Dies wird unter eine Leistungsgrenze gesetzt, was bedeutet, dass es angewendet wird, bis sich das Ergebnis nicht mehr ändert.

FUZxxl
quelle
Netter Algorithmus! Es hat die gleiche Länge in APL: {⍵+∨/2∧/⍵⊤⍨⍵⍴2}⍣=.
Zgarb
@ Randomra Ah, ich verstehe.
FUZxxl
4

Javascript, 25 19

Unter Verwendung der Tatsache, dass für eine 1-sparse Binärzahl x&2*x == 0:

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

JavaScript (ES6), 39 43

Kein regulärer Ausdruck, keine Zeichenfolgen, rekursiv:

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

Iterative Version:

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

Es ist sehr einfach, indem Sie einfach die rechte Umschalttaste verwenden, um eine Sequenz von 11 zu finden. Wenn ich sie finde, springen Sie zur nächsten Nummer. Die rekursive Version leitet sich direkt von der iterativen ab.

Ungolfed und offensichtlicher. Zum Golfen ist es am schwierigsten, die inneren und äußeren Loops zu verbinden (zu Beginn müssen Sie x bis 3 einleiten).

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
quelle
Das %4>2sieht aus wie eine Zauberei aus der Zahlentheorie. Kannst du das bitte erklären? || einen Link bereitstellen?
Jacob
@Jacob (x% 4> 2) ist einfach ((x & 3) == 3), aber mit der Operator-Priorität JS vermeiden Sie die 2 Klammern
edc65
Einfach als ich dachte. Jetzt mit der ungolfed Version ist es klar. Vielen Dank!
Jacob
3

Python 2, 37 Bytes

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

Verwendete die Logik x & 2*x == 0für 1-sparse-Zahl.
Vielen Dank an @Nick und @CarpetPython.

ShinMigami13
quelle
Warum die Gegenstimme? Dies funktioniert einwandfrei und ist auch gut golfen.
ETHproductions
Willkommen bei PPCG, übrigens, und schöne erste Antwort! Ich ermutige Sie, weiterhin auf die Herausforderungen auf der Website zu antworten :-)
ETHproductions
2

JavaScript, 75 66 62 Bytes

Danke an Martin Büttner für das Speichern von 9 Bytes und Pietu1998 für 4 Bytes!

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

So funktioniert es: Es wird eine forSchleife ausgeführt, beginnend a + 1mit der Zeit, in der die aktuelle Nummer nicht 1-dünn ist. Ist dies der Fall, wird die Schleife unterbrochen und die aktuelle Nummer zurückgegeben. Um zu überprüfen, ob eine Zahl 1-dünn ist, konvertiert sie diese in eine Binärzahl und prüft, ob sie keine enthält 11.

Code ohne Golf:

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

Julia, 40 Bytes

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

Dadurch wird eine anonyme Funktion erstellt, die eine einzelne Ganzzahl als Eingabe akzeptiert und die nächsthöhere Ganzzahl mit einer Teilung zurückgibt. Um es zu nennen, geben Sie ihm zB einen Namen f=n->...und tun Sie f(12).

Ungolfed + Erklärung:

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

Beispiele:

julia> f(12)
16

julia> f(16)
20

Anregungen und / oder Fragen sind wie immer willkommen!

Alex A.
quelle
2

> <> (Fisch) , 31 + 3 = 34 Bytes

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

Verwendung:

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

3 Bytes für das -vFlag hinzugefügt .

randomra
quelle
1

JavaScript (ECMAScript 6), 40

Durch Rekursion:

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

JavaScript, 56

Gleiche ohne Pfeilfunktionen.

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

Scala, 65 Bytes

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

(Wenn eine benannte Funktion erforderlich ist, beträgt die Lösung 69 Byte.)

Jacob
quelle
1

Python, 39 33 Bytes

Versuchen Sie es hier: http://repl.it/gpu/2

In Lambda-Form (danke an xnor fürs Golfen):

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

Die Standardfunktionssyntax erwies sich einmal als kürzer als ein Lambda!

def f(x):x+=1;return x*(x&x*2<1)or f(x)
mbomb007
quelle
Sie können das Lambda - eins bis 33 Bytes verkürzen: f=lambda x:1+x&x/2and f(x+1)or-~x. Es stellt sich heraus , dass von Ihnen Verschiebung Bit rechts statt links, können Sie x/2statt , (x+1)/2weil der Unterschied immer in Null - Bits von ist x+1. Die Spezifikation fragt jedoch nach einem Programm.
Xnor
Ich fragte und er sagte, wir könnten Funktionen ausführen. Die meisten Antworten sind bereits.
mbomb007
1

Java, 33 Bytes.

Verwendet die Methode in dieser Antwort

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

TIO

Benjamin Urquhart
quelle
0

Rubin, 44

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

Ziemlich einfach. Ein Lambda mit einer Endlosschleife und einem regulären Ausdruck zum Testen der Binärdarstellung. Ich wünsche das loopergab und Indexnummer.

Max
quelle
@ mbomb007 erledigt. Danke für den Tipp.
Max
0

Matlab ( 77 74 Bytes)

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

Anmerkungen:

  • Es genügt zu Testzahlen m+1zu 2*m, wo mder Eingang ist.
  • ~any(x)is trueif xenthält alle Nullen oder if xist leer
Luis Mendo
quelle
0

C (32 Bytes)

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

Rekursive Implementierung des gleichen Algorithmus wie so viele andere Antworten.

Alchymist
quelle
0

Perl, 16 Bytes

Kombiniere die x&2*xaus verschiedenen Antworten (ich denke, Nicks erste) mit Nutkis redo Erträgen:

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

Getestet in Strawberry 5.26.

msh210
quelle
0

Gelee , 7 Bytes

‘&Ḥ¬Ɗ1#

Ein vollständiges Programm, das eine einzelne, nicht negative Ganzzahl akzeptiert, die eine positive Ganzzahl ausgibt (als monadische Verknüpfung ergibt es eine Liste, die eine einzelne positive Ganzzahl enthält).

Probieren Sie es online!

Wie?

Beginnend mit v=n+1und inkrementierend, verdoppeln Sie v, um jedes Bit um eine Stelle nach oben und bitweise UND mit zu verschieben, vund führen Sie dann das logische NICHT aus, um zu testen, ob v1-spärlich ist, bis eine solche Zahl gefunden wird.

‘&Ḥ¬Ɗ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
quelle
0

Stax , 5 Bytes

╦>ù╤x

Führen Sie es aus und debuggen Sie es

Es funktioniert mit dieser Prozedur. Die Eingabe beginnt oben auf dem Stapel.

  • Erhöhe und kopiere zweimal.
  • Die Oberseite des Stapels halbieren.
  • Bitweises und oberste zwei Elemente auf dem Stapel.
  • Wenn das Ergebnis wahr ist (nicht Null), wiederholen Sie das gesamte Programm.
rekursiv
quelle