/*
Self describing numbers (Rosetta code) in Picat.
http://rosettacode.org/wiki/Self-describing_numbers
"""
There are several so-called "self-describing" or "self-descriptive" integers.
An integer is said to be "self-describing" if it has the property that, when
digit positions are labeled 0 to N-1, the digit in each position is equal to the number of
times that that digit appears in the number.
For example, 2020 is a four-digit self describing number:
position 0 has value 2 and there are two 0s in the number;
position 1 has value 0 and there are no 1s in the number;
position 2 has value 2 and there are two 2s;
position 3 has value 0 and there are zero 3s.
Self-describing numbers < 100.000.000: 1210, 2020, 21200, 3211000, 42101000.
Task Description
Write a function/routine/method/... that will check whether a given positive integer is self-describing.
As an optional stretch goal - generate and display the set of self-describing numbers.
"""
Cf http://hakank.org/picat/magic_sequence.pi
http://hakank.org/picat/magic_sequence_double_list.pi
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 =>
Num = 2020,
magic_sequence2(Num, Sequence),
println(Sequence),
nl.
go2 =>
List = [1210, 2020, 21200, 3211000, 42101000,
123456,98,10,-121],
foreach(N in List)
magic_sequence(N,_S),
println(N)
end,
nl.
% Non-CP variant: check all numbers of a range
go3 =>
foreach(N in 1..10_000_000)
if magic_sequence2(N,_S) then
println(N)
end
end,
nl.
%
% Using CP. Fast, but the largest length is 8 (42101000) due to Picat's restriced CP domain.
%
go4 =>
Len :: 1..10,
println(findall(Num, (indomain(Len), magic_sequence_len(Len,Num)))),
nl.
%
% Fast. Perhaps cheating since it's not about the numbers but the list of digits.
% It finds all self describing number 1210..9210000001000 in 0.004s.
%
go5 =>
Len :: 1..13,
println(findall(Seq, (indomain(Len), magic_sequence_len2(Len,Seq)))),
nl.
% cp
% cf http://hakank.org/picat/magic_sequence.pi
magic_sequence(Num, Sequence) =>
N = length(Num.to_string()),
Sequence = new_list(N),
Sequence :: 0..N-1,
% extra constraints
N #= sum(Sequence),
to_num(Sequence,10,Num),
scalar_product({ I : I in 0..N-1}, Sequence, N),
% using global_cardinality/2: or N=400: 0.8s
% GC = $[ I-Sequence[I+1] : I in 0..N-1],
% global_cardinality(Sequence,GC),
% using count/4 for N=400: 0.22s
foreach(I in 0..N-1) count(I,Sequence,#=,Sequence[I+1]) end,
solve([ffc,inout], Sequence).
% solve(Sequence).
%
% cp, different approach: checks all solution of a specific length.
% Note: This
%
magic_sequence_len(Len, Num) =>
Sequence = new_list(Len),
Sequence :: 0..Len-1,
% extra constraints
Len #= sum(Sequence),
scalar_product({ I : I in 0..Len-1}, Sequence, Len),
to_num(Sequence,10,Num),
% using global_cardinality/2: or N=400: 0.8s
% GC = $[ I-Sequence[I+1] : I in 0..N-1],
% global_cardinality(Sequence,GC),
% using count/4 for N=400: 0.22s
foreach(I in 0..Len-1) count(I,Sequence,#=,Sequence[I+1]) end,
solve([ffc,inout], Sequence).
% solve(Sequence).
%
% cp, different approach: checks all solution of a specific length.
% A variant of magic_sequence_len/2 where the list is used instead
% of the number
%
magic_sequence_len2(Len, Sequence) =>
Sequence = new_list(Len),
Sequence :: 0..Len-1,
% the digits must be <= 9
max(Sequence) #<= 9,
% extra constraints
Len #= sum(Sequence),
scalar_product([I : I in 0..Len-1], Sequence, Len),
% to_num(Sequence,10,Num),
% using global_cardinality/2: or N=400: 0.8s
% GC = $[ I-Sequence[I+1] : I in 0..Len-1],
% global_cardinality(Sequence,GC),
% using count/4 for N=400: 0.22s
foreach(I in 0..Len-1) count(I,Sequence,#=,Sequence[I+1]) end,
solve([ffc,inout], Sequence).
% solve(Sequence).
%
% no cp
%
magic_sequence2(Num,L) =>
L = [ I.to_integer() : I in Num.to_string()],
Len = L.len,
if sum(L) != Len then fail end,
foreach(J in L)
% cannot be a digit larger than the length of Num
if J >= Len then fail end
end,
foreach(I in 0..Len-1)
% if [1 : J in L, I==J].length != L[I+1] then
if sum([1 : J in L, I==J]) != L[I+1] then
fail
end
end.
%
% 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]).