W poprzednim wpisie pisałem o Google Treasure Hunt, a w szczególności o zadaniu czwartym. Teraz, w ramach przygotowań do kolokwióm z języka Prolog postanowiłem napisać w nim rozwiązanie postawionego problemu:

% Google Treasure Hunt 4 Solver
% by Michal Nazarewicz (mina86/AT/mina86/DOT/com)
% Released as "Public Domain"

treasure4(Max, Counts, Result) :-
	doSieve(Max, Primes),
	sumMember(Primes, Counts, Result).


doSieve(Max, Primes) :-
	Max > 2,
	buildSieve(Max, Sieve),
	buildPrimes(Sieve, Primes).


buildSieve(Max, Sieve) :-
	Max2 is (Max // 2) - 1,
	initTab(Max2, Tab, []),
	buildSieve(3, Max, Sieve, Tab).

initTab(0, Result, Result) :- !.
initTab(Count, Result, Acc) :-
	C2 is Count - 1,
	initTab(C2, Result, [ 1 | Acc ]).

buildSieve(Now, Max, Sieve, Sieve) :-
	Now > Max, !.
buildSieve(Now, Max, Sieve, Tab) :-
	isOddPrime(Now, Tab), !,
	negTab(Now, Tab, Tab2),
	Now2 is Now + 2,
	buildSieve(Now2, Max, Sieve, Tab2).
buildSieve(Now, Max, Sieve, Tab) :-
	Now2 is Now + 2,
	buildSieve(Now2, Max, Sieve, Tab).

isOddPrime(Number, Sieve) :-
	N2 is Number // 2,
	nth(N2, Sieve, 1).

negTab(Number, Tab, Result) :-
	negTab(3, Number, Tab, Result).

negTab(_, _, [ ], [ ]) :- !.
negTab(Idx, Number, [ _ | Rest ], [ 0 | Result ]) :-
	0 is Idx mod Number,
	Number \= Idx,
	!,
	Idx2 is Idx + 2,
	negTab(Idx2, Number, Rest, Result).
negTab(Idx, Number, [ X | Rest ], [ X | Result ]) :-
	Idx2 is Idx + 2,
	negTab(Idx2, Number, Rest, Result).


buildPrimes(Sieve, [ 2 | Primes ]) :-
	buildPrimes(3, Sieve, Primes).
buildPrimes(_, [ ], [ ]).
buildPrimes(Idx, [ 0 | Rest ], Primes) :-
	Idx2 is Idx + 2,
	buildPrimes(Idx2, Rest, Primes).
buildPrimes(Idx, [ 1 | Rest ], [ Idx | Primes]) :-
	Idx2 is Idx + 2,
	buildPrimes(Idx2, Rest, Primes).


sumMember(List, Counts, Result) :-
	sums(List, Counts, Result),
	member(Result, List).

sums(_, [ ], _).
sums(List, [ X | Counts ], Result) :-
	sum(List, X, Result),
	sums(List, Counts, Result).

sum(List, Count, Result) :-
	sum__do(List, Count, Result, 0).
sum([ _ | Rest ], Count, Result) :-
	sum(Rest, Count, Result).

sum__do(_, 0, Result, Result) :- !.
sum__do([ X | Rest ], Count, Result, Acc) :-
	var(Result), !,
	Acc2 is Acc + X,
	Count2 is Count - 1,
	sum__do(Rest, Count2, Result, Acc2).
sum__do([ X | Rest ], Count, Result, Acc) :-
	Acc2 is Acc + X,
	Count2 is Count - 1,
	Result >= Acc2,
	sum__do(Rest, Count2, Result, Acc2).

Niestety, z powodu głębokiej rekurencji (mój interpreter nie potrafi chyba zamieniać rekurencji w ogonie na pętle lub napisałem swój kod błędnie) kod nie jest w stanie rozwiązywać problemów takich jak podane w Treasure Hunt, ale dla mniejszych liczb daje wyniki, przykładowo:

| ?- treasure4(1000, [ 1, 5, 7 ], X).

X = 311 ? ;

X = 863 ? ;

X = 991 ? ;

(320 ms) no