Inspiré par le quatrième problème de BMO2 2009 .

Étant donné un entier positif n en entrée ou un paramètre, renvoyer le nombre d'entiers positifs dont les représentations binaires se produisent sous forme de blocs dans l'expansion binaire de n .

Par exemple, 13 -> 6 car 13 en binaire est 1101 et il a des sous-chaînes 1101, 110, 101, 11, 10, 1. Nous ne comptons pas les nombres binaires qui commencent par zéro et nous ne comptons pas zéro lui-même.

Cas de test

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

Vous pouvez prendre n comme l'un des éléments suivants:

• un nombre entier
• une liste de valeurs véridiques / fausses pour la représentation binaire
• une chaîne pour la représentation binaire
• une chaîne de base 10 (même si je ne sais pas pourquoi quelqu'un ferait cela)

Faites votre code aussi court que possible.

Python 3, 54 50 octets

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

Merci à Rod et Jonathan Allan d'avoir économisé quatre octets.

Gelée , 4 octets

ẆQSḢ

Essayez-le en ligne!

Prend la saisie sous forme de liste de 0s et 1s.

Essayez-le en ligne avec des chiffres!

Explication:

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

Preuve que ça marche:

Ce programme reçoit un numéro d'entrée, N . La première chose que ce produit fait est, bien sûr, de prendre les sous-chaînes de N ₂ ( N en base 2 ). Cela inclut les sous-chaînes en double commençant par 0 ou 1 .

Après cela, nous prenons simplement les sous-chaînes uniques en ne gardant que la première occurrence de chaque valeur dans la liste des sous-chaînes.

Ensuite, ce programme additionne les premiers éléments des listes, puis les deuxièmes éléments, puis les troisième, quatrième, etc. et si l'une des listes n'a pas un tel élément 0est supposé. Ce que le défi demande est effectivement Combien de sous-chaînes uniques commençant par 1 ce nombre a-t-il dans sa forme binaire? . Puisque chaque premier élément qui doit être compté l'est 1, nous pouvons simplement additionner au lieu de filtrer les sous-chaînes appropriées.

Maintenant, le premier élément de la liste résultante de la sommation décrite ci-dessus contient le décompte des premiers bits des sous-chaînes, donc nous simplement pop et finalement le retourner.

Octave , 62 61 octets

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

Essayez-le en ligne!

Explication

Pour l'entrée n, le code teste tous les nombres de 1à npour voir si leur représentation binaire est une sous-chaîne de la représentation binaire de l'entrée.

@(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 octets

Prend l'entrée comme une chaîne binaire.
L'en-tête convertit l'entrée entière en binaire pour faciliter les tests.

ŒCÙĀO

Essayez-le en ligne!

Explication

Π       # 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 octets

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

Essayez-le en ligne!

Prend l'entrée comme une chaîne binaire.

PowerShell , 103 92 82 octets

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

Essayez-le en ligne!

Prend l'entrée comme un tableau de 1et 0(vérité et falsey dans PowerShell). Boucle à travers $s(c'est-à-dire, combien d'éléments dans le tableau d'entrée). À l'intérieur de la boucle, nous bouclons du numéro actuel (enregistré sous $i) jusqu'à $s.count. Chaque boucle interne, nous -joinla tranche de tableau dans une chaîne. Nous avons ensuite sortavec le -udrapeau nique (qui est plus court selectqu'avec le -udrapeau nique et nous ne nous soucions pas qu'ils soient triés ou non), prenons ceux qui ne commencent pas 0et prenons le tout .count. Cela reste sur le pipeline et la sortie est implicite.

JavaScript (ES6), 55 octets

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

Prend l'entrée comme une chaîne binaire.

Voici une triste tentative de le faire avec des nombres et des fonctions récursives:

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)

Ancienne approche, 74 octets

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

Prend également l'entrée comme une chaîne binaire.

Python 2 ,  118  81 octets

Merci à @Rod pour avoir économisé 37 octets!

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

Prend l'entrée comme une chaîne binaire.

Essayez-le en ligne!

Python 2 , 81 octets

