Baum-Sweet Sequence (A086747 with a Twist)

Weź dodatnią liczbę całkowitą ni wydrukuj liczby całkowite od 1 do n, dla których sekwencja Baum-Sweet zwraca wartość true. Sekwencja Bauma-Sweeta powinna zwrócić wartość falsy, jeśli binarna reprezentacja liczby zawiera nieparzystą liczbę kolejnych zer w dowolnym miejscu liczby, i tak naprawdę jest inaczej. Aby uzyskać więcej informacji, kliknij link. Oto kilka przykładów:

1 -> 1 -> Truthy
2 -> 10 -> Falsy
3 -> 11 -> Truthy
4 -> 100 -> Truthy (Even run of zeros)

Oto podany przykład n=32

Krok 1: Wizualizacja sekwencji Baum-Sweet n=32

1               1 (1)
1 0             0 (2)
11              1 (3)
1 00            1 (4)
1 0 1           0 (5)
11 0            0 (6)
111             1 (7)
1 000           0 (8)
1 00 1          1 (9)
1 0 1 0         0 (10)
1 0 11          0 (11)
11 00           1 (12)
11 0 1          0 (13)
111 0           0 (14)
1111            1 (15)
1 0000          1 (16)
1 000 1         0 (17)
1 00 1 0        0 (18)
1 00 11         1 (19)
1 0 1 00        0 (20)
1 0 1 0 1       0 (21)
1 0 11 0        0 (22)
1 0 111         0 (23)
11 000          0 (24)
11 00 1         1 (25)
11 0 1 0        0 (26)
11 0 11         0 (27)
111 00          1 (28)
111 0 1         0 (29)
1111 0          0 (30)
11111           1 (31)
1 00000         0 (32)

Po obliczeniu sekwencji Bauma-Sweeta dla n, weź liczby, które były zgodne z prawdą dla sekwencji i zbierz je dla ostatecznego wyniku. Na n=32to mamy:

[1, 3, 4, 7, 9, 12, 15, 16, 19, 25, 28, 31]

Jako ostateczna odpowiedź.

To jest golf golfowy , wygrywa najmniejsza liczba bajtów.

05AB1E , 10 9 bajtów

Oszczędność bajtu dzięki Adnanowi

ƒNb00¡SP–

Wypróbuj online!

Wyjaśnienie

ƒ          # for N in [0 ... input]
 Nb        # convert N to binary
   00¡     # split at "00"
      S    # convert to list of digits
       P   # product of list
        –  # if 1, print N

JavaScript (ES6), 70 68 63 bajtów

g=n=>n?g(n-1).concat(/0/.test(n.toString(2).split`00`)?[]:n):[]

console.log(g(1000).join(", "))

Nieco ciekawsze rozwiązanie rekurencyjne:

n=>[...Array(n+1).keys()].filter(f=n=>n<2?n:n%4?n&f(n>>1):f(‌​n/4))

67 bajtów dzięki @Neil.

g to funkcja do wywołania.

Python 2, 62 bajty

g=lambda n:n*[0]and g(n-1)+[n]['0'in`bin(n)[1:].split('00')`:]

Sprawdza nieparzyste przebiegi 1 w reprezentacji binarnej, dzieląc 00i sprawdzając, czy w reprezentacji łańcuchowej wynikowej listy pozostały zera. Irytujące są liczby binarne zaczynające się 0bod zera, który należy usunąć, aby uniknąć fałszywie dodatniego wyniku.

Wyliczenie odbywa się poprzez rekurencję w dół.

Grzmotnąć, 58, 46 bajtów

EDYCJE:

• Zastąpione bc z DC (Thx @Digital Trauma!)
• Zacznij od 1;

Grał w golfa

seq $1|sed 'h;s/.*/dc -e2o&p/e;s/00//g;/0/d;x'

Test

>./baum 32
1 
3
4
7 
9
12
15
16
19
25
28
31

Wyjaśnił

muszla

seq $1 #generate a sequence of integers from 1 to N, one per line
|sed   #process with sed

sed

