Dureza digital de enteros

26

Para encontrar la dureza digitales de un entero, tome su representación binaria, y contar el número de veces que tanto uno de los principales y de arrastre 1puede ser retirado hasta que o bien se inicia o termina con una 0. El número total de bits eliminados es su dureza digital.

Esa es una explicación bastante prolija, así que analicemos con un ejemplo trabajado.

Para este ejemplo, usaremos el número 3167. En binario, esto es:

110001011111

(Tenga en cuenta que, durante la conversión a binario, debe asegurarse de eliminar los ceros iniciales)

No comienza ni termina con 0, por lo que eliminamos 1 par de bits:

1  1000101111  1

Y otro:

11  00010111  11

Pero ahora hay un 0 al principio, por lo que no podemos eliminar más 1pares. En total, eliminamos 4 bits, por lo que 4 es la dureza digital de 3167.

Sin embargo, para los números que pueden escribirse como 2 n -1 para n positivo (es decir, contener solo 1en representación binaria), nunca se alcanzará 0, por lo que todos los bits se pueden eliminar. Esto significa que la dureza es simplemente la longitud de bits del entero.


El reto

Su tarea es escribir un programa o función que, dado un número entero no negativo n >= 0, determine su dureza digital.

Puede enviar un programa completo que realice E / S o una función que devuelva el resultado. Su envío debe funcionar para valores ndentro del rango entero estándar de su idioma.


Casos de prueba

Notifíqueme si alguno de estos es incorrecto o si desea sugerir algún caso marginal para agregar.

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

Aquí está la solución de Python sin golf que utilicé para generar estos casos de prueba (no se garantiza que no tengan errores):

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
FlipTack
fuente
1
¿Cómo 1devuelve 1 cuando no hay 0en absoluto? Quiero decir, no puedes eliminar suficientes 1 de la cadena para que comience o termine 0.
busukxuan
2
@busukxuan Lea el párrafo justo antes del encabezado "El desafío": para los números que se pueden escribir como 2 ^ n-1 (es decir, contienen solo 1 en representación binaria), nunca se alcanzará 0 y, por lo tanto, se pueden eliminar todos los bits . Esto significa que la dureza es simplemente la longitud de bits del entero.
FlipTack
2
@busukxuan se puede considerar como el número de unos con los que se rellena cada lado, antes de alcanzar los ceros.
FlipTack
2
Para el votante que obviamente no le gustaron los casos de borde: la dureza es la cantidad de bits sólidos (1) con los que está acolchada: si todo es sólido, entonces seguramente tiene una dureza del 100%, ¿toda su longitud de bits?
FlipTack
1
@FlipTack No quiero influir demasiado, es tu desafío. Inicialmente entendí "dureza" como el número máximo de pares de externos que se pueden quitar, uno de cada lado. Pero puede que tenga razón, si queda una sola al final, tal vez debería tenerse en cuenta
Luis Mendo

Respuestas:

6

Jalea , 11 10 bytes

BµQL××Ṛa\S

Pruébalo en línea!

Cómo funciona

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.
Dennis
fuente
8

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)

Pruébalo en línea!

Cómo funciona

Esta es una solución recursiva que toma una entrada ny sigue incrementando k , comenzando en 0 , mientras que LSB k (n) (bit en el índice k desde la derecha) y MSB k (n) (bit en el índice k desde la izquierda) se establecen. Una vez finalizado, devuelve k si todos los bits de n están establecidos y 2k si no.

Comencemos reescribiendo la lambda f como una función con nombre F , con una variable auxiliar 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)

En cada invocación de F , primero desplazamos un bit n un total de k unidades a la derecha y almacenamos el resultado en t . De esta manera, LSB 0 (t) = LSB k (n) , entonces t es impar si y solo si LSB k (n) está configurado.

Determinar si MSB k (n) está configurado es un poco más complicado; Esto es lo que se n & t > t >> 1logra. Para ilustrar cómo funciona, consideremos un número entero n = 1αβγδεζη 2 de longitud de bit 8 y analicemos la llamada a la función F (n, 3) , es decir, k = 3 .

