HackerRank Challenge - Día 1

En esta serie de posts voy a documentar mi experiencia intentando entrar entre los mil mejores programadores de HackerRank, un sitio para practicar ejercicios de programación.

Julio 11 de 2016: Me di cuenta que el ranking es por tema, así que este reto solo aplica para el área de matemáticas de HackerRank. Disculpas por la confusión!

La mayor parte de mi vida como programador he estado enfocado en arquitectura de software y esta es una excelente oportunidad para mejorar en la resolución de problemas de programación específicos. HackerRank está dividio por temas y he decidido empezar por matemáticas, que es un tema que me interesa y en el que sé que puedo mejorar bastante.

Voy a intentar escribir un post al día describiendo el ejercicio en el que trabaje ese día, pero no es promesa.

El ejercicio de hoy se llama Sherlock and Permutations. Nos piden calcular el número de permutaciones únicas dado un número determinado de ceros (N) y unos (M) que comiencen con uno (1).

Por ejemplo, si N es 1 y M es 1 (un cero y un uno), las posibles permutaciones son 01 y 10. Solo la segunda permutación satisface la condición que empiece con 1, y por lo tanto la respuesta es 1 (solo existe una permutación que satisface la condición).

Veamos otro ejemplo. Si N es 1 y M es 2 (un cero y dos unos), las posibles permutaciones son 011, 101 y 110. Solo las dos últimas satisfacen la condición, así que la respuesta es 2.

Una posible solución sería diseñar un algoritmo que realice todas las combinaciones y solo tenga en cuenta las que comienzan con 1. Sin embargo, estos ejercicios de matemáticas generalmente se pueden resolver con alguna fórmula, así que decidí investigar primero un poco sobre permutaciones. Los videos de Khan Academy sobre el tema me llevaron a la solución.

El coeficiente binomial (n k) es el número de modos en los que se pueden escoger k objetos de un total de n.

Si llevamos esa frase a nuestro ejemplo, es el número de modos en los que se pueden escoger M unos (1) de un total N + M (el número de ceros + el número de unos). Sin embargo, como solo queremos los casos que comienzan en 1, el total es N + M - 1 (restamos 1 del número de unos).

La fórmula del coeficiente binomial es (n k) = n!/(n-k)!*k! (el ! significa factorial). Aplicado a nuestro caso el numerador sería (N + M - 1)! y el denominador simplificado sería (M-1)!*N!. Convirtamos eso a código Ruby:

def permutations(zeros, ones)
  numerator = fact(zeros + ones - 1)
  denominator = fact(ones - 1) * fact(zeros)
  numerator / denominator
end

También creé una función fact para sacar el factorial:

def fact(i)
  return 1 if i == 0
  (1..i).inject(:*)
end

Lo único es que el camino hacia esta solución fue más complicado de lo que lo hace parecer este post!

Mi nuevo ranking en HackerRank después de terminar este ejercicio es 9,945!

Te invito a hacer este reto conmigo. Puedes definir tu propio objetivo. Por ejemplo, si estás en el ranking 50,000, intenta llegar a 10,000. Si ya estás entre los primeros 1,000, intenta llegar a 100. Y así.