Fun in the SundaYS

Let's do a Fun FridaYS post on Sunday.

I wrote the YS one liner to open 40 random Rosetta Code tasks written in Clojure.

$ cd RosettaCodeData
$ vim $(ys -e 'sh-out("find Lang/Clojure"):lines:shuffle
               .mapv(fn([d] sh-out("ls $d"):lines
               .mapv(fn([f] say("$d/$f")))))' |
        grep -v '\-[0-9]' |
        head -40)

Pretty cool, right?

Best Shuffle

Today's task is called Best Shuffle  .

Shuffle the characters of a string in such a way that as many of the character values are in a different position as possible.

A shuffle that produces a randomized result among the best choices is to be preferred.

A deterministic approach that produces the same sequence every time is acceptable as an alternative.

Display the result as follows:

original string, shuffled string, (score)

The score gives the number of positions whose character value did not change.

Test cases:

abracadabra
seesaw
elk
grrrrrr
up
a

Clojure Solution

(defn score [before after]
  (->> (map = before after)
    (filter true?)
    count))

(defn merge-vecs [init vecs]
  (reduce (fn [counts [index x]]
            (assoc counts x (conj (get counts x []) index)))
    init vecs))

(defn frequency
  "Returns a collection of indices of distinct items"
  [coll]
  (->> (map-indexed vector coll)
    (merge-vecs {})))

(defn group-indices [s]
  (->> (frequency s)
    vals
    (sort-by count)
    reverse))

(defn cycles [coll]
  (let [n (count (first coll))
        cycle (cycle (range n))
        coll (apply concat coll)]
    (->> (map vector coll cycle)
      (merge-vecs []))))

(defn rotate [n coll]
  (let [c (count coll)
        n (rem (+ c n) c)]
    (concat (drop n coll) (take n coll))))

(defn best-shuffle [s]
  (let [ref (cycles (group-indices s))
        prm (apply concat (map (partial rotate 1) ref))
        ref (apply concat ref)]
    (->> (map vector ref prm)
      (sort-by first)
      (map second)
      (map (partial get s))
      (apply str)
      (#(vector s % (score s %))))))

(->> ["abracadabra" "seesaw" "elk" "grrrrrr" "up" "a"]
  (map best-shuffle)
  vec
  println)

Run it:

$ clj -M best-shuffle.clj
[[abracadabra racrababaad 0] [seesaw wssaee 0] [elk kel 0] [grrrrrr rgrrrrr 5] [up pu 0] [a a 1]]

Ported to YS

!YS-v0

defn main(input):
  say: read-string(input)
         .map(best-shuffle):vec

defn best-shuffle(s):
  ref =: s:group-indices:cycles
  prm =: concat.apply(map(partial(rotate 1) ref))
  ref =: concat(ref*)

  map(vector ref prm):
    .sort-by(first _)
    .map(second)
    .map(partial(get s))
    .str(*)
    .call(\([s _ s.score(_)]) _)

defn score(before after):
  map(== before after)
    .filter(true?).#

defn group-indices(s):
  map-indexed(vector s)
    .merge-vecs({}):vals
    .sort-by(count _):reverse

defn cycles(coll):
  n =: coll.0.#
  cycle =: range(n):cycle
  coll =: concat(coll*)
  map(vector coll cycle):
    .merge-vecs([])

defn rotate(n coll):
  c =: coll.#
  n =: (c + n) % c
  concat coll.drop(n): coll.take(n)

defn merge-vecs(vecs init):
  reduce _ init vecs:
    fn(counts [index x]):
      assoc counts x:
        counts.$x.or([]).conj(index)

and run it:

$ ys best-shuffle.ys '["abracadabra" "seesaw" "elk" "grrrrrr" "up" "a"]'
[[abracadabra racrababaad 0] [seesaw wssaee 0] [elk kel 0] [grrrrrr rgrrrrr 5] [up pu 0] [a a 1]]

And published on Rosetta Code  !

Comments