Hace poco leí una publicación ya vieja de coding horror que habla de la incapacidad de la “mayoría” de los programadores para programar, esto basado en que cuando los ponían a hacer un simple Fizz Buzz no podían hacerlo. Inmediatamente lo intente y no tarde mucho tiempo resolviéndolo pero me quedo la duda de si realmente podía resolver cosas mas complejas que un Fizz Buzz.

Hace tiempo escuche sobre codility y lo tenia en favoritos pero nunca lo probé, y hace unas semanas en facebook me recomendaron que si quería entrar en toptal le diera una revisada a codility que es una plataforma online para “testear” las habilidades de los programadores y es usado por un gran numero de empresas de software, de hecho si buscas de codility en Google hay muchos desarrolladores contando su primer experiencia por que alguna empresa se los puso como prueba y fallaron totalmente por que los agarraron por sorpresa.

Y es que pónganse a pensar cuando fue la ultima vez que resolvieron un problema el cual fue evaluado por su tiempo de ejecución y espacio en memoria, sinceramente la mayoría de los desarrolladores ya solo hacemos CRUD’s con ciertas particularidades.

Codility tiene una sección de lecciones abierta el cual te provee un PDF y 1 o mas ejercicios que son evaluados y te da una “calificación” basada en el tiempo de ejecución, espacio en memoria y una serie de pruebas que le hacen al código, así que cada semana voy a estar tratando de resolver un ejercicio de las lecciones de Codility de la manera mas optima. Esta semana empezare con binary gap de la sección de iteraciones. La intención es mejorar mis habilidades como programador y compartir las respuestas a estos ejercicios con ustedes y mi calificación y si ustedes tienen una mejor manera de resolver algún problema la puedan compartir.

Binary Gap

El problema:

A binary gap within a positive integer N is any maximal sequence of consecutive zeros that is surrounded by ones at both ends in the binary representation of N.

For example, number 9 has binary representation 1001 and contains a binary gap of length 2. The number 529 has binary representation 1000010001 and contains two binary gaps: one of length 4 and one of length 3. The number 20 has binary representation 10100 and contains one binary gap of length 1. The number 15 has binary representation 1111 and has no binary gaps.

Write a function:

def solution(N)

that, given a positive integer N, returns the length of its longest binary gap. The function should return 0 if N doesn’t contain a binary gap.

For example, given N = 1041 the function should return 5, because N has binary representation 10000010001 and so its longest binary gap is of length 5.

Assume that:

  • N is an integer within the range [1..2,147,483,647].

La solución:

def solution(N):
    return len(max("{0:b}".format(N).split("1")))

 

Para quienes tal vez no sepan ingles o no entendieron mi solución lo explicare paso por paso.

El problema nos pide que programemos una función a la cual se le pase como parámetro un numero N y que retorne la brecha/espacio binario (cadena de 0’s rodeado por 1’s. Ej. 100001) mas grande que tenga ese numero, ejemplo:

Si N es igual a 529 su representación binaria seria 1000010001 por lo tanto tiene una brecha binaria de 3 y de 4 y nos piden la mas grande por lo tanto retornaríamos 4.

  1. En cuanto a mi solución lo que hago es tomar N y formatear ese numero a binario con fomat.
  2. Teniendo ese string de unos y ceros uso split para que me retorne una lista de 0’s eliminando los 1’s. [”, ‘0000’, ‘000’, ”] 
  3. Después con max obtengo el string de 0’s mas grande de la lista.
  4. Y por ultimo obtengo la longitud de ese string de 0s retornado por max con len

 

Para que se entienda mejor aquí parto el código en mas de una linea:

def solution(N):
    binary = "{0:b}".format(N)
    gap_list = binary.split("1")
    max_gap = max(gap_list)
    return len(max_gap)

 

Mi resultado en codility fue 80 de 100, si tienen una duda o algún comentario o incluso si tienen una mejor manera de resolverlo, pueden dejarlo en la sección de comentarios.

NOTA:

  • Los problemas usan Big O notation pero apenas estoy aprendiendo sobre el tema asi que por el momento no tocaremos ese tema
  • Todas mis soluciones las subiré en mi cuenta de github usando timeit para medir el tiempo de ejecución y con su unitest. Esto a partir de la siguiente semana.
It's only fair to share...Share on Facebook7Tweet about this on TwitterShare on Google+0Share on LinkedIn0Share on Reddit0Pin on Pinterest0Email this to someone

