/*
Euler #43 in Picat.
"""
The number, 1406357289, is a 0 to 9 pandigital number because it is made up of
each of the digits 0 to 9 in some order, but it also has a rather interesting
sub-string divisibility property.
Let d1 be the 1st digit, d2 be the 2nd digit, and so on. In this way, we
note the following:
* d2d3d4=406 is divisible by 2
* d3d4d5=063 is divisible by 3
* d4d5d6=635 is divisible by 5
* d5d6d7=357 is divisible by 7
* d6d7d8=572 is divisible by 11
* d7d8d9=728 is divisible by 13
* d8d9d10=289 is divisible by 17
Find the sum of all 0 to 9 pandigital numbers with this property.
"""
This Picat model was created by Hakan Kjellerstrand, hakank@gmail.com
See also my Picat page: http://www.hakank.org/picat/
*/
import util.
import cp.
main => go.
go => time(euler43). % , time(euler43b).
% using CP is fast: 0.05s
euler43 =>
Primes = [2,3,5,7,11,13,17],
X = new_list(10),
X :: 0..9,
all_different(X),
foreach({I,P} in zip(2..8, Primes))
(100*X[I]+10*X[I+1]+X[I+2]) mod P #= 0
end,
All=solve_all(X),
Sum = 0,
foreach(A in All)
to_num(A, 10, Num),
% writeln(A),
Sum := Sum + Num
end,
writeln(sum=Sum),
nl.
to_num(List, Base, Num) =>
Len = length(List),
Num = sum([List[I]*Base**(Len-I) : I in 1..Len]).
% Here is Neng-Fa's simplification of euler43/0:
euler43b =>
Primes = [2,3,5,7,11,13,17],
X = new_list(10),
X :: 0..9,
all_different(X),
foreach({I,P} in zip(2..8, Primes))
(100*X[I]+10*X[I+1]+X[I+2]) mod P #= 0
end,
All=solve_all(X),
writeln(sum([to_num2(A) : A in All])),
nl.
to_num2(List) = Num =>
Str = [Char : D in List, D.to_string()=[Char]],
Num = Str.to_integer().
/*
% Notes:
%
% - got this error/warning ** Error : assignment_in_condition:while
% - it eats a lot of memory
% - it's very slow
%
% 34.7s
euler43c =>
PP = [2, 3, 5, 7, 11, 13, 17],
% skipping all permutations that starts with [0,..]
S = [1, 0, 2, 3, 4, 5, 6, 7, 8, 9],
Sum = 0,
Sdown = S.sort_down(),
while (S != Sdown)
S2 = S.to_string(),
I = 1,
% it's here the "assignment_in_condition:while" error come
while (I =< 7, [S[J].to_string() : J in 1+I..I+3].flatten().to_integer() mod PP[I] == 0)
I := I + 1
end,
if I == 8 then
println(s2=S2),
Sum := Sum + [S[J].to_string() : J in 1..S.length].flatten().to_integer()
end,
S := next_permutation(S)
end,
println(Sum).
next_permutation(P) = Perm =>
Perm1 = P,
N = Perm1.length,
K = N - 1,
while (Perm1[K] > Perm1[K+1], K >= 0)
K := K - 1
end,
% if K == 0 then Perm1 := [] end, % return
if K > 0 then
J = N,
while (Perm1[K] > Perm1[J]) J := J - 1 end,
Tmp := Perm1[K],
Perm1[K] := Perm1[J],
Perm1[J] := Tmp,
R = N,
S = K + 1,
while (R > S)
Tmp := Perm1[R],
Perm1[R] := Perm1[S],
Perm1[S] := Tmp,
R := R - 1,
S := S + 1
end
end,
Perm = Perm1.
*/