Merci à @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]})

Prend l'entrée comme une chaîne binaire.

Essayez-le en ligne!

Gelée , 5 octets

ẆḄQṠS

Essayez-le en ligne!

Prend l'entrée comme une liste de 1 et de 0. Le pied de page du lien applique la fonction à chacun des exemples de l'article.

Jonathan Allan a souligné qu'il ẆḄQTLs'agit d'une alternative à 5 octets qui utilise l' Tatome qui trouve les indices de tous les éléments véridiques.

Explication

Prenons l'exemple de bin (13) = 1101. L'entrée est[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

A pris l'idée de "vérité" (signe dans ce cas) de la réponse 05AB1E

R , 88 77 octets

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

Essayez-le en ligne!

Prend l'entrée comme une chaîne binaire.

à l'aide de mapply, génère un tableau de toutes les sous-chaînes de l'entrée. strtoiles convertit en 2entiers de base , et je prends la somme de la conversion logique ( !!) des entrées dans le résultat.

Rétine , 37 29 octets

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

Essayez-le en ligne!Je viens d'essayer le wmodificateur de Retina 1.0 . Edit: 8 octets enregistrés grâce à @MartinEnder. Explication:

.+
*

Convertissez de décimal en unaire.

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

Conversion d'unaire en binaire, en utilisant #pour 0et_ pour 1.

wp`_.*

Générer des sous - chaînes qui commencent par 1, je veux dire, _. Le wmodificateur correspond alors à toutes les sous-chaînes, pas seulement la plus longue à chaque démarrage _, tandis que le pmodificateur déduplique les correspondances. Enfin, comme il s'agit de la dernière étape, le nombre de correspondances est renvoyé implicitement.

Pyth , 8 octets

l #{vM.:

Essayez-le ici!

Prend l'entrée comme une chaîne binaire.

.:génère toutes les sous-chaînes, vMévalue chacune (c'est-à-dire qu'elle convertit chacune en binaire), {dédoublonne, <space>#filtre par identité et lobtient la longueur.

Wolfram Language (Mathematica) , 35 octets

Compter les sous-séquences uniques de la représentation binaire qui commencent par une, même si je ne suis pas sûr que ce code ait même besoin d'une explication.

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

Essayez-le en ligne!

Perl 6 , 47 octets

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

Essayez-le en ligne!

Julia 0.6 , 37 octets

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

Essayez-le en ligne!

Juliafication de la réponse Python par J843136028 à l' aide .d'une application de fonction élément par élément avec diffusion. ( lien )

Java, 232 octets

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();

Où n est l'entrée, b est la représentation binaire et l est une liste de toutes les sous-chaînes. Pour la première fois ici, vous devez absolument vous améliorer et n'hésitez pas à signaler toute erreur! Légèrement édité pour plus de lisibilité.

Attaché , 35 octets

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

Essayez-le en ligne!

De manière équivalente:

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

Explication

J'expliquerai la deuxième version, car elle est plus facile à suivre (en étant explicite):

{#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)

Rubis 41 36 27 octets

Prend une chaîne binaire en entrée

Est ultra-inefficace

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

Partiellement inspiré par cette réponse python 3

Essayez-le en ligne!

Java 8, 160 159 158 octets

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

Entrée sous forme de chaîne binaire.
Il doit y avoir un chemin plus court ..>.>

Explication:

Essayez-le en ligne.

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 octets

#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();}

Il s'agit d'une fonction récursive. Nous utilisons a std::setpour compter les valeurs, en ignorant les doublons. Les deux appels récursifs masquent les bits à gauche ( f(n&i)) et à droite (f(n/2) ), produisant éventuellement toutes les sous-chaînes sous forme d'entiers.

Notez que si vous souhaitez l'appeler à nouveau, sdoit être effacé entre les appels.

Programme de test

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

Résultats

./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 octets

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

Essayez-le en ligne!

J , 15 octets

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

L'entrée est une liste binaire. Essayez-le en ligne!

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

Perl 6 , 34 octets

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

Essaye-le

Étendu:

{
  +                                # 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
                                )
}