Zahlen mit mehreren Folgen von Einsen

30

Aufgabe

Suchen Sie den Satz von Zahlen, sodass die Binärdarstellung zwei oder mehr 1durch mindestens einen getrennte Reihen enthält 0.

Zum Beispiel für die Zahlen, die 4 Bits lang sind:

 0 0000        (no ones)
 1 0001        (only one run)
 2 0010        (only one run)
 3 0011        (only one run)
 4 0100        (only one run)
 5 0101 Valid
 6 0110        (only one run)
 7 0111        (only one run)
 8 1000        (only one run)
 9 1001 Valid
10 1010 Valid
11 1011 Valid
12 1100        (only one run)
13 1101 Valid
14 1110        (only one run)
15 1111        (only one run)

Eingang

Eine Ganzzahl, die der Anwendung über eine Eingabe im Bereich bereitgestellt wird 3 .. 32. Dies stellt die maximale Anzahl von Bits dar, bis zu der gezählt werden kann.

Die Eingabe von ngibt an, dass die Zahlen überprüft werden müssen.0 .. 2n-1

Ausgabe

Eine begrenzte Liste (Ihrer Wahl) aller Nummern, die die Kriterien erfüllen. Die Nummern sind in numerischer Reihenfolge anzugeben. Ein zusätzliches abschließendes Trennzeichen ist zulässig. Datenstrukturumschließungen (z. B. []und ähnliche) sind ebenfalls zulässig.

Beispiel

Input: 3
Output: 5

Input: 4
Output: 5, 9, 10, 11, 13

Input: 5
Output: 5, 9, 10, 11, 13, 17, 18, 19, 20, 21, 22, 23, 25, 26, 27, 29

Das ist - die Antwort mit der geringsten Anzahl von Bytes gewinnt.


quelle
Ich denke, Sie haben 23 für n = 5 verpasst.
xnor
@ xnoder Sie sind richtig. Vielen Dank und yep, das macht es auch nicht gleichbedeutend mit A094695. Hmm. oeis.org/A101082 vs oeis.org/A166934
@VTCAKAVSMoACE ja. Wenn man \nabgrenzt und ein \nin die letzte Zeile setzt, dann sollte ,ein ,Abschluß auch akzeptabel sein. Aktualisiert.
1
Kann die Eingabe in einem Listenformat wie [1, 2, 3]?
kirbyfan64sos
@ kirbyfan64sos ja. Aktualisiert.

Antworten:

7

Pyth, 12 Bytes

f<2r.BT8U^2Q

Probieren Sie es online aus.

Idee

Die binäre Darstellung einer positiven Zahl beginnt immer mit einem Lauf von 1 s, möglicherweise gefolgt von anderen abwechselnden Läufen von 0 s und 1 s. Wenn es mindestens drei separate Läufe gibt, sind zwei davon garantiert Läufe von 1 s.

Code

              (implicit) Store the evaluated input in Q.
         ^2Q  Calculate 2**Q.
f       U     Filter; for each T in [0, ..., 2**Q-1]:
    .BT         Compute T's binary representation.
   r   8        Perform run-length encoding.
                This returns a list of character/run-length pairs.
 <2             Discard the trailing two pairs.
                This returns a non-empty array if there are more than 2 runs.
              Keep T if the array was truthy (non-empty).
Dennis
quelle
22

Python, 48

lambda n:[i for i in range(2**n)if'01'in bin(i)]

Ich hatte das sehr überlegt. Wir müssen nur überprüfen, ob die binäre Erweiterung enthält '01'.

Damit es zwei Durchgänge von einem gibt, muss dem einen rechts ein vorangestellt werden 0. Wenn es nur einen Lauf gibt, wird es keine Führenden geben 0, also wird das nicht passieren.


Alte Antwort:

lambda n:[i for i in range(2**n)if len(set(bin(i).split('0')))>2]

Die Python-Binärdarstellung funktioniert hier sehr gut. Eine Binärzahl wird wie folgt geschrieben bin(9)=='0b10110'. Aufteilen auf '0'Ergebnisse in einer Liste von

  • Leere Zeichenfolgen links neben dem Anfangsbuchstaben 0, zwischen zwei aufeinanderfolgenden Zeichenfolgen 0, und rechts von einem Finale0
  • Der Brief bgefolgt von einem oder mehreren führenden
  • Läuft von 1's, die nicht führen

Die ersten beiden Kategorien existieren immer, aber die letzte existiert nur, wenn es eine Lauf-Kategorie gibt, 1die die führende nicht enthält '1', und daher nur, wenn es mehr als eine Lauf- Kategorie gibt 1. Es reicht also zu prüfen, ob die Liste mehr als 2unterschiedliche Elemente enthält.

Python 3.5 spart 2 Zeichen durch Auspacken {*_}anstelle von set(_).

xnor
quelle
Vielen Dank für die Idee, /01/anstelle von zu verwenden /10+1/. Das habe ich in Perl ausgenutzt .
msh210
13

Ruby, 44 40 38 Zeichen

