Pour trouver la dureté numérique d'un entier, prenez sa représentation binaire et comptez le nombre de fois où un début et un retour 1peuvent être supprimés jusqu'à ce qu'il commence ou se termine par a 0. Le nombre total de bits supprimés est sa dureté numérique.

C'est une explication assez verbeuse - alors décomposons-la avec un exemple concret.

Pour cet exemple, nous utiliserons le nombre 3167. En binaire, c'est:

110001011111

(Notez que, lors de la conversion en binaire, vous devez vous assurer de supprimer les zéros non significatifs)

Il ne commence ni ne se termine par 0, nous supprimons donc 1 paire de bits:

1  1000101111  1

Et un autre:

11  00010111  11

Mais maintenant, il y a un 0 au début, donc nous ne pouvons plus supprimer de 1paires. Au total, 4 bits que nous avons supprimés, et donc 4 est la dureté numérique de 3167.

Cependant, pour les nombres qui peuvent être écrits comme 2 ⁿ -1 pour n positif (c'est-à-dire qu'ils ne contiennent que 1dans une représentation binaire), 0 ne sera jamais atteint, et donc tous les bits peuvent être supprimés. Cela signifie que la dureté est simplement la longueur de bits de l'entier.

Le défi

Votre tâche consiste à écrire un programme ou une fonction qui, étant donné un entier non négatif n >= 0, détermine sa dureté numérique.

Vous pouvez soumettre un programme complet qui effectue des E / S, ou une fonction qui renvoie le résultat. Votre soumission doit fonctionner pour des valeurs comprises ndans la plage d'entiers standard de votre langue.

Cas de test

Veuillez m'informer si l'une de ces erreurs est incorrecte ou si vous souhaitez suggérer des cas supplémentaires à ajouter.

0     -> 0
1     -> 1
8     -> 0
23    -> 2
31    -> 5
103   -> 4
127   -> 7
1877  -> 2
2015  -> 10

Voici la solution Python non golfée que j'ai utilisée pour générer ces cas de test (non garantis sans bug):

def hardness(num) -> int:
    binary = bin(num)[2:]

    if binary.count('0') == 0:
        return num.bit_length()

    revbin = binary[::-1]

    return min(revbin.find('0'), binary.find('0')) * 2

Gelée , 11 10 octets

BµQL××Ṛa\S

Essayez-le en ligne!

Comment ça marche

BµQL××Ṛa\S  Main link. Argument: n

B           Binary; convert n to base 2.
 µ          Begin a new, monadic chain. Argument: A (array of binary digits)
  Q         Unique; deduplicate the digits.
   L        Length; count the unique digits.
    ×       Multiply each digit by the result.
     ×Ṛ     Multiply the results by reversed A.
       a\   Cumulative reduce by logical AND.
            This zeroes out all elements after the first zero.
         S  Compute the sum of the result.

Python , 76 69 68 63 62 60 57 octets

f=lambda n,k=0:n>>k&(n&n>>k>n>>k+1)and(n&n+1>0)-~f(n,k+1)

Essayez-le en ligne!

Comment ça marche

Il s'agit d'une solution récursive qui prend une entrée n et continue à incrémenter k - à partir de 0 - tandis que LSB _k (n) (bit à l'index k de droite) et MSB _k (n) (bit à l'index k de gauche) sont définis. Une fois terminé, il retourne k si tous les bits de n sont définis et 2k sinon.

Commençons par réécrire le lambda f en fonction nommée F , avec une variable auxiliaire t .

def F(n, k = 0):
    t = n >> k
    return t & (n & t > t >> 1) and (n & (n + 1) > 0) + 1 + F(n, k + 1)

Dans chaque invocation de F , nous décalons d'abord n un total de k unités vers la droite et stockons le résultat dans t . De cette façon, LSB ₀ (t) = LSB _k (n) , donc t est impair si et seulement si LSB _k (n) est défini.

Il est légèrement plus difficile de déterminer si MSB _k (n) est défini; c'est ce qui n & t > t >> 1réussit. Pour illustrer son fonctionnement, considérons un entier n = 1αβγδεζη ₂ de longueur binaire 8 et analysons l'appel de fonction F (n, 3) , c'est-à-dire k = 3 .

Nous essayons de déterminer si MSB ₃ (n) = γ est défini en examinant la valeur de vérité de la comparaison (n & t> t >> 1) = (1αβγδεζη ₂ & 1αβγδ ₂ > 1αβγ ₂ ) . Examinons les entiers impliqués.

MSB-index  012k4567

n          1αβγδεζη
t             1αβγδ

t >> 1         1αβγ

Nous affirmons que γ = 1 si et seulement si n & t> t >> 1 .

• Si γ = 1 , alors n & t a une longueur de bit 5 tandis que t >> 1 a une longueur de bit 4 , donc n & t> t >> 1 .

  Cela prouve que γ = 1 implique n & t> t >> 1 .

• Si n & t> t >> 1 , il y a deux options: soit γ = 1, soit γ = 0 . Dans le premier cas, il n'y a plus rien à prouver.

  Dans le second cas, on a que αβγδ ₂ ≥ n & t> t >> 1 = 1αβγ ₂ .

  Puisque αβγδ ₂ > 1αβγ ₂ , nous devons avoir MSB ₀ (αβγδ ₂ ) ≥ MSB ₀ (1αβγ ₂ ) , ce qui signifie que α = 1 .

  De cette façon, 1βγδ ₂ > 11βγ ₂ , nous devons donc avoir MSB ₁ (1βγδ ₂ ) ≥ MSB ₁ (11βγ ₂ ) , ce qui signifie que β = 1 .

  À son tour, cela implique que 11γδ ₂ > 111γ ₂ . En se souvenant que γ = 0 dans le second cas, on obtient l'inégalité 110δ ₂ > 1110 ₂ , ce qui est faux puisque MSB ₂ (110δ ₂ ) = 0 <1 = MSB ₂ (1110 ₂ ) .

  Ainsi, seul le premier cas est possible et n & t> t >> 1 implique γ = 1 .

En résumé, si LSB _k (n) et MSB _k (n) sont définis, t sera impair et n & t> t >> 1 sera Vrai , donc t & (n & t> t >> 1) sera rendement 1 . Cependant, si LSB _k (n) ou MSB _k (n) n'est pas défini (ou si les deux le sont), t sera pair ou n & t> t >> 1 sera faux , donc t & (n & t> t> > 1) donnera 0 .

L'appel de F avec un seul argument initialise k = 0 . Bien que la condition dont nous avons discuté précédemment soit vérifiée, le code suivant andest exécuté, qui (entre autres) appelle récursivement F avec k incrémenté .

Une fois que LSB _k (n) ou MSB _k (n) n'est pas défini, la condition échoue et F (n, k) renvoie 0 . Chacun des k appels de fonction précédents ajoute (n & (n + 1)> 0) + 1 à F (n, k) = 0 , donc F (n) renvoie ((n & (n + 1)> 0) + 1) k .

Maintenant, si tous les bits de n sont égaux (c'est-à-dire, si n est soit 0 ou que tous ses bits sont définis), n + 1 n'aura aucun bit en commun avec n , donc n & (n + 1) = 0 et F (n) renvoie k . Cependant, si n a à la fois des bits définis et non définis, n & (n + 1)> 0 et F (n) renvoie 2k .

MATL , 13 12 octets

Btv`6L&)}x@q

Essayez-le en ligne! Ou vérifiez tous les cas de test .

Explication

Le code répète chaque chiffre binaire et compte le nombre de fois où il est possible d'en supprimer deux externes.

B        % Input number (implicit). Horizontal vector of binary digits
tv       % Duplicate and concatenate vertically
`        % Do...while
  6L&)   %   Flatten the array if needed (in column-major order), and split it
         %   into two subarrays: one with the inner entries, and another
         %   with the two outer entries. The latter will be used for deciding
         %   if the loop continues or is exited
}        % Finally (execute before exiting the loop)
  x      %   Delete last subarray of inner entries
  @q     %   Push last iteration index minus 1
         % End (implicit). The next iterarion is executed if the array at the
         % top of the stack is non-empty and only contains nonzero values. 
         % Otherwise the loop is exited, executing the "finally" block first
         % Display (implicit)

Python, 82 octets

J'ai l'impression qu'il peut encore être joué au golf, mais j'ai passé un certain temps à essayer différentes méthodes et c'était la plus courte.

def f(n):b=bin(n)[2:];x=min(b.find('0'),b[::-1].find('0'));print(x<0)*len(b)or x*2

Essayez-le en ligne

Bien que cela fonctionne de manière similaire au programme Python de l'OP, je l'ai créé avant la publication de la question, après avoir consulté la question dans le bac à sable, qui ne contenait pas un tel programme.

Python 2, 66 octets

s=bin(input())[2:].split('0')
print len(min(s[-1],s[0]))<<1%len(s)

Divise la représentation binaire de l'entrée en morceaux de 1. Compte le nombre de 1 dans le plus petit du premier et du dernier morceau, puis le double, à moins qu'il n'y ait un seul morceau que cela double.

PowerShell , 109106 octets

$a=[convert]::ToString($args[0],2)-split0;(((($b=$a[0].length),$a[-1].length|sort)[0]*2),$b)[$a.count-eq1]

Essayez-le en ligne!

Prend entrée $args[0], utilise l'appel .NET convertil toStringavec une base 2( par exemple, rendre binaire), puis -splits cette chaîne sur 0s, les magasins qui en $a. Important à noter: l'appel .NET ne renvoie pas de zéros non significatifs, donc le premier chiffre est toujours a 1.

Il y a donc deux possibilités - la chaîne binaire est toute une, ou il y avait au moins un zéro. On différencie ceux avec un pseudo-ternaire indexé par $a.count-eq1. Si le binaire a au moins un zéro, le cas de gauche, on prend le minimum de la longueur de la première [0]chaîne de 1s et de la dernière [-1]chaîne (trouvée par |sortpuis [0]). Le plus court de ceux-ci est le plus de paires que nous pourrions retirer, donc nous multiplions cela par 2. Notez que si la chaîne binaire d'origine se termine par un 0, comme pour l'entrée 8, le [-1].lengthsera également 0(car il s'agit d'une chaîne vide), qui, lorsqu'il est multiplié par, 2est toujours 0.

Sinon, avec la chaîne binaire tous les uns, nous prenons juste $b(qui était précédemment défini pour être la longueur de la première [0]chaîne, dans ce cas, l'intégralité de la chaîne binaire).

Dans les deux cas, ce résultat est laissé sur le pipeline et la sortie est implicite.

JavaScript (ES6), 57 octets

f=
n=>n.toString(2).replace(/^(1*)(.*(\1))?$/,'$1$3').length

<input oninput=o.value=1/this.value?f(+this.value):''><input id=o readonly>

Prend le binaire et essaie de faire correspondre tous 1sou à défaut un nombre égal de début et de fin 1s.

Rétine , 48 octets

.+
$*
+`(1+)\1
$1o
o1
1
m(+`^1(.*)1$
xx¶$1
x|^1$

Essayez-le en ligne

Explication:

.+              # Convert to unary
$*
+`(1+)\1        # Convert to binary (but with `o` instead of `0` -- it's shorter)
$1o
o1
1
m(+`^1(.*)1$    # Replace pairs of surrounding ones with `xx`
xx¶$1
x|^1$,          # Count x's, including the possibility of a single remaining `1`

C #, 133 octets

Fonction qui rend la dureté. Prend un entier de l'argument.

int h(int b){var n=Convert.ToString(b,2);for(b=0;;){if(n[0]+n[n.Length-1]==98)n=n.Substring(1,n.Length-2);else break;b+=2;}return b;}

Eh bien, aujourd'hui, je l'ai découvert '1' + '1' = 98en C #.

C, 89 88 85 octets

Enregistré deux octets en raison de @FlipTack soulignant une déclaration inutile.

Appelez f()avec le numéro à tester, la sortie est renvoyée par la fonction.

t,h;f(l){for(t=l;t&&~t&1<<30;t*=2);for(h=0;t&1<<30&&l&1;t*=2,l/=2)++h;return h<<!!l;}

Essayez-le sur ideone .

JavaScript (ES6), 59 58 octets

f=(n,m=1<<30)=>m>n?f(n,m/2):m>1?n&m&&n&1&&2+f(n/2,m/4):n&1

Cas de test

f=(n,m=1<<30)=>m>n?f(n,m/2):m>1?n&m&&n&1&&2+f(n/2,m/4):n&1

console.log(
  [0, 1, 8, 23, 31, 103, 127, 1877, 2015].map(
    n => n + ' -> ' + f(n)
  ).join('\n')
)

Gelée , 14 octets

Eo2
BµŒg.ịṂS×Ç

Essayez-le en ligne!

C, 137 132 122 119 119 117 114 98 94 92 87 85 Octets

Il est temps de commencer à jouer au golf B-)

i,j;f(n){for(i=1<<30;i&~n;i/=2);for(j=0;n&i;n/=2,i/=4)j+=~n&1?i=0:2;return j-=n<1*j;}

Voici la preuve

main()
{
  printf("%d %d\n", 0, f(0));
  printf("%d %d\n", 1, f(1));
  printf("%d %d\n", 8, f(8));
  printf("%d %d\n", 23, f(23));
  printf("%d %d\n", 31, f(31));
  printf("%d %d\n", 103, f(103));
  printf("%d %d\n", 127, f(127));
  printf("%d %d\n", 1877, f(1877));
  printf("%d %d\n", 2015, f(2015));
  printf("%d %d\n", 3167, f(3167));
} 