12 thoughts on “Binary Gap

  1. Se me hizo un problema interesante y en mi cabeza lo resolví con un algoritmo distinto (pensando más al estilo C). Lo implementé en Python y comparé el rendimiento de cada código:

    PY – OI – 3.07us por iter
    PY – OA – 5.80us por iter

    Entonces decidí implementar ambos algoritmos en C y obtuve resultados curiosos:

    C – OI – 0.72us por iter
    C – OA – 0.22us por iter

    Lo curioso no es que Python haya sido inferior que C en rendimiento, pues es parte del tradeoff usual entre ambos lenguajes. Lo curioso es que el algoritmo que resultó superior en una plataforma resultó inferior en la otra.

    Estos son los códigos en cada caso:
    https://gist.github.com/alvarezp/be5a8c78cdfe9854f8bc

    Esto significa que en los cuatro casos podría haber aún mucho lugar a optimización en todos los casos, considerando los aspectos específicos de cada plataforma.

    También significa que aún no entiendo bien Python. 🙂

    1. OmarIbannez says:

      wow implementaste todas las funciones que utilizo en Python a C.

      Recuerda que Python esta escrito en C, creo que la razón es tal vez por que la implementacion “real” en C de las funciones que uso en Python están mas optimizadas en el source code: https://hg.python.org/cpython/file/c6880edaf6f3/Objects

      Pero ya han pasado por un sin fin de optimizaciones a través de los años por cientos de desarrolladores.

      Tambien creo que no importa realmente el lenguaje, si eliminas la obvia ventaja de C sobre Python un algoritmo siempre sera mas rápido que otro sin importar el lenguaje.

      Pasaría mi código a C con las implementaciones “reales” para comprobar lo que digo pero no se C :p

  2. Alexis Ortega says:

    Muy cierto tu comentario…
    “Y es que pónganse a pensar cuando fue la ultima vez que resolvieron un problema el cual fue evaluado por su tiempo de ejecución y espacio en memoria, sinceramente la mayoría de los desarrolladores ya solo hacemos CRUD’s con ciertas particularidades.”

  3. Jose Martinez says:

    Lo resolví con C de una forma un poco distinta a la de Omar y parecida a la de Octavio, básicamente el único problema es que los ceros deben estar entre medio de unos, y por eso podríamos usar un flag para así evitar contar los ceros al final de la representación binaria, por ejemplo, números elevados a la 2da. potencia, como 8 (1000).

    Sobre la notación O(n), básicamente es la representación de a que razón de cambio crece el tiempo de ejecución, o las iteraciones de el código en base a el input. En este caso O(n) es el número de divisiones de N entre 2 (N/=2) hasta que hemos dividido N=1, (1/2) = 0. Lo que al final nos deja que el número de iteraciones para llegar a 1 se puede modelar como 1 = N/ 2^x, donde x es el numero de iteraciones. El resultado es O(n) = x = log2(N). Aqui mi codigo:

    #include
    int solution(int N) {

    int maxZeroes = 0;
    int currentZeroes = 0;
    bool isBetween = false;
    while (N > 0) {

    if (N%2 == 0) {

    if (isBetween) {
    currentZeroes++;
    }
    } else {

    if (isBetween && currentZeroes > maxZeroes) {
    maxZeroes = currentZeroes;
    }

    currentZeroes = 0;
    isBetween = true;
    }
    N/=2;
    }
    return maxZeroes;
    }

    P.D. Sorry por el formato y no usar algún repo; ando en el cell.

    1. OmarIbannez says:

      Creo que esta es la mejor solución para el problema.

  4. Marcos Carrera says:

    Hice la funcion solucion(N), y despues vi la de Jose Martinez (solucion2(N)), y vi que era mejor con un inconveniente, ya que C puede manejar bitwise, no es necesario hacer los calculos de division y de mod, esto es muy costos, solo hice esa modificacion y me parece que quedo mejor (solucion(N)).

    La funcion nMayor(int number), con ella calculo el numero de bits que debo evaluar, ya que de lo contrario tendria que evaluar lo 32 o 64 bits que correspondan al tipo de dato que estamos usando, en este caso int.

    #include

    # define VALTEST 529

    int nMayor(int number)
    {
    int aux=1, iter =0;

    while(aux < number){
    iter++;
    aux = aux< max0){
    max0 = count;
    //printf(“max0= %d, “, max0);
    }
    band = 0;
    }
    number = number >> 1;
    //printf(“count= %d, “, count);

    }
    return max0;
    }

    int solucion2(int number)
    {
    int maxZeroes = 0;
    int currentZeroes = 0;
    bool isBetween = false;
    int bLenght = nMayor(number);

    while (bLenght–) {
    if (!(number & 1)) {

    if (isBetween) {
    currentZeroes++;
    }
    } else {

    if (isBetween && currentZeroes > maxZeroes) {
    maxZeroes = currentZeroes;
    }

    currentZeroes = 0;
    isBetween = true;
    }
    number = number>>1;
    }
    return maxZeroes;
    }

    int main()
    {
    printf(“\nSOLUCION: %d: %d\n”, VALTEST, solucion(VALTEST));
    printf(“\nSOLUCION2: %d: %d\n”, VALTEST, solucion2(VALTEST));
    }

    1. Marcos Carrera says:

      Le sucedio algo raro a la funcion nMayor(), me imagino que por la combinacion de ciertos caracteres, aqui esta en Git: https://gist.github.com/cpm586/e86d300903215a938f0f

      1. OmarIbannez says:

        Aquí esta el resultado que obtiene tu código: https://codility.com/demo/results/training78E3PH-DDM/ y también puedes ver en que fallo tu algoritmo, tienes un resultado de 40, Octavio y yo de 80 y Jose tiene 100, hasta ahorita Jose a sido el de mejor puntuacion.

  5. Wow, nunca me percaté del requisito de que estuviera entre unos. Tendré que volverlo a hacer.

  6. Eduardo says:

    Yo usé una lógica diferente: https://codility.com/demo/results/trainingRNKCBU-NTB/

    En vez de un solo ciclo con varios condicionales, utilizo varios ciclos, que van consumiendo bits según sea el caso (eliminar ceros a la derecha, consumir los unos, etc).

  7. Luis says:

    public static int solution(int N) {
    String[] list1 = Integer.toBinaryString(N).split(“1”);
    ArrayList list = new ArrayList();
    for(String value: list1){
    if(!value.equals(“”)){
    list.add(value);
    }
    }
    int largerValueLength = 0;
    for(int i = 0; i largerValueLength){
    largerValueLength = v.length();
    }
    }
    return largerValueLength;
    }

Leave a Reply

Your email address will not be published. Required fields are marked *

Comment moderation is enabled. Your comment may take some time to appear.