Estamos tratando de determinar si MSB 3 (n) = γ se establece examinando el valor de verdad de la comparación (n & t> t >> 1) = (1αβγδεζη 2 & 1αβγδ 2 > 1αβγ 2 ) . Examinemos los enteros involucrados.

MSB-index  012k4567

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

t >> 1         1αβγ

Afirmamos que γ = 1 si y solo si n & t> t >> 1 .

  • Si γ = 1 , entonces n & t tiene una longitud de bits 5 mientras que t >> 1 tiene una longitud de bits 4 , entonces n & t> t >> 1 .

    Esto prueba que γ = 1 implica n & t> t >> 1 .

  • Si n & t> t >> 1 , hay dos opciones: γ = 1 o γ = 0 . En el primer caso, no queda nada que demostrar.

    En el segundo caso, tenemos que αβγδ 2 ≥ n & t> t >> 1 = 1αβγ 2 .

    Como αβγδ 2 > 1αβγ 2 , debemos tener MSB 0 (αβγδ 2 ) ≥ MSB 0 (1αβγ 2 ) , lo que significa que α = 1 .

    De esta manera, 1βγδ 2 > 11βγ 2 , por lo que debemos tener MSB 1 (1βγδ 2 ) ≥ MSB 1 (11βγ 2 ) , lo que significa que β = 1 .

    A su vez, esto implica que 11γδ 2 > 111γ 2 . Recordando que γ = 0 en el segundo caso, obtenemos la desigualdad 110δ 2 > 1110 2 , lo cual es falso ya que MSB 2 (110δ 2 ) = 0 <1 = MSB 2 (1110 2 ) .

    Por lo tanto, solo el primer caso es posible y n & t> t >> 1 implica γ = 1 .

En resumen, si ambos LSB k (n) y MSB k (n) se establecen, t será par y n & t> t >> 1 será verdadera , por lo que t & (n & t> t >> 1) se rendimiento 1 . Sin embargo, si LSB k (n) o MSB k (n) está desarmado (o si ambos lo están), t será par o n & t> t >> 1 será Falso , entonces t & (n & t> t> > 1) producirá 0 .

Llamar a F con un solo argumento inicializa k = 0 . Si bien la condición que hemos discutido anteriormente se mantiene, el código posterior andse ejecuta, lo que (entre otras cosas) llama recursivamente F con k incrementado .

Una vez que LSB k (n) o MSB k (n) se desarma, la condición falla y F (n, k) devuelve 0 . Cada una de las llamadas a funciones k anteriores agrega (n & (n + 1)> 0) + 1 a F (n, k) = 0 , por lo que F (n) devuelve ((n & (n + 1)> 0) + 1) k .

Ahora, si todos los bits de n son iguales (es decir, si n es 0 o todos sus bits están establecidos), n + 1 no tendrá ningún bit en común con n , entonces n & (n + 1) = 0 y F (n) devuelve k . Sin embargo, si n tiene bits establecidos y no establecidos, n & (n + 1)> 0 y F (n) devuelve 2k .

Dennis
fuente
2
Las soluciones recursivas en Python parecen estar puntuando muy bien últimamente.
mbomb007
Al menos en comparación con las soluciones iterativas, siempre lo han hecho. input(),, whiley printya son 17 bytes ...
Dennis
Sí, pero los encuentro mucho más difíciles de escribir.
mbomb007
1
Lo suficientemente justo. Sin embargo, una implementación iterativa directa de la misma idea solo sería 5 bytes más.tio.run/nexus/… Se podrían guardar 2 bytes más con algunos trucos. tio.run/nexus/python2#JY1BDsIgFAXX7SnepgUUI1BNm1K4jKVJQ/…
Dennis
6

MATL , 13 12 bytes

Btv`6L&)}x@q

Pruébalo en línea! O verificar todos los casos de prueba .

Explicación

El código repite cada dígito binario y cuenta cuántas veces es posible eliminar dos dígitos externos.

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)
Luis Mendo
fuente
6

Python, 82 bytes

Siento que todavía se puede jugar golf, pero pasé un tiempo probando diferentes métodos y este fue el más corto.

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

Pruébalo en línea

Aunque esto funciona de manera similar al programa Python del OP, creé esto antes de que se publicara la pregunta, después de ver la pregunta en el Sandbox, que no contenía dicho programa.

mbomb007
fuente
6

Python 2, 66 bytes

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

Divide la representación binaria de la entrada en fragmentos de 1. Cuenta el número de 1 en la parte más pequeña de la primera y la última parte, luego la duplica, a menos que haya una sola parte que cuente dos veces.

xnor
fuente
Inteligente, pero aún así fácil de entender. ¡Me gusta!
mbomb007
55
@ mbomb007 Tómelo como un calentamiento para comprender Dennis's :)
xnor
3

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]

Pruébalo en línea!

Toma de entrada $args[0], utiliza la llamada .NET para convertque toStringcon la base 2(es decir, hacer que sea binario), a continuación, -splitde que la cadena en 0s, tiendas que en $a. Importante tener en cuenta: la llamada .NET no devuelve ceros a la izquierda, por lo que el primer dígito siempre es un1 .

Por lo tanto, hay dos posibilidades: la cadena binaria son todas, o había al menos un cero. Diferenciamos entre aquellos con un pseudoternario indexado por $a.count-eq1. Si el binario tiene al menos un cero, el caso de la izquierda, tomamos el mínimo de la longitud de la primera [0]cadena de 1sy la última [-1]cadena (encontrada por |sorty luego [0]). El más corto de esos es la mayor cantidad de pares que podríamos eliminar, por lo que multiplicamos eso por 2. Tenga en cuenta que si la cadena binaria original termina en a 0, como para input 8, entonces [-1].lengthtambién será 0(ya que es una cadena vacía), que cuando se multiplica por 2sigue siendo 0.

De lo contrario, con la cadena binaria todas, tomamos solo $b(que previamente se estableció como la longitud de la primera [0]cadena, en este caso, la totalidad de la cadena binaria).

En cualquier situación, ese resultado se deja en la tubería y la salida es implícita.

AdmBorkBork
fuente
3

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>

Toma el binario e intenta hacer coincidir todos 1so, en su defecto, un número igual de iniciales y finales 1s.

Neil
fuente
2

Retina , 48 bytes

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

Pruébalo en línea

Explicación:

.+              # 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`
mbomb007
fuente
2

C #, 133 bytes

Función que devuelve dureza. Toma entero del argumento.

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

Bueno, hoy me enteré '1' + '1' = 98en C #.

devRicher
fuente
1
Eso es porque '1'es el ASCII char 49, y 49 + 49 = 98.
FlipTack
Literalmente pasé 10 minutos descubriendo por qué mi 1 + 1 = 2no funcionó. @FlipTack
devRicher
2

C, 89 88 85 bytes

Se guardaron dos bytes debido a que @FlipTack señalaba una declaración inútil.

Llame f()con el número para probar, la salida devuelve la función.

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

Pruébalo con ideone .

owacoder
fuente
2

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

Casos de prueba

Arnauld
fuente
2

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

Hora de empezar a jugar al 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;}

Aquí está la prueba

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

y la salida;

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

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

Pruébalo en línea!

Pavel
fuente
1

Mathematica, 63 56 bytes

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

Explicación

l=#~IntegerDigits~2

Genere la representación de base 2 de la entrada, envuelta con a List. Almacenar eso enl

(2-Min[...])

Si el elemento mínimo de les 1, salida 1. Si no, salida 2. Multiplique esto por ...

Split[l]

Dividir len carreras.

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

Toma el primer y el último elemento.

Tr/@ ...

Toma el total de ambos.

Min[ ... ]

Encuentra el más pequeño entre los dos.

(Multiplique el primer resultado (1 o 2) con este resultado).

JungHwan Min
fuente
1

Octava, 56 54 bytes

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

Pruébalo en línea!

Explicación:

d=dec2bin(n)-48

representación binaria de n

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

Tomar min acumulativo d y min acumulativo de volteadod

res = cumd * cumfd ';

hacer multiplicación de matrices

out = res*2^!all(d)

multiplique por 2 si todos los dígitos son 1;

rahnema1
fuente
@FlipTack Gracias, enlace actualizado!
rahnema1
1

Pyth, 18 bytes

?*FJjQ2lJyhSxR0_BJ

Un programa que toma la entrada de un número entero e imprime el resultado.

Conjunto de pruebas (primera línea para formatear)

Cómo funciona

?*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
TheBikingViking
fuente
1

APL, 26 bytes

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

Casos de prueba:

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

Explicación:

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

                         ⊢ entrada
                    2⊥⍣¯1 convertir a representación binaria
   ()
        (⊢ ¨⌽) para cada bit y su bit correspondiente en el otro lado
            (∧) tome la lógica y de ambos bits,
             , haga una lista de ambos bits,
              ∧ luego toma el y de la lista y el y
         ∊ aplanar la matriz resultante
      ↑ ↑ tome solo los primeros N bits, donde N es el
                                longitud de la lista original de bits
    Take \ tomar un funcionamiento lógico y (dejando solo el
                                principiantes)
+ / ∘ suma esos
marinus
fuente
1

J, 22 bytes

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

Esto se basa en el ingenioso truco aprendido de este desafío .

Pruébalo en línea!

Explicación

(#<.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
millas
fuente
1

PHP, 83 74 bytes

3 + 6 bytes guardados por Jörg

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

toma entrada de STDIN; correr con -nR.

Descompostura

<?=                     # 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)
Titus
fuente
1
<?=~($s=decbin($argn))[$a=strspn($s,1)]?2*min($a,strspn(strrev($s),1)):$a;
Jörg Hülsermann
0

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

Sin 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);
    }
}
Joshua David
fuente
0

Mathematica, 62 bytes

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

Función pura donde #representa el primer argumento.

(h=0;...;h)&establece h=0, hace un montón de cosas ..., luego regresa h(la dureza). Veamos el montón de cosas:

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

Gracias a Greg Martin por presentarme este truco .

ngenisis
fuente
0

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

Pruébalo en línea! Uso:

Prelude> sum.h.b $ 3167
4

Explicación:
b convierte un número a binario y devuelve una lista de cero y unos con el bit menos significativo primero. En h, esta lista se invierte y se multiplica por elementos con la lista original, luego se span(>0)divide después de la inicial 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])

La tupla resultante coincide con el patrón (c,_:_)donde _:_coincide con cualquier lista no vacía, por lo tanto c = [1,1]. Debido a que los bytes se eliminan en la parte delantera y trasera, c++c = [1,1,1,1]se devuelve y finalmente se resume para obtener la dureza digital .

Si la segunda lista de tuplas está vacía, entonces la representación binaria solo contiene unos, y el número de unos es la dureza digital. Con la coincidencia de patrones, el error hdevuelve solo n, lo que nuevamente se resume.

Laikoni
fuente
0

Perl, 61 bytes

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

El corazón de esto es la expresión regular, /^(1+).*\1$/donde 2 veces la longitud $1es la respuesta. El resto del código está sobrecargado y se ocupa del caso especial de todos los 1.

cdlane
fuente
Puede omitir el paréntesis en torno a los sprintfargumentos. Además, el uso de -pflag le permitirá escribir un programa completo que será más corto que su función, ya que podrá omitirlo sub f{...}(en su lugar, tendrá que terminar $_=...pero eso sigue siendo una mejora de 4 bytes). Finalmente, en lugar de tu length(...), puedes hacerlo /0/&&s/^(1+).*\1$/$1$1/;$_=y///c. Esto debería llevarte a 51 bytes.
Dada
0

PHP, 65 bytes

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

Versión en línea

Jörg Hülsermann
fuente
0

CJam, 14 bytes

ri2b_0#\W%0#e<

Explicación:

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
Fruta Esolanging
fuente