Inspirowany czwartym problemem z BMO2 2009 .

Biorąc pod uwagę dodatnią liczbę całkowitą n jako dane wejściowe lub parametr, zwróć liczbę liczb całkowitych dodatnich, których reprezentacje binarne występują jako bloki w binarnym rozwinięciu n .

Na przykład 13 -> 6, ponieważ 13 w systemie binarnym to 1101 i ma podciągi 1101, 110, 101, 11, 10, 1. Nie liczymy liczb binarnych rozpoczynających się od zera i nie liczymy samego zera.

Przypadki testowe

13 -> 6
2008 -> 39
63 -> 6
65 -> 7
850 -> 24
459 -> 23
716 -> 22
425 -> 20
327 -> 16

Możesz wziąć n jako jeden z poniższych:

• Liczba całkowita
• lista wartości prawda / fałsz dla reprezentacji binarnej
• ciąg reprezentacji binarnej
• ciąg podstawowy 10 (choć nie jestem pewien, dlaczego ktoś miałby to zrobić)

Ustaw swój kod tak krótko, jak to możliwe.

Python 3, 54 50 bajtów

lambda n:sum(bin(i)[2:]in bin(n)for i in range(n))

Podziękowania dla Rod i Jonathan Allan za uratowanie czterech bajtów.

Galaretka , 4 bajty

ẆQSḢ

Wypróbuj online!

Pobiera dane wejściowe jako listę 0s i 1s.

Wypróbuj online z numerami!

Wyjaśnienie:

ẆQSḢ Argument: B = list of bits, e.g. [1, 1, 0, 1]
Ẇ    Get B's non-empty sublists (i.e. [[1], [1], [0], [1], [1, 1], [1, 0], [0, 1], [1, 1, 0], [1, 0, 1], [1, 1, 0, 1]])
 Q   Keep first occurrences (i.e. [[1], [0], [1, 1], [1, 0], [0, 1], [1, 1, 0], [1, 0, 1], [1, 1, 0, 1]])
  S  Reduce by vectorized addition (i.e. [6, 4, 1, 1])
   Ḣ Pop first element (i.e. 6)

Dowód to działa:

Ten program pobiera numer wejścia, N . Pierwszą rzeczą, którą robi ten produkt, jest oczywiście pobranie podciągów N ₂ ( N w bazie 2 ). Obejmuje to zduplikowane podciągi zaczynające się od 0 lub 1 .

Następnie po prostu bierzemy unikalne podciągi, zachowując tylko pierwsze wystąpienie każdej wartości na liście podciągów.

Następnie ten program sumuje pierwsze elementy list, następnie drugie elementy, a następnie trzeci, czwarty itd. I jeśli jedna z list nie ma takiego elementu, 0zakłada się. Zadanie polega na tym, ile efektywnie Ile unikatowych podciągów zaczynających się od 1 ma ten numer w postaci binarnej? . Ponieważ każdy pierwszy element, który należy policzyć 1, możemy po prostu sumować zamiast filtrować pod kątem odpowiednich podciągów.

Teraz pierwszy element wynikowej listy podsumowania opisanej powyżej zawiera liczbę pierwszych bitów podciągów, więc po prostu wstawiamy i ostatecznie zwracamy.

Oktawa , 62 61 bajtów

@(n)sum(arrayfun(@(t)any(strfind((g=@dec2bin)(n),g(t))),1:n))

Wypróbuj online!

Wyjaśnienie

W przypadku danych wejściowych nkod sprawdza wszystkie liczby od, 1aby nsprawdzić, czy ich reprezentacja binarna jest podciągiem binarnej reprezentacji danych wejściowych.

@(n)                                                          % Anonymous function of n
        arrayfun(                                      ,1:n)  % Map over range 1:n
                 @(t)                                         % Anonymous function of t
                         strfind(               ,    )        % Indices of ...
                                                 g(t)         % t as binary string ...
                                 (g=@dec2bin)(n)              % within n as binary string
                     any(                             )       % True if contains nonzero
    sum(                                                    ) % Sum of array

05AB1E , 5 bajtów

Pobiera dane wejściowe jako ciąg binarny.
Nagłówek konwertuje liczbę całkowitą na binarną, co ułatwia testowanie.

ŒCÙĀO

Wypróbuj online!

Wyjaśnienie

Π       # push all substrings of input
 C       # convert to base-10 int
  Ù      # remove duplicates
   Ā     # truthify (convert non-zero elements to 1)
    O    # sum

Perl 5 , 36 + 1 ( -p) = 37 bajtów

/.*(.+?)(?{$k{0|$1}++})(?!)/;$_=%k-1

Wypróbuj online!

Pobiera dane wejściowe jako ciąg binarny.

PowerShell , 103 92 82 bajtów

param($s)(($s|%{$i..$s.count|%{-join$s[$i..$_]};$i++}|sort -u)-notmatch'^0').count

Wypróbuj online!

