/*
Euler #32 in Picat.
Problem 32
"""
We shall say that an n-digit number is pandigital if it makes use of
all the digits 1 to n exactly once; for example, the 5-digit number,
15234, is 1 through 5 pandigital.
The product 7254 is unusual, as the identity, 39 × 186 = 7254,
containing multiplicand, multiplier, and product is 1 through 9
pandigital.
Find the sum of all products whose multiplicand/multiplier/product
identity can be written as a 1 through 9 pandigital.
HINT: Some products can be obtained in more than one way so be sure
to only include it once in your sum.
"""
This Picat model was created by Hakan Kjellerstrand, hakank@gmail.com
See also my Picat page: http://www.hakank.org/picat/
*/
import cp.
main => go.
go => time(euler32).
% using CP: 0.03s
euler32 =>
L = findall(Res, $pandigital(Res)).remove_dups(),
writeln(sum(L)).
% 1.5s
euler32b =>
Sum = 0,
ProdHash = new_map(),
foreach (A in 2..98, B in A+1..9876)
Prod = A*B,
L = A.to_string() ++ B.to_string() ++ Prod.to_string(),
if L.length == 9, not member('0',L) then
Hash = new_map([(I.to_integer()=1) : I in L]),
if Hash.keys().length == 9, not ProdHash.has_key(Prod) then
% println([a=A, b=B, prod=Prod,l=L]),
Sum := Sum + Prod,
ProdHash.put(Prod,1)
end
end
end,
println(Sum).
%
% converts a number Num to/from a list of integer List given a base Base
%
to_num(List, Base, Num) =>
Len = length(List),
Num #= sum([List[I]*Base**(Len-I) : I in 1..Len]).
pandigital(Res) =>
Len1 :: 1..2,
Len2 :: 3..4,
Len3 #= 4,
Len1 + Len2 + Len3 #= 9,
indomain(Len1),
% set length of lists
X1 = new_list(Len1),
X1 :: 1..9,
X2 = new_list(Len2),
X2 :: 1..9,
X3 = new_list(Len3), % the result
X3 :: 1..9,
% convert to number
Base = 10,
to_num(X1, Base, Num1),
to_num(X2, Base, Num2),
to_num(X3, Base, Res),
% calculate result
Num1 * Num2 #= Res,
Vars = X1 ++ X2 ++ X3,
all_different(Vars),
solve([ff],Vars).