CHR : Project Euler 70-79

70.swi

:- use_module(library(primality_test),[is_prime/1]).
:- use_module(library(chr)).
:- chr_option(optimize, full).
:- chr_type list(T) ---> []; [T|list(T)].
:- chr_type heap(T) ---> T-list(heap(T)).
:- chr_type ratio   ---> ratio(int,int,float).
:- chr_constraint
	heap(+heap(ratio)), pop, top(+ratio),
	prime(+int), solve(+int), gen(+int,+int), answer(+int,+float),
	problem70.

problem70 <=> floor(sqrt(10**7),N), prime(N).

heap(A), heap(B) <=> pair(A,B).
heap(H-T), pop <=> merge(T), top(H).

comp(ratio(_,_,A),ratio(_,_,B)) :- A =< B.

pair(A-X,B-Y) :- comp(A,B), !, heap(A-[B-Y|X]).
pair(A-X,B-Y) :- heap(B-[A-X|Y]).

merge([A,B|T]) :- !, pair(A,B), merge(T).
merge([A])     :- !, heap(A).
merge([]).

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

prime(N) <=> N >= (10**7)**(1/3) | solve(N).
prime(_) <=> true.

solve(N) <=> gen(N,N), pop.

answer(_,M) \ answer(_,N) <=> M < N | true.

top(ratio(A,B,R)), heap(_) <=> is_answer(A,B) | X is A*B, answer(X,R).
top(_)                     <=> pop.
pop                        <=> true.

gen(M,N) <=> M*N < 10**7 | ratio(M,N), next_prime(N,N1), gen(M,N1).
gen(_,_) <=> true.

ratio(A,B) :- X is A/(A-1)*B/(B-1), heap(ratio(A,B,X)-[]).

next_prime(N,X) :- N1 is N+2, is_prime(N1), !, X = N1.
next_prime(N,X) :- N1 is N+2, next_prime(N1,X).

is_answer(A,B) :- X is A*B,         i2d(X,X1), msort(X1,X2),
                  Y is (A-1)*(B-1), i2d(Y,Y1), msort(Y1,X2).

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

71.swi

:- use_module(library(chr)).
:- chr_option(optimize, full).
:- chr_type rational ---> int rdiv int.
:- chr_constraint num(+int,+int), max(+rational), problem71.

problem71 <=> Max is 1000000*3//7, num(1,Max).

num(M,N) <=> M > N | true.
num(M,N) <=> X is M rdiv (M*7//3+1), max(X), M1 is M+1, num(M1,N).

max(M) \ max(N) <=> M > N | true.

74.swi

:- use_module(library(digits),[i2d/2]).
:- use_module(library(chr)).
:- chr_option(optimize, full).
:- chr_type list(T) ---> []; [T|list(T)].
:- chr_constraint
	list(+list(int)), push(+list(int),+list(int)),
	seq(+list(list(int))), chain(+list(list(int))),
	perm(+list(list(int))), digits(+list(int)), factorial(+int,+int),
	next(+list(int),-list(int)), next(+list(int),+int,-list(int)),
	way(+list(int),?int), way(+list(int),+int,?int),
	sum, sum(+int), answer, problem74.

problem74 <=> factorial(0,1), numlist(1,9,L), push(L,[]), answer.

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

list(L)     <=> length(L,6) | seq([L]).
list([H|T]) <=> seq([[H|T]]), numlist(1,H,L), push(L,[H|T]).

seq([H|T]) <=> member(H,T) | chain(T).
seq([H|T]) <=> next(H,H1), seq([H1,H|T]).

chain(L) <=> \+ length(L,60) | true.
chain(L) <=> last(L,L1), findall(X,permutation(L1,X),Xs), perm(Xs), sum.

perm([])    <=> true.
perm([H|T]) <=> digits(H), perm(T).

digits(L) \ digits(L) <=> true.

sum \ digits(L) <=> way(L,X), sum(X).
sum             <=> true.

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

factorial(N,X) ==> N < 9 | N1 is N+1, X1 is X*N1, factorial(N1,X1).

next(L,X)                        <=> next(L,0,X).
next([],N,X)                     <=> i2d(N,X).
factorial(H,F) \ next([H|T],N,X) <=> N1 is N+F, next(T,N1,X).

way([_|T],X)   <=> way(T,0,N), X is 2**N.
way([],N,X)    <=> X = N.
way([1|T],N,X) <=> N1 is N+1, way(T,N1,X).
way([_|T],N,X) <=> way(T,N,X).

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

75.swi

:- use_module(library(chr)).
:- chr_option(optimize, full).
:- chr_type list(T) ---> []; [T|list(T)].
:- chr_constraint
	triangle(+list(int)), next_triangle(+list(int)),
	sum_sides(+int,+int,+int),
	set(+int,+int),
	count(+int), count,
	problem75.

problem75 <=> triangle([3,4,5]), count.

next_triangle([A,B,C]) <=> X is -A-2*B+2*C,
	                   Y is -2*A-B+2*C,
			   Z is -2*A-2*B+3*C,
			   triangle([X,Y,Z]).

triangle(L)       <=> sumlist(L,X), X > 1500000 | true.
triangle([A,B,C]) ==> A1 is -A, B1 is -B,
                      next_triangle([A1,B,C]),
		      next_triangle([A1,B1,C]),
		      next_triangle([A,B1,C]).

triangle(L) <=> sumlist(L,N), sum_sides(N,1,N).

sum_sides(N,P,_) ==> P1 is P+1, N1 is N*P1, N1 =< 1500000 | sum_sides(N,P1,N1).
sum_sides(_,_,N) <=> set(N,1).

set(N,A), set(N,B) <=> X is A+B, set(N,X).

count \ set(_,N) <=> N = 1 | count(1).
count \ set(_,_) <=> true.
count            <=> true.

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

76.swi

:- use_module(library(chr)).
:- chr_option(optimize, full).
:- chr_constraint
	num(+int), p(+int,+int), add(+int,+int,+int), return(+int,-int),
	answer(+int), problem76.

problem76 <=> partition(100,X), X1 is X-1, answer(X1).

partition(N,X) :- num(N), add(N,2,2), return(N,X).

num(N) ==> N > 0 | N1 is N-1, num(N1).
num(N) <=> p(N,1).

add(N,A,_) <=> N < A | true.
add(N,A,B) <=> N < B | A1 is A+1, add(N,A1,A1).

p(C,Y) # passive \ p(B,X) # passive, add(N,A,B)
<=> C =:= B-A | X1 is X+Y, p(B,X1), B1 is B+1, add(N,A,B1).

return(N,X) \ p(N,Y) <=> X = Y.
return(_,_) \ p(_,_) <=> true.
return(_,_) <=> true.

77.swi

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

problem77 <=> answer(10).

answer(N) <=> \+ (num(N), prime(N), count(0), answer) | N1 is N+1, answer(N1).

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

num(N) \ list(L)      <=> sumlist(L,Sum), Sum > N | true.
prime(N), list([H|T]) ==> N =< H | list([N,H|T]).
num(N) \ list(L)      <=> sumlist(L,Sum), Sum < N | true.

count(N), list(_) <=> N1 is N+1, count(N1).

answer \ prime(_) <=> true.
answer \ num(_)   <=> true.
answer, count(N)  <=> N >= 5000 | true.
answer, count(_)  <=> false.

79.swi

:- use_module(library(chr)).
:- chr_option(optimize, full).
:- chr_constraint read_line/1, vertex/2, answer/1, problem79.

problem79 <=> see('keylog.txt'), seeing(S), read_line(S), answer([]).

vertex(N,A), vertex(N,B) <=> union(A,B,X), vertex(N,X).
vertex(N,[]), answer(L)  <=> append(L,[N],X), answer(X).
answer(X) \ vertex(N,Y)  <=> intersection(X,Y,L), \+ length(L,0) |
                             subtract(Y,X,Z), vertex(N,Z).

read_line(S) <=> read_line_to_codes(S,L), L \= end_of_file |
		 maplist(to_num,L,[A,B,C]),
		 vertex(A,[]), vertex(B,[A]), vertex(C,[A,B]),
		 read_line(S).
read_line(_) <=> seen.

to_num(N,X) :- X is N-"0".