Re-posted from: http://perfectionatic.org/?p=494
I came across a neat math puzzle involving counting the number of unique combinations in a hypothetical lock where digit order does not count. Before you continue, please watch at least the first minute of following video:
The rest of the video describes two related approaches for carrying out the counting. Often when I run into complex counting problems, I like to do a sanity check using brute force computation to make sure I have not missed anything.
Julia is fantastic choice for doing such computation. It has
C like speed, and with an expressiveness that rivals many other high level languages.
Without further ado, here is the Julia code I used to verify my solution the problem.
d=digits(i,10,n) # The digits on an integer in an array with padding
ds=d |> sort |> join # putting the digits in a string after sorting
get(pat_lookup,ds,false) || (pat_lookup[ds]=true)
println("The number of unique digits is $(length(pat_lookup))")
line 2 we create a dictionary that we will be using to check if the number fits a previously seen pattern. The loop starting in
line 3, examines all possible ordered combinations. The
digits function in
line 4 takes any integer and generate an array of its constituent digits. We generate the unique digit string in
line 5 using pipes, by first sorting the integer array of digits and then combining them in a string. In
line 6 we check if the pattern of digits was seen before and make use of quick short short-circuit evaluation to avoid an