Just thought this would be fun to share. The question is:
“What is the sum of all 5 digit numbers formed using the digits 1,2,3,4 and 5 without repetition.” So numbers like 12345 and 32415 but not 11123.
My solution was to generate all the permutations of [1,2,3,4,5], convert them to numbers, and add them up
using Combinatorics
sum(evalpoly.(10,permutations(1:5)))
(The answer is 3,999,960). What I liked about this solution was using evalpoly(10,x) like an inverse for digits() functions.
I went for sum(1:5) * 11111 * prod(1:4).
Ah very slick. I went with a very literal approach. I also saw an approach that considered pairing up permutations so that each digit place added up to 6 (e.g. 12345 + 54321 = 66666). There would be 5! / 2 = 60 pairs total so the sum would be: 66666 * 60 = 3,999,960.
I guess you could also be lazy and just check all the numbers
sum(x for x in 12345:54321 if sort(digits(x))==[1,2,3,4,5])
I prefer to be clever for code, and brute force for unit tests without any cleverness, math, or assumptions if possible. So for the latter I would go for
let d = Set(1:5)
sum(x for x in 0:100_000 if Set(digits(x)) == d)
end
This is a great question for interviews, because there are so many possible answers and it tells you a lot about the candidate. Thanks for sharing!
If the interviewee gets the result 6,666,660 or 66,666,000, the chances for them being GPT-4 are high.
I would hire the person who gives the answer instantly without need for a computer
Obviously that code was an after-construction to explain 15 * 11111 * 24. I don’t need a computer to sum the first five integers or compute 4!. 
I’m not nearly as clever as any of you, but I managed to do it 
using Combinatorics
vec_to_int(vec) = 10e3 * vec[1] + 1e3 * vec[2] + 100 * vec[3] + 10 * vec[4] + vec[5]
julia> sum(vec_to_int.(permutations(1:5)))
3.99996e6
Yes my comment is that your method does not need a computer since the most hairy operation is 360*11111
Very straightforward. If you replace 10e3 with 10_000 and 1e3 with 1000 your answer will come out as an integer
You don’t need to do even this much work. The average of the numbers is 33333 and there are 120 permutations: 33333*120 = 3999960.
Inspired by Richard Towers | Typescripting the technical interview I wrote a little translation of the Typescript code to julia.
The question:
Given an NxN chessboard, you need to find a way to place N queens on that board safely. Try to keep your code concise.
and the solution:
macro Symbol(x)
Rune = Symbol("typeof(", x, ")")
Expr(:toplevel, :(struct $Rune end), :(const $(esc(x)) = $Rune()))
end
@Symbol ᚾ
@Symbol ᛊ
@Symbol ᛚ
@Symbol ᛞ
const Nil = typeof(ᚾ)
struct Cons{x, xs} end
first( ::Type{T}) where {T} = T.parameters[1]
second(::Type{T}) where {T} = T.parameters[2]
const True = typeof(ᛊ)
const False = typeof(ᛚ)
@generated Not(::Type{T}) where {T} = T <: True ? False : T <: False ? True : error()
@generated Or( ::Type{A}, ::Type{B}) where {A, B} = A <: True ? True : B <: True ? True : False
@generated AnyTrue(::Type{list}) where {list} = list <: Cons ? let x = first(list), xs = second(list)
x <: True ? True : AnyTrue(xs)
end : False
const Zero = typeof(ᛞ)
struct S{N} end
const One = S{Zero}
const Two = S{One}
const Three = S{Two}
const Four = S{Three}
const Five = S{Four}
const Six = S{Five}
@generated Equals(::Type{a}, ::Type{b}) where {a, b} = (a <: S) ? let a_ = first(a)
b <: S ? let b_ = first(b)
Equals(a_, b_)
end : False
end : b <: Zero ?
True : False
@generated AbsDiff(::Type{a}, ::Type{b}) where {a, b} = a <: S ? let a_ = first(a)
b <: S ? let b_ = first(b)
AbsDiff(a_, b_)
end : a
end : b <: S ? b : Zero
@generated RangeFromZeroTo(::Type{n}, ::Type{xs}=Nil) where {n, xs} = n <: S ? let n_ = first(n)
RangeFromZeroTo(n_, Cons{n, xs})
end : Cons{Zero, xs}
struct Queen{x, y} end
@generated RowOfQueens(::Type{cols}, ::Type{row}) where {cols, row} = cols <: Cons ? let col = first(cols), cols_ = second(cols)
Cons{Queen{row, col}, RowOfQueens(cols_, row)}
end : cols
@generated Threatens(::Type{a}, ::Type{b}) where {a, b} = a <: Queen ? let ax = first(a), ay = second(a)
b <: Queen ? let bx = first(b), by = second(b)
Or(
Or(Equals(ax, bx), Equals(ay, by)),
Equals(AbsDiff(ax, bx), AbsDiff(ay, by))
)
end : error()
end : error()
@generated ThreateningQueens(::Type{placedQueens}, ::Type{queen}) where {placedQueens, queen} =
placedQueens <: Cons ? let placedQueen = first(placedQueens), placedQueens_ = second(placedQueens)
Cons{
Threatens(placedQueen, queen),
ThreateningQueens(placedQueens_, queen)
}
end : Nil
@generated Safe(::Type{placedQueens}, ::Type{queen}) where {placedQueens, queen} = Not(AnyTrue(ThreateningQueens(placedQueens, queen)))
@generated FilterSafeQueens(::Type{candidates}, ::Type{placedQueens}) where {candidates, placedQueens} =
candidates <: Cons ? let q = first(candidates), qs = second(candidates)
Safe(placedQueens, q) <: True ?
Cons{q, FilterSafeQueens(qs, placedQueens)} : FilterSafeQueens(qs, placedQueens)
end : Nil
@generated Next(::Type{row}, ::Type{placedQueens} = Nil) where {row, placedQueens} =
FilterSafeQueens(RowOfQueens(RangeFromZeroTo(N), row), placedQueens)
@generated SolveNextRow(::Type{row}, ::Type{placedQueens}) where {row, placedQueens} =
Solve(Next(S{row}, placedQueens), S{row}, placedQueens)
@generated Solve(::Type{candidates}, ::Type{row}, ::Type{placedQueens}) where {candidates, row, placedQueens} =
Equals(row, N) <: True ? candidates <: Cons ? let x = first(candidates)
Cons{x, placedQueens}
end : Nil : candidates <: Cons ? let x = first(candidates), xs = second(candidates)
SolveNextRow(row, Cons{x, placedQueens}) <: Nil ?
Solve(xs, row, placedQueens) : SolveNextRow(row, Cons{x, placedQueens})
end : Nil
const N = Six
const Solution = Solve(Next(Zero), Zero, Nil)
Cons{
Queen{S{S{S{S{S{S{var"typeof(ᛞ)"}}}}}}, S{S{S{S{S{var"typeof(ᛞ)"}}}}}},
Cons{
Queen{S{S{S{S{S{var"typeof(ᛞ)"}}}}}, S{S{S{var"typeof(ᛞ)"}}}},
Cons{
Queen{S{S{S{S{var"typeof(ᛞ)"}}}}, S{var"typeof(ᛞ)"}},
Cons{
Queen{S{S{S{var"typeof(ᛞ)"}}}, S{S{S{S{S{S{var"typeof(ᛞ)"}}}}}}},
Cons{
Queen{S{S{var"typeof(ᛞ)"}}, S{S{S{S{var"typeof(ᛞ)"}}}}},
Cons{
Queen{S{var"typeof(ᛞ)"}, S{S{var"typeof(ᛞ)"}}},
Cons{Queen{var"typeof(ᛞ)", var"typeof(ᛞ)"},
var"typeof(ᚾ)"}}}}}}}
julia> @code_typed Solve(Next(Zero), Zero, Nil)
CodeInfo(
1 ─ return Solution
) => Type{Solution}
As you can see, this is an easy, concise and natural way to solve this interview question in julia.
There is a famous story about Gauss as a schoolboy immediately writing down the answer when given the assignment to sum the integers from 1 to 100. The “trick”is to make a 100x2 matrix with first row 1 … 100 and second row 100 … 1. Each column sums to 101, so the sum is
100x101/2.
The same trick works here: make a matrix with rows the permutations of 1…5.
Each column has each digit occurring 12 times and the sum of 1…5 is 15.
John
I believe you mean 24 times. Cf. Fun "interview" question solved easily in Julia - #2 by GunnarFarneback
digits = [1, 2, 3, 4, 5]
perms = permutations(digits)
total_sum = sum([parse(Int64, join(perm)) for perm in perms])
Gauss’s pairing trick seems more similar to RobertGregg’s addition of reversed pairs to 66666 earlier. Your more straightforward matrix solution should have each digit occurring 5!/5=24 times: 11111*(1+2+3+4+5)*24=3999960
Yes
Yes, it should be 24 times
There’s a JuMP tutorial for this: