# Fun "interview" question solved easily in Julia

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.

13 Likes

I went for `sum(1:5) * 11111 * prod(1:4)`.

7 Likes

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])`

5 Likes

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!

8 Likes

If the interviewee gets the result 6,666,660 or 66,666,000, the chances for them being GPT-4 are high.

1 Like

I would hire the person who gives the answer instantly without need for a computer

1 Like

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!.

1 Like

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
``````
1 Like

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.

4 Likes

//@gucken How did you come up with this average though ?

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.

5 Likes

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

1 Like

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

1 Like

Yes

Yes, it should be 24 times

There’s a JuMP tutorial for this: