Swapping a specific number in list 1 with a specific number in list 2

Question

I have been brushing up on some Prolog recently. I kind of enjoy just coming up with random problems to try and solve and then working them out. This one is quite tough though, and I'm not one to give up on a problem that I have set out to solve.

The problem: I want to make a predicate that will have 2 predetermined lists, 2 numbers to swap, and then output the lists after the swapping is done.

Further Explanation: I made it a little harder on myself by wanting to find a specific unique number from list 1, and swapping this with a specific unique number from list 2 so that if I have 2 lists... [7,2,7,8,5], and [1,2,3,8,7,9,8], and then give the predicate 2 numbers(Lets just say 8 and 7), then the number 8 and the number 7 will be swapped between the lists IF AND ONLY IF the number 8 is in the first list and the number 7 is in the second list. (It would disregard an 8 in the second list and a 7 in the first list).

Sample query with expected answer:

?- bothSwap([7,2,7,8,5],[1,2,3,8,7,9,8],8,7,X,Y).
X = [7,2,7,7,5], Y = [1,2,3,8,8,9,8].

I kind of got stuck at this point:

bothSwap([],L2,N1,N2,[],L2).
bothSwap(L1,[],N1,N2,L1,[]).
bothSwap([H1|T1],[H2|T2],N1,N2,X,Y) :- H1 == N1, H2 == N2, bothSwap(T1,T2,N1,N2,D1,D2), append(D1,[H2],X), append(D2,[H1],Y).
bothSwap([H1|T1],[H2|T2],N1,N2,X,Y) :- H1 == N1, H2 =\= N2, bothSwap([H1|T1],T2,N1,N2,D1,D2).
bothSwap([H1|T1],[H2|T2],N1,N2,X,Y) :- H1 =\= N1, H2 == N2, bothSwap(T1,[H2|T2],N1,N2,D1,D2).

Any bright minds out there willing to tackle this problem with me? :)

Should `bothSwap([7,2,7,8,5,8], [1,2,3,8,7,6,5,7,2], 8, 7, X, Y)` be `X = [7,2,7,7,5,7], Y = [1,2,3,8,8,6,5,8,2]`? Or `X = [7,2,7,7,5,8], Y = [1,2,3,8,8,6,5,7,2]`? — lurker, Jun 19 '15 at 11:34

score 5 · Answer 1 · answered Jun 19 '15 at 05:47

5

Imagine how easy this problem would be if we could just "wish" for a list to be split up at the occurrence of the desired element, like this:

?- splitsies([1,2,3,4,5,6,7,8], 4, Prefix, Suffix).
Prefix = [1, 2, 3],
Suffix = [5, 6, 7, 8] ;

Guess what? :) append/3 can do that:

% splitsies is true if X splits list into a prefix/suffix pair.
splitsies(List, X, Start, Finish) :-
    append(Start, [X|Finish], List).

Now the problem seems pretty simple!

bothSwap(Left, Right, A, B, AfterLeft, AfterRight) :-
    % break up the inputs
    splitsies(Left,  A, LPre, LPost),
    splitsies(Right, B, RPre, RPost),

    % glue together the outputs (note that A and B are switched)
    splitsies(AfterLeft,  B, LPre, LPost),
    splitsies(AfterRight, A, RPre, RPost).

I wouldn't pretend that this solution is efficient… but it's so hot you better wear oven mitts when you type it in. Oh, and check this out:

?- bothSwap([7,2,7,8,5],[1,2,3,8,7,9,8], X, Y, [7,2,7,7,5], [1,2,3,8,8,9,8]).
X = 8,
Y = 7 ;
false.

answered Jun 19 '15 at 05:47

Daniel Lyons

22,421
2
50
77

Was this about **one** replacement? – false Jun 19 '15 at 14:31
I think you misread my original question, and you have it backwards! I want to provide the predicate bothswap/6 with the numbers 8 and 7, not provide the predicate with the intended lists and solve for X and Y. Your solution looks good though! Solid work. – Volman2014 Aug 27 '15 at 00:54
@JohnSmith It does both—try it! That's the beauty of Prolog! Looking forward to your next reply in three months. :) – Daniel Lyons Aug 27 '15 at 00:56
@DanielLyons Its been awhile! Sorry for the late reply. Summer class and internship took its toll, so I have had to postpone little personal projects. I'll check out your solution though! Thank you for contributing. – Volman2014 Aug 27 '15 at 01:03