h                #Save input line to the hold space
s/.*/dc -e2o&p/e #Convert input to binary, with dc
s/00//g          #Remove all successive pairs of 0-es
/0/d             #If there are still some zeroes left
                 #(i.e. there was at least one odd sequence of them)
                 #drop the line, proceed to the next one
x                #Otherwise, exchange the contents of the hold 
                 #and pattern spaces and (implicitly) print

Wypróbuj online!

Partia, 143 bajty

@for /l %%i in (1,1,%1)do @call:c %%i
@exit/b
:c
@set/ai=%1
:l
@if %i%==1 echo %1&exit/b
@set/ar=%i%%%4,i/=4-r%%2*2
@if %r% neq 2 goto l

Perl 6 , 40 bajtów

{grep {.base(2)!~~/10[00]*[1|$]/},1..$_}

Spróbuj

{
  grep            # find all of them
  {
    .base(2)      # where the binary representation
    !~~           # does not match
    /
      10          # ｢10｣
      [ 00 ]*     # followed by an even number of ｢0｣s
      [ 1 | $ ]   # either at end or before a ｢1｣
    /
  }, 1 .. $_      # from one to the input
}

( []są używane do grupowania nie przechwytywania, z <[]>klasami znaków)

PowerShell , 79 61 bajtów

1..$args[0]|?{0-notin([convert]::ToString($_,2)-split'1|00')}

Wypróbuj online!

Dziś rano zainspirowałem się, aby zmienić sposób wykonywania -splitoperacji, a następnie przekonać się, że jest to podobne do budowy odpowiedzi xnor , więc myślę, że wielkie umysły myślą podobnie?

Pętlujemy od 1wejścia do wejścia $args[0]i używamy Where-Objectoperatora, aby wyciągnąć odpowiednie liczby |?{...}. Klauzula jest prostą wartością logiczną - zapewniamy, że 0są -notinto wyniki (...).

Wewnątrz parenów bierzemy [convert]::bieżącą liczbę $_ ToStringz podstawą 2(tzn. Zamieniamy ją na ciąg binarny). Następnie -splitciąg znaków w wyrażeniu regularnym 1|00- jest to zachłanne dopasowanie i skutkuje tablicą ciągów (na przykład 100010zamieniłoby się w '','','0','','0'itd.).

Tak więc, jeśli każdy 0ciąg s w ciągu binarnym jest parzysty (co oznacza, że ​​wyrażenie regularne podzieliło je na puste ciągi), to 0będzie -notinwynik, więc Whereklauzula jest prawdziwa, a liczba jest wybrana. Te liczby są pozostawione w potoku, a dane wyjściowe są niejawne.

Python 2 , 67 47 bajtów

f=lambda n,k=1:n/k*[1]and[k]+f(n,k-~k)+f(n,4*k)

Dzięki @xnor do gry w golfa z 20 (!) Bajtów!

Zwraca nieuporządkowaną listę. Jest dość wydajny: wejście 100 000 zajmuje około 40 ms w TIO.

Wypróbuj online!

Mathematica, 59 bajtów

Select[Range@#,!Or@@OddQ/@Tr/@Split[1-#~IntegerDigits~2]&]&

Mathematica odpowiedź numer 4 ...

MATL , 12 11 bajtów

:"@BY'og)?@

Wypróbuj online!

Wyjaśnienie

Aby wykryć, czy liczba jest poprawna, konwertuje się na binarną, stosuje kodowanie długości przebiegu, zachowuje tylko przebiegi o nieparzystej długości i sprawdza, czy nie zachodzi żaden ciąg zer.

:       % Take input n implicitly. Push range [1 2 ... n]
"       % For each k in [1 2 ... n]
  @     %   Push k
  B     %   Convert to binary
  Y'    %   Run-length encoding. Pushes array of values and array of run-lengths
  o     %   Parity. Gives array that contains 0 for even lengths, 1 for odd
  g)    %   Convert to logical and use index into the array of values
  ?     %   If the result does not contain zeros
    @   %     Push k
        %   End
        % End
        % Implicitly display stack 

