79 lines
1.9 KiB
Awk
79 lines
1.9 KiB
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 characters 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"]
|
|
}
|
|
}
|