JoinTheRanks

EvenOddPeriodic.swift

func mergeByTwo(R: Int, height: Int) -> [(a: Int, b: Int)] {
    /** Merges the top two sorted decks. The first has `height` cards of each rank. */
    // Loop through zero-indexed rank of the card on top.
    return stride(from: 0, to: R - 1, by: 2)
    // a: Move the next two ranks below.
    // b: There are three components in the remaining deck:
    //      (1) the remainder (greater ranks) of the top deck;
    //      (2) the accumulated smaller ranks in the bottom deck; and
    //      (3) the number of matching ranks in the bottom.
    //    (R - rank - 2) * height + rank * (height + 1) + 1
      .map { (a: 2 * height, b: (R - 2) * height + $0 + 1) }
}

func joinTheRanks(state: [(a: Int, b: Int)] = [], R: Int, S: Int) -> [(a: Int, b: Int)] {
    /** Joins S sorted decks of rank R into a single sorted deck. */
    if R == 1 { return state }
    switch S {
    case 0, 1: return state
    case _ where S > 1:
        // Each deck satisfies the invariant of being sorted, but the top two
        // are potentially of different size. We accumulate all the cards in the
        // the top-most deck.
        let height = 1 + (state.count * 2) / R
        let head = state + mergeByTwo(R: R, height: height)
        // For even ranks, the period is one merge.
        if (R % 2 == 0) { return joinTheRanks(state: head, R: R, S: S - 1) }
        // If we're at the end, we just need one extra move.
        if (S == 2) { return head + [(a: height, b: (R - 1) * (height + 1) + 1)] }
        // Otherwise, the period is 2 merges, and we move the last rank together
        // with the first rank. Since we're moving two ranks, there are R - 2
        // ranks in the second deck.
        let body = [(a: 2 * height + 1, b: (R - 2) * (height + 1) + 1)]
        // After that there are still R - 1 ranks left, which is an even
        // number. We add an offset to the second deck to account for the first
        // rank already having been moved.
        let tail = mergeByTwo(
          R: R - 1, height: height + 1).map { ($0.a, $0.b + height + 2) }
        return joinTheRanks(state: head + body + tail, R: R, S: S - 2)
    default: fatalError("S must be nonnegative but S = \(S).")
    }
}

let T = Int(readLine()!)!
for t in 1...T {
    let args = readLine()!.split(separator: " ").map { Int($0)! }
    let (R, S) = (args[0], args[1])
    let swaps = joinTheRanks(R: R, S: S)
    print("Case #\(t): \(swaps.count)")
    print(swaps.map({ "\($0.a) \($0.b)" }).joined(separator: "\n"))
}

TopTwoRanks.swift

struct CyclicDeck {
    /**
     A deck sorted cyclically: [topRank,..., (topRank + R - 1) % R]
     There are rankCounts[rank] cards of each rank.
     */
    let rankCounts: [Int]
    let topRank: Int
    let size: Int

    init(R: Int) {
        self.init(rankCounts: Array(repeating: 1, count: R), topRank: 0, size: R)
    }

    func swap(S: Int) -> ((a: Int, b: Int), CyclicDeck) {
        let nextRank = (topRank + 1) % rankCounts.count
        // Move two ranks if possible.
        let (a, swappedRanks) = rankCounts[nextRank] < S ?
          (rankCounts[topRank] + rankCounts[nextRank], Set([topRank, nextRank])) :
          (rankCounts[topRank], Set([topRank]))
        return (
          (a: a, b: size - a + 1),
          CyclicDeck(
            rankCounts: rankCounts.enumerated().map {
                swappedRanks.contains($0.offset) ? $0.element + 1 : $0.element
            },
            topRank: (topRank + swappedRanks.count) % rankCounts.count,
            size: size + swappedRanks.count))
    }

    private init(rankCounts: [Int], topRank: Int, size: Int) {
        self.rankCounts = rankCounts
        self.topRank = topRank
        self.size = size
    }
}

func joinTheRanks(R: Int, S: Int) -> [(a: Int, b: Int)] {
    // The initial deck is S sorted decks of rank R.
    var topDeck = CyclicDeck(R: R) 
    // Continually grow the top deck until there's one deck.
    var swaps: [(a: Int, b: Int)] = []
    while topDeck.size < R * S {
        let (swap, swappedDeck) = topDeck.swap(S: S)
        swaps.append(swap)
        topDeck = swappedDeck
    }
    return swaps
}

let T = Int(readLine()!)!
for t in 1...T {
    let args = readLine()!.split(separator: " ").map { Int($0)! }
    let (R, S) = (args[0], args[1])
    let swaps = joinTheRanks(R: R, S: S)
    print("Case #\(t): \(swaps.count)")
    print(swaps.map({ "\($0.a) \($0.b)" }).joined(separator: "\n"))
}