false · Accepted Answer · 2015-06-20T11:11:04.843

Let's start, what you mean by swapping.

swap(X0,X, S0,S) :-
   if_(X0 = S0, S = X, S = S0).

bothSwap0(Xs0, Ys0, X0,X, Xs,Ys) :-
   maplist(swap(X0,X), Xs0,Xs),
   maplist(swap(X,X0), Ys0,Ys).

if_( C_1, Then_0, Else_0) :-
   call(C_1, Truth),
   functor(Truth,_,0),  % safety check
   ( Truth == true -> Then_0 ; Truth == false, Else_0 ).

=(X, Y, R) :- X == Y, !, R = true.
=(X, Y, R) :- ?=(X, Y), !, R = false. % syntactically different
=(X, Y, R) :- X \= Y, !, R = false. % semantically different
=(X, Y, R) :- R == true, !, X = Y.
=(X, X, true).
=(X, Y, false) :-
   dif(X, Y).

Now you wanted a particular condition - it is not clear how to apply it. I see two interpretations:

bothSwap(Xs0, Ys0, X0,X, Xs,Ys) :-
   memberd(X0, Xs0),
   memberd(X, Ys0),
   maplist(swap(X0,X), Xs0,Xs),
   maplist(swap(X,X0), Ys0,Ys).

Which means that bothSwap/6 will fail should the two elements not occur in their respective list.

Another interpretation might be that you want that otherwise the lists remain the same. To express this (in a pure monotonic fashion):

bothSwap(Xs0, Ys0, X0,X, Xs,Ys) :-
   if_( ( memberd_t(X0, Xs0), memberd_t(X, Ys0) ),
        ( maplist(swap(X0,X), Xs0,Xs), maplist(swap(X,X0), Ys0,Ys) ),
        ( Xs0 = Xs, Ys0 = Ys) ).

memberd_t(E, Xs, T) :-
   list_memberd(Xs, E, T).

list_memberd([], _, false).
list_memberd([X|Xs], E, T) :-
   if_(E = X, T = true, list_memberd(Xs, E, T) ).

','( A_1, B_1, T) :-
   if_( A_1, call(B_1, T), T = false ).

score 1 · Answer 3 · answered Jun 22 '15 at 19:37

Since Prolog is a descriptive language (that is, we describe what constitutes a solution and let Prolog work it out), If I understand your problem statement correctly, something like this ought to suffice:

both_swap(L1, L2, A, B, S1, S2 ) :- % to do the swap,
  memberchk(A,L1) ,                 % - L1 must contain an A
  memberchk(B,L2) ,                 % - L2 must contain a B
  replace(L1,A,B,S1) ,              % - replace all As in L1 with a B
  replace(L2,B,A,S2)                % - replace all Bs in L2 with an A
  .                                 % Easy!

replace([],_,_,[]) .                % if the list is empty, we're done.
replace([H|T],A,B,[S|Ss]) :-        % otherwise...
  ( H = A -> S=B ; S=H ) ,          % - do the swap (if necessary),
  replace(T,A,B,Ss)                 % - and recurse down
  .                                 % Also easy!

s(X). Beware that code based on `memberchk/2` can easily break when confronting it with non-ground Prolog terms. (The same applies to the "in-then-else" construct.) — repeat, Jun 23 '15 at 06:29

lefunction · Answer 4 · 2015-06-23T22:12:26.310

1

This replicates the implementation that uses splitsies/4

swap_two(A,B,C,D,E,F) :-
    nth0(I1,A,C,L1),
    dif(A,L1),
    nth0(I2,B,D,L2),
    dif(B,L2),
    nth0(I1,E,D,L1),
    nth0(I2,F,C,L2).

edited Jun 23 '15 at 22:12

answered Jun 23 '15 at 22:00

lefunction

301
2
16

Swapping a specific number in list 1 with a specific number in list 2

4 Answers4

Linked