CODEWITHSUNDEEP
prolog
aidamo
aidamo

Reputation: 1

repeat of numbers in prolog and see how many

Is there anybody that can help me with this please? There is a list of numbers for which we know that there are exactly two occurrences of each number except one. Please write a Prolog code to find this irregular number in the list. Example: For the list ‘(2 3 2 4 1 6 1 3 6), the sought irregular number is 4.

Upvotes: 0

Views: 104

Answers (2)

David Tonhofer
David Tonhofer

Reputation: 15328

Let's choose a Prolog-y approach to this problem.

Using bagof/2. (These "collect all solutions" meta-calls are really the bread-and-butter of Prolog, and they aren't even First-Order. Who wants to slum in First-order Logic?)

Complete with test code:

% find_irreg(+List,?Number)

find_irreg(L,N) :- member(N,L),\+bagof(_,member(N,L),[_,_]).

% ===
% Test code
% ===

:- begin_tests(irreg).

test(1, fail)                  :- find_irreg([1,2,3,4,1,2,3,4],_).
test(2, [true(X == 1),nondet]) :- find_irreg([1,2,3,4,2,3,4],X).
test(3, fail)                  :- find_irreg([],_).
test(4, fail)                  :- find_irreg([1,2,3,4,2,3,4],10).

:- end_tests(irreg).

rt(irreg) :- run_tests(irreg).

And so:

?- rt(_).
% PL-Unit: irreg .... done
% All 4 tests passed
true.

Why does this work:

find_irreg(L,N) :-                % N is an irregular member of L if
   member(N,L),                   % N is a member of L AND
   \+bagof(_,member(N,L),[_,_]).  % Collecting all Ns from L does not 
                                  % give a list of two elements

Operationally, Prolog attempts to fulfill the \+bagof with each N picked from L. bagof/3 backtracks over its inner member(N,L) (with fixed N now) and whenever it finds an N its puts a don't care variable _ into a bag list. At the end, it checks whether its bag list unifies with [_,_], i.e. has exactly two elements. If this works, N is one of the elements we don't want, so we put a \+ in front of bagof.

Upvotes: 0

SierraV
SierraV

Reputation: 104

Try this code:

findIrregular(L,Z):-
    member(Z,L),
    count(L,Z,1).

count([], Z ,0).
count([H|T], X, Z):-
    count(T, X, Z1),
    (X == H -> Z is Z1 +1 ; Z is Z1).

So for the input:
?- findIrregular([2 ,3 ,2 ,4 ,1 ,6 ,1, 3, 6],Z).

The output is:
Z = 4

Upvotes: 1

Related Questions