# Treasure Hunt w Prologu

Posted by Michał ‘mina86’ Nazarewicz on 17th of January 2009

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```