Last active
December 26, 2015 10:59
-
-
Save jlemmett/7140649 to your computer and use it in GitHub Desktop.
Annotated example solution to the problem of finding the largest multiple of consecutive five numbers from a long string of numbers, in Clojure.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
;; A helper function that converts a single character string into a numeric value | |
(defn as-int [char] | |
(Character/getNumericValue char)) | |
;; The solution as a one-liner: function that returns the largest multiple of 5 | |
;; consecutive digits in the given string of digits | |
(defn max-of-5-multiply-v1 [str] | |
(apply max (map #(apply * %) (partition 5 1 (map as-int str))))) | |
;; Example of use with the given input string | |
(def numbers-in-string (str "37900490610897696126265185408732594047834333441947" | |
"01850393807417064181700348379116686008018966949867" | |
"75587222482716536850061657037580780205386629145841" | |
"06964490601037178417735301109842904952970798120105" | |
"47016802197685547844962006690576894353336688823830" | |
"22913337214734911490555218134123051689058329294117" | |
"83011983450277211542535458190375258738804563705619" | |
"55277740874464155295278944953199015261800156422805" | |
"72771774460964310684699893055144451845092626359982" | |
"79063901081322647763278370447051079759349248247518")) | |
(max-of-5-multiply-v1 numbers-in-string) | |
;; Returns 34992 | |
;; The annotated solution | |
;; Defines a function named 'max-of-5-multiply-v1' | |
(defn max-of-5-multiply-v1 | |
;; The function takes one argument: `str` - this is the string of numbers | |
[str] | |
;; We `apply` the function `max` to the sequence that is created by the subsequent | |
;; function calls. | |
;; Applying a function to a sequence (rather can calling the function directly) 'unrolls' | |
;; the elements of the sequence into individual arguments to the applied function. | |
;; You cannot call max with a e.g. a vector: (max [1 2 3]) does not work, but calling | |
;; (apply max [1 2 3]) is equivalent to (max 1 2 3). | |
;; max simply returns the largest of the given arguments. Note that we apply max to | |
;; sequence of numbers of any length because max works with any number of arguments. | |
(apply max | |
;; The `map` function applies the function given as its first parameter to each element | |
;; of the collection given as the second parameter and returns a sequence containing | |
;; these 'transformed' elements. | |
(map | |
;; Here we define the function as the first argument to map above. #() is a shorthand | |
;; syntax for defining anonymous functions. The % is a place holder for the single | |
;; input argument to the anonymous function. | |
;; | |
;; This function will be called for each element of the collection that is passed as | |
;; the second argument to the map call above. In this case the anonymous function | |
;; applies the multiplication function to each value it receives. Here we expect to | |
;; always get collections of values since multiplication of a single value doesn't | |
;; work. | |
;; | |
;; Again `apply` unrolls the collection into individual arguments so if an element of | |
;; the input collection were [1 2 3], (apply * [1 2 3]) would result in the | |
;; call (* 1 2 3). | |
#(apply * %) | |
;; The function `partition` takes a sequence and splits it into partitions of length n | |
;; (here n = 5). | |
;; The optional second argument defines how much the input sequence is 'offset' for | |
;; each partition. | |
;; | |
;; Examples: | |
;; (partition 2 '(1 2 3 4)) results in ((1 2) (3 4)) | |
;; (partition 2 1 '(1 2 3 4) results in ((1 2) (2 3) (3 4)) | |
;; | |
;; So in this particular problem we need (partition 5 1 ...) which splits the input | |
;; sequence into partitions of five consecutive elements | |
(partition 5 1 | |
;; The string of digits `str` is converted into a sequence of numeric values by | |
;; calling the `as-int` function for each character in the string separately. | |
;; Since strings are sequences, they can be transformed with `map` like any other | |
;; sequence. | |
(map as-int str))))) | |
;; To follow the flow of execution you have to start from the inner most (map as-int str) | |
;; call in the end: | |
;; | |
;; 1) The string "37900490610..." is transformed into a sequence of numeric values: | |
;; '(3 7 9 0 0 4 ...) | |
;; | |
;; 2) The sequence of numeric values is partitioned into sequences containing five | |
;; consecutive numbers (always offset by one) from the input sequence: | |
;; ((3 7 9 0 0) (7 9 0 0 4) (9 0 0 4 9) ...) | |
;; | |
;; 3) The sequence of sequences is given to map which calls the anonymous #(apply * %) for | |
;; each 5 element sequence resulting in a sequence containing the results of multiplying | |
;; the numbers in each subsequence together: (0 0 0 ... 27216). We get a lot of zeroes in | |
;; the beginning because the first five number sequence without a zero takes a while to | |
;; come up. | |
;; | |
;; 4) max is applied to the sequence of multiples which yields the largest of them. | |
;; Easier to read version of the same function can be achieved with the double arrow or | |
;; 'thread last' macro `->>`. | |
;; | |
;; This macro 'threads' the first argument expression (in this case `str`) through each | |
;; form given as subsequent arguments: str is inserted as the last argument to the first | |
;; form, that form is inserted as the last argument of the second form and so on: | |
(defn max-of-5-multiply-v2 [str] (->> str | |
(map as-int) | |
(partition 5 1) | |
(map #(apply * %)) | |
(apply max))) | |
;; In this example `str` goes as the last argument to the map call: (map as-int str). | |
;; The result of this then is inserted as the last argument to (partition 5 1): | |
;; (partition 5 1 (map as-int str)) and so on. So this will eventually yield exactly the same | |
;; code as the original solution but can be read in a more natural way. | |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment