"Números curiosos" (Hackerrank PE 34) -- lojure campo con programming-challenge campo con unit-testing campo con functional-programming campo con clojure campo con lisp camp codereview Relacionados El problema

“Curious Numbers” (HackerRank PE 34)


8
vote

problema

Español

Me inspiró en un determinado Pregunta para probar mi mano en este desafío:

Proyecto EULER # 34: DIGIT FACTORIOS

$ 19! $ es un número curioso, como $ 1! +9! = 1 + 362880 = 362881 $ es divisible por $ 19 $.

Encuentre la suma de todos los números debajo de $ N $ que divide la suma de la Factorial de sus dígitos. Nota: ¡As $ 1!, 2!, CDOTS, 9! $ No son sumas, por lo que no están incluidos.

Formato de entrada: la entrada contiene un entero $ n $

Formato de salida: imprima la respuesta correspondiente a la caja de prueba.

Restricciones: $ 10 ^ 1 le n le 10 ^ 5 $

Entrada de muestra

  20   

Salida de muestra

  19   

El código funciona bien, con el único problema desafortunado que está fuera de mi control, pero me está impidiendo completar el desafío de "Oficial" Hackerrank: 9988776655544332 no funciona (todavía) con Clojure . Googled esto y la pila se desbordó que, y parece que todos tienen problemas (incluso simples 99887776655544333 en el sitio web de Hackerrank usando errores de Lenguaje de Clojure), así que sé que no es solo yo. La función que aborda directamente el desafío es sum-all-curious-numbers-up-to .

Escribí un montón de pruebas para asegurarme de que todo estaba funcionando correctamente. También incluyí algunas pruebas de referencia en la parte inferior de la publicación, ya que también estoy interesado en mejorar el rendimiento, si hay una forma idiomática de hacerlo.

Este es mi primer desafío "real" usando FP y, por lo tanto, me gustaría críticas sobre todos los aspectos del Código, incluidos algoritmos / lógica, estilo y pruebas. También tengo algunas áreas específicas de enfoque que me gustaría abordadas en términos más generales:

  1. es Idiomatic FP para tirar excepciones, como IllegalArgumentException que a menudo hago aquí, o tendría más sentido devolver un valor de falsey cuando funcione se pasan un argumento que no están diseñados para manejar?

  2. Específicamente con explode-num-to-digits (y, en consecuencia, test-explode-num-to-digits ) ¿Es esa función intentando manejar demasiados casos de borde? Pensé que sería "limpio" para poder aceptar números como cuerdas y analizar aquellos iguales que un número regular, pero ¿incluso tiene sentido para esta función para manejar dichos argumentos?

