Блог

Я пытаюсь объединить элементы в списке, правила следующие:

1. Объедините список таким образом, чтобы, если 2 последовательных числа в списке были одинаковыми, они должны были объединиться в одно путем их суммирования (т. е. [4,4,0,0] -> [8,0,0,0]).

2. Недавно объединенный тайл нельзя объединить с другим тайлом в тот же ход (пример: [4,4,8,0] ->[8,8,0,0] True, но [16,0,0,0] False)

3. Длина списка должна быть 4. Который добавляет ноль к хвосту, если список уменьшается после слияния. (Пример: [4,4,0,2] -> [8,0,2,0]).

4. Примечание в случае нулей: [0,0,2,2] -> [0,4,0,0].

Я смог создать код, однако я хочу найти более простой подход, подробно объясненный.

Мой подход:

 merge([H|T],L):-
   merge2([H|T],J),
    (
    length(J,2)->  
    append(J,[0,0],L);
    length(J,3)->  
    append(J,[0],L);length(J,4)-> J=L).

merge2(_,[]).
merge2([X],[X|_]).
merge2([H1,H2|T],[W|L]):-
    H1=H2,
    W is H1 H2,
    merge2(T,L).
merge2([H1,H2|T],[H1|L]):-
    H1=H2,
    merge2([H2|T],L).
 

Длина 4 недостаточно велика, чтобы не просто выписывать случаи:

 merge( [A,B,C,D], Y) :-
  ( A=B -> ( C=D -> X=[A B,C D,0,0] 
                 ;  X=[A B,C,D,0] )
        ;  ( B=C -> X=[A,B C,D,0]
                 ;  ( C=D -> X=[A,B,C D,0]
                          ;  X=[A,B,C,D] ))),
  maplist(is,Y,X).
 

Это просто записывает случаи в соответствии с вашей спецификацией. Мы избавляем себя от необходимости вручную вызывать is каждый раз, когда добавляем две переменные, вместо этого записывая суммы символически, с помощью, и вызывая is для каждого элемента результата сразу в конце, через maplist .

Вот решение для списков произвольной длины и за один проход без append . (Но, как редкий случай для меня, с сокращением!)

Основной предикат отправляется помощнику, который подсчитывает количество нулей для добавления в конце:

 merge(List, Merged) :-
    merge(List, 0, Merged).
 

Важное предложение помощника объединяет два соседних равных значения. Он также увеличивает счетчик нулей, который будет добавлен в конце:

 merge([X, X | Xs], ExtraZeros, [Sum | MergedRest]) :-
    !,
    Sum is X   X,
    merge(Xs, s(ExtraZeros), MergedRest).
 

В противном случае копируйте элементы, пока мы не дойдем до конца списка:

 merge([X | Xs], ExtraZeros, [X | Ys]) :-
    merge(Xs, ExtraZeros, Ys).
 

В конце списка создайте нули по мере необходимости:

 merge([], ExtraZeros, ZeroList) :-
    length_zerolist(ExtraZeros, ZeroList).

length_zerolist(0, []).
length_zerolist(s(N), [0 | Zeros]) :-
    length_zerolist(N, Zeros).
 

Тесты из вопроса:

 ?- merge([4, 4, 0, 0], Merged).
Merged = [8, 0, 0, 0].

?- merge([4, 4, 8, 0], Merged).
Merged = [8, 8, 0, 0].

?- merge([4, 4, 0, 2], Merged).
Merged = [8, 0, 2, 0].

?- merge([0, 0, 2, 2], Merged).
Merged = [0, 4, 0, 0].
 

Более длинный список:

 ?- merge([0, 1, 1, 2, 3, 3, 4, 4, 5], Merged).
Merged = [0, 2, 2, 6, 8, 5, 0, 0, 0].