Prolog changes order of facts, gives different results
New for Prolog. I have a tiny glitch that I cannot explain, but the program works if I add other dictionary (X) facts. This program takes a list of strings in which the letters have been encoded and creates a decoded list. Each letter represents a different letter in the word list. So go ([abccd, edfgh, ade, ifb, kdl], X) returns X = ['HELLO', 'WORLD', 'HOW', 'ARE', 'YOU']. The problem is that the dictionary fact ("HOW") comes before the dictionary fact ("YOU"), then the program returns X = ["HELLO", "WORLD", "HOW", "ARE", "HOW"), Here buggy code:
/*word bank*/
dictionary('HELLO').
dictionary('WORLD').
dictionary('HOW').
dictionary('ARE').
dictionary('YOU').
/*This spits out a single list where
the lengths of words in the dictionary
are matched to each word in the encoded
message, so [abccd,edfgh,ade,ifb,kdl]
matches [HELLO,WORLD,HOW,ARE,HOW] or
any combination*/
sameLength([X|XTail],[Y|YTail]) :-
dictionary(Y),
name(X,L1),name(Y,L2),
length(L1,Z),length(L2,Z),
sameLength(XTail,YTail).
sameLength([],[]).
/*Turns a list of lists into
a single list*/
oneWord([X|XTail],Y) :-
name(X,L),
append(L,Z,Y),
oneWord(XTail,Z).
oneWord([],[]).
/*This replaces the letters that are in
the dictionary, with the letters in the
message. If at any point a letter has
been replaced because it is UPPERCASE,
and that letter is being replaced by
something else then fail, other wise,
the letter has to be lowercase*/
replaceLetters(List,[X|XTail],[Y|YTail],Result) :-
(X<91,X=Y);(X>96),
replaceP(X,Y,List,Result1),
replaceLetters(Result1,XTail,YTail,Result).
replaceLetters(Result,[],[],Result).
/*the call to action*/
go(X,Y) :-
sameLength(X,Y),
oneWord(X,A),
oneWord(Y,B),
replaceLetters(A,A,B,C),
B=C,
!.
/*replace thanks to @repeat*/
replaceP(_, _, [], []).
replaceP(O, R, [O|T], [R|T2]) :- replaceP(O, R, T, T2).
replaceP(O, R, [H|T], [H|T2]) :- dif(H,O), replaceP(O, R, T, T2).
I would like to add that Prolog is cool. Thanks for your help.
source to share
My solution allowed me to understand if the issue was released
go(X,Y) :-
go(X,Y,[]).
go([],[],_Dict).
go([W|Ws],[T|Ts],Dict) :-
assoc_codes(W,T,Dict,DictUpd),
go(Ws,Ts,DictUpd).
assoc_codes(W,T,Dict,DictUpd) :-
atom_codes(W, Cs),
dictionary(T),
atom_codes(T, Tcs),
upd_dict(Cs, Tcs, Dict, DictUpd).
upd_dict([], [], DictUpd, DictUpd). % done, all went well
upd_dict([C|Cs], [D|Ds], Dict, DictUpd) :-
memberchk(C-T, Dict) % if C already 'assigned', must match D
-> T = D,
upd_dict(Cs, Ds, Dict, DictUpd)
; \+ ( memberchk(X-D, Dict), X \= C ),
upd_dict(Cs, Ds, [C-D|Dict], DictUpd).
Note the else branch: when C is not assigned yet, the same should be true for D. If we comment this (i.e.
... ; % \+ ( memberchk(X-D, Dict), X \= C ), ...
) we have a problem you are reporting
?- go([abccd,edfgh,ade,ifb,kdl],X).
X = ['HELLO', 'WORLD', 'HOW', 'ARE', 'HOW'] ;
X = ['HELLO', 'WORLD', 'HOW', 'ARE', 'YOU'] ;
false.
This follows from the fact that "L" must be assigned to both "c" and "g". After termination of the test, we have
?- go([abccd,edfgh,ade,ifb,kdl],X).
false.
?- go([abccd,edfch,ade,ifb,kdl],X).
X = ['HELLO', 'WORLD', 'HOW', 'ARE', 'YOU'] ;
false.
source to share
a few points:
- I think you have ';' the precedence is incorrect and a different set of parentheses is needed.
- The double HOW is indeed a valid answer as you are not checking this for example. both "a" and "k" are mapped to H (incidentally, the middle "O" matches both 3-letter patterns).
- Perhaps there is a more "Prologue" way to solve your problem using the natural vars unification, ie.
Repeat [abccd, edfgh, ade, ifb, kdl] as a similar list of vars:
[[A,B,C,C,D],[E,D,F,G,H],[A,D,E],[I,F,B][K,D,L]]
and save the dictionary as lists of letters eg.
dictionary(['H','E','L','L','O']).
dictionary('['W','O','R','L','D']).
Then just use Prolog rollback to match all words:
solve([],[]).
solve([Word|Ps],[Word|Words]) :- dictionary(Word), solve(Ps,Words).
and call something like
:- solve([[A,B,C,C,D],[E,D,F,G,H],[A,D,E],[I,F,B],[K,D,L]], Answer).
Note that this still has the same "bug" as your code - no check that all vars match different letters - you'll have to code for this ...
source to share