Nota: agregué un ;` y ;' Al final de una línea cerca de la parte superior de los archivos, estos son para compensar el hecho de que los lisp La sintaxis que resalta en el código PRETTIFICE / SE es Borked.

hackerrankprojecteuler34.clj

  19 0  

HackerrankProjecteuler34test.clj

  19 1  

Pruebas de Benchark

  19 2  

Resultados

Parece que hay un gran aumento de tiempo (comparativamente) de $ 10 ^ 4 $ a $ 10 ^ 5 $, me doy cuenta de que es todo un orden de magnitud más alto, pero el aumento del tiempo de cálculo parece no ser proporcional a los otros aumentos en un orden de magnitud.

 números curiosos a 10 ^ 2: "Tiempo transcurrido: 0.481473 MSECS" Números curiosos a 10 ^ 3: "Tiempo transcurrido: 0.055067 MSECs" Números curiosos a 10 ^ 4: "Tiempo transcurrido: 0.05914 MSECS" Números curiosos a 10 ^ 5: "Tiempo transcurrido: 1.444254 MSECS" Suma números curiosos hasta 10 ^ 2: "Tiempo transcurrido: 40.795465 MSECS" Suma números curiosos hasta 10 ^ 3: "Tiempo transcurrido: 141.380443 MSECS" Suma números curiosos hasta 10 ^ 4: "Tiempo transcurrido: 859.525103 MSECS" Números curiosos de suma hasta 10 ^ 5: "Tiempo transcurrido: 5655.463085 MSECS"   
Original en ingles

I was inspired by a certain recent question to try my hand at this challenge:

Project Euler #34: Digit factorials

\$19!\$ is a curious number, as \$1!+9!=1+362880=362881\$ is divisible by \$19\$.

Find the sum of all numbers below \$N\$ which divide the sum of the factorial of their digits. Note: as \$1!,2!,\cdots,9!\$ are not sums, so they are not included.

Input Format: Input contains an integer \$N\$

Output Format: Print the answer corresponding to the test case.

Constraints: \$10^1 \le N \le 10^5\$

Sample Input

20 

Sample Output

19 

The code works great, with the only unfortunate problem being outside of my control, but is preventing me from completing the "official" HackerRank challenge: STDIN doesn't work (yet) with clojure. I Googled this and Stack Overflowed that, and seems everyone is having issues (even simple STDIN on HackerRank website using Clojure language errors out) so I know it's not just me. The function that directly addresses the challenge is sum-all-curious-numbers-up-to.

I wrote a whole bunch of tests to ensure that everything was working correctly. I also included some benchmark tests at the bottom of the post, as I am also interested in improving performance, if there is an idiomatic way to do so.

This is my first "real" challenge using FP and so I would like criticism on any and all aspects of the code, including algorithms/logic, style and tests. I also have a few specific areas of focus that I would like addressed in more general terms:

  1. Is it idiomatic FP to throw exceptions, such as IllegalArgumentException which I often do here, or would it make more sense to return a falsey value when functions are passed an argument they are not designed to handle?

  2. Specifically with explode-num-to-digits (and consequently test-explode-num-to-digits) is that function trying to handle too many edge cases? I thought it would be "neat" to be able to accept numbers as strings and parse those the same as a regular number, but does it even make sense for this function to handle such arguments?

Note: I added a ;` and ;' at the end of a line near the top of the files, these are to compensate for the fact the Lisp syntax highlighting on Code Prettify/SE is borked.

HackerRankProjectEuler34.clj

(ns   ^{:author Phrancis}   sandbox.HackerRankProjectEuler34)  ;; HackerRank Project Euler #34: Digit factorials ;; https://www.hackerrank.com/contests/projecteuler/challenges/euler034  (defmacro throw-number-exc   "Shortcut 'not a number' exception with optional argument"   ([]     `(throw (IllegalArgumentException. "Not a number"))) ;`   ([arg]     `(throw (IllegalArgumentException. (str "Not a number: " ~arg)))) ;`   ([arg msg]     `(throw (IllegalArgumentException. (str ~msg " " ~arg))))) ;`  (defn exponent   "Given a number N, returns N^x (i.e. N to the power of x)"   [N x]   (if (and (number? N) (number? x))     (cond       (= N 0) 0       (= x 0) 1       (> x 0) (reduce * (repeat x N))       (< x 0) (/ 1 (exponent N (- x))))     (if (number? x)       (throw-number-exc N)       (throw-number-exc x))))  (defn factorial   "Given a number N, returns N! (i.e., N factorial)"   [N]   (if (number? N)     (cond       (= N 0) 1       (>= N 1) (* N (factorial (- N 1)))       (<= N -1) (- (* (- N) (factorial (- (- N) 1)))))     (throw-number-exc N)))  (defn explode-num-to-digits   "Given a nmber N, returns a list of its separate digits."   [N]   (if (number? N)     ;; Maps a lambda expr which converts a char to base-10 digit     ;; to each char of a string representation of N.     (if (>= N 0)       (map #(Character/digit % 10) (str N))       (map #(Character/digit % 10) (str (- N))))     ;; Special cases where N is passed as a string, but would still be     ;; a valid number otherwise, including leading zeroes     ;; valid examples: "123", "01", "007", "-123"     (if (and           (string? N)           (re-matches #"[0-9]+" (clojure.string/replace-first N #"-" "")))       (map #(Character/digit % 10) (clojure.string/replace-first N #"-" ""))       (throw-number-exc N))))  (defn sum-of-factorials-of-digits   "Given a number N, returns the sum of the factorials of each digit of N.   Example: N = 35 -> 3! + 5! = 6 + 120 = 126"   [N]   (if (number? N)     (reduce + (map #(factorial %) (explode-num-to-digits N)))     (throw-number-exc N)))  (defn is-curious-number   "A 'Curious Number' is a number where the sum of the factorial of each of its digits   is evenly divisible by the number itself.   For example 19 is a 'Curious Number': 1! + 9! = 1 + 362880 = 362881, and 362881 % 19 = 0."   [N]   (if (number? N)     (if (= (mod (sum-of-factorials-of-digits N) N) 0)       N       false)     (throw-number-exc N)))  (defn list-all-curious-numbers-between   "Given numbers min and max, return a list of all 'Curious Numbers' from min to max inclusive."   [min max]   (if (and (number? min) (number? max))     (remove nil? (map #(when (is-curious-number %) %) (range min (+ max 1))))   (if (number? max)     (throw-number-exc min)     (throw-number-exc max))))  (defn sum-all-curious-numbers-up-to   "Given a number N between 10 and 10^5, return the sum of a list of all 'Curious Numbers' 10 to N inclusive.   This is as per constraint: 10 xe2x89xa4 N xe2x89xa4 10^5 "   [N]   (if (number? N)     (if (and (>= N 10) (<= N (exponent 10 5)))       (reduce + (list-all-curious-numbers-between 10 N))       (throw-number-exc N "Number is not 10 <= N <= 10^5: "))     (throw-number-exc N))) 

HackerRankProjectEuler34Test.clj

(ns   ^{:author Phrancis}   sandbox.HackerRankProjectEuler34Test   (:require [clojure.test :as t])   (:require sandbox.HackerRankProjectEuler34Test)   (:use sandbox.HackerRankProjectEuler34))  (t/run-tests 'sandbox.HackerRankProjectEuler34Test) ;'  (t/deftest test-throw-number-exc   (t/is (thrown? IllegalArgumentException (throw-number-exc)))   (t/is (thrown? IllegalArgumentException (throw-number-exc "foo")))   (t/is (thrown? IllegalArgumentException (throw-number-exc "bar" "this is an error message: "))))  (t/deftest test-exponent   (t/is (thrown? IllegalArgumentException (exponent 2 "foo")))   (t/is (thrown? IllegalArgumentException (exponent "bar" 2)))   (t/is (= 0 (exponent 0 0)))   (t/is (= 0 (exponent 0 2)))   (t/is (= 1 (exponent 2 0)))   (t/is (= 2 (exponent 2 1)))   (t/is (= 4 (exponent 2 2)))   (t/is (= -2 (exponent -2 1)))   (t/is (= 4 (exponent -2 2)))   (t/is (= -8 (exponent -2 3)))   (t/is (= 16 (exponent -2 4)))   (t/is (= 1/2 (exponent 2 -1)))   (t/is (= 1/4 (exponent 2 -2)))   (t/is (= 1/125 (exponent 5 -3))))  (t/deftest test-factorial   (t/is (thrown? IllegalArgumentException (factorial "foo")))   (t/is (= 1 (factorial 0)))   (t/is (= 1 (factorial 1)))   (t/is (= 2 (factorial 2)))   (t/is (= 6 (factorial 3)))   (t/is (= 24 (factorial 4)))   (t/is (= 120 (factorial 5)))   (t/is (= 720 (factorial 6)))   (t/is (= 5040 (factorial 7)))   (t/is (= 40320 (factorial 8)))   (t/is (= 362880 (factorial 9)))   (t/is (= -1 (factorial -1)))   (t/is (= -2 (factorial -2)))   (t/is (= -6 (factorial -3)))   (t/is (= -24 (factorial -4)))   (t/is (= -120 (factorial -5)))   (t/is (= -720 (factorial -6)))   (t/is (= -5040 (factorial -7)))   (t/is (= -40320 (factorial -8)))   (t/is (= -362880 (factorial -9))))  (t/deftest test-explode-num-to-digits   (t/is (thrown? IllegalArgumentException (explode-num-to-digits "foo")))   ;; standard cases:   (t/is (= (list 0) (explode-num-to-digits 0)))   (t/is (= (list 0) (explode-num-to-digits 0000)))   (t/is (= (list 1 2 3) (explode-num-to-digits 123)))   (t/is (= (list 3 2 1) (explode-num-to-digits 321)))   (t/is (= (list 1 2 3) (explode-num-to-digits -123)))   ;; special case strings to be considered as numbers, including 1 or more leading zeroes:   (t/is (= (list 1 2 3) (explode-num-to-digits "123")))   (t/is (= (list 1 2 3) (explode-num-to-digits "-123")))   (t/is (= (list 0 1) (explode-num-to-digits "01")))   (t/is (= (list 0 0 7) (explode-num-to-digits "007")))   (t/is (= (list 0 0 0 0 0 0 0) (explode-num-to-digits "0000000"))))  (t/deftest test-sum-of-factorials-of-digits   (t/is (thrown? IllegalArgumentException (sum-of-factorials-of-digits "foo")))   (t/is (= 1 (sum-of-factorials-of-digits 0)))   (t/is (= 24 (sum-of-factorials-of-digits 4)))   (t/is (= 9 (sum-of-factorials-of-digits 123)))   (t/is (= 33 (sum-of-factorials-of-digits 1234))))  ;; Curious Numbers to 10^5: (19 56 71 93 145 219 758 768 7584 7684 9696 10081 21993 40585)  (t/deftest test-is-curious-number   (t/is (thrown? IllegalArgumentException (is-curious-number "foo")))   (t/is (false? (is-curious-number 10)))   (t/is (= 19 (is-curious-number 19)))   (t/is (false? (is-curious-number 20)))   (t/is (= 56 (is-curious-number 56)))   (t/is (false? (is-curious-number 57))))  (t/deftest test-list-all-curious-numbers-between   (t/is (thrown? IllegalArgumentException (list-all-curious-numbers-between "foo" 100)))   (t/is (thrown? IllegalArgumentException (list-all-curious-numbers-between 10 "bar")))   (t/is (=           (list 19 56 71 93 145 219 758 768 7584 7684 9696 10081 21993 40585)           (list-all-curious-numbers-between 10 (exponent 10 5)))))  (t/deftest test-sum-all-curious-numbers-up-to   (t/is (thrown? IllegalArgumentException (sum-all-curious-numbers-up-to "foo")))   ;; test challenge constraint: 10 xe2x89xa4 N xe2x89xa4 10^5   (t/is (thrown? IllegalArgumentException (sum-all-curious-numbers-up-to 9)))   (t/is (thrown? IllegalArgumentException (sum-all-curious-numbers-up-to (exponent 11 5))))   ;; test values   (t/is (= 19 (sum-all-curious-numbers-up-to 55)))   (t/is (= 75 (sum-all-curious-numbers-up-to 70)))   (t/is (= 146 (sum-all-curious-numbers-up-to 92)))   (t/is (= 239 (sum-all-curious-numbers-up-to 144)))) 

Benchark tests

(defn -main   [& args]   ;; benchmark tests   (print "Curious Numbers to 10^2: ") (time (list-all-curious-numbers-between 10 (exponent 10 2)))   (print "Curious Numbers to 10^3: ") (time (list-all-curious-numbers-between 10 (exponent 10 3)))   (print "Curious Numbers to 10^4: ") (time (list-all-curious-numbers-between 10 (exponent 10 4)))   (print "Curious Numbers to 10^5: ") (time (list-all-curious-numbers-between 10 (exponent 10 5)))   (print "Sum Curious Numbers up to 10^2: " ) (time (sum-all-curious-numbers-up-to (exponent 10 2)))   (print "Sum Curious Numbers up to 10^3: " ) (time (sum-all-curious-numbers-up-to (exponent 10 3)))   (print "Sum Curious Numbers up to 10^4: " ) (time (sum-all-curious-numbers-up-to (exponent 10 4)))   (print "Sum Curious Numbers up to 10^5: " ) (time (sum-all-curious-numbers-up-to (exponent 10 5)))) 

Results

There seems to be a big time increase (comparatively) going from \$10^4\$ to \$10^5\$, I realize it is a whole order of magnitude higher but the increase in computation time seems to not be proportional to the other increases in one order of magnitude.

Curious Numbers to 10^2: "Elapsed time: 0.481473 msecs" Curious Numbers to 10^3: "Elapsed time: 0.055067 msecs" Curious Numbers to 10^4: "Elapsed time: 0.05914 msecs" Curious Numbers to 10^5: "Elapsed time: 1.444254 msecs" Sum Curious Numbers up to 10^2: "Elapsed time: 40.795465 msecs" Sum Curious Numbers up to 10^3: "Elapsed time: 141.380443 msecs" Sum Curious Numbers up to 10^4: "Elapsed time: 859.525103 msecs" Sum Curious Numbers up to 10^5: "Elapsed time: 5655.463085 msecs"
                 

Lista de respuestas

4
 
vote
vote
La mejor respuesta
 

Realmente no conozco Clojure, pero disfruté leyendo este código. Es especialmente bueno que haya incluido pruebas de unidad. Aunque tengo algunos nitpicks.


De acuerdo con sus pruebas, el exponente de 0 es 0:

    (t/is (= 0 (exponent 0 0)))   

Pero por matemáticas, $ 0 ^ 0 $ debe ser 1.


De manera similar, el factorial generalmente no se define para números negativos, ¡pero usted define $ (- N)! $ como $ - (n!) $. Sin embargo, no es un gran problema.


algo más que me parece extraño es que is-curious-number devuelve dos tipos de tipos, booleano o numérico:

    (t/is (false? (is-curious-number 10)))   (t/is (= 19 (is-curious-number 19)))   

Me pregunto si esta es una práctica común en Clojure por alguna razón, porque normalmente no es una gran idea. Parecería tener sentido devolver boolean, como lo indica el nombre de la función.


  1. Específicamente con explosiones de números a dígitos (y, en consecuencia, prueba de explosión a dígitos) ¿Es la función que intenta manejar demasiados casos de borde? Pensé que sería "limpio" para poder aceptar números como cuerdas y analizar los mismos que un número regular, pero ¿incluso tiene sentido para esta función para manejar dichos argumentos?

Creo que es una trampa común cuando los programadores intentan hacer algo "limpio", que realmente no necesitan, y luego en problemas para ello. El desafío establece que la entrada es un número $ n $. No tendrá mucho sentido pasar nada más, Solo agrega la tediosa sobrecarga de la validación numérica. No es necesario apoyar las entradas de cadena, así que no.

Por supuesto, al leer de STDIN, debe convertir las cadenas a los números en algún momento, pero debe hacerlo solo una vez, lo más cerca posible del punto de entrada posible, y deje que las capas internas de su solución de manera segura Supongamos que recibirán valores numéricos válidos.

Por ejemplo, no hay necesidad de exponent para manejar argumentos no numéricos. Se usa en niveles más bajos de su solución, y debe poder esperar proteger por los niveles más altos.

  1. es que Idiomatic FP arroja excepciones, como IlleGalArgumentException que a menudo hago aquí, o ¿daría más sentido devolver un valor falso cuando las funciones se les pasa un argumento que no están diseñados para manejar?

Por mi respuesta a su segunda pregunta, esta pregunta simplemente desaparece (en lo que respecta a este proyecto Euler Ejemplo). Además, la validación de entrada es generalmente redundante en los desafíos en línea. En las aplicaciones de la vida real, el código debe ser robusto y vigilante al manejar cualquier tipo de entrada no confiable, pero generalmente no es el caso en los desafíos en línea.

 

I don't really know Clojure, but I enjoyed reading this code. It's especially great that you've included unit tests. I have a few nitpicks though.


According to your tests, the exponent of 0 is 0:

  (t/is (= 0 (exponent 0 0))) 

But by math, \$0^0\$ should be 1.


Somewhat similarly, factorial is usually not defined for negative numbers, but you define \$(-n)!\$ as \$-(n!)\$. Not a big deal though.


Something else that I find strange is that is-curious-number returns two kinds of types, boolean or numeric:

  (t/is (false? (is-curious-number 10)))   (t/is (= 19 (is-curious-number 19))) 

I'm wondering if this is common practice in Clojure for some reason, because normally it's not a great idea. It would seem to make sense to return boolean, as the function name implies.


  1. Specifically with explode-num-to-digits (and consequently test-explode-num-to-digits) is that function trying to handle too many edge cases? I thought it would be "neat" to be able to accept numbers as strings and parse those the same as a regular number, but does it even make sense for this function to handle such arguments?

I think it's a common trap when programmers try to do something "neat", that they don't really need, and then get into trouble for it. The challenge states that the input is a number \$N\$. It won't make much sense passing anything else, it only adds the tedious overhead of numeric validation. It's not necessary to support string inputs, so don't.

Of course, when reading from STDIN, you do need to convert strings to numbers at some point, but you should do that only once, as close to the point of input as possible, and let the inner layers of your solution safely assume that they will receive valid numeric values.

For example there's no need for exponent to handle non-numeric arguments. It's used at lower levels of your solution, and should be able to expect to be protected by the higher levels already.

  1. Is it idiomatic FP to throw exceptions, such as IllegalArgumentException which I often do here, or would it make more sense to return a falsey value when functions are passed an argument they are not designed to handle?

By my answer to your second question, this question simply vanishes (as far as this Project Euler example is concerned). In addition, input validation is generally redundant in online challenges. In real life applications the code needs to be robust and vigilant when handling any kind of untrusted input, but this is generally not the case in online challenges.

 
 
         
         

Relacionados problema

4  Parser NetString en Lisp comunes  ( Netstring parser in common lisp ) 
A continuación se muestra una NetString Parser I escribí en Common Lisp. El documento contiene el uso y la devolución. (defun parse-netstring (netstring ...

5  Multiplicación de matriz y producto de punto  ( Matrix multiplication and dot product ) 
Ejercicio 2.37. Supongamos que representamos vectores v = (vi) como secuencias de números, y matrices m = (MIJ) como secuencias de vectores (las filas ...

1  Árbol cuadrado con mapas y recursión  ( Square tree using maps and recursion ) 
Defina un procedimiento de árbol cuadrado análogo a la Procedimiento de la lista cuadrada del ejercicio. 2.21. Es decir, la lista cuadrada debe comportar...

6  Redefinir las hojas de recuento como una acumulación  ( Redefine count leaves as an accumulation ) 
Ejercicio 2.35. Redefinir hojas de recuento Desde la sección 2.2.2 como acumulación: (define (count-leaves t) (accumulate <??> <??> (map <??> <??>))) ...

5  Invertir en términos de pliegue derecho y plegable-izquierda  ( Reverse in terms of fold right and fold left ) 
Ejercicio 2.39 Completar las siguientes definiciones de reversa (Ejercicio 2.18) en términos de pliegue derecho y plegable-izquierda del ejercicio 2....

1  Ejercicio: limpiar y formatear un número de teléfono en Clojure  ( Exercism clean and format a phone number in clojure ) 
Declaración de problemas Número de teléfono Escriba un programa que limpie los números de teléfono ingresados ​​por el usuario para que puedan ser envi...

1  ¿Está usando defvar para una variable no global OK?  ( Is using defvar for a non global variable ok ) 
Estoy llamando defvar en medio de una definición de función. Y hasta ahora, siempre he visto su uso, con defparameter para la variable global. Como *erro...

6  Determinar si f (n) = n ^ 2 + 3n + 5 es divisible por 121  ( Determining if fn n2 3n 5 is ever divisible by 121 ) 
Dado el siguiente problema: Se conjeture eso para cualquier $ N & GT; 0 $, $ N ^ 2 + 3n + 5 $ nunca es divisible por 121. Pruebe esta conjetura por ...

3  Buscando caracteres repetidos en una secuencia de caracteres  ( Searching for repeated characters in a sequence of characters ) 
El siguiente código resuelve este problema: Los 3072 caracteres a continuación contienen una secuencia de 5 caracteres que es repetido. Sin embargo, hay ...

4  Función abstracta del mapa del árbol  ( Abstract tree map function ) 
Ejercicio 2.31. Resumen tu respuesta Para ejercer 2.30 para producir un Procedimiento Árbol - Mapa con la propiedad. ese árbol cuadrado podría definirs...




© 2022 respuesta.top Reservados todos los derechos. Centro de preguntas y respuestas reservados todos los derechos