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.