CHR : Project Euler 50-59

50.swi

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

problem50 <=> max_primes(3,[2]).

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

primes([])    <=> true.
primes(L)     <=> sumlist(L,N), is_prime(N) | length(L,X), answer(N,X).
primes([_|T]) <=> primes(T).

rev_primes([])    <=> true.
rev_primes([H|T]) <=> reverse([H|T],L), primes(L), rev_primes(T).

max_primes(_,[H|T]) <=> sumlist([H|T],N), N >= 1000000 | rev_primes(T).
max_primes(N,L) <=> \+ is_prime(N) | N1 is N+2, max_primes(N1,L).
max_primes(N,L) <=> N1 is N+2, max_primes(N1,[N|L]).

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+2, is_prime(N,P1).

51.swi

:- use_module(library(chr)).
:- chr_option(optimize, full).
:- chr_type list(T) ---> []; [T|list(T)].
:- chr_type digit   ---> 0; 1; 2; 3; 4; 5; 6; 7; 8; 9; x.
:- chr_constraint
	digits(+list(digit)), digits(+int,+list(digit)),
	prime, count_prime(+int), is_answer, answer(+int).

problem51 :-
	prime(56003,P), i2d(P,L),
	between(0,9,N), selectchk(N,L,x,L1),
	select(x,L1,N,L2), digits(L2), answer(P), !.

prime(N,N) :- is_prime(N).
prime(N,X) :- N1 is N+2, prime(N1,X).

count_mask([],0).
count_mask([x|T],X) :- !, count_mask(T,X1), X is X1+1.
count_mask([_|T],X) :- count_mask(T,X).

digits(L) <=> \+ count_mask(L,3) | false.
digits(L) <=> count_prime(0), digits(0,L), is_answer.

digits(N,_)     <=> N > 9 | true.
digits(0,[x|T]) <=> digits(1,[x|T]).
digits(N,L)     ==> N1 is N+1, digits(N1,L).
digits(N,L)     <=> selectchk(x,L,N,L1), d2i(L1,X), is_prime(X) | prime.
digits(_,_)     <=> true.

count_prime(N), prime <=> N1 is N+1, count_prime(N1).

count_prime(N), is_answer <=> N < 8 | false.
count_prime(_), is_answer <=> true.

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).

d2i(L,X)       :- d2i(L,0,X).
d2i([],X,X)    :- !.
d2i([H|T],N,X) :- N1 is 10*N+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+2, is_prime(N,P1).

52.swi

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

problem52 <=> num(100002).

num(N) <=> is_answer(N) | answer(N).
num(N) <=> N1 is N+3, num(N1).

is_answer(N) :- i2d(N,L1), msort(L1,X),
	        N2 is N*2, i2d(N2,L2), msort(L2,X),
	        N3 is N*3, i2d(N3,L3), msort(L3,X),
	        N4 is N*4, i2d(N4,L4), msort(L4,X),
	        N5 is N*5, i2d(N5,L5), msort(L5,X),
	        N6 is N*6, i2d(N6,L6), msort(L6,X).

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).

53.swi

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

problem53 <=> triangle([1,1]).

triangle([_,N|_]) <=> N > 100 | true.
triangle(L)       <=> list(L), join(L,[0|L],L1), triangle(L1).

join([],L,X)          <=> L = X.
join([A|As],[B|Bs],X) <=> N is A+B, join(As,Bs,X1), X = [N|X1].

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

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

54.swi

:- use_module(library(chr)).
:- chr_option(optimize, full).
:- chr_constraint
	readline/1, line/1, to_num/2, card/2, hand/2, play/2,
	value_rank/2, straight/1, rank/3, win/1, same/2, problem54.

problem54 <=> see('poker.txt'), seeing(S), readline(S).

readline(S) <=> read_line_to_codes(S,Cs), Cs \= end_of_file |
		line(Cs), hand(player1,[]), hand(player2,[]), readline(S).
readline(_) <=> seen.

to_num(84,X) <=> X = 10. % T
to_num(74,X) <=> X = 11. % J
to_num(81,X) <=> X = 12. % Q
to_num(75,X) <=> X = 13. % K
to_num(65,X) <=> X = 14. % A
to_num(N,X)  <=> number_chars(X,[N]).

line([N,S])     <=> to_num(N,X), card(player2,X-S).
line([N,S,_|T]) <=> length(T,Len), Len < 14 |
		    to_num(N,X), card(player2,X-S), line(T).
line([N,S,_|T]) <=> to_num(N,X), card(player1,X-S), line(T).

hand(Player,L), card(Player,Card) <=> hand(Player,[Card|L]).

hand(player1,A), hand(player2,B)
<=> keysort(A,A1), rank(A1,Ar,Ax), value_rank(A1,Av),
    keysort(B,B1), rank(B1,Br,Bx), value_rank(B1,Bv),
    play(Ar-Ax-Av,Br-Bx-Bv).

value_rank(L,X) <=> pairs_keys(L,L1), sort(L1,L2), reverse(L2,X).

straight([_])     <=> true.
straight([M,N|T]) <=> succ(M,N), straight([N|T]).

% Royal Flush
rank([10-S,11-S,12-S,13-S,14-S],R,X) <=> R = 10, X = 14.

% Straight Flush
rank([N1-S,N2-S,N3-S,N4-S,N5-S],R,X)
<=> straight([N1,N2,N3,N4,N5]) | R = 9, X = N5.

% Four of a Kind
rank([N-_,N-_,N-_,N-_,_],R,X) <=> R = 8, X = N.
rank([_,N-_,N-_,N-_,N-_],R,X) <=> R = 8, X = N.

% Full House
rank([N-_,N-_,N-_,N1-_,N1-_],R,X)  <=> R = 7, max_list([N,N1],X).
rank([N-_,N-_,N1-_,N1-_,N1-_],R,X) <=> R = 7, max_list([N,N1],X).

% Flush
rank([_-S,_-S,_-S,_-S,N-S],R,X) <=> R = 6, X = N.

% Straight
rank([N1-_,N2-_,N3-_,N4-_,N5-_],R,X)
<=> straight([N1,N2,N3,N4,N5]) | R = 5, X = N5.

% Three of a Kind
rank([N-_,N-_,N-_,_,_],R,X) <=> R = 4, X = N.
rank([_,N-_,N-_,N-_,_],R,X) <=> R = 4, X = N.
rank([_,_,N-_,N-_,N-_],R,X) <=> R = 4, X = N.

% Two Pairs
rank([N-_,N-_,N1-_,N1-_,_],R,X) <=> R = 3, max_list([N,N1],X).
rank([N-_,N-_,_,N1-_,N1-_],R,X) <=> R = 3, max_list([N,N1],X).
rank([_,N-_,N-_,N1-_,N1-_],R,X) <=> R = 3, max_list([N,N1],X).

% One Pair
rank([N-_,N-_,_,_,_],R,X) <=> R = 2, X = N.
rank([_,N-_,N-_,_,_],R,X) <=> R = 2, X = N.
rank([_,_,N-_,N-_,_],R,X) <=> R = 2, X = N.
rank([_,_,_,N-_,N-_],R,X) <=> R = 2, X = N.

% High Card
rank([_,_,_,_,N-_],R,X) <=> R = 1, X = N.

play(M-_-_,N-_-_) <=> M > N | win(1).
play(X-M-_,X-N-_) <=> M > N | win(1).
play(X-Y-M,X-Y-N) <=> same(M,N).
play(_,_)         <=> true.

same([],[])         <=> false.
same([X|_],[Y|_])   <=> X > Y | win(1).
same([X|_],[Y|_])   <=> X < Y | true.
same([_|Xs],[_|Ys]) <=> same(Xs,Ys).

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

55.swi

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

problem55 <=> num(9999), count(0).

num(N) ==> N > 1 | N1 is N-1, num(N1).
num(N) <=> rev(N,N1), X is N+N1, list([X]).

list([H|_]) <=> rev(H,H) | true.
list(L)     <=> length(L,N), N >= 50 | lychrel.
list([H|T]) <=> rev(H,H1), N is H+H1, list([N,H|T]).

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

rev(N,X)   <=> rev(N,0,X).
rev(0,R,X) <=> X = R.
rev(N,R,X) <=> R1 is R*10+(N rem 10), N1 is N//10, rev(N1,R1,X).

56.swi

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

problem56 <=> answer(0), num(99,99).

num(1,_)             <=> true.
answer(N) \ num(A,B) <=> log10(A**B) < N//9 | A1 is A-1, num(A1,99).
answer(N), num(A,B)  <=> sum_digits(A**B,X), X > N
                       | answer(X), B1 is B-1, num(A,B1).
num(A,B)             <=> B1 is B-1, num(A,B1).

sum_digits(N,X)   :- sum_digits(N,0,X).
sum_digits(0,X,X) :- !.
sum_digits(M,N,X) :- M1 is M//10, N1 is N + M rem 10, sum_digits(M1,N1,X).

57.swi

:- use_module(library(chr)).
:- chr_option(optimize, full).
:- chr_type rational ---> int rdiv int.
:- chr_constraint
	fraction(+natural,+rational),
	answer(+rational),
	digits(+natural,-natural),
	check(+rational),
	count(+natural),
	problem57.

problem57 <=> count(0), R is 1 rdiv 2, fraction(1,R).

fraction(I,_) <=> I > 1000 | true.
fraction(I,R) <=> X is R+1, answer(X), I1 is I+1, R1 is 1 rdiv (R+2), fraction(I1,R1).

digits(N,X) <=> N < 10 | X = 1.
digits(N,X) <=> N1 is N//10, digits(N1,X1), X is X1+1.

check(R) <=> rational(R,N,D), digits(N,X), digits(D,Y), X > Y.

answer(R) <=> \+ check(R) | true.

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

58.swi

:- use_module(library(primality_test),[is_prime/1]).
:- use_module(library(chr)).
:- chr_option(optimize, full).
:- chr_constraint
	primes(+int), total(+int), side_length(+int),
	next, num(+int), prime,
	problem58.

problem58 <=> next, side_length(5), primes(3), total(9).

side_length(N) ==> A is N*N, Diff is N-1,
	           B is A-Diff,   num(B),
		   C is A-2*Diff, num(C),
		   D is A-3*Diff, num(D).

num(N) <=> is_prime(N) | prime.
num(_) <=> true.

primes(N), prime <=> N1 is N+1, primes(N1).

primes(M), total(N) \ next <=> M/N < 0.1 | true.

next \ side_length(L), total(T) <=> L1 is L+2, side_length(L1),
	                            T1 is T+4, total(T1).

59.swi

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

problem59 <=> csv_read_file('cipher1.txt',[H|_]), H =.. [_|L],
	      encrypted(L), decrypt(L).

encrypted([])        <=> true.
encrypted([A,B,C|T]) <=> key(1,A,1), key(2,B,1), key(3,C,1), encrypted(T).
encrypted([A,B])     <=> key(1,A,1), key(2,B,1).
encrypted([A])       <=> key(1,A,1).

key(N,S,X), key(N,S,X) <=> X1 is X+X, key(N,S,X1).

decrypt(_), key(N,_,X) \ key(N,_,Y) <=> X >= Y | true.
decrypt(_) \ key(N,X,_) <=> X1 is X xor " ", key(N,X1).

key(1,X), key(2,Y), key(3,Z) \ decrypt([A,B,C|T])
<=> A1 is A xor X, sum(A1),
    B1 is B xor Y, sum(B1),
    C1 is C xor Z, sum(C1),
    decrypt(T).
key(1,X), key(2,Y) \ decrypt([A,B])
<=> A1 is A xor X, sum(A1),
    B1 is B xor Y, sum(B1),
    decrypt([]).
key(1,X) \ decrypt([A])
<=> A1 is A xor X, sum(A1), decrypt([]).

decrypt([]), key(1,_), key(2,_), key(3,_) <=> true.

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