Permute a specific number in list 1 with a specific number in list 2
I've been sneaking up on the prologue a bit lately. I like to just come up with random problems to try to solve and then work them out. It is quite difficult though, and I am not the only one to give up the problem I have decided to solve.
Problem: I want to create a predicate that will have 2 predefined lists, 2 numbers to exchange, and then output the lists after the exchange is complete.
Further explanation: I made it a little more difficult for myself, wanting to find a specific unique number from list 1 and replacing it 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 predicate 2 numbers (Lets just say 8 and 7), then number 8 and number 7 will change between IF lists AND ONLY IF number 8 is in the first list, and the number 7 in the second list. (It will ignore 8 in the second list and 7 in the first list).
An example of a request with an expected response:
?- 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'm kind of 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 willing to solve this problem with me? :)
source to share
Let's start what you mean by replacement.
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 need a certain 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).
This means it bothSwap/6
will fail if two items do not appear in their respective list.
Another interpretation might be that you want the lists to stay the same otherwise. To express this (in a purely monotonic way):
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 ).
source to share
Imagine how easy this problem would be if we could just "wish" to split the list when the desired item appears, for example:
?- 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 this:
% 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 effective ... but it's so hot that you better wear gloves when you introduce it. Oh, and check it 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.
source to share
Since Prolog is a descriptive language (i.e. we describe what the solution is and let Prolog work). If I understand your problem statement correctly, then this should be enough:
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!
source to share