CHR : Project Euler 40-49

40.swi

:- use_module(library(chr)).
:- chr_option(optimize, full).
:- chr_constraint solve(+int), digit(+int,+int,+int), mul(+int), problem40.

problem40 <=> solve(1).

solve(1000000) <=> true.
solve(N)       <=> digit(N,0,0), N1 is N*10, solve(N1).

digit(N,0,0) <=> N < 10 | mul(N).
digit(N,D,Total)
<=> X is 9*10**D, D1 is D+1, T1 is Total+X*D1, N > T1 
  | digit(N,D1,T1).
digit(N,D,Total)
<=> T1 is N-Total, D1 is D+1, N1 is 10**D+T1//D1, R is T1 rem D1,
    X is N1//10**(D1-R) rem 10, mul(X).

mul(M), mul(N) <=> X is M*N, mul(X).

41.swi

:- use_module(library(chr)).
:- chr_option(optimize, full).
:- chr_type list(T) ---> []; [T|list(T)].
:- chr_constraint
	digits(+list(int)), cat(+list(int),+list(int)),
	answer(+int), problem41.

problem41 <=> digits([]).

answer(_) \ digits(_) <=> true.
answer(_) \ cat(_,_)  <=> true.

digits(L) <=> length(L,7), d2i(L,N), is_prime(N) | answer(N).
digits(L) <=> length(L,7) | true.
digits(L) <=> subtract([7,6,5,4,3,2,1],L,L1), cat(L,L1).

cat(L,[H|T]) <=> append(L,[H],L1), digits(L1), cat(L,T).

d2i(L,X)       :- d2i(L,0,X).
d2i([],X,X)    :- !.
d2i([H|T],N,X) :- N1 is N*10+H, d2i(T,N1,X).

is_prime(2) :- !.
is_prime(N) :- N > 2, N rem 2 =\= 0, is_prime(N,3).
is_prime(N,P) :- N < P*P.
is_prime(N,P) :- N rem P =\= 0, P1 is P+1, is_prime(N,P1).

42.swi

:- use_module(library(clpfd)).
:- use_module(library(chr)).
:- chr_option(optimize, full).
:- chr_type list(T) ---> []; [T|list(T)].
:- chr_constraint list(+list(int)), sum(+int), problem42.

problem42 <=> csv_read_file('words.txt',[H|_]), H =.. [_|T],
              maplist(val,T,L), list(L).

list([H|T]) <=> triangle(_,H) | sum(1), list(T).
list([_|T]) <=> list(T).
list([])    <=> true.

sum(M), sum(N) <=> X is M+N, sum(X).

