cached_shuffle.clj

(ns shuffle)
 
(defn gcd [a b] (if (zero? b) a (recur b (mod a b))))
(defn lcm [a b] (/ (* a b) (gcd a b)))
 
(defn- new-position [deck-size cut-size initial-position]
  (let [cards-shuffled (* 2 cut-size)
        offset (- deck-size cards-shuffled)]
    (cond
      (<= initial-position cut-size)       (+ (dec (* 2 initial-position)) offset)
      (<= initial-position cards-shuffled) (+ (* 2 (- initial-position cut-size)) offset)
      :else (- initial-position cards-shuffled))))
 
(defn- shuffles-required [deck-size cut-size cache initial-position]
  (when-not (@cache initial-position)
    (swap! cache conj initial-position)
    (let [move-card #(new-position deck-size cut-size %)]
      (loop [position (move-card initial-position) iterations 1]
        (swap! cache conj position)
        (if (= position initial-position)
          [iterations]
          (recur (move-card position) (inc iterations)))))))
 
(defn count-shuffles [deck-size cut-size]
  (let [cache (atom #{})]
    (->> (range 1 (inc deck-size))
      (mapcat #(shuffles-required deck-size cut-size cache %))
      (reduce lcm))))

shuffle.clj

(ns shuffle)

(defn gcd [a b] (if (zero? b) a (recur b (mod a b))))
(defn lcm [a b] (/ (* a b) (gcd a b)))

(defn- new-position [deck-size cut-size initial-position]
  (let [cards-shuffled (* 2 cut-size)
        offset (- deck-size cards-shuffled)]
  (cond
    (<= initial-position cut-size)       (+ (dec (* 2 initial-position)) offset)
    (<= initial-position cards-shuffled) (+ (* 2 (- initial-position cut-size)) offset)
    :else (- initial-position cards-shuffled))))

(defn- shuffles-required [deck-size cut-size initial-position]
  (let [move-card #(new-position deck-size cut-size %)]
    (loop [position (move-card initial-position) iterations 1]
      (if (= position initial-position)
        iterations  
        (recur (move-card position) (inc iterations))))))

(defn pcount-shuffles [deck-size cut-size]
  (->> (range 1 (inc deck-size))
    (pmap #(shuffles-required deck-size cut-size %))
    (reduce lcm)))

shuffle.rb

class Shuffle
  def initialize(deck_size, cut_size)
    @deck_size = deck_size
    @cut_size  = cut_size
    @offset    = deck_size - (2 * cut_size)
  end

  def new_position(old_pos)
    case 
    when old_pos <= @cut_size
      2 * old_pos - 1 + @offset
    when old_pos <= (2 * @cut_size)
      2 * (old_pos - @cut_size) + @offset
    else
      old_pos - (2 * @cut_size)
    end
  end

  def cycles_required(initial_pos)
    counter = 1
    position = new_position(initial_pos)
    until position == initial_pos
      counter += 1
      position = new_position(position)
    end
    counter
  end

  def count_shuffles
    (1..@deck_size).map {|i| cycles_required i}.reduce(:lcm)
  end
end

require 'set'
require 'benchmark'

class FastShuffle
  def initialize(deck_size, cut_size)
    @deck_size = deck_size
    @cut_size  = cut_size
    @offset    = deck_size - (2 * cut_size)
    @explored  = Set.new
  end
 
  def new_position(old_pos)
    case 
    when old_pos <= @cut_size
      2 * old_pos - 1 + @offset
    when old_pos <= (2 * @cut_size)
      2 * (old_pos - @cut_size) + @offset
    else
      old_pos - (2 * @cut_size)
    end
  end
 
  def cycles_required(initial_pos)
    return [] if @explored.member? initial_pos
    counter = 1
    position = new_position(initial_pos)
    @explored | [initial_pos, position]
    until position == initial_pos
      counter += 1
      position = new_position(position)
      @explored << position
    end
    counter
  end
 
  def count_shuffles
     @count ||= (1..@deck_size).flat_map {|i| cycles_required i}.reduce(:lcm)
  end
end

Benchmark.bmbm do |x|
  x.report { FastShuffle.new(1002, 101).count_shuffles}
  x.report { Shuffle.new(1002, 101).count_shuffles}  
end