Fun "interview" question solved easily in Julia

Offtopic
,
13

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