26
\$\begingroup\$

To find the digital hardness of an integer, take its binary representation, and count the number of times both a leading and trailing 1 can be removed until it either start or ends with a 0. The total number of bits removed is its digital hardness.

That's quite a wordy explanation - so let's break it down with a worked example.

For this example, we'll use the number 3167. In binary, this is:

110001011111

(Note that, during the conversion to binary, you should make sure to strip leading zeroes)

It doesn't start or end with 0, so we remove 1 pair of bits:

1  1000101111  1

And another:

11  00010111  11

But now there is a 0 at the beginning, so we can't remove anymore 1 pairs. In total, 4 bits we removed, and so 4 is the digital hardness of 3167.

However, for numbers that can be written as 2n-1 for positive n (i.e. contain only 1 in binary representation), 0 will never be reached, and so all the bits can be removed. This means that the hardness is simply the integer's bit length.


The Challenge

You task is to write a program or function which, given a non-negative integer n >= 0, determines its digital hardness.

You can submit a full program which performs I/O, or a function which returns the result. Your submission should work for values of n within your language's standard integer range.


Test Cases

Please notify me if any of these are incorrect, or if you'd like to suggest any edge cases to add.

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

Here's the ungolfed Python solution which I used to generate these test cases (not guaranteed to be bug-less):

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
\$\endgroup\$
  • 1
    \$\begingroup\$ How does 1 return 1 when there is no 0 in it whatsoever? I mean, you can't possibly remove enough 1's from the string to have the it start or end in 0. \$\endgroup\$ – busukxuan Jan 6 '17 at 20:06
  • 2
    \$\begingroup\$ @busukxuan Read the paragraph just before the "The Challenge" heading: for numbers that can be written as 2^n-1 (i.e. contain only 1 in binary representation), 0 will never be reached, and so all the bits can be removed. This means that the hardness is simply the integer's bit length. \$\endgroup\$ – FlipTack Jan 6 '17 at 20:06
  • 2
    \$\begingroup\$ @busukxuan you can think of it as the number of ones each side is padded with, before zeroes are reached. \$\endgroup\$ – FlipTack Jan 6 '17 at 20:09
  • 2
    \$\begingroup\$ To the downvoter who obviously didn't like the edge cases: The hardness is the number of solid (1) bits it is padded with - if the whole thing is solid, then surely it has 100% hardness, its whole bit length? \$\endgroup\$ – FlipTack Jan 6 '17 at 20:18
  • 1
    \$\begingroup\$ @FlipTack I don't want to influence too much, it's your challenge. I initially understood "hardness" as the maximum number of pairs of outer ones that can be removed, one from each side. But you may be right, if a single one remains at the end, perhaps it should be counted in \$\endgroup\$ – Luis Mendo Jan 6 '17 at 20:24

26 Answers 26

6
\$\begingroup\$

Jelly, 11 10 bytes

BµQL××Ṛa\S

Try it online!

How it works

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.
\$\endgroup\$
8
\$\begingroup\$

Python, 76 69 68 63 62 60 57 bytes

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

Try it online!

How it works

This is a recursive solution that takes an input n and keeps incrementing k – starting at 0– while both LSBk(n) (bit at index k from the right) and MSBk(n) (bit at index k from the left) are set. Once finished, it returns k if all of n's bit are set and 2k if not.

Let's start by rewriting the lambda f as a named function F, with an auxiliary variable 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)

In each invocation of F, we first bit-shift n a total of k units to the right and store the result in t. This way, LSB0(t) = LSBk(n), so t is odd if and only if LSBk(n) is set.

Determining whether MSBk(n) is set is slightly trickier; this is what n & t > t >> 1 achieves. To illustrate how it works, let's consider an integer n = 1αβγδεζη2 of bit-length 8 and analyze the function call F(n, 3), i.e., k = 3.

We're trying to determine whether MSB3(n) = γ is set by examining the truth value of the comparison (n & t > t >> 1) = (1αβγδεζη2 & 1αβγδ2 > 1αβγ2). Let's examine the involved integers.

