Best shuffle: Difference between revisions
Content added Content deleted
m (→{{header|Phix}}: added syntax colouring, made p2js compatible) |
|||
Line 3,018: | Line 3,018: | ||
up pu (0) |
up pu (0) |
||
a a (1)</pre> |
a a (1)</pre> |
||
=={{header|Picat}}== |
|||
Using a CP (Constraint Programming) solver guarantees an optimal solution. This is deterministic since the solve heuristic ("split") always give the same first result. |
|||
<lang Picat>go => |
|||
Words = ["abracadabra", |
|||
"seesaw", |
|||
"elk", |
|||
"grrrrrr", |
|||
"up", |
|||
"a", |
|||
"shuffle", |
|||
"aaaaaaa" |
|||
], |
|||
foreach(Word in Words) |
|||
best_shuffle(Word,Best,_Score), |
|||
printf("%s, %s, (%d)\n", Word,Best,diff_word(Word, Best)) |
|||
end, |
|||
nl. |
|||
best_shuffle(Word,Best,Score) => |
|||
WordAlpha = Word.map(ord), % convert to integers |
|||
WordAlphaNoDups = WordAlpha.remove_dups(), |
|||
% occurrences of each character in the word |
|||
Occurrences = occurrences(WordAlpha), |
|||
Len = Word.length, |
|||
% Decision variables |
|||
WordC = new_list(Len), |
|||
WordC :: WordAlphaNoDups, |
|||
% |
|||
% The constraints |
|||
% |
|||
% Ensure that the shuffled word has the same |
|||
% occurrences for each character |
|||
foreach(V in WordAlphaNoDups) |
|||
count(V, WordC,#=, Occurrences.get(V)) |
|||
end, |
|||
% The score is the number of characters |
|||
% in the same position as the origin word |
|||
% (to be minimized). |
|||
Score #= sum([WordC[I] #= WordAlpha[I] : I in 1..Len]), |
|||
if var(Score) then |
|||
% We don't have a score yet: minimize Score |
|||
solve([$min(Score),split], WordC) |
|||
else |
|||
% Get a solution for the given Score |
|||
solve([split], WordC) |
|||
end, |
|||
% convert back to alpha |
|||
Best = WordC.map(chr). |
|||
diff_word(W1,W2) = Diff => |
|||
Diff = sum([1 : I in 1..W1.length, W1[I]==W2[I]]). |
|||
occurrences(L) = Occ => |
|||
Occ = new_map(), |
|||
foreach(E in L) |
|||
Occ.put(E, Occ.get(E,0) + 1) |
|||
end.</lang> |
|||
Output: |
|||
<pre>abracadabra, baabacadrar, (0) |
|||
seesaw, assewe, (0) |
|||
elk, kel, (0) |
|||
grrrrrr, rgrrrrr, (5) |
|||
up, pu, (0) |
|||
a, a, (1) |
|||
shuffle, effhlsu, (0) |
|||
aaaaaaa, aaaaaaa, (7)</pre> |
|||
Using a constraint solver makes it quite easy to generate all optimal solutions. |
|||
<lang Picat>go2 ?=> |
|||
Words = ["abracadabra", |
|||
"seesaw", |
|||
"elk", |
|||
"grrrrrr", |
|||
"up", |
|||
"a", |
|||
"shuffle", |
|||
"aaaaaaa" |
|||
], |
|||
member(Word,Words), |
|||
println(word=Word), |
|||
best_shuffle(Word,_Best,Score), |
|||
println(best_score=Score), |
|||
% Find all optimal solutions |
|||
All = findall(Best2,best_shuffle(Word,Best2,Score)), |
|||
Len = All.len, |
|||
println(num_solutions=All.len), |
|||
if Len <= 10 then |
|||
println(solutions=All) |
|||
else |
|||
println("Only showing the first 10 solutions:"), |
|||
println(solutions=All[1..10]) |
|||
end, |
|||
nl, |
|||
fail, |
|||
nl. |
|||
go2 => true.</lang> |
|||
Output: |
|||
<pre>word = abracadabra |
|||
best_score = 0 |
|||
num_solutions = 780 |
|||
Only showing the first 10 solutions: |
|||
solutions = [baabacadrar,baabacaradr,baabacardar,baabacarrad,baabacrdaar,baabacrraad,baabadacrar,baabadaracr,baabadarcar,baabadarrac] |
|||
word = seesaw |
|||
best_score = 0 |
|||
num_solutions = 29 |
|||
Only showing the first 10 solutions: |
|||
solutions = [assewe,asswee,aswees,aswese,awsees,awsese,easews,easwes,easwse,eawess] |
|||
word = elk |
|||
best_score = 0 |
|||
num_solutions = 2 |
|||
solutions = [kel,lke] |
|||
word = grrrrrr |
|||
best_score = 5 |
|||
num_solutions = 6 |
|||
solutions = [rgrrrrr,rrgrrrr,rrrgrrr,rrrrgrr,rrrrrgr,rrrrrrg] |
|||
word = up |
|||
best_score = 0 |
|||
num_solutions = 1 |
|||
solutions = [pu] |
|||
word = a |
|||
best_score = 1 |
|||
num_solutions = 1 |
|||
solutions = [a] |
|||
word = shuffle |
|||
best_score = 0 |
|||
num_solutions = 640 |
|||
Only showing the first 10 solutions: |
|||
solutions = [effhlsu,effhlus,effhsul,effhusl,efflhsu,efflhus,efflshu,efflsuh,effluhs,efflush] |
|||
word = aaaaaaa |
|||
best_score = 7 |
|||
num_solutions = 1 |
|||
solutions = [aaaaaaa]</pre> |
|||
=={{header|PicoLisp}}== |
=={{header|PicoLisp}}== |