Best shuffle: Difference between revisions
m (Javascript: style change) |
|||
Line 95: | Line 95: | ||
var r= []; |
var r= []; |
||
for (var j= 0; j<a.length; j++) |
for (var j= 0; j<a.length; j++) |
||
for (var k= 0; k<a[j].length; k++) |
for (var k= 0; k<a[j].length; k++) r.push(a[j][k]); |
||
r.push(a[j][k]); |
|||
return r; |
return r; |
||
} |
} |
||
Line 105: | Line 104: | ||
for (var j= 0; j<chs.length; j++) { |
for (var j= 0; j<chs.length; j++) { |
||
var ch= chs[j]; |
var ch= chs[j]; |
||
if (null == gr[ch]) gr[ch]= []; |
if (null == gr[ch]) gr[ch]= []; |
||
gr[ch].push(j); |
gr[ch].push(j); |
||
if (mx < gr[ch].length) mx++; |
if (mx < gr[ch].length) mx++; |
||
} |
} |
||
var inds= []; |
var inds= []; |
||
for (var ch in gr) |
for (var ch in gr) inds.push(gr[ch]); |
||
inds.push(gr[ch]); |
|||
var ndx= raze(inds); |
var ndx= raze(inds); |
||
var cycles= []; |
var cycles= []; |
||
for (var k= 0; k < mx; k++) |
for (var k= 0; k < mx; k++) cycles[k]= []; |
||
⚫ | |||
cycles[k]= []; |
|||
⚫ | |||
cycles[j%mx].push(ndx[j]); |
|||
var ref= raze(cycles); |
var ref= raze(cycles); |
||
for (var k= 0; k < mx; k++) |
for (var k= 0; k < mx; k++) cycles[k].push(cycles[k].shift()); |
||
cycles[k].push(cycles[k].shift()); |
|||
var prm= raze(cycles); |
var prm= raze(cycles); |
||
var shf= []; |
var shf= []; |
||
for (var j= 0; j<chs.length; j++) |
for (var j= 0; j<chs.length; j++) shf[ref[j]]= chs[prm[j]]; |
||
shf[ref[j]]= chs[prm[j]]; |
|||
return shf.join(''); |
return shf.join(''); |
||
} |
} |
||
Line 132: | Line 126: | ||
var n= 0; |
var n= 0; |
||
for (var j= 0; j<ex.length; j++) |
for (var j= 0; j<ex.length; j++) |
||
n+= ex.substr(j, 1) == r.substr(j,1) ?1 :0; |
|||
⚫ | |||
n++; |
|||
⚫ | |||
}</lang> |
}</lang> |
||
Line 144: | Line 137: | ||
var sample= ['abracadabra', 'seesaw', 'elk', 'grrrrrr', 'up', 'a'] |
var sample= ['abracadabra', 'seesaw', 'elk', 'grrrrrr', 'up', 'a'] |
||
for (var i= 0; i<sample.length; i++) |
for (var i= 0; i<sample.length; i++) |
||
document.getElementById('out').innerHTML+= disp(sample[i]); |
document.getElementById('out').innerHTML+= disp(sample[i])+'\r\n'; |
||
</script></lang> |
</script></lang> |
||
Revision as of 19:47, 17 December 2010
You are encouraged to solve this task according to the task description, using any language you may know.
Shuffle the characters of a string in such a way that as many of the characters are in a different position as possible. Print the result as follows: original string, shuffled string, (num characters ignored)
For example: tree, eetr, (0)
The words to test with are: abracadabra
, seesaw
, elk
, grrrrrr
, up
, a
D
<lang d>int bestShuffle(string s) {
int countSamePositions(T, U)(T s1, U s2) { return count!("a[0] == a[1] && a[0] != b")(zip(s1, s2), '-'); }
const len = s.length; if (len == 0) { throw new Exception("input string cannot have zero length"); }
char[] ch = s.dup.sort;
auto problemChar = sort!("a[1] > b[1]")(array(group(ch)))[0]; if ((problemChar[1] - len / 2) > 0) { int numToRemove = problemChar[1] - (len - problemChar[1]); for (int i, j; i < len && j < numToRemove; i++) { if (ch[i] == problemChar[0]) { ch[i] = '-'; j++; } } }
do { for (int i = len; i > 1; i--) { swap(ch[i-1], ch[uniform(0, i)]); } } while(countSamePositions(s, ch) > 0);
string result = replace(to!string(ch), "-", to!string(problemChar[0])); int samePos = countSamePositions(s, result);
writefln("%s %s (%s)", s, result, samePos);
return samePos;
}</lang>
output:
abracadabra baadacbraar (0) seesaw easwes (0) elk lke (0) grrrrrr rrrrrgr (5) up pu (0) a a (1)
<lang d>unittest {
assert(bestShuffle("abracadabra") == 0); assert(bestShuffle("seesaw") == 0); assert(bestShuffle("elk") == 0); assert(bestShuffle("grrrrrr") == 5); assert(bestShuffle("up") == 0); assert(bestShuffle("a") == 1);
}</lang>
J
Based on Dan Bron's approach:
<lang j>bestShuf =: verb define
yy=. (\:#&>)@:(<@I.@=) y y C.~ (;yy) </.~ (i.#y) |~ #>{. yy
)
fmtBest=:3 :0
b=. bestShuf y y,', ',b,' (',')',~":+/b=y
) </lang>
Example:
<lang j> fmtBest&>;:'abracadabra seesaw elk grrrrrr up a' abracadabra, bdabararaac (0) seesaw, eawess (0) elk, lke (0) grrrrrr, rgrrrrr (5) up, pu (0) a, a (1) </lang>
JavaScript
Based on the J implementation (and this would be a lot more concise if we used something like jQuery):
<lang javascript>function raze(a) { // like .join() except producing an array instead of a string var r= []; for (var j= 0; j<a.length; j++) for (var k= 0; k<a[j].length; k++) r.push(a[j][k]); return r; } function bestShuf(txt) { var chs= txt.split(); var gr= {}; var mx= 0; for (var j= 0; j<chs.length; j++) { var ch= chs[j]; if (null == gr[ch]) gr[ch]= []; gr[ch].push(j); if (mx < gr[ch].length) mx++; } var inds= []; for (var ch in gr) inds.push(gr[ch]); var ndx= raze(inds); var cycles= []; for (var k= 0; k < mx; k++) cycles[k]= []; for (var j= 0; j<chs.length; j++) cycles[j%mx].push(ndx[j]); var ref= raze(cycles); for (var k= 0; k < mx; k++) cycles[k].push(cycles[k].shift()); var prm= raze(cycles); var shf= []; for (var j= 0; j<chs.length; j++) shf[ref[j]]= chs[prm[j]]; return shf.join(); }
function disp(ex) { var r= bestShuf(ex); var n= 0; for (var j= 0; j<ex.length; j++) n+= ex.substr(j, 1) == r.substr(j,1) ?1 :0; return ex+', '+r+', ('+n+')'; }</lang>
Example:
<lang html><html><head><title></title></head><body>
</body></html>
<script type="text/javascript"> /* ABOVE CODE GOES HERE */ var sample= ['abracadabra', 'seesaw', 'elk', 'grrrrrr', 'up', 'a'] for (var i= 0; i<sample.length; i++) document.getElementById('out').innerHTML+= disp(sample[i])+'\r\n'; </script></lang>
Produces:
<lang>abracadabra, bdabararaac, (0) seesaw, eawess, (0) elk, lke, (0) grrrrrr, rrrrrrg, (5) up, pu, (0) a, a, (1))</lang>
PicoLisp
<lang PicoLisp>(de bestShuffle (Str)
(let Lst NIL (for C (setq Str (chop Str)) (if (assoc C Lst) (con @ (cons C (cdr @))) (push 'Lst (cons C)) ) ) (setq Lst (apply conc (flip (by length sort Lst)))) (let Res (mapcar '((C) (prog1 (or (find <> Lst (circ C)) C) (setq Lst (delete @ Lst)) ) ) Str ) (prinl Str " " Res " (" (cnt = Str Res) ")") ) ) )</lang>
Output:
: (bestShuffle "abracadabra") abracadabra raarababadc (0) : (bestShuffle "seesaw") seesaw essewa (0) : (bestShuffle "elk") elk lke (0) : (bestShuffle "grrrrrr") grrrrrr rgrrrrr (5) : (bestShuffle "up") up pu (0) : (bestShuffle "a") a a (1)
REXX
<lang rexx>/*REXX program to find best shuffle (of a character string). */
list='tree abracadabra seesaw elk grrrrrr up a'
/*find width of the longest word (prettify output).*/
L=0; do k=1 for words(list); L=max(L,length(word(list,k))); end; L=L+5
do j=1 for words(list) /*process the words in the list. */ $=word(list,j) /*the original word in the list. */ new=bestShuffle($) /*shufflized version of the word.*/ say 'original:' left($,L) 'new:' left(new,L) 'count:' countSame($,new) end
exit
/*─────────────────────────────────────bestShuffle procedure────────────*/ bestShuffle: procedure; parse arg x 1 ox; Lx=length(x) if Lx<3 then return reverse(x) /*fast track these puppies. */
do j=1 for Lx-1 /*first take care of replications*/ a=substr(x,j ,1) b=substr(x,j+1,1) if a\==b then iterate _=verify(x,a); if _==0 then iterate /*switch 1st rep with some char. */ y=substr(x,_,1); x=overlay(a,x,_); x=overlay(y,x,j) rx=reverse(x); _=verify(rx,a); if _==0 then iterate /*¬ enuf unique*/ y=substr(rx,_,1); _=lastpos(y,x) /*switch 2nd rep with later char.*/ x=overlay(a,x,_); x=overlay(y,x,j+1) /*OVERLAYs: a fast way to swap*/ end
do j=1 for Lx /*take care of same o'-same o's. */ a=substr(x, j,1) b=substr(ox,j,1) if a\==b then iterate if j==Lx then x=left(x,j-2)a||substr(x,j-1,1) /*spec case of last*/ else x=left(x,j-1)substr(x,j+1,1)a || substr(x,j+2) end
return x
/*─────────────────────────────────────countSame procedure──────────────*/ countSame: procedure; parse arg x,y; k=0
do j=1 for min(length(x),length(y)) k=k+(substr(x,j,1)==substr(y,j,1)) end
return k</lang> Output (with a freebie thrown in):
original: tree new: eert count: 0 original: abracadabra new: baaracadrab count: 0 original: seesaw new: eswase count: 0 original: elk new: lke count: 0 original: grrrrrr new: rrrrrrg count: 5 original: up new: pu count: 0 original: a new: a count: 1
Scheme
<lang scheme> (define count
(lambda (str1 str2) (let ((len (string-length str1))) (let loop ((index 0) (result 0)) (if (= index len) result (loop (+ index 1) (if (eq? (string-ref str1 index) (string-ref str2 index)) (+ result 1) result)))))))
(define swap
(lambda (str index1 index2) (let ((mutable (string-copy str)) (char1 (string-ref str index1)) (char2 (string-ref str index2))) (string-set! mutable index1 char2) (string-set! mutable index2 char1) mutable)))
(define shift
(lambda (str) (string-append (substring str 1 (string-length str)) (substring str 0 1))))
(define shuffle
(lambda (str) (let* ((mutable (shift str)) (len (string-length mutable)) (max-index (- len 1))) (let outer ((index1 0) (best mutable) (best-count (count str mutable))) (if (or (< max-index index1) (= best-count 0)) best (let inner ((index2 (+ index1 1)) (best best) (best-count best-count)) (if (= len index2) (outer (+ index1 1) best best-count) (let* ((next-mutable (swap best index1 index2)) (next-count (count str next-mutable))) (if (= 0 next-count) next-mutable (if (< next-count best-count) (inner (+ index2 1) next-mutable next-count) (inner (+ index2 1) best best-count)))))))))))
(for-each
(lambda (str) (let ((shuffled (shuffle str))) (display (string-append str " " shuffled " (" (number->string (count str shuffled)) ")\n")))) '("abracadabra" "seesaw" "elk" "grrrrrr" "up" "a"))
</lang>
Output:
abracadabra baacadabrar (0) seesaw easews (0) elk lke (0) grrrrrr rrrrrrg (5) up pu (0) a a (1)
Tcl
<lang tcl>package require Tcl 8.5 package require struct::list
- Simple metric function; assumes non-empty lists
proc count {l1 l2} {
foreach a $l1 b $l2 {incr total [string equal $a $b]} return $total
}
- Find the best shuffling of the string
proc bestshuffle {str} {
set origin [split $str ""] set best $origin set score [llength $origin] struct::list foreachperm p $origin {
if {$score > [set score [tcl::mathfunc::min $score [count $origin $p]]]} { set best $p }
} set best [join $best ""] return "$str,$best,($score)"
}</lang> Demonstration: <lang tcl>foreach sample {abracadabra seesaw elk grrrrrr up a} {
puts [bestshuffle $sample]
}</lang> Output:
abracadabra,baabacadrar,(0) seesaw,assewe,(0) elk,kel,(0) grrrrrr,rgrrrrr,(5) up,pu,(0) a,a,(1)