R, 75 bajtów

for(i in 1:scan()){x=rle(miscFuncs::bin(i));if(!any(x$l%%2&!x$v))cat(i,"")}

Odczytuje dane wejściowe ze standardowego wejścia i używa binfunkcji z miscFuncspakietu do konwersji z wektora dziesiętnego na binarny. W konsekwencji wykonuje kodowanie długości przebiegu, aby sprawdzić wartości, == 0a długości są nieparzyste.

Skumulowane , 69 bajtów

Wypróbuj tutaj!

:>1+[bits{e.b:e b 0#=}chunkby[0 has]filter$sizemap 2%0 eq all]"filter

Lub niekonkurencyjny przy 67 bajtach:

:>1+[bits{e.b:e b 0#=}chunkby[0 has]filter$sizemap even all]"filter

I jeszcze więcej niekonkurencyjnych przy 49 bajtach:

:>1+[bits rle{k:k 0=}filter values even all]fkeep

Wszystkie przyjmują dane wejściowe jako TOS i pozostawiają dane wyjściowe w TOS.

Wyjaśnienie

:>1+[...]"filter   input: n
:>                 range from [0, n)
  1+               range from [1, n]
    [...]          a function
         "filter   apply to each cell and filter

Funkcja:

bits{e.b:e b 0#=}chunkby[0 has]filter$sizemap 2%0 eq all  input: c
bits                                                      convert c to binary
    {e.b:e b 0#=}chunkby                                  split into chunks of contiguous 0s
                        [0 has]filter                     take only chunks with 0s
                                     $sizemap             map each chunk to its size
                                              2%          vectorized modulus 2
                                                0 eq      vectorized equality with 0
                                                     all  all of them are of even lengths

Wyjaśnienie niekonkurencyjnych:

Jest taki sam jak powyżej, z kilkoma kluczowymi różnicami:

:>1+[bits rle{k:k 0=}filter values even all]fkeep   input: y
          rle                                       run length encode y
             {k:k 0=}filter                         keep keys that = 0
                            values                  get those values
                                            fkeep   like `filter`, but is implemented with
                                                    taking `f` as a boolean mask

Befunge, 84 51 49 bajtów

Po drobnych eksperymentach zdałem sobie sprawę, że mogę zrobić trochę lepiej niż moje oryginalne rozwiązanie, stosując technikę podobną do odpowiedzi wsadowej, którą wymyślił Neil .

<v::\<&1
:_v#:/+2*2!%2:_v#-2%4
:$<@_v#!:-1\+1$<:.

Wypróbuj online!

Podobnie jak w moim oryginalnym rozwiązaniu, istnieją dwie pętle - zewnętrzna pętla iterująca liczby, które chcemy przetestować, oraz wewnętrzna pętla testująca sekwencję bitów dla każdej liczby. Sposób działania testu polega na badaniu dwóch bitów na raz (moduł 4 bieżącej wartości). Jeśli jest to równe 2, mamy nieparzystą sekwencję zer i możemy przerwać wewnętrzną pętlę i przejść do następnej liczby.

Jeśli moduł 4 nie jest równy 2, musimy kontynuować testowanie pozostałych bitów, więc przesuwamy bity, które zostały już przetestowane. Odbywa się to poprzez podzielenie wartości, nazwijmy ją n , przez2+2*!(n%2) . Oznacza to, że jeśli pierwszy bit miał wartość 1, dzielimy przez 2 (upuszczając ten 1 bit), ale jeśli był to 0, dzielimy przez 4, więc zawsze będziemy upuszczać pary zer.

Jeśli w końcu dojdziemy do zera, oznacza to, że nie było żadnych dziwnych sekwencji zerowych bitów, więc wypisujemy liczbę.

Visual Basic (.net 4.5) 163 bajty

Pierwsza odpowiedź tutaj, więc jestem pewien, że coś spieprzyłem. Daj mi znać, a naprawię. Czy lambda Visual Basic są w ogóle dozwolone?

Dzięki MamaFunRoll za pomysł na usunięcie kolejnych zer

Dim R=Sub(m)System.Console.WriteLine(String.Join(",",System.Linq.Enumerable.Range(1, m).Where(Function(s) Not Convert.ToString(s,2).Replace("00","").Contains(0))))

Wyjścia R (32)

1,3,4,7,9,12,15,16,19,25,28,31

Java, 144 130 128 bajtów

Nie jest to tak golfowe, jak mi się wydaje, ale pomyślałem, że byłoby uroczym rozwiązaniem, aby użyć Regexa, mimo że nigdy go nie użyłem.

Gra w golfa:

static String a(int n){String s="";for(Integer i=0;i++<n;)if(i.toString(i,2).replaceAll("00|1","").isEmpty())s+=i+" ";return s;}

Nie golfowany:

static String a(int n){
    String s="";                      //Cheaper than using a list/array
    for(Integer i=0;i++<n;)           //Loop n times
        if(i.toString(i,2)            //Convert int to base 2 string
                .replaceAll("00|1","")//Find and remove ones and consecutive zeroes
                .isEmpty())           //If any chars remain, i is truthy
            s+=i+" ";                 //Append i to the storage string
    return s;                         //Return all values
}

Edycja: Udało mi się zapisać 14 bajtów, tworząc wyrażenie regularne 00 | 1 zamiast 00 i usuwając „.replace („ 1 ”,„ ”)” między replaceAll i isEmpty!

Edycja 2: Byłem w stanie zapisać 2 bajty, czyniąc i liczbą całkowitą i odwołując się do Integer.toString za pomocą i.toString.

Clojure, 103 bajty

Nie sądzę, że to najkrótsza droga ...

#(remove(fn[v]((set(map(fn[s](mod(count s)2))(re-seq #"0+"(Integer/toString v 2))))1))(range 1(inc %)))

Używa re-seqdo znajdowania kolejnych zer, mapuje ich długości modulo-2 na a set, odrzuca je, jeśli liczba 1zostanie znaleziona z zestawu.

Cud , 38 bajtów

@(!>@=1len iO0Rstr#["00"]bn#0)rng1+1#0

Stosowanie:

(@(!>@=1len iO0Rstr#["00"]bn#0)rng1+1#0) 32

Wyjaśnienie

Bardziej czytelny:

@(
  fltr@
    = 1 
      len 
        iO 0 
          Rstr #["00"] 
            bn #0
) rng 1 +1 #0

rng 1 +1 #0: Zakres od 1 do wejścia.

fltr@ ...: Zakres filtru z następującym predykatem.

bn #0: Konwertuj bieżący element na binarny. (To będzie miało wiodące 0b).

Rstr #["00"]: Rekurencyjnie przycinaj wszelkie wystąpienia 00ciągu.

len iO 0: Policz ilości 0s w ciągu.

=1: Sprawdź, czy kwota jest równa 1. Jeśli pozostała tylko 0część łańcucha po przycinaniu znajduje się na początku 0b, to zwraca wartość true; w przeciwnym razie zwraca false.

Rubin, 78 69 68 bajtów

->n{(1..n).select{|m|m.to_s(s=2).split(?1).map{|i|s|=i.size};s&1<1}}

Starsza wersja:

->n{(1..n).select{|m|m.to_s(2).split(?1).select{|i|i.size%2>0}[0].!}}
->n{(1..n).select{|m|b=z=0;(m.to_s(2)+?1).each_char{|i|z+=i>?0?b|=z:1};b&1<1}}

Mathematica, 81 bajtów

Select[Range@#,FreeQ[Union@#+Mod[Length@#,2,1]&/@Split[#~IntegerDigits~2],{1}]&]&

Oblicza dla każdego przebiegu kolejnych cyfr w liczbie {wspólna cyfra w tym przebiegu plus (1, jeśli długość jest nieparzysta, 2, jeśli długość jest parzysta)}; jeśli którakolwiek z odpowiedzi to {1}, to liczby nie ma w sekwencji.

Mathematica, 75 bajtów

Select[Range@#,And@@EvenQ/@Length/@Cases[Split[#~IntegerDigits~2],{0..}]&]&

#~IntegerDigits~2oblicza listę cyfr binarnych wejścia #. Splittę listę do serii identycznych elementów, weź Casesto dopasowanie {0..}, weź Lengthkażdy z nich, weź EvenQdługości, a następnie zwróć Andwyniki.

Python 3, 86 82 bajtów

Gra w golfa w toku ...

lambda n:[x for x in range(1,n+1)if 1-any(i%2for i in map(len,bin(x).split('1')))]

Grałem w golfa 4 bajty, zmieniając bin(x)[2:]na just bin(x)- pozostawia to 0bna początku łańcucha, ale zdałem sobie sprawę, że to tak naprawdę nie wpływa na obliczenia :)

Python, 142 bajty

Ma to głównie na celu ćwiczenie gry w golfa w moim Pythonie.

def o(n):
 r=0
 for i in bin(n)[2:]:
  if i=='1':
   if r&1:return 0
   r=0
  else:r+=1
 return ~r&1
lambda n:[i for i in range(1,n+1)if o(i)]

Galaretka , 10 bajtów

2ṗx"`ḂḄf@R

Okropnie nieefektywny. Wypróbuj online!

Rubin, 54 53 48 bajtów

->n{(1..n).reject{|x|x.to_s(2)=~/10(00)*(1|$)/}}

Nie sądziłem, że regex tego będzie tak prosty.

edycja 1: przełączono na odrzucanie, aby pozbyć się negacji dla -1.

edycja 2: zmieniono matchna =~na -5.

C # 159 157 155 bajtów

Zaoszczędź 2 x dwa bajty dzięki TuukkaX.

Uwaga: wypisuje ints w odwrotnej kolejności.

void B(int n){var b=Convert.ToString(n,2);int c=0,i=0;for(;i<b.Length;){if(b[i++]<49)c++;else if(c%2>0)break;}if(c%2<1)Console.WriteLine(n);if(n>1)B(--n);}

Wyjaśnienie:

void B(int n)
{
    // convert our int to a binary string
    var b = Convert.ToString(n, 2);

    // set our '0' counter 'c' and our indexer 'i' 
    int c = 0, i = 0;

    // loop over the binary string, without initialisation and afterthought
    for (; i < b.Length;)
    {
        // check for '0' (48 ASCII) and increment i. increment c if true
        if (b[i++] < 49)
            c++;

        // otherwise check if c is odd, and break if it is
        else if (c%2 > 0)
            break;
    }

    // print the int if c is even
    if (c%2 < 1)
        Console.WriteLine(n);

    // recursively call B again with the next number
    if (n > 1)
        B(--n);
}

Mathematica, 69 bajtów

Select[Range@#,FreeQ[#~IntegerDigits~2//.{x___,0,0,y___}:>{x,y},0]&]&

Ta sama długość:

Select[Range@#,#~IntegerString~2~StringDelete~"00"~StringFreeQ~"0"&]&

Ruby, 53 bajtów

->n{(1..n).each{|n|p n if n.to_s(2).count(?0).even?}}

Galaretka, 15 13 10 bajtów

zapisał dwa bajty po przeanalizowaniu innych odpowiedzi, kolejne 3 bajty dzięki Dennisowi

Bœṣ0,0Ȧµ€T

Wyjaśnienie

Bœṣ0,0Ȧµ€T -Helper link: argument K (integer): ex. 24
B          -Convert K to a list of its binary digits: 24 -> [1,1,0,0,0]
   0,0     -Create a list of two 0's: [0,0]
 œṣ        -Split the binary digits on instances of the sublist: [1,1,0,0,0]-> [[1,1],[0]]
      Ȧ    -Any and All: Check if our list has any falsy values or is empty
       µ   -Take all our previous atoms and wrap them into one monad.
        €  -Map this new monad over a list. Since our input is an integer, this implicitly maps it over the range [1..N] (Like the 'R' atom)
         T -Get the indices of all truthy values (1's)