Skip to content

Instantly share code, notes, and snippets.

@Koitaro

Koitaro/80.swi

Created June 29, 2011 12:47
Show Gist options

  • Select an option

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

Select an option

Learn more about clone URLs
Save Koitaro/1053754 to your computer and use it in GitHub Desktop.
Download ZIP
CHR : Project Euler 80-89
Raw
80.swi
:- use_module(library(chr)).
:- chr_option(optimize, full).
:- chr_constraint
bin(+int), bin(+int,+int,+int,+int),
num(+int), sqrt(+int), sum(+int), problem80.
problem80 <=> num(100).
num(N) ==> N > 1 | N1 is N-1, num(N1).
num(N) <=> sqrt(N,R), floor(R,X), X*X =:= N | true.
num(N) <=> N1 is N*100**100, bin(N1).
bin(X) <=> Half is X//2, bin(0,Half,Half,X).
bin(N,N,_,_) <=> N1 is N//10, sqrt(N1).
bin(_,Half,Max,X) <=> Half**2 < X | N is (Half+Max)//2, bin(Half,N,Max,X).
bin(Min,Half,_,X) <=> N is (Min+Half)//2, bin(Min,N,Half,X).
sqrt(N) <=> N < 10 | sum(N).
sqrt(N) <=> D is N rem 10, sum(D), N1 is N//10, sqrt(N1).
sum(M), sum(N) <=> X is M+N, sum(X).
Raw
81.swi
:- use_module(library(chr)).
:- chr_option(optimize, full).
:- chr_type list(T) ---> []; [T|list(T)].
:- chr_constraint
conv(+int,+list(list(int))), conv(+int,+int,+list(int)),
node(+int,+int,+int), path(+int,+int,+int),
answer, min(+int), problem81.
problem81 <=> data(L), conv(1,L), answer.
node(1,1,X) ==> path(1,1,X).
path(M,N,X) \ path(M,N,Y) <=> X =< Y | true.
path(M,N,X) # passive, node(M,N1,Y) ==> N+1 =:= N1 | X1 is X+Y, path(M,N1,X1).
path(M,N,X) # passive, node(M1,N,Y) ==> M+1 =:= M1 | X1 is X+Y, path(M1,N,X1).
answer \ path(80,80,X) <=> min(X).
answer \ path(_,_,_) <=> true.
answer \ node(_,_,_) <=> true.
answer <=> true.
conv(M,[H|T]) <=> conv(M,1,H), M1 is M+1, conv(M1,T).
conv(_,[]) <=> true.
conv(M,N,[H|T]) <=> node(M,N,H), N1 is N+1, conv(M,N1,T).
conv(_,_,[]) <=> true.
data(X) :- csv_read_file('matrix.txt',L), maplist(term_list,L,X).
term_list(T,X) :- T =.. [_|X].
/* With priority queue */
:- 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 node ---> node(int,int).
:- chr_constraint
heap(+heap(node)), pop, top(+node),
list(+int,+list(int)), edge(+int,+int,+int),
answer(+int), problem81.
problem81 <=> data, pop.
heap(A), heap(B) <=> pair(A,B).
heap(H-T), pop <=> merge(T), top(H).
comp(node(_,M),node(_,N)) :- M =< N.
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([]).
answer(_) \ heap(_) <=> true.
answer(_) \ edge(_,_,_) <=> true.
top(node(6400,X)) <=> answer(X).
top(node(N,X)) \ edge(N,M,Y) <=> Z is X+Y, heap(node(M,Z)-[]).
top(_) <=> pop.
edge(0,1,N) <=> heap(node(1,N)-[]).
edge(N,_,_) <=> N =< 0 | true.
edge(M,N,_) <=> M+1 =:= N, N rem 80 =:= 1 | true.
list(N,[H|T]) <=> A is N-1, edge(A,N,H),
B is N-80, edge(B,N,H),
N1 is N+1, list(N1,T).
list(_,[]) <=> true.
data :- csv_read_file('matrix.txt', CSV),
maplist(tr,CSV,L), flatten(L,L1), list(1,L1).
tr(Term,T) :- Term =.. [_|T].
top(_) <=> pop.
edge(0,1,N) <=> heap(node(1,N)-[]).
edge(N,_,_) <=> N =< 0 | true.
edge(M,N,_) <=> M+1 =:= N, N rem 80 =:= 1 | true.
list(N,[H|T]) <=> A is N-1, edge(A,N,H),
B is N-80, edge(B,N,H),
N1 is N+1, list(N1,T).
list(_,[]) <=> true.
data :- csv_read_file('matrix.txt', CSV),
maplist(tr,CSV,L), flatten(L,L1), list(1,L1).
tr(Term,T) :- Term =.. [_|T].
Raw
82.swi
:- 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 node ---> node(int,int).
:- chr_constraint
heap(+heap(node)), pop, top(+node),
list(+int,+list(int)), edge(+int,+int,+int),
answer(+int), problem82.
problem82 <=> data, pop.
heap(A), heap(B) <=> pair(A,B).
heap(H-T), pop <=> merge(T), top(H).
comp(node(_,M),node(_,N)) :- M =< N.
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([]).
answer(_) \ heap(_) <=> true.
answer(_) \ edge(_,_,_) <=> true.
top(node(N,X)) <=> N rem 80 =:= 0 | answer(X).
top(node(N,X)) \ edge(N,M,Y) <=> Z is X+Y, heap(node(M,Z)-[]).
top(_) <=> pop.
edge(_,N,X) <=> N rem 80 =:= 1 | heap(node(N,X)-[]).
edge(M,_,_) <=> M < 1 | true.
edge(M,_,_) <=> M > 6400 | true.
list(N,[H|T]) <=> A is N-1, edge(A,N,H),
B is N-80, edge(B,N,H),
C is N+80, edge(C,N,H),
N1 is N+1, list(N1,T).
list(_,[]) <=> true.
data :- csv_read_file('matrix.txt', CSV),
maplist(tr,CSV,L), flatten(L,L1), list(1,L1).
tr(Term,T) :- Term =.. [_|T].
Raw
83.swi
:- 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 node ---> node(int,int).
:- chr_constraint
heap(+heap(node)), pop, top(+node),
list(+int,+list(int)), edge(+int,+int,+int),
answer(+int), problem83.
problem83 <=> data, pop.
heap(A), heap(B) <=> pair(A,B).
heap(H-T), pop <=> merge(T), top(H).
comp(node(_,M),node(_,N)) :- M =< N.
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([]).
answer(_) \ heap(_) <=> true.
answer(_) \ edge(_,_,_) <=> true.
top(node(6400,X)) <=> answer(X).
top(node(N,X)) \ edge(N,M,Y) <=> Z is X+Y, heap(node(M,Z)-[]).
top(_) <=> pop.
edge(0,1,X) <=> heap(node(1,X)-[]).
edge(M,_,_) <=> M < 1 | true.
edge(M,_,_) <=> M > 6400 | true.
edge(M,N,_) <=> M+1 =:= N, N rem 80 =:= 1 | true.
edge(M,N,_) <=> N+1 =:= M, M rem 80 =:= 1 | true.
list(N,[H|T]) <=> A is N-1, edge(A,N,H),
B is N-80, edge(B,N,H),
C is N+80, edge(C,N,H),
D is N+1, edge(D,N,H),
N1 is N+1, list(N1,T).
list(_,[]) <=> true.
data :- csv_read_file('matrix.txt', CSV),
maplist(tr,CSV,L), flatten(L,L1), list(1,L1).
tr(Term,T) :- Term =.. [_|T].
Raw
87.swi
:- use_module(library(chr)).
:- chr_option(optimize, full).
:- chr_type list(T) ---> []; [T|list(T)].
:- chr_constraint
prime(+int), prime_list(+int), list(+list(int)), list,
answer(+int), answer, problem87.
problem87 <=> prime_list(4), prime_list(3), prime_list(2), answer.
prime(N) ==> N > 2 | N1 is N-1, prime(N1).
prime(M) \ prime(N) <=> N rem M =:= 0 | true.
prime_list(N) <=> floor(50000000**(1/N),X), prime(X), list([]), list.
list \ prime(N), list(L) <=> list([N|L]).
list <=> true.
list(A), list(B), list(C), answer
<=> aggregate_all(count,sort(X),add(A,B,C,X),N), answer(N).
add(L,L1,L2,X) :-
member(A,L),
member(B,L1), A+B < 50000000,
member(C,L2), X is A+B+C, X < 50000000.
Raw
89.swi
:- use_module(library(chr)).
:- chr_option(optimize, full).
:- chr_type list(T) ---> []; [T|list(T)].
:- chr_constraint
i, iv, v, ix, x, xl, l, xc, c, cd, d, cm, m,
valid(+list(int)),
read_line(+any),
best(+list(int)),
count(+int), count,
problem89.
problem89 <=> see('roman.txt'), seeing(S), read_line(S), count.
read_line(S) <=> read_line_to_codes(S,L), L \= end_of_file |
length(L,N), count(N), best(L), read_line(S).
read_line(_) <=> seen.
count(M), count(N) <=> X is M+N, count(X).
best(L) <=> valid(L), count.
count \ i <=> count(-1).
count \ iv <=> count(-2).
count \ v <=> count(-1).
count \ ix <=> count(-2).
count \ x <=> count(-1).
count \ xl <=> count(-2).
count \ l <=> count(-1).
count \ xc <=> count(-2).
count \ c <=> count(-1).
count \ cd <=> count(-2).
count \ d <=> count(-1).
count \ cm <=> count(-2).
count \ m <=> count(-1).
count <=> true.
valid([73,86|T]) <=> iv, valid(T).
valid([73,88|T]) <=> ix, valid(T).
valid([88,76|T]) <=> xl, valid(T).
valid([88,67|T]) <=> xc, valid(T).
valid([67,68|T]) <=> cd, valid(T).
valid([67,77|T]) <=> cm, valid(T).
valid([73|T]) <=> i, valid(T).
valid([86|T]) <=> v, valid(T).
valid([88|T]) <=> x, valid(T).
valid([76|T]) <=> l, valid(T).
valid([67|T]) <=> c, valid(T).
valid([68|T]) <=> d, valid(T).
valid([77|T]) <=> m, valid(T).
valid([]) <=> true.
cm, cm <=> m, d, c, c, c.
cm, d <=> m, cd.
cm, cd <=> m, c, c, c.
cm, c <=> m.
d, d <=> m.
d, cd <=> cm.
cd, cd <=> d, c, c, c.
cd, c <=> d.
c, c, c, c <=> cd.
xc, xc <=> c, l, x, x, x.
xc, l <=> c, xl.
xc, xl <=> c, x, x, x.
xc, x <=> c.
l, l <=> c.
l, xl <=> xc.
xl, xl <=> l, x, x, x.
xl, x <=> l.
x, x, x, x <=> xl.
ix, ix <=> x, v, i, i, i.
ix, v <=> x, iv.
ix, iv <=> x, i, i, i.
ix, i <=> x.
v, v <=> x.
v, iv <=> ix.
iv, iv <=> v, i, i, i.
iv, i <=> v.
i, i, i, i <=> iv.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment