Search code examples
prolog

Getting longest subsequence of even numbers in a list with Prolog


I want to implement a predicate longest_even_sequence(X,Y) where X is the given list, Y is a list that returns the longest subsequence of even number. For example for the given list 2,4,6,3,5,2,2 I want to return 2,4,6.

Here is the code that I tried and I don't know how to make it work (I am a total beginner in Prolog)

longest_even_sequence([],[]).
longest_even_sequence([H|T],[R]):-
    H mod 2 =:= 0,
    longest_even_sequence(T,R1)
    R is [H|R1]                .
longest_even_sequence([H|T],[]):-
    H mod 2 =\= 0,
    longest_even_sequence(T,R2),
    R2 is [].

Solution

  • To be honest this is a rather beginner-unfriendly task because it doesn't point directly to the beauty of prolog and has multiple issues for using the recursive approach.

    First try: adding an argument. Doing it in the basic recursive way requires you to add an argument to hold your current streak to compare it to your current best. This requires the introduction of a new predicate and seems to be the easiest beginner-friendly solution using recursion. For not stressing myself to hard I used the if-then-else ( ... -> ... ; ...) to handle the maximum-chosing. Basic idea is going through the list and collecting a streak in the second argument. Once I hit an uneven number, I get the maximum even subsequence for the rest of the list (longest_even_sequence(T,[],Rtmp)) and compare it with the current streak (LT > LR). The larger list will be copied to the output argument. Once I reach the end, I just copy my current streak (longest_even_sequence([],R,R).).

    Potential problem with this one is that the streak is in reverse order so you need to reverse it. Also using the if-then-else is not beginner-level. Staring with a streak and ending with a streak is no problem.

    longest_even_sequence(In,Out) :-
        longest_even_sequence(In,[],ROut),
        reverse(ROut,Out).
    
    longest_even_sequence([],R,R).
    longest_even_sequence([H|T],Tmp,R):-
        H mod 2 =:= 0,
        longest_even_sequence(T,[H|Tmp],R).
    longest_even_sequence([H|T],Tmp,R):-
        H mod 2 =\= 0,
        longest_even_sequence(T,[],Rtmp),
        length(Rtmp,LR),
        length(Tmp,LT),
        (
            LT > LR
        ->  R = Tmp
        ;   R = Rtmp
        ).
    

    Tested with SWISH:

    ?- longest_even_sequence([2,4,6,2,3,4,5,4,4,4,5,6],R).
    R = [2, 4, 6, 2]; 
    false.
     
    

    Just for fun (yeah, I mean it), let's do it another, more complex and computational intense way:

    range(High, _, High).
    range(Out,Low,High) :- 
        NewH is High-1, 
        NewH >= Low, 
        range(Out, Low, NewH).
    
    alleven([]).
    alleven([H|T]):-
        H mod 2 =:= 0,
        alleven(T).
    
    les(In,Out):-
        length(In,Lin),
        range(N,0,Lin),
        length(Out,N),
        append(_,InRest,In),
        append(Out,_,InRest),
        alleven(Out), 
        !.
    

    Test:

    ?- les([2,4,6,2,3,4,5,4,4,4,5,6],R).
    R = [2, 4, 6, 2].
    

    So what happens? At first a number between 0 and the length of the input list is generated (with range(N,0,Lin), modfied code from here) in descending order. Then a list with N (unknown) elements is created length(Out,N),. Then the Input list In is split into 3 parts, where the beginning and the end is not interesting but the middle has to have N elements, which is enforced by unifying it with Out, which is a list with N elements. This list has to have all even numbers. If it succeeds, skip all other answers (!, called a cut, more advanced prolog). If it doens't succeeds, the next fitting sublist is tested. If no list of length N fits, then the next lower N is tested until you eventually hit N=0.