Skip to content

Instantly share code, notes, and snippets.

@Koitaro

Koitaro/40.swi

Created June 4, 2011 21:09
Show Gist options

  • Select an option

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

Select an option

Learn more about clone URLs
Save Koitaro/1008366 to your computer and use it in GitHub Desktop.
Download ZIP
CHR : Project Euler 40-49
Raw
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).
Raw
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).
Raw
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).
Raw
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).
Raw
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.
Raw
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).
Raw
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).
Raw
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).
Raw
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).
Raw
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).
@md2perpe
Copy link
Copy Markdown

md2perpe commented Jun 4, 2011

What language is this? It looks somewhat similar to Prolog.

@Koitaro
Copy link
Copy Markdown
Author

Koitaro commented Jun 4, 2011 via email

@gordanielyan
Copy link
Copy Markdown

gordanielyan commented Sep 30, 2020 •
edited
Loading

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

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment