• mina86.com

  • Categories
  • Code
  • Contact
  • 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