|
<lang awk>{
scram = best_shuffle($0)
print $0 " -> " scram " (" unchanged($0, scram) ")"
}
function best_shuffle(s, c, i, j, len, r, t) {
len = split(s, t, "")
# Swap elements of t[] to get a best shuffle.
for (i = 1; i <= len; i++) {
for (j = 1; j <= len; j++) {
# Swap t[i] and t[j] if they will not match
# the original characters from s.
if (i != j &&
t[i] != substr(s, j, 1) &&
substr(s, i, 1) != t[j]) {
c = t[i]
t[i] = t[j]
t[j] = c
break
}
}
}
}
}
}
# Join t[] into one string.
r = ""
for (i = 1; i <= len; i++)
r = r t[i]
return r
}
function unchanged(s1, s2, count, len) {
count = 0
len = length(s1)
for (i = 1; i <= len; i++) {
if (substr(s1, i, 1) == substr(s2, i, 1))
count++
}
}
return count
}</lang>
<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++
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++
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>
|