Treasure Hunt w Prologu
Posted by Michał ‘mina86’ Nazarewicz on 17th of January 2009 | (cite)
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