Pobiera dane wejściowe jako tablicę 1i 0(truey i falsey w PowerShell). Pętle przechodzą przez $s(tzn. Ile elementów w tablicy wejściowej). Wewnątrz pętli zapętlamy od bieżącego numeru (zapisanego jako $i) do $s.count. W każdej wewnętrznej pętli -jointablica kroimy na ciąg. Następnie sortz -uflagą nique (która jest krótsza niż selectz -uflagą nique i nie obchodzi nas, czy są posortowane, czy nie), bierzemy te, które nie zaczynają się od 0, i bierzemy całość .count. Pozostaje to w potoku, a dane wyjściowe są niejawne.

JavaScript (ES6), 55 bajtów

f=(s,q="0b"+s)=>q&&s.includes((q--).toString(2))+f(s,q)

Pobiera dane wejściowe jako ciąg binarny.

Oto smutna próba zrobienia tego za pomocą liczb i funkcji rekurencyjnych:

f=(n,q=n)=>q&&(g=n=>n?n^q&(h=n=>n&&n|h(n>>1))(q)?g(n>>1):1:0)(n)+f(s,q-1)

Stare podejście, 74 bajty

s=>(f=s=>+s?new Set([+s,...f(s.slice(1)),...f(s.slice(0,-1))]):[])(s).size

Pobiera również dane wejściowe jako ciąg binarny.

Python 2 ,  118  81 bajtów

Dzięki @Rod za oszczędność 37 bajtów!

lambda n:len({int(n[i:j+1],2)for i in range(len(n))for j in range(i,len(n))}-{0})

Pobiera dane wejściowe jako ciąg binarny.

Wypróbuj online!

Python 2 , 81 bajtów

Dzięki @Rod!

lambda n:len({n[i:j+1]for i in range(len(n))for j in range(i,len(n))if'1'==n[i]})

Pobiera dane wejściowe jako ciąg binarny.

Wypróbuj online!

Galaretka , 5 bajtów

ẆḄQṠS

Wypróbuj online!

Pobiera dane wejściowe jako listę 1 i 0. Stopka w łączu stosuje funkcję do każdego z przykładów w poście.

Jonathan Allan wskazał, że ẆḄQTLjest to 5-bajtowa alternatywa, która korzysta zT atom, który znajduje wskaźniki wszystkich prawdziwych elementów.

Wyjaśnienie

Weźmy jako przykład bin (13) = 1101. Dane wejściowe to[1,1,0,1]

ẆḄQṠS
Ẇ       All contiguous sublists -> 1,1,0,1,11,10,01,110,101,1101 (each is represented as a list)
 Ḅ      From binary to decimal. Vectorizes to each element of the above list -> 1,1,0,1,3,2,1,6,5,13
  Q     Unique elements
   Ṡ    Sign. Positive nums -> 1 , 0 -> 0.
    S   Sum

Wziął pomysł „prawda” (znak w tym przypadku) z odpowiedzi 05AB1E

R , 88 77 bajtów

function(x)sum(!!unique(strtoi(mapply(substring,x,n<-1:nchar(x),list(n)),2)))

Wypróbuj online!

Pobiera dane wejściowe jako ciąg binarny.

using mapply, generuje tablicę wszystkich podciągów danych wejściowych. strtoikonwertuje je jako bazę2 liczby całkowite i biorę sumę logicznej konwersji ( !!) pozycji w wyniku.

Retina , 37 29 bajtów

.+
*
+`(_+)\1
$1#
#_
_
wp`_.*

Wypróbuj online! Musiałem tylko wypróbować Retina 1.0w modyfikator . Edycja: Zapisano 8 bajtów dzięki @MartinEnder. Wyjaśnienie:

.+
*

Konwertuj z dziesiętnego na jednoargumentowy.

+`(_+)\1
$1#
#_
_

Konwertuj z jednoargumentowego na binarny, używając #for 0i_ for 1.

wp`_.*

Generowanie podciągi, które zaczynają się 1, znaczy _. wModyfikator następnie dopasowuje wszystkie podciągi, nie tylko najdłuższy jednym przy każdym rozruchu _, natomiast pmodyfikujących deduplikuje mecze. Wreszcie, ponieważ jest to ostatni etap, domyślnie zwracana jest liczba dopasowań.

Pyth , 8 bajtów

l #{vM.:

Wypróbuj tutaj!

Pobiera dane wejściowe jako ciąg binarny.

.:generuje wszystkie podciągi, vMocenia każdy (czyli konwertuje każdy z binarnego), {deduplikuje, <space>#filtruje według tożsamości i lotrzymuje długość.

Wolfram Language (Mathematica) , 35 bajtów

Zliczanie unikatowych podsekwencji reprezentacji binarnej, które zaczynają się od jednej, chociaż nie jestem pewien, czy ten kod wymaga nawet wyjaśnienia.

Union@Subsequences@#~Count~{1,___}&

Wypróbuj online!

Perl 6 , 47 bajtów

->\n{+grep {n.base(2).contains(.base: 2)},1..n}

Wypróbuj online!

Julia 0.6 , 37 bajtów

~n=sum(contains.([bin(n)],bin.(1:n)))

Wypróbuj online!

Juliafikacja odpowiedzi w języku Python autorstwa J843136028 przy użyciu .aplikacji funkcji elementu z rozgłaszaniem. ( link )

Java, 232 bajty

String b=toBin(n);
l.add(b);
for(int i=1;i<b.length();i++){
for(int j=0;j<=b.length()-i;j++){
String t="";
if((""+b.charAt(j)).equals("0"))continue;
for(int k=0;k<i;k++){
t+=""+b.charAt(j+k);
}
if(!l.contains(t))l.add(t);
}
}
return l.size();

Gdzie n jest wejściem, b jest reprezentacją binarną, a l jest listą wszystkich podciągów. Po raz pierwszy zamieszczając tutaj, zdecydowanie musisz poprawić i nie krępuj się wskazać ewentualne błędy! Nieznacznie zredagowano pod kątem czytelności.

Attache , 35 bajtów

`-&1@`#@Unique@(UnBin=>Subsets@Bin)

Wypróbuj online!

Równoważnie:

{#Unique[UnBin=>Subsets[Bin[_]]]-1}

Wyjaśnienie

Wyjaśnię drugą wersję, ponieważ łatwiej jest ją śledzić (mówiąc wprost):

{#Unique[UnBin=>Subsets[Bin[_]]]-1}
{                                 }   lambda: _ = first argument
                        Bin[_]        convert to binary
                Subsets[      ]       all subsets of input
         UnBin=>                      map UnBin over these subsets
  Unique[                      ]      remove all duplicates
 #                              -1    size - 1 (since subsets is improper)

Ruby 41 36 27 bajtów

Pobiera ciąg binarny jako dane wejściowe

Jest bardzo nieefektywny

->n{(?1..n).count{|j|n[j]}}

Częściowo zainspirowany tą odpowiedzią na python 3

Wypróbuj online!

Java 8, 160 159 158 bajtów

import java.util.*;b->{Set s=new HashSet();for(int l=b.length(),i=0,j;i<l;i++)for(j=l-i;j>0;s.add(new Long(b.substring(i,i+j--))))s.add(0L);return~-s.size();}

Wprowadź jako ciąg binarny.
Musi być krótsza droga ..>.>

Wyjaśnienie:

Wypróbuj online.

import java.util.*;          // Required import for Set and HashSet
b->{                         // Method with String as parameter and integer as return-type
  Set s=new HashSet();       //  Create a Set
  for(int l=b.length(),      //  Set `l` to the length of the binary-String
      i=0,j;i<l;i++)         //  Loop from 0 up to `l` (exclusive)
    for(j=l-i;j>0;           //   Inner loop from `l-i` down to `0` (exclusive)
      s.add(new Long(b.substring(i,i+j--))))
                             //    Add every substring converted to number to the Set
      s.add(0L);             //    Add 0 to the Set
  return~-s.size();}         //  Return the amount of items in the Set minus 1 (for the 0)

C ++, 110 bajtów

#include<set>
std::set<int>s;int f(int n){for(int i=1;i<n;i+=i+1)f(n&i);return n?s.insert(n),f(n/2):s.size();}

To jest funkcja rekurencyjna. Używamy a std::setdo zliczania wartości, ignorując duplikaty. Dwie rekurencyjne wywołania maskują bity od lewej ( f(n&i)) i od prawej (f(n/2) ), ostatecznie wytwarzając wszystkie podciągi jako liczby całkowite.

Pamiętaj, że jeśli chcesz zadzwonić ponownie, smusisz wyczyścić między połączeniami.

Program testowy

#include <cstdlib>
#include <iostream>

int main(int, char **argv)
{
    while (*++argv) {
        auto const n = std::atoi(*argv);
        s={};
        std::cout << n << " -> " << f(n) << std::endl;
    }
}

Wyniki

./153846 13 2008 63 65 850 459 716 425 327
13 -> 6
2008 -> 39
63 -> 6
65 -> 7
850 -> 24
459 -> 23
716 -> 22
425 -> 20
327 -> 16

J , 34 bajty

f=.3 :'<:#~.,(#:i.2^##:y)#.;.1#:y'

Wypróbuj online!

J , 15 bajtów

#.\\.#@=@-.&,0:

Dane wejściowe to lista binarna. Wypróbuj online!

#.\\.               Convert every substring to decimal
         -.&,0:     Flatten and remove the 0s.        
     #@=            How many unique elements?

Perl 6 , 34 bajtów

{+unique ~«(.base(2)~~m:ex/1.*/)}

Sprawdź to

Rozszerzony:

{
  +                                # turn into Numeric (number of elements)
   unique                          # use only the unique ones
          ~«(                      # turn into strings
             .base(2)              # the input in base 2
                     ~~
                       m:ex/1.*/   # :exhaustive match substrings
                                )
}