val(Atom,X) :- atom_codes(Atom,L), sumlist(L,N), length(L,M), X is N-M*(0'A-1).

triangle(N,X) :- N #> 0, 2*X #= N*(N+1).

43.swi

:- use_module(library(chr)).
:- chr_option(optimize, full).
:- chr_type list(T) ---> []; [T|list(T)].
:- chr_constraint
	list(+list(int)), cat(+list(int),+list(int)), sum(+int), problem43.

problem43 <=> list([]).

cat([H|T],L) <=> append(L,[H],L1), list(L1), cat(T,L).
cat([],_)    <=> true.

list([_,_,A,B,C|_])         <=> (A+B+C)        rem  3 =\= 0 | true.
list([_,_,_,_,A,B,C|_])     <=> (100*A+10*B+C) rem  7 =\= 0 | true.
list([_,_,_,_,_,A,B,C|_])   <=> (100*A+10*B+C) rem 11 =\= 0 | true.
list([_,_,_,_,_,_,A,B,C|_]) <=> (100*A+10*B+C) rem 13 =\= 0 | true.
list([_,_,_,_,_,_,_,A,B,C]) <=> (100*A+10*B+C) rem 17 =\= 0 | true.

list(L) <=> length(L,N), member(N,[0,1,2,4,6,7,8,9])
		  | numlist(0,9,L1), subtract(L1,L,L2), cat(L2,L).
list(L) <=> length(L,3) | subtract([0,2,4,6,8],L,L1), cat(L1,L).
list(L) <=> length(L,5) | subtract([0,5],L,L1), cat(L1,L).
list(L) <=> d2i(L,N), sum(N).

sum(M), sum(N) <=> X is M+N, sum(X).

d2i(L,X)       :- d2i(L,0,X).
d2i([],X,X)    :- !.
d2i([H|T],N,X) :- N1 is N*10+H, d2i(T,N1,X).

44.swi

:- use_module(library(chr)).
:- chr_option(optimize, full).
:- chr_constraint is_pent(+int), pent(+int,+int), answer(+int), problem44.

problem44 <=> pent(1,1).

answer(_) \ pent(_,_) <=> true.

pent(_,D) # passive, pent(_,K)
<=> J is K-D, is_pent(J), A is K+K-D, is_pent(A) | answer(D).
pent(N,_) ==> N1 is N+1, X is N1*(3*N1-1)//2, pent(N1,X).

is_pent(N) <=> X is 1+24*N, floor(sqrt(X),Y), X =:= Y*Y, (Y+1) rem 6 =:= 0.

45.swi

:- use_module(library(chr)).
:- chr_option(optimize, full).
:- chr_constraint
	pent(+int), pent(+int,+int), hex(+int), hex(+int,+int),
	answer(+int), problem45.

problem45 <=> pent(166), hex(143).

pent(N) <=> X is N*(3*N-1)//2, pent(N,X).
hex(N)  <=> X is N*(2*N-1), hex(N,X).

pent(_,X) \ hex(N,Y) <=> X > Y | N1 is N+1, hex(N1).
hex(_,X) \ pent(N,Y) <=> X > Y | N1 is N+1, pent(N1).
pent(_,X), hex(_,X)  <=> answer(X).

46.swi

:- use_module(library(chr)).
:- chr_option(optimize, full).
:- chr_constraint num(+int), problem46.

problem46 <=> num(3).

num(N) <=> \+ (\+ is_prime(N), check(N,1)) | N1 is N+2, num(N1).

check(N,R) :- 2*R*R >= N.
check(N,R) :- X is N-2*R*R, \+ is_prime(X), R1 is R+1, check(N,R1).

is_prime(2) :- !.
is_prime(N) :- N > 2, N rem 2 =\= 0, is_prime(3,N).
is_prime(P,N) :- P*P > N.
is_prime(P,N) :- N rem P =\= 0, P1 is P+2, is_prime(P1,N).

47.swi

:- use_module(library(prime_factors),[prime_factors/2]).
:- use_module(library(chr)).
:- chr_option(optimize, full).
:- chr_type list(T) ---> []; [T|list(T)].
:- chr_constraint
	set(+list(int)),
	set(+list(int),+list(int),+list(int),+list(int)),
	answer(+int),
	problem47.

problem47 <=> count_primes(647,N), set([647,N]).

answer(_) \ set(_) <=> true.

set([N,4],[_,4],[_,4],[_,4]) <=> answer(N).
set(_,_,_,_)                 <=> true.

set([N,4])
==> A is N-3, count_primes(A,A1),
    B is N-2, count_primes(B,B1),
    C is N-1, count_primes(C,C1),
    D is N+1, count_primes(D,D1),
    E is N+2, count_primes(E,E1),
    F is N+3, count_primes(F,F1),
    set([A,A1],[B,B1],[C,C1],[N,4]),
    set([B,B1],[C,C1],[N,4],[D,D1]),
    set([C,C1],[N,4],[D,D1],[E,E1]),
    set([N,4],[D,D1],[E,E1],[F,F1]).

set([M,_]) <=> M1 is M+4, count_primes(M1,N1), set([M1,N1]).

count_primes(N,X) :- prime_factors(N,L), sort(L,L1), length(L1,X).

48.swi

:- use_module(library(chr)).
:- chr_option(optimize, full).
:- chr_constraint num(+int), sum(+int), problem48.

problem48 <=> num(1000).

num(N) ==> N > 1 | N1 is N-1, num(N1).
num(N) <=> X is N**N, sum(X).

sum(M), sum(N) <=> X is (M+N) rem (10**10), sum(X).

49.swi

:- use_module(library(chr)).
:- chr_option(optimize, full).
:- chr_type list(T) ---> []; [T|list(T)].
:- chr_constraint
	prime(+int), prime(+int,+list(int)), answer(+int), problem49.

problem49 <=> prime(9999).

prime(N) ==> N > 2 | N1 is N-1, prime(N1).
prime(M) \ prime(N) <=> N rem M =:= 0 | true.

prime(N) <=> N < 1000 | true.
prime(N) <=> i2d(N,L), msort(L,L1), prime(N,L1).

prime(A,L), prime(B,L), prime(C,L)
<=> A \= 1487, A < B, B < C, 2*B-A =:= C
  | X is A*(10**8)+B*(10**4)+C, answer(X).

answer(_) \ prime(_,_) <=> true.

i2d(N,X)   :- i2d(N,[],X).
i2d(0,X,X) :- !.
i2d(N,L,X) :- N1 is N//10, N2 is N rem 2, i2d(N1,[N2|L],X).

Can you rewrite it without CHR? I am curios about the 44th problem