durchgestrichen 44 ist immer noch regulär 44; (

->n{(0..2**n).select{|x|/01/=~'%b'%x}}

Eine anonyme Funktion (proc), die eine Ganzzahl annimmt und ein Array zurückgibt.

Verwendet den regulären Ausdruck /10+1/: a 1, mindestens einer 0und dann ein anderer 1. @histocrat weist darauf hin, dass 01sich irgendwo in der Zeichenfolge ein Irgendwo davor befinden muss1 .

Türknauf
quelle
1
Ein Format - String zu verwenden ist ein bisschen hier kürzer: /10+1/=~'%b'%x. Sie können ein Zeichen auch mit einem inklusiven Bereich ( 0..2**n) speichern, da 2**nes nie mehrere Läufe gibt.
Histokrat
@histocrat Huh, ich wusste nie, dass du die Reihenfolge der Zeichenkette und des Regex mit umdrehen könntest =~. Vielen Dank!
Türklinke
1
Warten Sie, eigentlich /01/funktioniert der reguläre Ausdruck genauso gut. Wenn es eine 01gibt, muss irgendwo links eine 1 sein.
Histokrat
@histocrat Oh, das ist klug! Das spart zwei Zeichen.
Türklinke
7

Julia, 43 41 Bytes

n->filter(i->ismatch(r"01",bin(i)),1:2^n)

Dadurch wird eine unbenannte Funktion erstellt, die eine Ganzzahl akzeptiert und ein Array zurückgibt. Es wird der Regex-Trick der Histokraten verwendet (in der Antwort von Doorknob verwendet), bei dem 01nur dann eine Übereinstimmung erzielt wird, wenn es eine vorangestellte 1 gibt.

Ungolfed:

function f(n::Int)
    # Take the integers from 1 to 2^n and filter them down to
    # only those such that the binary representation of the integer
    # matches the regex /01/.
    filter(i -> ismatch(r"01", bin(i)), 1:2^n)
end
Alex A.
quelle
Der Trick eines Histokraten, nicht meiner. :)
Türklinke
@Doorknob Oh hey, jetzt kriegt ihr beide Kredit. :)
Alex A.
6

Matlab, 79 68 64 59

Die Idee ist, die Binärzahl als Array von Nullen und Einsen zu interpretieren und dann die absolute Differenz zwischen jedem Paar von Nachbarn zu berechnen. Wenn wir zwei oder mehr Male einen Unterschied von 1 haben, dann haben wir offensichtlich einen Lauf von zwei oder mehr. Beachten Sie, dass dies nur funktioniert, wenn wir die Binärzahl ohne führende Nullen darstellen.

@(n)find(arrayfun(@(k)sum(~~diff(dec2bin(k)+0))>1,1:2^n-1))

Alte Versionen:

k=1:2^input('')-1;k(arrayfun(@(k)sum(~~diff(dec2bin(k)+0))>1,k))

for k=1:2^input('')-1;if sum(~~diff(dec2bin(k)+0))>1;disp(k);end;end

for k=1:2^input('')-1;if sum(~~conv(dec2bin(k)+0,[-1,1],'v'))>1;disp(k);end;end
Fehler
quelle
6

JavaScript (ES7), 89 85 72 69 62 Byte

Heilige Kuh, das Erstellen von Bereichen in JS ist nicht einfach. Vielleicht wäre es mit einer tatsächlichen forSchleife kürzer . Nein, ich habe gelogen. es ist eigentlich ein bisschen länger. Naja. Ich denke, ich muss mich nur mit 27 gesparten Bytes zufrieden geben. (7 dank Mwr247!)

x=>[for(a of Array(1<<x).keys())if(/01/.test(a.toString(2)))a]

Funktioniert ordnungsgemäß in den neuesten Versionen von Firefox, wahrscheinlich jedoch in keinem anderen Browser. Versuch es:

