Skip to content

Instantly share code, notes, and snippets.

@Koitaro

Koitaro/60.swi

Created June 22, 2011 22:45
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save Koitaro/1041455 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save Koitaro/1041455 to your computer and use it in GitHub Desktop.
Download ZIP
CHR : Project Euler 60-69
Raw
60.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_constraint
set(+int,+int), set(+int,+int,+int), set(+int,+int,+int,+int),
prime(+int), gen(+int), answer/1, problem60.
problem60 <=> gen(3).
answer(_) \ gen(_) <=> true.
answer(_) \ prime(_) <=> true.
answer(_) \ set(_,_) <=> true.
answer(_) \ set(_,_,_) <=> true.
answer(_) \ set(_,_,_,_) <=> true.
prime(A) # passive, prime(B) ==> join(A,B) | set(A,B).
set(A,B), set(A,C), set(B,C) ==> set(A,B,C).
set(A,B,C), set(A,B,D), set(C,D) ==> set(A,B,C,D).
set(A,B,C,D), set(A,B,C,E), set(D,E) ==> X is A+B+C+D+E, answer(X-[A,B,C,D,E]).
gen(N) ==> is_prime(N) | prime(N).
gen(N) <=> N1 is N+2, gen(N1).
join(A,B) :- floor(log10(B),M), A1 is A*10**(M+1)+B, is_prime(A1),
floor(log10(A),N), B1 is B*10**(N+1)+A, is_prime(B1).
/* Complete version */
:- use_module(library(primality_test),[is_prime/1]).
:- use_module(library(chr)).
:- chr_option(optimize, full).
:- chr_type list(T) ---> []; [T|list(T)].
:- chr_constraint
prime(+int), gen(+int),
set(+int,+int), set(+int,+int,+int),
set(+int,+int,+int,+int), set(+int,+int,+int,+int,+int),
answer, answer(+int), answer(+int,+int,+int,+int,+int),
candidate(+int,+list(int),+int),
problem60.
problem60 <=> gen(3), answer.
answer, answer(A,B,C,D,E) <=> X is A+B+C+D+E, answer(X).
answer(A,B,C,D,E) \ answer(F,G,H,I,J)
<=> X is A+B+C+D+E, Y is F+G+H+I+J, X =< Y | true.
answer(_,_,_,_,_) \ gen(_) <=> true.
answer(_,_,_,_,_) \ prime(_) <=> true.
answer(_,_,_,_,_) \ set(_,_) <=> true.
answer(_,_,_,_,_) \ set(_,_,_) <=> true.
answer(N1,N2,N3,N4,N5) \ set(A,B,C,D)
<=> X is N1+N2+N3+N4+N5+2, candidate(X,[A,B,C,D],N5).
candidate(X,[A,B,C,D],Y) <=> X < Y+A+B+C+D | true.
candidate(X,L,Y) <=> \+ is_prime(Y) | Y1 is Y+2, candidate(X,L,Y1).
candidate(_,[A,B,C,D],Y) <=> join(A,Y), join(B,Y), join(C,Y), join(D,Y) |
answer(A,B,C,D,Y).
candidate(X,L,Y) <=> Y1 is Y+2, candidate(X,L,Y1).
prime(A) # passive, prime(B) ==> join(A,B) | set(A,B).
set(A,B), set(A,C), set(B,C) ==> set(A,B,C).
set(A,B,C), set(A,B,D), set(C,D) ==> set(A,B,C,D).
set(A,B,C,D), set(A,B,C,E), set(D,E) ==> answer(A,B,C,D,E).
gen(N) ==> is_prime(N) | prime(N).
gen(N) <=> N1 is N+2, gen(N1).
join(A,B) :- floor(log10(B),M), A1 is A*10**(M+1)+B, is_prime(A1),
floor(log10(A),N), B1 is B*10**(N+1)+A, is_prime(B1).
Raw
61.swi
:- use_module(library(chr)).
:- chr_option(optimize, full).
:- chr_constraint
gen(+int,+int,+int), polygonal(+int,+int,+int),
answer(+int), problem61.
problem61 <=> gen(3,1,1), gen(4,1,1), gen(5,1,1),
gen(6,1,1), gen(7,1,1), gen(8,1,1).
p(P,N,X) :- X is N*(N*(P-2)-(P-4))//2.
gen(_,_,N) <=> N > 9999 | true.
gen(P,M,N) <=> N < 1000 | M1 is M+1, p(P,M1,N1), gen(P,M1,N1).
gen(P,M,N) <=> N1 is N//100, N2 is N rem 100, polygonal(P,N1,N2),
M1 is M+1, p(P,M1,X), gen(P,M1,X).
polygonal(P1,A,B), polygonal(P2,B,C), polygonal(P3,C,D),
polygonal(P4,D,E), polygonal(P5,E,F), polygonal(P6,F,A)
<=> msort([P1,P2,P3,P4,P5,P6],[3,4,5,6,7,8])
| X is (A+B+C+D+E+F)*101, answer(X).
answer(_) \ polygonal(_,_,_) <=> true.
Raw
62.swi
:- use_module(library(chr)).
:- chr_option(optimize, full).
:- chr_type list(T) ---> []; [T|list(T)].
:- chr_constraint
cube(+int), cube(+list(int),+list(int)), answer(+int), problem62.
problem62 <=> cube(1).
cube(Key,L), cube(Key,L1) <=> append(L,L1,L2), cube(Key,L2).
cube(_,L) <=> length(L,5) | min_list(L,X), answer(X).
answer(_) \ cube(_) <=> true.
answer(_) \ cube(_,_) <=> true.
cube(N) <=> Val is N**3, i2d(Val,L), msort(L,Key), cube(Key,[Val]),
N1 is N+1, cube(N1).
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).
Raw
63.swi
:- use_module(library(chr)).
:- chr_option(optimize, full).
:- chr_constraint num(+int,+int), count(+int), problem63.
problem63 <=> num(2,1), count(1). % log10(1,0)
num(N,1) ==> N < 9 | N1 is N+1, num(N1,1).
num(M,N) <=> N =\= ceiling(log10(M**N)) | true.
num(M,N) ==> N1 is N+1, num(M,N1).
count(N), num(_,_) <=> N1 is N+1, count(N1).
Raw
64.swi
:- use_module(library(chr)).
:- chr_option(optimize, full).
:- chr_type list(T) ---> []; [T|list(T)].
:- chr_constraint num(+int), list(+list(int)), count(+int), problem64.
problem64 <=> count(0), num(10000).
num(N) ==> N > 2 | N1 is N-1, num(N1).
num(N) <=> sqrt_cf(N,cf(_,L)), list(L).
list(L) <=> length(L,N), N rem 2 =:= 0 | true.
count(N), list(_) <=> N1 is N+1, count(N1).
sqrt_cf(R,cf(R,[])) :- floor(sqrt(R),N), N*N =:= R, !.
sqrt_cf(R,X) :- floor(sqrt(R),N),
sqrt_cf(init(1,N,1),expr((1*sqrt(R)-N)/1),cf(N,[]),X).
sqrt_cf(init(A,B,C),expr((A*sqrt(_)-B)/C),cf(N,L),X) :-
L \= [], !, X = cf(N,L).
sqrt_cf(init(S,T,U),expr((A*sqrt(R)-B)/C),cf(N,L),X) :-
M is floor(C/(A*sqrt(R)-B)),
C1 is A*A*R-B*B,
A1 is A*C,
B1 is M*C1-B*C,
G is gcd(gcd(A1,B1),C1),
A2 is A1//G, B2 is B1//G, C2 is C1//G,
append(L,[M],L1),
sqrt_cf(init(S,T,U),expr((A2*sqrt(R)-B2)/C2),cf(N,L1),X).
Raw
67.swi
:- use_module(library(chr)).
:- chr_option(optimize, full).
:- chr_type list(T) ---> []; [T|list(T)].
:- chr_constraint list(+list(list(int))), problem67.
problem67 <=> csv_read_file('triangle.txt',L,[separator(32),match_arity(false)]),
maplist(term_list,L,L1), reverse(L1,L2), list(L2).
term_list(L,X) :- L =.. [_|X].
join(_,[],[]) :- !.
join([A,B|T],[H|T1],[N1|X1]) :- max_list([A,B],N), N1 is N+H, join([B|T],T1,X1).
list([A,B|T]) <=> join(A,B,X), list([X|T]).
Raw
68.swi
:- use_module(library(chr)).
:- chr_option(optimize, full).
:- chr_type list(T) ---> []; [T|list(T)].
:- chr_constraint
num(+int),
line(+int, +int, +int, +int),
join(+int, +list(int)),
max(+int),
answer(-int),
problem68(?int).
problem68(X) <=> num(10), answer(X).
num(N) ==> N > 1 | N1 is N-1, num(N1).
num(A), num(B), num(C) ==> X is A+B+C, line(A,B,C,X).
line(A,B,C,S), line(D,C,E,S), line(F,E,G,S), line(H,G,I,S), line(J,I,B,S)
==> A < D, A < F, A < H, A < J,
member(10,[D,F,H,J]),
numlist(1,10,L), msort([A,B,C,D,E,F,G,H,I,J],L)
| join(0,[A,B,C,D,C,E,F,E,G,H,G,I,J,I,B]).
join(N,[]) <=> max(N).
join(N,[10|T]) <=> join(N,[1,0|T]).
join(N,[H|T]) <=> N1 is 10*N+H, join(N1,T).
max(M) \ max(N) <=> M >= N | true.
answer(_) \ num(_) <=> true.
answer(_) \ line(_,_,_,_) <=> true.
answer(X), max(Y) <=> X = Y.
Raw
69.swi
:- use_module(library(chr)).
:- chr_option(optimize, full).
:- chr_constraint prime(+int), num(+int), answer(+int), problem69.
problem69 <=> num(2), prime(3).
prime(P) <=> \+ is_prime(P) | P1 is P+2, prime(P1).
num(N), prime(P) <=> N*P > 1000000 | answer(N).
num(N), prime(P) <=> N1 is N*P, num(N1), P1 is P+2, prime(P1).
is_prime(2) :- !.
is_prime(N) :- N > 2, N rem 2 =:= 1, !, is_prime(N,3).
is_prime(M,N) :- M < N*N, !.
is_prime(M,N) :- M rem N =\= 0, !, N1 is N+2, is_prime(M,N1).
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment