while solving a Kakuro puzzle I decided to brute force a section of the puzzle (see image with 8 squares marked x1…x8)
I wrote a succinct iterator based approach (f1()
in the code below) which is not very efficient compared to 8 nested for loops (f2()
in the code below).
runtime comparison:
julia> @time x = f1();
0.306097 seconds (14.73 M allocations: 1.243 GiB, 18.50% gc time)
julia> @time x = f2();
0.000110 seconds (1.86 k allocations: 58.250 KiB)
The main issue is that the iterator-based code (f1()
) checks all constraints and continue
s to cycle the product iterator in the order of the iterators rather than skipping the relevant iterator.
Is there a syntax for combining filter
and product
which is both efficient, succinct, and readable?
code:
ts(s, n) = length(s) == length(unique(s)) && sum(s) == n
function f1()
for x ∈ Iterators.product((1:9 for i in 1:8)...)
ts((x[1], x[2]), 6) || continue
ts((x[3], x[4], x[5]), 20) || continue
ts((x[6], x[7], x[8]), 10) || continue
ts((x[3], x[6]), 11) || continue
ts((9, 7, x[1], x[4], x[7]), 33) || continue
ts((x[2], x[5], x[8]), 8) || continue
return x
end
end
function f2()
x = zeros(Int, 8)
for x[1] ∈ vcat(1:6,8)
for x[2] ∈ 1:9
x[2] == x[1] && continue
x[1] + x[2] != 6 && continue
for x[3] ∈ 1:9
for x[4] ∈ vcat(1:6,8)
x[4] == x[1] && continue
for x[5] ∈ 1:9
x[5] ∈ (x[2], x[3], x[4]) && continue
x[3] + x[4] + x[5] != 20 && continue
for x[6] ∈ 1:9
x[6] == x[3] && continue
x[3] + x[6] != 11 && continue
for x[7] ∈ vcat(1:6,8)
x[7] ∈ (x[1], x[4], x[6]) && continue
x[1] + x[4] + x[7] != (33-9-7) && continue
for x[8] ∈ 1:9
x[8] ∈ (x[2], x[5], x[6], x[7]) && continue
x[2] + x[5] + x[8] != 8 && continue
x[6] + x[7] + x[8] != 10 && continue
return x
end
end
end
end
end
end
end
end
end