MSB-index  012k4567

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

t >> 1         1αβγ

We claim that γ = 1 if and only if n & t > t >> 1.

  • If γ = 1, then n & t has bit-length 5 while t >> 1 has bit-length 4, so n & t > t >> 1.

    This proves that γ = 1 implies n & t > t >> 1.

  • If n & t > t >> 1, there are two options: either γ = 1 or γ = 0. In the first case, there's nothing left to prove.

    In the second case, we have that αβγδ2 ≥ n & t > t >> 1 = 1αβγ2.

    Since αβγδ2 > 1αβγ2, we must have MSB0(αβγδ2) ≥ MSB0(1αβγ2), meaning that α = 1.

    This way, 1βγδ2 > 11βγ2, so we must have MSB1(1βγδ2) ≥ MSB1(11βγ2), meaning that β = 1.

    In turn, this implies that 11γδ2 > 111γ2. Remembering that γ = 0 in the second case, we get the inequality 110δ2 > 11102, which is false since MSB2(110δ2) = 0 < 1 = MSB2(11102).

    Thus, only the first case is possible and n & t > t >> 1 implies γ = 1.

Summing up, if both LSBk(n) and MSBk(n) are set, t will be odd and n & t > t >> 1 will be True, so t & (n & t > t >> 1) will yield 1. However, if LSBk(n) or MSBk(n) is unset (or if both are), t will be even or n & t > t >> 1 will be False, so t & (n & t > t >> 1) will yield 0.

Calling F with a single argument initializes k = 0. While the condition we've discussed earlier holds, the code after and is executed, which (among other things) recursively calls F with incremented k.

Once LSBk(n) or MSBk(n) is unset, the condition fails and F(n, k) returns 0. Each of the preceding k function calls adds (n & (n + 1) > 0) + 1 to F(n, k) = 0, so F(n) returns ((n & (n + 1) > 0) + 1)k.

Now, if all bits of n are equal (i.e., if n is either 0 or all of its bits are set), n + 1 will not have any bits in common with n, so n & (n + 1) = 0 and F(n) returns k. However, if n has both set and unset bits, n & (n + 1) > 0 and F(n) returns 2k.

\$\endgroup\$
  • 2
    \$\begingroup\$ Recursive solutions in Python seems to be scoring really well lately. \$\endgroup\$ – mbomb007 Jan 7 '17 at 5:13
  • \$\begingroup\$ At least compared with iterative solutions, they always have. input(), while, and print are already 17 bytes... \$\endgroup\$ – Dennis Jan 7 '17 at 20:26
  • \$\begingroup\$ Yeah, but I find them so much harder to write. \$\endgroup\$ – mbomb007 Jan 8 '17 at 4:02
  • 1
    \$\begingroup\$ Fair enough. An straightforward iterative implementation of the same idea would only be 5 bytes longer though. tio.run/nexus/… 2 more bytes could be saved with a few tricks. tio.run/nexus/python2#JY1BDsIgFAXX7SnepgUUI1BNm1K4jKVJQ/… \$\endgroup\$ – Dennis Jan 8 '17 at 4:27
6
\$\begingroup\$

MATL, 13 12 bytes

Btv`6L&)}x@q

Try it online! Or verify all test cases.

Explanation

The code repeats each binary digit, and counts how many times it is possible to remove two outer ones.

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)
\$\endgroup\$
6
\$\begingroup\$

Python, 82 bytes

I feel like it can still be golfed, but I spent a while trying different methods and this was the shortest.

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

Try it online

Though this works similarly to the OP's Python program, I created this before the question was posted, after viewing the question in the Sandbox, which did not contain such a program.

\$\endgroup\$
6
\$\begingroup\$

Python 2, 66 bytes

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

Splits the binary representation of the input into chunks of 1. Counts the number of 1's in the smaller of the first and last chunk, then doubles it, unless there's a single chunk that this would double-count.

\$\endgroup\$
  • \$\begingroup\$ Clever, but still easy to understand. I like it! \$\endgroup\$ – mbomb007 Jan 7 '17 at 5:14
  • 5
    \$\begingroup\$ @mbomb007 Take it as a warm up for understanding Dennis's :) \$\endgroup\$ – xnor Jan 7 '17 at 5:15
3
\$\begingroup\$

PowerShell, 109 106 bytes

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

Try it online!

Takes input $args[0], uses the .NET call to convert it toString with base 2 (i.e., make it binary), then -splits that string on 0s, stores that into $a. Important to note: the .NET call does not return leading zeros, so the first digit is always a 1.

There are thus two possibilities -- the binary string is all ones, or there was at least one zero. We differentiate between those with a pseudo-ternary indexed by $a.count-eq1. If the binary has at least one zero, the left case, we take the minimum of the length of the first [0] string of 1s and the last [-1] string (found by |sort and then [0]). The shorter of those is the most pairs we could remove, so we multiply that by 2. Note that if the original binary string ends in a 0, like for input 8, then the [-1].length will also be 0 (since it's an empty string), which when multiplied by 2 is still 0.

Otherwise, with the binary string all ones, we take just $b (which was previously set to be the length of the first [0] string, in this case, the entirety of the binary string).

In either situation, that result is left on the pipeline and output is implicit.

\$\endgroup\$
3
\$\begingroup\$

JavaScript (ES6), 57 bytes

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>

Takes the binary and tries to match all 1s or failing that an equal number of leading and trailing 1s.

\$\endgroup\$
2
\$\begingroup\$

Retina, 48 bytes

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

Try it online

Explanation:

.+              # 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`
\$\endgroup\$
2
\$\begingroup\$

C#, 133 bytes

Function that returns hardness. Takes integer from 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;}

Well, today I found out '1' + '1' = 98 in C#.

\$\endgroup\$
  • 1
    \$\begingroup\$ That's because '1' is the ASCII char 49, and 49 + 49 = 98. \$\endgroup\$ – FlipTack Jan 6 '17 at 21:20
  • \$\begingroup\$ I literally spent 10 minutes figuring out why my 1 + 1 = 2 didn't work. @FlipTack \$\endgroup\$ – devRicher Jan 6 '17 at 21:21
2
\$\begingroup\$

C, 89 88 85 bytes

Saved two bytes due to @FlipTack pointing out a useless declaration.

Call f() with the number to test, the output is returned from the function.

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

Try it on ideone.

\$\endgroup\$
2
\$\begingroup\$

JavaScript (ES6), 59 58 bytes

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

Test cases

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

\$\endgroup\$
2
\$\begingroup\$

Jelly, 14 bytes

Eo2
BµŒg.ịṂS×Ç

Try it online!

\$\endgroup\$
2
\$\begingroup\$

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

Time to start golfing 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;}

Here's the proof

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

and the output;

0 0
1 1
8 0
23 2
31 5
103 4
127 7
1877 2
2015 10
3167 4 
\$\endgroup\$
1
\$\begingroup\$

Java (OpenJDK), 181 156 150 bytes

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

Try it online!

\$\endgroup\$
1
\$\begingroup\$

Mathematica, 63 56 bytes

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

Explanation

l=#~IntegerDigits~2

Generate the base-2 representation of the input, wrapped with a List. Store that in l

(2-Min[...])

If the min element of l is 1, output 1. If not, output 2. Multiply this by...

Split[l]

Split l into runs.

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

Take the first and the last element.

Tr/@ ...

Take the total of both.

Min[ ... ]

Find the smaller between the two.

(Multiply the first result (1 or 2) with this result).

\$\endgroup\$
1
\$\begingroup\$

Octave, 56 54 bytes

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

Try it Online!

Explanation:

d=dec2bin(n)-48

binary representation of n

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

Take cumulative min of d and cumulative min of flipped d

res = cumd * cumfd ';

do matrix multiplication

out = res*2^!all(d)

multiply with 2 if all of digits is 1;

\$\endgroup\$
  • \$\begingroup\$ @FlipTack Thanks, link updated! \$\endgroup\$ – rahnema1 Jan 7 '17 at 13:14
1
\$\begingroup\$

Pyth, 18 bytes

?*FJjQ2lJyhSxR0_BJ

A program that takes input of an integer and prints the result.

Test suite (First line for formatting)

How it works

?*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
\$\endgroup\$
1
\$\begingroup\$

APL, 26 bytes

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

Test cases:

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

Explanation:


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

                         ⊢   input
                    2⊥⍣¯1    convert to binary representation
   (               )
        (  ⊢    ¨⌽)          for each bit and its matching bit on the other side
            (  ∧)               take the logical and of both bits,
             ,                  make a list of both bits,
              ∧                 then take the and of the list and the and
         ∊                   flatten the resulting array
      ≢↑                     take only the first N bits, where N is the
                                length of the original list of bits
    ∧\                       take a running logical and (leaving only the
                                starting ones)
+/∘                          sum those
\$\endgroup\$
1
\$\begingroup\$

J, 22 bytes

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

This is based on the neat trick learned from this challenge.

Try it online!

Explanation

(#<.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
\$\endgroup\$
1
\$\begingroup\$

PHP, 83 74 bytes

3+6 bytes saved by Jörg

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

takes input from STDIN; run with -nR.

breakdown

<?=                     # 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)
\$\endgroup\$
  • 1
    \$\begingroup\$ <?=~($s=decbin($argn))[$a=strspn($s,1)]?2*min($a,strspn(strrev($s),1)):$a; \$\endgroup\$ – Jörg Hülsermann May 3 '17 at 12:49
0
\$\begingroup\$

JavaScript (ES6), 83 Bytes

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

Ungolfed:

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);
    }
}
\$\endgroup\$
0
\$\begingroup\$

Mathematica, 62 bytes

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

Pure function where # represents the first argument.

(h=0;...;h)& sets h=0, does a bunch of stuff ..., then returns h (the hardness). Let's look at the bunch of stuff:

#~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

Thanks to Greg Martin for introducing me to this trick.

\$\endgroup\$
0
\$\begingroup\$

Haskell, 94 92 bytes

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

Try it online! Usage:

Prelude> sum.h.b $ 3167
4

Explanation:
b converts a number to binary and returns a list of zero and ones with the least significant bit first. In h, this list is reversed and element-wise multiplied with the original list, then span(>0) splits after the initial 1s:

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

The resulting tuple is pattern matched with (c,_:_) where _:_ matches any non-empty list, so c = [1,1]. Because the bytes are removed at front and back, c++c = [1,1,1,1] is returned and finally summed up to yield the digital hardness.

If the second list of the tuple is empty, then the binary representation contains ones only, and the number of ones is the digital hardness. With the pattern matching failed h returns just n, which is again summed up.

\$\endgroup\$
0
\$\begingroup\$

Perl, 61 bytes

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

The heart of this is the regex /^(1+).*\1$/ where 2 times the length of $1 is the answer. Rest of the code is overhead and dealing with the all 1's special case.

\$\endgroup\$
  • \$\begingroup\$ You can omit the parenthesis around sprintf arguments. Also, using -p flag will allow you to write a full program that will be shorter than your function as you'll be able to omit sub f{...} (instead you'll have to end with $_=... but that's still a 4 bytes improvement). Finally, instead of your length(...), you can do /0/&&s/^(1+).*\1$/$1$1/;$_=y///c. This should get you to 51 bytes. \$\endgroup\$ – Dada May 11 '17 at 11:36
0
\$\begingroup\$

PHP, 65 Bytes

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

Online Version

\$\endgroup\$
0
\$\begingroup\$

CJam, 14 bytes

ri2b_0#\W%0#e<

Explanation:

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
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.