et la sortie;

0 0
1 1
8 0
23 2
31 5
103 4
127 7
1877 2
2015 10
3167 4 

Java (OpenJDK) , 181 156 150 octets

n->{int i=0;String s=n.toString(n,2);if(s.matches("1*"))i=s.length();else for(;!s.matches("(.*0)|(0.*)");s=s.substring(1,s.length()-1))i+=2;return i;}

Essayez-le en ligne!

Mathematica, 63 56 octets

(2-Min[l=#~IntegerDigits~2])Min[Tr/@Split[l][[{1,-1}]]]&

Explication

l=#~IntegerDigits~2

Générez la représentation en base 2 de l'entrée, enveloppée d'un List. Stockez cela dansl

(2-Min[...])

Si l'élément min de lest 1, sortie 1. Sinon, sortie 2. Multipliez ceci par ...

Split[l]

Divisé len pistes.

... [[{1,-1}]]

Prenez le premier et le dernier élément.

Tr/@ ...

Prenez le total des deux.

Min[ ... ]

Trouvez le plus petit entre les deux.

(Multipliez le premier résultat (1 ou 2) par ce résultat).

Octave, 56 54 octets

 @(n)cummin(d=dec2bin(n)-48)*cummin(flip(d))'*2^!all(d)

Essayez-le en ligne!

Explication:

d=dec2bin(n)-48

représentation binaire de n

cumd= cummin(d);
cumfd = cummin(flip(d));

Prendre les minutes cumulées d et les minutes cumulées de retournéesd

res = cumd * cumfd ';

faire une multiplication matricielle

out = res*2^!all(d)

multipliez par 2 si tous les chiffres sont 1;

Pyth, 18 octets

?*FJjQ2lJyhSxR0_BJ

Un programme qui prend l'entrée d'un entier et imprime le résultat.

Suite de tests (première ligne de mise en forme)

Comment ça marche

?*FJjQ2lJyhSxR0_BJ  Program. Input: Q
?                   If
  F                 reducing
    jQ2             the binary representation of Q as a list
   J                (store in J)
 *                  by multiplication is truthy:
       lJ            Yield len(J)
                    Else:
          hS         Yield the minimum
            xR0      of the first index of zero
               _BJ   in J and its reverse
         y           * 2
                    Implicitly print

APL, 26 octets

+/∘(∧\≢↑(∊⊢(,∧∧)¨⌽))2⊥⍣¯1⊢

Cas de test:

      ( +/∘(∧\≢↑(∊⊢(,∧∧)¨⌽))2⊥⍣¯1⊢ ) ¨ 0 1 8 23 31 103 127 1877 2015    
0 1 0 2 5 4 7 2 10

Explication:

+ / ∘ (∧ \ ≢ ↑ (∊⊢ (, ∧∧) ¨⌽)) 2⊥⍣¯1⊢

                         ⊢ entrée
                    2⊥⍣¯1 convertir en représentation binaire
   ()
        (⊢ ¨⌽) pour chaque bit et son bit correspondant de l'autre côté
            (∧) prendre le logique et les deux bits,
             , faites une liste des deux bits,
              ∧ puis prendre le et de la liste et le et
         ∊ aplatir le tableau résultant
      ≢ ↑ ne prend que les N premiers bits, où N est le
                                longueur de la liste originale de bits
    ∧ \ prendre une logique en cours d'exécution (en ne laissant
                                ceux de départ)
+ / ∘ additionne ces

J, 22 octets

(#<.2*(<.&(#.~)|.))@#:

Ceci est basé sur l'astuce soignée tirée de ce défi .

Essayez-le en ligne!

Explication

(#<.2*(<.&(#.~)|.))@#:  Input: integer n
                    #:  Binary digits of n
(                 )@    Operate on those digits D
               |.         Reverse D
       <.                 Take the minimum of
         &(#.~)           the "trailing truths" of D and reverse(D)
    2*                    Multiply by 2
 #                        The length of D
  <.                      Minimum of length and the previous result

PHP, 83 74 octets

3 + 6 octets enregistrés par Jörg

<?=(~$s=decbin($argn))[$a=strspn($s,1)]?min($a,strspn(strrev($s),1))*2:$a;

prend l'entrée de STDIN; courir avec -nR.

panne

<?=                     # print ...
(~
    $s=decbin($argn)        # $s = binary representation of input
)[
    $a=strspn($s,1)         # $a = number of leading `1`s
]                           # if $s has more than $a digits,
?   min($a,                     # 2. minimum of $a and
        strspn(strrev($s),1)    # 1. number of trailing `1`s
    )*2                         # 3. *2
:   $a                      # else $a (==strlen)

JavaScript (ES6), 83 octets

f=x=>(y=x.toString(2),y.match(/^1*$/)?y:([s,e]=y.match(/^1*|1*$/g),s<e?s:e)).length

Non golfé:

function f(n) {
    var binStr = n.toString(2);
    if(binStr.match(/^1*$/)) {
        // If binary representation is all 1s, return length of binary
        return binStr.length;
    } else {
        // Grab the starting and ending 1s in the binary representation
        var [start1s, end1s] = binStr.match(/^1*|1*$/g);
        var startHardness = start1s.length;
        var endHardness = end1s.length;
        return Math.min(startHardness, endHardness);
    }
}

Mathematica, 62 octets

(h=0;#~IntegerDigits~2//.{{1,m___,1}:>(h+=2;{m}),{1}:>h++};h)&

Fonction pure où #représente le premier argument.

(h=0;...;h)&définit h=0, fait un tas de choses ..., puis retourne h(la dureté). Regardons le tas de choses:

#~IntegerDigits~2                                     Binary representation of the input
                 //.                                  Apply the following list of rules repeatedly until there is no change
                    {                                 Start of the list of rules
                     {1,m___,1}                       If you see a list starting and ending with 1 with the sequence m (possibly empty) in between
                               :>(h+=2;{m}),            replace it with just {m} after incrementing h twice.
                                            {1}       If you see the singleton list {1}
                                               :>h++    replace it with h, then increment h.
                                                    } End of the list of rules

Merci à Greg Martin de m'avoir présenté cette astuce .

Haskell , 94 92 octets

b 0=[]
b n=mod n 2:b(div n 2)
h n|(c,_:_)<-span(>0)$zipWith(*)n$reverse n=c++c|1<3=n
sum.h.b

Essayez-le en ligne! Usage:

Prelude> sum.h.b $ 3167
4

Explication:
b convertit un nombre en binaire et renvoie en premier une liste de zéro et de uns avec le bit le moins significatif. Dans h, cette liste est inversée et multipliée par élément avec la liste d'origine, puis span(>0)se divise après le 1s initial :

       b 3167 = [1,1,1,1,1,0,1,0,0,0,1,1] = n
    reverse n = [1,1,0,0,0,1,0,1,1,1,1,1] = m
zipWith(*)n m = [1,1,0,0,0,0,0,0,0,0,1,1] = z
   span(>0) z = ([1,1],[0,0,0,0,0,0,0,0,1,1])

Le tuple résultant est mis en correspondance avec le modèle (c,_:_)où _:_correspond à toute liste non vide, donc c = [1,1]. Parce que les octets sont supprimés à l'avant et à l'arrière, il c++c = [1,1,1,1]est renvoyé et finalement résumé pour donner la dureté numérique .

Si la deuxième liste du tuple est vide, alors la représentation binaire n'en contient que quelques-unes, et le nombre de celles-ci est la dureté numérique. Avec le modèle correspondant, les hretours ont échoué n, ce qui est à nouveau résumé.

Perl, 61 octets

sub f{$_=sprintf('%b',pop);length(/0/?/^(1+).*\1$/&&$1x2:$_)}

Le cœur de ceci est le regex /^(1+).*\1$/où 2 fois la longueur de $1est la réponse. Le reste du code est en surcharge et traite du cas spécial de all 1.

PHP, 65 octets

<?=strlen(preg_filter('#^(1*)(.*(\1))?$#',"$1$3",decbin($argn)));

Version en ligne

CJam, 14 octets

ri2b_0#\W%0#e<

Explication:

ri e# Read integer:      | 3167
2b e# Convert to binary: | [1 1 0 0 0 1 0 1 1 1 1 1]
_  e# Duplicate:         | [1 1 0 0 0 1 0 1 1 1 1 1] [1 1 0 0 0 1 0 1 1 1 1 1]
0# e# Index of first 0:  | [1 1 0 0 0 1 0 1 1 1 1 1] 2
\  e# Swap:              | 2 [1 1 0 0 0 1 0 1 1 1 1 1]
W% e# Reverse:           | 2 [1 1 1 1 1 0 1 0 0 0 1 1]
0# e# Index of first 0:  | 2 5
e< e# Minimum:           | 2