% file: m3alt.pro
% author: Robert Keller
% purpose: Predicate m3 succeeds exactly for lists of 1's and 0's
%          that represent multiples of 3 in binary, most-significant bit first.
%          By convention, the empty list is considered a multiple of 3.
%
% This version uses a universal finite-state-machine simulator to determine
% the sequence of states. The simulator has 4 arguments:
%   The input sequence
%   The starting state
%   The final state
%   The list of transitions for the machine, in the form
%       (CurrentState, InputSymbol, NextState)

m3(X) :- fsmSim(X, m3, Final, [(m3, 0, m3),
                               (m3, 1, m1),
                               (m1, 0, m2), 
                               (m1, 1, m3), 
                               (m2, 0, m1),
                               (m2, 1, m2)]),
         member(Final, [m3]).

fsmSim([], Start, Start, _Transitions).

fsmSim([A | X], Start, Final, Transitions) :- 
        member((Start, A, Next), Transitions),
        fsmSim(X, Next, Final, Transitions).

% Tests for numbers divisible by 3.

test(0) :- m3([0]).
test(3) :- m3([1, 1]).
test(6) :- m3([1, 1, 0]).
test(9) :- m3([1, 0, 0, 1]).
test(12) :- m3([1, 1, 0, 0]).

% Tests for numbers not divisible by 3.

test(1) :- \+ m3([1]).
test(2) :- \+ m3([1, 0]).
test(4) :- \+ m3([1, 0, 0]).
test(5) :- \+ m3([1, 0, 1]).
test(7) :- \+ m3([1, 1, 1]).
test(8) :- \+ m3([1, 0, 0, 0]).
test(10) :- \+ m3([1, 0, 1, 0]).
test(11) :- \+ m3([1, 0, 1, 1]).


% testDriver(N) runs test(N) and reports the results.

testDriver(N) :- test(N) -> (write('Test '), write(N), write(' succeeded'), nl) ; 
                            (write('Test '), write(N), write(' failed'), nl).


% enum(M, N, K) binds K to numbers from M through N, one at a time.

enum(M, N, M) :- M =< N.
enum(M, N, K) :- M < N, M1 is M+1, enum(M1, N, K).


% testall runs the available tests.

testall :- enum(1, 12, K), testDriver(K), fail.
testall.