<!--                               Try the test suite below!                              --><strong id="bytecount" style="display:inline; font-size:32px; font-family:Helvetica"></strong><strong id="bytediff" style="display:inline; margin-left:10px; font-size:32px; font-family:Helvetica; color:lightgray"></strong><br><br><pre style="margin:0">Code:</pre><textarea id="textbox" style="margin-top:5px; margin-bottom:5px"></textarea><br><pre style="margin:0">Input:</pre><textarea id="inputbox" style="margin-top:5px; margin-bottom:5px">5</textarea><br><button id="testbtn">Test!</button><button id="resetbtn">Reset</button><br><p><strong id="origheader" style="font-family:Helvetica; display:none">Original Code Output:</strong><p><div id="origoutput" style="margin-left:15px"></div><p><strong id="newheader" style="font-family:Helvetica; display:none">New Code Output:</strong><p><div id="newoutput" style="margin-left:15px"></div><script type="text/javascript" id="golfsnippet">var bytecount=document.getElementById("bytecount");var bytediff=document.getElementById("bytediff");var textbox=document.getElementById("textbox");var inputbox=document.getElementById("inputbox");var testbtn=document.getElementById("testbtn");var resetbtn=document.getElementById("resetbtn");var origheader=document.getElementById("origheader");var newheader=document.getElementById("newheader");var origoutput=document.getElementById("origoutput");var newoutput=document.getElementById("newoutput");textbox.style.width=inputbox.style.width=window.innerWidth-50+"px";var _originalCode="x=>[for(a of Array(1<<x).keys())if(/01/.test(a.toString(2)))a]";function getOriginalCode(){if(_originalCode!=null)return _originalCode;var allScripts=document.getElementsByTagName("script");for(var i=0;i<allScripts.length;i++){var script=allScripts[i];if(script.id!="golfsnippet"){originalCode=script.textContent.trim();return originalCode}}}function getNewCode(){return textbox.value.trim()}function getInput(){try{var inputText=inputbox.value.trim();var input=eval("["+inputText+"]");return input}catch(e){return null}}function setTextbox(s){textbox.value=s;onTextboxChange()}function setOutput(output,s){output.innerHTML=s}function addOutput(output,data){output.innerHTML+='<pre style="background-color:'+(data.type=="err"?"lightcoral":"lightgray")+'">'+escape(data.content)+"</pre>"}function getByteCount(s){return(new Blob([s],{encoding:"UTF-8",type:"text/plain;charset=UTF-8"})).size}function onTextboxChange(){var newLength=getByteCount(getNewCode());var oldLength=getByteCount(getOriginalCode());bytecount.innerHTML=newLength+" bytes";var diff=newLength-oldLength;if(diff>0){bytediff.innerHTML="(+"+diff+")";bytediff.style.color="lightcoral"}else if(diff<0){bytediff.innerHTML="("+diff+")";bytediff.style.color="lightgreen"}else{bytediff.innerHTML="("+diff+")";bytediff.style.color="lightgray"}}function onTestBtn(evt){origheader.style.display="inline";newheader.style.display="inline";setOutput(newoutput,"");setOutput(origoutput,"");var input=getInput();if(input===null){addOutput(origoutput,{type:"err",content:"Input is malformed. Using no input."});addOutput(newoutput,{type:"err",content:"Input is malformed. Using no input."});input=[]}doInterpret(getNewCode(),input,function(data){addOutput(newoutput,data)});doInterpret(getOriginalCode(),input,function(data){addOutput(origoutput,data)});evt.stopPropagation();return false}function onResetBtn(evt){setTextbox(getOriginalCode());origheader.style.display="none";newheader.style.display="none";setOutput(origoutput,"");setOutput(newoutput,"")}function escape(s){return s.toString().replace(/&/g,"&amp;").replace(/</g,"&lt;").replace(/>/g,"&gt;")}window.alert=function(){};window.prompt=function(){};function doInterpret(code,input,cb){var workerCode=interpret.toString()+";function stdout(s){ self.postMessage( {'type': 'out', 'content': s} ); }"+" function stderr(s){ self.postMessage( {'type': 'err', 'content': s} ); }"+" function kill(){ self.close(); }"+" self.addEventListener('message', function(msg){ interpret(msg.data.code, msg.data.input); });";var interpreter=new Worker(URL.createObjectURL(new Blob([workerCode])));interpreter.addEventListener("message",function(msg){cb(msg.data)});interpreter.postMessage({"code":code,"input":input});setTimeout(function(){interpreter.terminate()},1E4)}setTimeout(function(){getOriginalCode();textbox.addEventListener("input",onTextboxChange);testbtn.addEventListener("click",onTestBtn);resetbtn.addEventListener("click",onResetBtn);setTextbox(getOriginalCode())},100);function interpret(code,input){window={};alert=function(s){stdout(s)};window.alert=alert;console.log=alert;prompt=function(s){if(input.length<1)stderr("not enough input");else{var nextInput=input[0];input=input.slice(1);return nextInput.toString()}};window.prompt=prompt;(function(){try{var evalResult=eval(code);if(typeof evalResult=="function"){var callResult=evalResult.apply(this,input);if(typeof callResult!="undefined")stdout(callResult)}}catch(e){stderr(e.message)}})()};</script>

(Ausschnitt aus dieser Seite )

Vorschläge willkommen!

ETHproductions
quelle
Sie können .keys()anstelle von .fill()und aanstelle von verwenden i, um meine für 62 zu binden:x=>[for(a of Array(1<<x).keys())if(/01/.test(a.toString(2)))a]
Mwr247
@ Mwr247 Danke! Ich frage mich, ob es unter 62 möglich ist ... :)
ETHproductions
6

Haskell, 68 61 53 Bytes

Verbesserung von Damien

g x|x`mod`4==1=x>4|2>1=g$x`div`2
a x=filter g[1..2^x]

Geschichte:

Dies behebt den Fehler (Switched == und =, und Quadrat statt Potenz von zwei). Und ersetze true durch 2> 1 und false durch 1> 2. Auch danke, darauf hinzuweisen, dass 2 ^ x immer ausfällt. Danke an Thomas Kwa und nimi

g x|x<5=1>2|x`mod`4==1=2>1|2>1=g$x`div`2
a x=filter g[1..2^x]

Ursprünglich

g x|x<5=False|x`mod`4=1==True|2>1=g$x`div`2
a x=filter g[1..(x^2-1)]

Wenn es volles Programm sein muss,

g x|x<5=False|x`mod`4==1=True|2>1=g$x`div`2
main=interact$show.a
a x=filter g[1..2^(read x)]
Akangka
quelle
1
Lambdas sind in Ordnung, da OP das Schreiben einer benannten Funktion oder eines benannten Programms nicht spezifiziert hat. Übrigens, willkommen bei PPCG!
Lirtosiast
1
Ich denke du meinst 1..(2^x-1)das kann einfach sein 1.. (2^x)da 2 ^ x immer ausfällt.
Lirtosiast
Sie können die Konstanten Falseund Truedurch 1>2und ersetzen 1<2. Die Klammern sind nicht erforderlich 2^x-1. (Übrigens: Sie haben einen Tippfehler: es muss sein 4==1=True).
nimi
Danke für die Tippfehlerbehebung. Es war spät in der Nacht in meiner Zeit.
Akangka
Schöne Tricks! Ich denke, Sie können g reduzieren auf: gx | x mod4 == 1 = x> 4 | 2> 1 = g $ x div2
Damien
5

APL, 34 27 Bytes

{0~⍨{⍵×2<+/2≢/⍵⊤⍨⍵/2}¨⍳2*⍵}

Dadurch wird eine unbenannte monadische Funktion erstellt, die eine Ganzzahl auf der rechten Seite akzeptiert und ein Array zurückgibt.

