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

1 Like

I’m not nearly as clever as any of you, but I managed to do it :wink:

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
2 Likes

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 :wink:

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: