Best shuffle: Difference between revisions
→{{header|Picat}}
m (→{{header|Phix}}: added syntax colouring, made p2js compatible) |
|||
Line 3,018:
up pu (0)
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}}==
| |||