Anonymous user
Best shuffle: Difference between revisions
→{{header|C}}: Add AWK.
(→{{header|REXX}}: Add Ruby.) |
(→{{header|C}}: Add AWK.) |
||
Line 4:
The words to test with are: <code>abracadabra</code>, <code>seesaw</code>, <code>elk</code>, <code>grrrrrr</code>, <code>up</code>, <code>a</code>
=={{header|AWK}}==
{{trans|Perl 6}}
Awk is a poor choice for this task, because Awk provides no array functions, except for split(). This Awk program uses its own code
* to sort an array,
* to insert an element into the middle of an array,
* to remove an element from the middle of an array (and close the gap),
* to pop an element from the end of an array, and
* to join the elements of an array into a string.
The equivalent programs for [[#Perl 6|Perl 6]] and for [[#Ruby|Ruby]] use several built-in array functions. But if those array functions seem strange to you, and if you can understand this bunch of for loops, then you might prefer this Awk program.
This algorithm calculates an order of positions, then fills a new string in this order, by moving each letter from the original string. It will never replace an old letter with an identical letter, unless the remainder of the original string has only this letter. The next position in the order of filling is always the position of the old letter with the most occurrences among the remaining old letters. This special order can always replace every old letter, unless some old letter occurs in more than half of the original string.
<lang awk># out["string"] = best shuffle of string _s_
# out["score"] = number of matching characters
function best_shuffle(out, s, c, i, j, k, klen, p, pos, set, rlen, slen) {
slen = length(s)
for (i = 1; i <= slen; i++) {
c = substr(s, i, 1)
# _set_ of all characters in _s_, with count
set[c] += 1
# _pos_ classifies positions by letter,
# such that pos[c, 1], pos[c, 2], ..., pos[c, set[c]]
# are the positions of _c_ in _s_.
pos[c, set[c]] = i
}
# k[1], k[2], ..., k[klen] sorts letters from low to high count
klen = 0
for (c in set) {
# insert _c_ into _k_
i = 1
while (i <= klen && set[k[i]] <= set[c])
i++ # find _i_ to sort by insertion
for (j = klen; j >= i; j--)
k[j + 1] = k[j] # make room for k[i]
k[i] = c
klen++
}
# Fill pos[slen], ..., pos[3], pos[2], pos[1] with positions
# in the order that we want to fill them.
i = 1
while (i <= slen) {
for (j = 1; j <= klen; j++) {
c = k[j]
if (set[c] > 0) {
pos[i] = pos[c, set[c]]
i++
delete pos[c, set[c]]
set[c]--
}
}
}
# Now fill in _new_ with _letters_ according to each position
# in pos[slen], ..., pos[1], but skip ahead in _letters_
# if we can avoid matching characteers that way.
rlen = split(s, letters, "")
for (i = slen; i >= 1; i--) {
j = 1
p = pos[i]
while (letters[j] == substr(s, p, 1) && j < rlen)
j++
for (new[p] = letters[j]; j < rlen; j++)
letters[j] = letters[j + 1]
delete letters[rlen]
rlen--
}
out["string"] = ""
for (i = 1; i <= slen; i++) {
out["string"] = out["string"] new[i]
}
out["score"] = 0
for (i = 1; i <= slen; i++) {
if (new[i] == substr(s, i, 1))
out["score"]++
}
}
BEGIN {
count = split("abracadabra seesaw elk grrrrrr up a", words)
for (i = 1; i <= count; i++) {
best_shuffle(result, words[i])
printf "%s, %s, (%d)\n",
words[i], result["string"], result["score"]
}
}</lang>
Output:
<lang bash>$ awk -f best-shuffle.awk
abracadabra, baarrcadaab, (0)
seesaw, essewa, (0)
elk, kel, (0)
grrrrrr, rgrrrrr, (5)
up, pu, (0)
a, a, (1)</lang>
The output might change if the <tt>for (c in set)</tt> loop iterates the array in a different order. (Awk specifies not an order of iteration.)
=={{header|C}}==
| |||