Word break problem: Difference between revisions
Content added Content deleted
(→{{header|Phix}}: added syntax colouring, made p2js compatible, added to distro with some more experiments/notes) |
|||
Line 1,328: | Line 1,328: | ||
abcdd: not possible |
abcdd: not possible |
||
</pre> |
</pre> |
||
=={{header|Picat}}== |
|||
===Non-determinism using member/2=== |
|||
<code>s/2</code> checks all possible combinations. It uses <code>member/2</code> to select some element from Dict and backtracks if no solution is found. |
|||
<lang Picat>main => |
|||
Tests = [["aab", ["a", "aa", "b", "ab", "aab"]], |
|||
["abba", ["a", "aa", "b", "ab", "aab"]], |
|||
["aa b", ["a", "aa", "b", "ab", "aab"]], |
|||
["abcd", ["abc", "a", "ac", "b", "c", "cb", "d"]], |
|||
["abbc", ["abc", "a", "ac", "b", "c", "cb", "d"]], |
|||
["abcbcd", ["abc", "a", "ac", "b", "c", "cb", "d"]], |
|||
["acdbc", ["abc", "a", "ac", "b", "c", "cb", "d"]], |
|||
["abcdd", ["abc", "a", "ac", "b", "c", "cb", "d"]] |
|||
], |
|||
foreach([String,Dict] in Tests) |
|||
println([string=String,dict=Dict]), |
|||
All = findall(S, S = s3(Dict,String)), |
|||
println(All), |
|||
nl |
|||
end, |
|||
nl. |
|||
s(Dict,String) = S => |
|||
S = [], |
|||
while(S.flatten != String, S.flatten.len < String.len) |
|||
member(D,Dict), % pick some element in Dict |
|||
S := S ++ [D] |
|||
end, |
|||
S.flatten==String.</lang> |
|||
{{out}} |
|||
<pre>[string = aab,dict = [a,aa,b,ab,aab]] |
|||
[[a,a,b],[a,ab],[aa,b],[aab]] |
|||
[string = abba,dict = [a,aa,b,ab,aab]] |
|||
[[a,b,b,a],[ab,b,a]] |
|||
[string = aa b,dict = [a,aa,b,ab,aab]] |
|||
[] |
|||
[string = abcd,dict = [abc,a,ac,b,c,cb,d]] |
|||
[[abc,d],[a,b,c,d]] |
|||
[string = abbc,dict = [abc,a,ac,b,c,cb,d]] |
|||
[[a,b,b,c]] |
|||
[string = abcbcd,dict = [abc,a,ac,b,c,cb,d]] |
|||
[[abc,b,c,d],[a,b,c,b,c,d],[a,b,cb,c,d]] |
|||
[string = acdbc,dict = [abc,a,ac,b,c,cb,d]] |
|||
[[a,c,d,b,c],[ac,d,b,c]] |
|||
[string = abcdd,dict = [abc,a,ac,b,c,cb,d]] |
|||
[[abc,d,d],[a,b,c,d,d]]</pre> |
|||
===Non-determinism using member/2 and append/3=== |
|||
<code>s2/2</code> is more efficient. It uses <code>append/3</code> to extract the found prefix from the string. |
|||
<lang Picat>s2(Dict,String) = S => |
|||
String2 = copy_term(String), |
|||
S = [], |
|||
while(S.flatten != String, S.flatten.len < String.len) |
|||
% Pick an element from Dict |
|||
member(D,Dict), |
|||
% Check that it fits and remove it from the string. |
|||
% If not: backtrack |
|||
append(D,String3,String2), |
|||
% ok! |
|||
String2 := String3, |
|||
S := S ++ [D] |
|||
end, |
|||
S.flatten==String.</lang> |
|||
===Using recursion=== |
|||
<code>s3/2</code> use the same idea as <code>s2/2</code> but use recursion. Neater and more efficient. |
|||
<lang Picat>s3(Dict,String) = S => |
|||
s3(Dict,String,S). |
|||
s3(_Dict,[],[]). |
|||
s3(Dict,String,[E|S]) :- |
|||
member(E,Dict), |
|||
append(E,String2,String), |
|||
s3(Dict,String2,S).</lang> |
|||
===Some tests=== |
|||
Here is the test engine. |
|||
<lang Picat>main => |
|||
garbage_collect(300_000_000), |
|||
_ = random2(), |
|||
Chars = "ab", |
|||
Dict = ["a", "aa", "b", "ab", "aab"], |
|||
println(dict=Dict), |
|||
String = [Chars[random(1,Chars.len)] : _ in 1..11], |
|||
% The tested strings |
|||
% String := "abbaabba", |
|||
% String := "babbbbaabbababb", |
|||
% String := "babbbbaabbababbaaaaababbaaabbb", |
|||
% String := "babbbbaabbababbaaaaababbaaabbbbaaabbbaba", |
|||
% String := "aabababbbaaabaababaaabababaaabbabbaabbba", |
|||
println(string=String), |
|||
All = findall(S, S = s3(Dict,String)), |
|||
Len = All.len, |
|||
if Len < 100 then |
|||
println(All) |
|||
end, |
|||
println(len=All.len), |
|||
nl.</lang> |
|||
As can be seen by this summary, <code>s3/2</code> is the most efficient of these versions. <code>s/2</code> is too slow but for the simplest examples. |
|||
{{out}} |
|||
<pre>dict = [a,aa,b,ab,aab] |
|||
string = abbaabba |
|||
[[a,b,b,a,a,b,b,a],[a,b,b,a,ab,b,a],[a,b,b,aa,b,b,a],[a,b,b,aab,b,a],[ab,b,a,a,b,b,a],[ab,b,a,ab,b,a],[ab,b,aa,b,b,a],[ab,b,aab,b,a]] |
|||
len = 8 |
|||
s: 0.012s |
|||
s2: 0.0s |
|||
s3: 0.0 |
|||
Dict = ["a", "aa", "b", "ab", "aab"], |
|||
string = babbbbaabbababb |
|||
[[b,a,b,b,b,b,a,a,b,b,a,b,a,b,b],[b,a,b,b,b,b,a,a,b,b,a,b,ab,b],[b,a,b,b,b,b,a,a,b,b,ab,a,b,b],[b,a,b,b,b,b,a,a,b,b,ab,ab,b],[b,a,b,b,b,b,a,ab,b,a,b,a,b,b],[b,a,b,b,b,b,a,ab,b,a,b,ab,b],[b,a,b,b,b,b,a,ab,b,ab,a,b,b],[b,a,b,b,b,b,a,ab,b,ab,ab,b],[b,a,b,b,b,b,aa,b,b,a,b,a,b,b],[b,a,b,b,b,b,aa,b,b,a,b,ab,b],[b,a,b,b,b,b,aa,b,b,ab,a,b,b],[b,a,b,b,b,b,aa,b,b,ab,ab,b],[b,a,b,b,b,b,aab,b,a,b,a,b,b],[b,a,b,b,b,b,aab,b,a,b,ab,b],[b,a,b,b,b,b,aab,b,ab,a,b,b],[b,a,b,b,b,b,aab,b,ab,ab,b],[b,ab,b,b,b,a,a,b,b,a,b,a,b,b],[b,ab,b,b,b,a,a,b,b,a,b,ab,b],[b,ab,b,b,b,a,a,b,b,ab,a,b,b],[b,ab,b,b,b,a,a,b,b,ab,ab,b],[b,ab,b,b,b,a,ab,b,a,b,a,b,b],[b,ab,b,b,b,a,ab,b,a,b,ab,b],[b,ab,b,b,b,a,ab,b,ab,a,b,b],[b,ab,b,b,b,a,ab,b,ab,ab,b],[b,ab,b,b,b,aa,b,b,a,b,a,b,b],[b,ab,b,b,b,aa,b,b,a,b,ab,b],[b,ab,b,b,b,aa,b,b,ab,a,b,b],[b,ab,b,b,b,aa,b,b,ab,ab,b],[b,ab,b,b,b,aab,b,a,b,a,b,b],[b,ab,b,b,b,aab,b,a,b,ab,b],[b,ab,b,b,b,aab,b,ab,a,b,b],[b,ab,b,b,b,aab,b,ab,ab,b]] |
|||
len = 32 |
|||
s: 22.513s |
|||
s2: 0s |
|||
s3: 0s |
|||
Dict = ["a", "aa", "b", "ab", "aab"], |
|||
string = babbbbaabbababbaaaaababbaaabbb |
|||
len = 6144 |
|||
s2: 0.088s |
|||
s3: 0.012s |
|||
Dict = [a,aa,b,ab,aab] |
|||
string = babbbbaabbababbaaaaababbaaabbbbaaabbbaba |
|||
len = 73728 |
|||
s2: 1.466s |
|||
s3: 0.341 |
|||
sdict = [a,aa,b,ab,aab] |
|||
string = aabababbbaaabaababaaabababaaabbabbaabbba |
|||
len = 884736 |
|||
s2: 19.431 seconds |
|||
s3: 3.81 seconds</pre> |
|||
=={{header|PicoLisp}}== |
=={{header|PicoLisp}}== |