Erläuterung:

                     }¨⍳2*⍵}  ⍝ For each integer from 1 to 2^input...
              ⍵⊤⍨⍵/2         ⍝ Get the binary representation as a vector
           2≢/                ⍝ Pairwise non-match, yielding a boolean vector
       2<+/                   ⍝ Check whether the number of trues is >2
     ⍵×                       ⍝ Yield the integer if so, otherwise 0
{0~⍨{                         ⍝ Remove the zeros from the resulting array

7 Bytes gespart dank Dennis!

Alex A.
quelle
4

R, 55 47 Bytes

(mit etwas Hilfe von @ Alex.A)

cat(grep("10+1",R.utils::intToBin(1:2^scan())))

R hat keine eingebaute Funktion, um konvertierte Zahlen auf bequeme Weise anzuzeigen. Ich verwende R.utils::intToBindiese Funktion, während der Rest so gut wie nur die Position des übereinstimmenden regulären Ausdrucks angibt und an STDOUT druckt, während er durch ein getrennt ist Platz.

David Arenburg
quelle
Ich denke, das Standardtrennzeichen für catist ein Leerzeichen, so dass Sie ,sep=","vollständig weglassen und 7 Bytes sparen könnten .
Alex A.
@AlexA. Ja, kann ich hier ein Leerzeichen als Sep verwenden? Ich war mir nicht sicher
David Arenburg
1
Das OP hat ein Trennzeichen Ihrer Wahl genannt, daher erscheint mir ein Leerzeichen angemessen genug. :)
Alex A.
Braucht das wirklich die Katzenfunktion? Andernfalls wird die Ausgabe tabulatorgetrennt. Der Zähler für die linke Hand ist Teil der Benutzeroberfläche. Wenn Sie ihn in eine Datei schreiben, wird er nicht einbezogen, sodass er nicht Teil der Ausgabe ist.
Freekvd
@freekvd ohne wird nicht auf STDOUT gedruckt. Irgendwas über die albernen Regeln dieser Seite.
David Arenburg
4

CJam, 14

2qi#{2b2,#)},p

3 Bytes kürzer dank Dennis. Probieren Sie es online aus

aditsu
quelle
Wie wäre es 2be`,2>.
Jimmy23013
2
2be`2>und 2,#)sollte auch funktionieren. Außerdem hat das OP klargestellt, dass die Ausgabe in Listenform gedruckt werden kann.
Dennis
4

JavaScript (ES6), 69 68 67 62 Byte

a=>[...Array(1<<a).keys()].filter(i=>/01/.test(i.toString(2)))

Heute habe ich einen neuen, kürzeren Weg gefunden, um Arrays ohne Verwendung von Fill oder Map dynamisch zu füllen. Dadurch x=>[...Array(x).keys()]wird ein Array von 0 bis x zurückgegeben. Wenn Sie Ihren eigenen Bereich / Werte definieren möchten, verwenden Sie x=>[...Array(x)].map((a,i)=>i), da dieser nur einige Bytes länger ist.

Mwr247
quelle
4

Java, 214 165 155 154 148 141 110 Bytes

Diese Übermittlung nutzt die Tatsache aus, dass eine binäre Zeichenfolgendarstellung einer Zahl in Java niemals eine führende Null hat. Wenn der String "01" in der Binärdarstellung einer Zahl erscheint, muss das sein das zweite Vorkommen der Zahl "1" markieren.

Golf gespielt:

String f(int l){String r="";for(long i=5;i<1L<<l;++i)if(Long.toString(i,2).contains("01"))r+=i+", ";return r;}

Ungolfed:

public class NumbersWithMultipleRunsOfOnes {

  public static void main(String[] a) {
    // @formatter:off
    String[][] testData = new String[][] {
      { "3", "5" },
      { "4", "5, 9, 10, 11, 13" },
      { "5", "5, 9, 10, 11, 13, 17, 18, 19, 20, 21, 22, 23, 25, 26, 27, 29" }
    };
    // @formatter:on

    for (String[] data : testData) {
      System.out.println("Input: " + data[0]);
      System.out.println("Expected: " + data[1]);
      System.out.print("Actual:   ");
      System.out.println(new NumbersWithMultipleRunsOfOnes().f(Integer.parseInt(data[0])));
      System.out.println();
    }
  }

  // Begin golf
  String f(int l) {
    String r = "";
    for (long i = 5; i < 1L << l; ++i)
      if (Long.toString(i, 2).contains("01")) r += i + ", ";
    return r;
  }
  // End golf
}

Programmausgabe (denken Sie daran, abschließende Trennzeichen sind akzeptabel):

Input: 3
Expected: 5
Actual:   5, 

Input: 4
Expected: 5, 9, 10, 11, 13
Actual:   5, 9, 10, 11, 13, 

Input: 5
Expected: 5, 9, 10, 11, 13, 17, 18, 19, 20, 21, 22, 23, 25, 26, 27, 29
Actual:   5, 9, 10, 11, 13, 17, 18, 19, 20, 21, 22, 23, 25, 26, 27, 29, 

quelle
Könnten Sie nicht intfür die Zählervariable verwenden ?
Fehler
Alle Integer-Typen in Java sind vorzeichenlos. Um mit einer positiven 32-Bit-Ganzzahl zu arbeiten, ist ein 64-Bit- longWert erforderlich. Darüber hinaus intwürde die Verwendung von a die Größe des Codes erhöhen, da auf die IntegerWrapper-Klasse verwiesen wird, die die Zahlenanalyse durchführt. Ich denke, der wahrscheinlichste Ort, um Platz zu sparen, wäre der .*
Oh, richtig, aber ich dachte, Sie könnten den LongWrapper mit verwenden int? (Nun, nicht in diesem Fall, aber im Allgemeinen?)
Fehler
Ja, das intwird longbei Verwendung als Parameter mit zu befördern Long. In diesem Fall gibt es jedoch keine Möglichkeit, ein " intwegen des Vorzeichens" -Bit zu verwenden, und es Integerist länger als Long. Trotzdem habe ich ein paar Möglichkeiten gefunden, um mehr Platz in einer Sprache zu schaffen, die so ausführlich ist wie Java.
Können Sie new Long()anstelle von verwenden Long.parseLong()?
Ypnypn
4

C (GCC) , 111 99 Bytes

long i,x;main(a,b)char**b;{for(;++i<1L<<atol(b[1]);x>>ffsl(~x)-1&&printf("%ld,",i))x=i>>ffsl(i)-1;}

Probieren Sie es online!

Dank @ceilingcat 12 Bytes rasiert!

Ungolfed:

int main(int a, char **b) {
  for(long i = 0, x = 0; ++i < (1LL << atol(b[1])); ) {
    x = i >> (ffsl(i) - 1);
    if (x >> (ffsl(~x) - 1))
      printf("%ld,", i);
  }
}

Die Funktion ffsl () gibt den Index des ersten Bits an, das in einer langen Ganzzahl gesetzt ist. Also schleifen wir von i = 1zu 2 ^ number_of_bits. Wir setzen xauf inach rechts verschoben , bis wir alle aufeinanderfolgenden Null - Bits auf dem am wenigsten signifikanten Ende entfernt haben. Dann xbewegen wir uns nach rechts, bis wir alle aufeinanderfolgenden 1-Bits am Ende mit der geringsten Signifikanz entfernt haben. Wenn das Ergebnis immer noch nicht Null ist, haben wir eine Übereinstimmung gefunden.

G. Sliepen
quelle
2
Ich muss sagen, dass ich es wirklich mag, wenn jemand eine kleine Manipulationsantwort ausführt, anstatt einen "In String und Regex konvertieren" -Ansatz.
@MichaelT Ich frage mich, ob es eine kurze Lösung gibt, die nur primitive bitweise Operationen verwendet.
Lirtosiast
@ThomasKwa Das könnte eine Herausforderung für den Code sein .
Interessant. Sie können den Test auch folgendermaßen schreiben if (popcount(i ^ (i*2))>3):, und popcount () zu einer Reihe bitweiser UND-Verknüpfungen und Verschiebungsoperationen erweitern. Das würde aber zu recht langem Code führen.
G. Sliepen
1
@ThomasKwa y = x | (x-1), um alle am weitesten rechts liegenden 0-Bits einzuschalten. Dann ist z = y & (y + 1), um alle nachfolgenden 1 Bits auszuschalten. Wenn z ungleich Null ist, hat die ursprüngliche Nummer mehr als einen Lauf hinter sich.
Alchymist
3

JavaScript (ES6) 76

f=n=>Array(1<<n).fill().map((_,x)=>/01/.test(x.toString(2))?x+',':'').join``

//TEST
for(i=1;i<16;i++)O.innerHTML+=i+' -> '+f(i)+'\n'
<pre id=O></pre>

edc65
quelle
@ DLosc Nein, das Ergebnis wäre etwa,,,,,5,,,,9,10,11,,13,,,,17,18,19,20,21,22,23,,25,26,27,,29,,
edc65
3

K5, 19 Bytes

Dies funktioniert nach ähnlichen Prinzipien wie die Lösung von Dennis, jedoch mit weniger integrierten Funktionen.

{&2<+/'~0=':'+!x#2}

Generieren Sie zunächst eine Reihe von binären x-Tupeln ( +!x#2), und suchen Sie dann für jedes Tupel jeden Punkt, an dem eine Ziffer nicht mit der vorherigen übereinstimmt, wenn wir das -1. Element der Liste zu diesem Zweck als 0 behandeln ( ~0=':'). Bei unseren Lösungen sind zwei weniger als die Summe jeder Auflagenanzahl. ( &2<+/').

Das Anzeigen der einzelnen Zwischenschritte ist klarer:

  4#2
2 2 2 2

  !4#2
(0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1
 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1
 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1
 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1)

  +!4#2
(0 0 0 0
 0 0 0 1
 0 0 1 0
 0 0 1 1
 0 1 0 0
 0 1 0 1
 0 1 1 0
 0 1 1 1
 1 0 0 0
 1 0 0 1
 1 0 1 0
 1 0 1 1
 1 1 0 0
 1 1 0 1
 1 1 1 0
 1 1 1 1)

  ~0=':'+!4#2
(0 0 0 0
 0 0 0 1
 0 0 1 1
 0 0 1 0
 0 1 1 0
 0 1 1 1
 0 1 0 1
 0 1 0 0
 1 1 0 0
 1 1 0 1
 1 1 1 1
 1 1 1 0
 1 0 1 0
 1 0 1 1
 1 0 0 1
 1 0 0 0)

  +/'~0=':'+!4#2
0 1 2 1 2 3 2 1 2 3 4 3 2 3 2 1

  2<+/'~0=':'+!4#2
0 0 0 0 0 1 0 0 0 1 1 1 0 1 0 0

  &2<+/'~0=':'+!4#2
5 9 10 11 13

Und alles zusammen:

  {&2<+/'~0=':'+!x#2}'3 4 5 
(,5
 5 9 10 11 13
 5 9 10 11 13 17 18 19 20 21 22 23 25 26 27 29)
JohnE
quelle
2

Pip, 13 + 1 = 14 Bytes

Übernimmt Eingaben von der Befehlszeile und verwendet das -sFlag für Leerzeichen zwischen Ausgabenummern.

01NTB_FI,2**a

Ganz einfach: Bauen range(2**a)und Filtern lambda _: "01" in toBinary(_). Ich war ziemlich glücklich darüber, die 01Idee selbstständig auszudenken. Es sind keine Anführungszeichen erforderlich, 01da die Suche als numerisches Literal ausgeführt wird (Zahlen und Zeichenfolgen sind in Pip vom gleichen Typ).

DLosc
quelle
2

Julia, 40 Bytes

n->filter(i->count_ones(i$i>>1)>2,1:2^n)

Dies verwendet einen etwas anderen Ansatz als die andere Julia-Lösung - anstatt eine Zeichenfolgensuche nach "01" in der Bitfolge durchzuführen, verwendet es eine gewisse Mathematik, um zu bestimmen, ob die Zahl die Bedingung erfüllt.

i$i>>1wird Einsen nur an den Stellen haben, an denen sich die Ziffer von Null auf Eins oder von Eins auf Null ändert. Aus diesem Grund müssen mindestens drei Einsen vorhanden sein i, damit zwischen Null und Eins ausreichend oft hin und her gewechselt werden kann. count_onesFindet die Anzahl von Einsen und filterentfernt dann diejenigen, die nicht genug Einsen haben.

Glen O
quelle
2

C ++, 197 188 141 Bytes

Hinweis: Dies wurde mit MSVC ++ 2013 geschrieben und getestet. Es scheint, dass #includeing<iostream> alle erforderlichen C-Header enthält, damit dies funktioniert. Es scheint auch, dass der Code nicht mehr wirklich C ++ ist, aber das Kompilieren mit C ++ ermöglicht den Headertrick, der die Codegröße im Vergleich zum Einbeziehen einiger C-Header verringert.

Mit printfstatt coutspart man auch ein paar Bytes.

Golf gespielt:

#include<iostream>
int main(int a,char**b){char c[34];for(long i=5;i<1L<<atol(b[1]);++i){_ltoa(i,c,2);if(strstr(c,"01"))printf("%ld\n",i);}}

Ungolfed:

#include <iostream>
int main(int a, char **b) {
  char c[34];
  for (long i = 5; i < 1L << atol(b[1]); ++i) {
    _ltoa(i, c, 2);
    if (strstr(c, "01"))
      printf("%ld\n", i);
  }
}

quelle
Yoiu kann '\n'anstelle von std :: endl (im Allgemeinen) verwenden, oder ','da ein beliebiges Trennzeichen gültig ist und ein nachfolgendes in Ordnung ist.
G. Sliepen
Anstelle von regulären Ausdrücken könnte man es auch einfach so machen strstr(c,"01").
G. Sliepen
@ G.Sliepen danke! Ich habe ehrlich gesagt nur meine Java-Lösung kopiert und in C ++ konvertiert, aber die einfache Lösung ist oft die beste. Ich sollte jetzt wahrscheinlich etwas Ähnliches mit Java machen.
Zwei kleine Fehler: 1<<atol(b[1])sollten sein 1L<<atol(b[1]), sonst ist das Ergebnis dieses Ausdrucks eine vorzeichenbehaftete 32-Bit-Ganzzahl, was bedeutet, dass der Code nur bis zu 2 ^ 30 ausgeführt wird. Mit printf sollten %ldZahlen zwischen 2 ^ 31 und 2 ^ 32 korrekt gedruckt werden.
G. Sliepen
2

Perl 5, 55 53 49 47 41 Bytes

sprintf("%b",$_)=~/01/&&say for 0..2**<>

54 52 48 46 40 Bytes plus eins für das -EFlag anstelle von -e.


Danke an xnor für den Hinweis , /01/stattdessen /10+1/zwei Bytes gespart zu haben.

Vielen Dank an Dennis für den Rat, der <>stattdessen $ARGV[0]sechs Bytes gespart hat.

msh210
quelle
2

C 84 81 Bytes

long i,j,k;main(){for(scanf("%ld",&j);++i<1L<<j;k&k+1&&printf("%ld ",i))k=i|i-1;}

Dies basiert auf den Kommentaren, die ich zu einer anderen C-Antwort auf diese Frage bezüglich der Möglichkeit der Verwendung einfacher bitweiser Operatoren abgegeben habe. Es funktioniert, indem alle nachfolgenden 0-Bits in der Anweisung i | (i-1) auf 1 geschaltet werden. Dann werden alle nachfolgenden 1-Bits mit k & (k + 1) auf 0 geschaltet. Dies führt zu einer Null, wenn es nur einen Lauf von Einsen gibt und ansonsten ungleich Null. Ich gehe davon aus, dass long 64-Bit ist, aber ich könnte dies auf Kosten von drei Bytes korrigieren, indem ich stattdessen int64_t verwende.

Ungolfed

long i,j,k;
main()
{
    for(scanf("%ld",&j);++i<1L<<j;)
    {
        k=i|(i-1);
        if((k&(k+1)) == 0)
            printf("%d ",i);
    }
}
Alchymist
quelle
int64_tist nur bei dir definiert #include<stdint.h>. Um den 64-Bit-Betrieb zu gewährleisten, ist ein long longTyp mit 5 Byte erforderlich .
Chqrlie
Beachten Sie, dass Sie undefiniertes Verhalten aufrufen, das long ials %dFormat übergeben wird. Beachten Sie auch, dass dies ()für die Operatoren &und überflüssig ist |. Das Beheben dieses Problems spart 3 Bytes! long i,j,k;main(){for(scanf("%ld",&j);++i<1L<<j;k&k+1&&printf("%ld ",i))k=i|i-1;}
Chqrlie
@chqrlie Alles sehr gute Punkte. Vielen Dank.
Alchymist
1

Pyth, 20 17 16 Bytes

f:.BT"10+1"ZU^2Q

Live-Demo.

kirbyfan64sos
quelle
Sie können einfach zusammenpassen "01". Mit Ausnahme von 0 wird die binäre Repr. wird immer mit einer 1 beginnen.
Dennis
1

Python 2.7, 89 Bytes

print[i for i in range(1,2**input())if[n[:1]for n in bin(i)[2:].split("0")].count("1")-1]

Ich denke, das könnte ein bisschen golfen werden.

Loovjo
quelle
@ mbomb007 Das habe ich versucht, es hat nicht funktioniert.
Loovjo
@ mbomb007 Verwendest du Python 2.7?
Loovjo
Ist es wichtig, welche Version von 2.7? Ich starte es auf repl.it (2.7.2) und es funktioniert nicht, aber Ideone (2.7.10). Es könnte jedoch nur ein Fehler in repl.it sein, nicht notwendigerweise ein Versionsunterschied.
mbomb007
Ihr Programm druckt falsch 0in der Ausgabe.
mbomb007
Ist auch print[i for i in range(2**input())if[n[:1]for n in bin(i)[2:].split("0")].count("1")-1]zwei Bytes kürzer. Aber mit dem Fix für 0wäre die Länge gleich (89), wenn du benutzt range(1,2**input()).
mbomb007
1

TI-BASIC, 34 32 30 Bytes

Für einen Taschenrechner der Serie TI-83 + / 84 +.

For(X,5,e^(Ans
If log(sum(2=int(4fPart(X/2^randIntNoRep(1,Ans
Disp X
End

Damit eine Zahl zwei 1er-Läufe enthält, muss sie zwei 10s enthalten, wenn wir eine nachgestellte Null in die Binärdarstellung einfügen.

Anstatt die Binärdarstellung zu generieren und nach a zu 10suchen, testen wir Bitpaare mathematisch, indem wir den Rest mit 4 ( int(4fPart() verwenden, was ergibt, 2wo es a gibt 10. Da uns die Reihenfolge egal ist, randIntNoRep(ist dies der kürzeste Weg, um die Liste der Exponenten zu erstellen.

Wir verwenden log(, um die Anzahl der Läufe zu überprüfen:

  • Wenn es mindestens 2 Durchläufe gibt, log(ist der positiv und die Nummer wird angezeigt.

  • Wenn es einen Durchlauf gibt, ist der log(Wert 0 und die Nummer wird nicht angezeigt.

  • Wenn es keine Läufe gibt (was zuerst bei X = 2 ^ Ans passiert), wird log(ein ERR: DOMAIN ausgelöst, wodurch die Ausgabe genau am richtigen Punkt gestoppt wird.

Wir verwenden es e^(Ansals Endargument der For(Schleife - es ist immer größer als 2^Ans, aber es e^(ist ein einzelnes Token, also ein Byte kürzer.

Eingabe / Ausgabe für N = 4:

4:prgmRUNSONES
               5
               9
              10
              11
              13

Dann gibt der Rechner einen Fehler aus; Der Fehlerbildschirm sieht folgendermaßen aus:

ERR:DOMAIN
1:Quit
2:Goto

Wenn 1 gedrückt wird, wird der Startbildschirm erneut angezeigt:

4:prgmRUNSONES
               5
               9
              10
              11
              13
           Error

TI-Taschenrechner speichern alle Zahlen in einem BCD-Gleitkomma mit einer Genauigkeit von 14 Stellen, kein Int- oder Binär-Gleitkomma. Daher kann eine Division durch Potenzen von mehr als zwei 2^14nicht genau sein. Während ich , dass die kniffligsten Zahlen überprüft haben, 3*2^30-1und 2^32-1werden korrekt behandelt, habe ich nicht die Möglichkeit der Rundungsfehler ausgeschlossen. Es würde mich jedoch wundern, wenn es bei der Eingabe Fehler gäbe.

Lirtosiast
quelle
Wie zählt man 32 Bytes? Es sieht aus wie 70 für mich (einschließlich der Zeilenumbrüche).
msh210
TI-BASIC ist tokenisiert; Es wird eine proprietäre Zeichencodierung verwendet, bei der alle diese Befehle jeweils ein Byte und die anderen zwei Byte umfassen. Es ist der Konsens der Community, nach dieser Kodierung zu punkten - siehe meta.codegolf.stackexchange.com/a/4764/39328 für Details.
Lirtosiast
Oh cool. Danke zu Ihrer Information.
msh210
1
  • dies schlägt die antwort von flawr nicht, aber ich konnte dem charme der frage nicht widerstehen

matlab(90)(70)

j=input('');for l=2:j-1,a=1;for k=l:-1:2,a=a+2^k;a:a+2^(k-1)-2,end,end

Ausführung

4

ans =

5

ans =

9    10    11

ans =

13

Prinzip

  • Die Zahlenreihe ergibt sich aus aufeinanderfolgenden Einsen, was f (n, l) = 2 ^ l + 2 ^ (l + 1) + .... 2 ^ n bedeutet

Eine beliebige Zahl aus dem Intervall] f (n, l), f (n, l) + 2 ^ (l-1) [wobei l> 1 diese Bedingung überprüft, sodass das Ergebnis aus der Negation dieser Reihe in resultiert Begriffe von n.

x = 1

x = x + 1 = 01,

x = x + 2 ^ 0 = 11,

x = x + 1 = 001,

x = x + 2 ^ 1 = 011,

x = x + 2 ^ 0 = 111,

x = x + 1 = 0001,

x = x + 2 ^ 2 = 0011,

x = x + 2 ^ 1 = 0111,

x = x + 2 ^ 0 = 0111,

x = x + 1 = 1111...

x + 1, x = x + 2 ^ n, x = x + 2 ^ (n-1) ... x = x + 2 ^ 0

Mein Programm druckt den Bereich zwischen zwei Zeilen (falls vorhanden)


Bearbeiten: leider macht es nicht mehr Golf, aber ich wollte einen anderen Ansatz zur Durchführung dieser Idee hinzufügen

Nach einer Zeit des Kampfes gelang es mir, eine mathematische Darstellung für diese Reihe zu finden:

2 ^ l (0 + 1 + 2 ^ 1 + ... 2 ^ k) mit l + k <n

= 2 ^ l (2 ^ k-1)

Punktzahl = 90

@(n)setdiff(0:2^n-1,arrayfun(@(x)2^mod(x,(n+1)-fix(x/(n+1)))*(2^fix(x/(n+1))-1),0:(n+1)^2))
Abr001am
quelle
1

C, 103 102 Bytes

long i,x;main(int a,char**b){for(;++i<1L<<atoi(b[1]);)for(x=i;x>4&&(x%4!=1||!printf("%ld,",i));x/=2);}

Erweitern (tatsächlich verkleinern) des G.Sliepen-Eintrags, wobei xnicht auf das 01Muster in der Binärdarstellung hingewiesen wird , sondern nur Standardfunktionen und etwas Twiddling verwendet werden.

Ungolfed-Version:

long i, x;
main(int a, char**b) {
    for (; ++i < 1L << atoi(b[1]);) {
        for (x = i; x > 4 && (x % 4 != 1 || !printf("%ld,", i)); x /= 2)
            ;
    }
}

Die innere Schleife sucht inach dem binären Muster, 01indem sie iterativ xnach rechts verschoben wird , solange noch 3 Bits übrig sind. printfgibt die Anzahl der gedruckten Zeichen zurück, also niemals0 . Der Test der inneren Schleife schlägt nach dem fehl, sodass printfkeine breakAnweisung erforderlich ist .

C ++, 129 128 Bytes

In Anlehnung an dieselbe Idee ist die C ++ - Variante hier:

#include<iostream>
long i,x;int main(int a,char**b){for(;++i<1L<<atoi(b[1]);)for(x=i;x>4&&(x%4!=1||!(std::cout<<i<<','));x/=2);}

Technisch gesehen sollte ich ieine long long64-Bit-Operation sicherstellen und bis 2^32zu 5 zusätzliche Bytes berechnen , aber moderne Plattformen haben 64-Bit-Ints.

chqrlie
quelle
1

JavaScript ES6, 60 Byte

Code

n=>[...Array(1<<n).keys()].filter(g=x=>x>4?x%4==1|g(x>>1):0)

Probieren Sie es online!

Erläuterung

[...Array(1<<n).keys()]                                          Create an array of numbers from 0 to 2^n-1
                       .filter(                                  Find the numbers which meet criteria
                               g=x=>x>4?                  :0     If x is less than or equal to four return zero (false/invalid)
                                        x>4?x%4==1|              If the binary pattern ends with 01 return one (true/valid)
                                                   g(x>>1)       Otherwise bitshift right by one and try again
fəˈnəˈtɪk
quelle
0

C (Art - Kompiliert mit Warnungen in GCC) - 103

Dies verwendet keinerlei Bibliotheksfunktionen außer printf. Dies zeigt, dass keine Anstrengungen unternommen wurden, um die Standards zu erfüllen oder UB zu vermeiden.

x,c;main(n,v){n--;for(;c<1<<n;c++)for(v=0;v<32;v++)if(c&1<<v){if(x&&x<v&&printf("%d ",c))break;x=v+1;}}

Um es kompatibel zu machen, müssten Sie viele Dinge tun, wie z. B. stdio.h, was gegen den Geist wäre, es so klein wie möglich zu machen.

Wenn jemand Vorschläge zur Verkürzung hat, lass es mich wissen.

Jerry Jeremiah
quelle
0

PowerShell, 80 Byte

while([Math]::Pow(2,$args[0])-gt$n++){$n|?{[Convert]::ToString($n,2)-match"01"}}
Andrew
quelle
0

Python, 44 Bytes

Okay, das könnte wahrscheinlich kürzer sein, aber es ist mein erster Codegolf:

x=1
while True:
    if '01' in bin(x):
        print(x)
    x+=1

Denken Sie, dies beantwortet die Frage, bitte stimmen Sie nicht ab, wenn dies nicht der Fall ist.

Zachary Smith
quelle
1
Sie müssen Eingaben vornehmen ( input()ist ideal), um eine Endlosschleife zu erhalten n, und dann nur bis zu zählen 2^n-1. Außerdem können Sie anstelle von 4 und 8 1 und 2 Leerzeichen für die Verschachtelung verwenden, und die Verwendung von mapoder eines Listenverständnisses würde Ihren Code wahrscheinlich erheblich verkürzen.
Mego
0

Eine weitere andere Matlab-Antwort von guter Punktzahl.

matlab 60(57)

@(n)find(mod(log2(bitcmp(1:2^n,fix(log2(1:2^n)+1))+1),1))

Ausführung

>> @(n)find(mod(log2(bitcmp(1:2^n,fix(log2(1:2^n)+1))+1),1))

ans =

@(n)find(mod(log2(bitcmp(1:2^n,fix(log2(1:2^n)+1))+1),1))

>> ans(5)

ans =

 5     9    10    11    13    17    18    19    20    21    22    23    25    26    27    29

  • Die Idee ist, Zahlen x aufzunehmen, bei denen die binäre Darstellung von - (x) +1 nicht nur ein Vorkommen von enthält1

Beispiel:

0000111wird abgelehnt, weil ~ x = 1111, ~ x + 1 = 00001eine Ziffer = 1 enthält

0100111wird akzeptiert, weil ~ x = 1011, ~ x + 1 = 0111viele Einsen enthält

Abr001am
quelle