Solving a not-so-easy riddle with clojure.math.combinatorics
source link: https://blog.klipse.tech/clojure/2016/09/16/combinatorics-riddle.html
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
A friend of mine (Hillel Kahana) shared with me a riddle that his 10-year old son brought from a math workshop. At first, the riddle sounded easy…
The riddle
You’ve got the first 6 digits 1,2,3,4,5 and 6.
You have to partition the digits into 3 numbers x
, y
and z
where:
x
is a 3-digit numbery
is a 2-digit numberz
is a single digit number
Such that the multiplication x*y*z
is maximal.
Each digit must be used only once.
For instance, 123*45*6
:
xxxxxxxxxx
(* 123 45 6)
the evaluation will appear here (soon)...
But, obviously we can do better.
Sounds easy. Right?
So give it a try.
Before reading the rest of this article, take a pencil and a sheet of paper and try to find the solution.
Have fun with the digits!
Elegant or brute force
Maybe, you are a math genius and you are able to find the elegant solution to this riddle and to prove mathematically that your solution is correct.
It’s not my case, so we are going to go with a brute force algorithm with a couple of lines of clojure
code.
We are going to go over the 6!
permutations and take the one that leads to the greatest number.
But, wait a minute 6!=720
!
How are we going to generate those 720 permutations?
Hmm….
Clojure.math.combinatorics to the rescue
There is a clojure
library named clojure.math.combinatorics
(by Mark Engelberg) that has a permutations
function (and a lot of other useful functions: check it here).
For instance, let’s generate all the 3!
permutations of [1 2 3]
:
xxxxxxxxxx
(ns my.combinatorics
(:require [clojure.math.combinatorics :refer [permutations]]))
(permutations [1 2 3])
xxxxxxxxxx
the evaluation will appear here (soon)...
The solution
With permutations
, it’s really easy to find the solution to the riddle:
xxxxxxxxxx
(apply max-key (fn [[a b c d e f]]
(* (+ (* 100 a) (* 10 b) c)
(+ (* 10 d) e)
f))
(permutations (range 1 7)))
xxxxxxxxxx
the evaluation will appear here (soon)...
max-key
returns the value for which the function is greatest.
If you want to play with more digits, you’d find it more convenient to open the KLIPSE repl, because in this article the code is evaluated as you type…
Clojure rocks!
PS: Do you have a more elegant solution to this riddle? Let us know in the comments below…
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK