5
\$\begingroup\$

I have some code which executes a simple task, counting the number of states reachable from a particular state, would just like some advice on how to improve it.

So far it stores all the states it has seen in seen_states. It's just counting them seems so clunky.

move([Head, Head1|Tail], [N|Tail]):-
    N is Head1 - Head,
    N >= 0.
move([Head|Tail], [Head|Tail1]):-
    move(Tail, Tail1).


:- dynamic counted_states/1.





count_state(S, V):-
    count_state(S,V, V).

count_state([], N,N).
count_state(S, Acc, Acc):-
    findall(X, move(S,X), Succ),
    count_sub_states(Succ, Acc, 0).

count_sub_states([],L,L).
count_sub_states([HeadList|List], Count, Acc):-
    count_node(HeadList,N),
    Acc1 is Acc+N,
    count_sub_states(List, Count, Acc1).

count_node(State, 0):-
    counted_states(State),!.

count_node(State, V):-
    not(counted_states(State)), 
    assert(counted_states(State)),
    count_state(State, V1, V1),
    V is V1 +1.
\$\endgroup\$
3
\$\begingroup\$

As a general rule of thumb, you should avoid using the global database for such purposes.

For example, in your case, after the predicate completes, counted_states/1 is still asserted, and will influence later invocations of the predicate.

This certainly is not intended, no?

There is a straight-forward solution for this:

  1. First, describe what it means that that a state is reachable from a particular state.
  2. Then, use findall/3 to collect all such reachable states into a list of results.
  3. On that list, simply use length/2 to obtain the number of reachable states.

This works without modifying the global database in any way.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.