Cribbage On Steroids ⧉

At the time of writing, this problem has a difficulty rating of 6.7 on Kattis, which qualifies as a Hard. It's fresh from the contest — I think the difficulty will even out to around a 4.0.

This is a 3-part implementation task. Implement a cribbage scorer for n-length hands.

There are three main subtasks: Given an array of integers...

... count all the ways you can sum to 15.
This is solveable in n^2 steps using dynamic programming. See the function count_sums_to_k for implementation details.
... count all pairs of identical values.
This is given by n choose 2 (n(n-1)/2), with n being the frequency of each value in the array.
... count all ways to make a maximum length contiguous runs of length 3 or more after sorting the array.
This is done in linear time by iterating over an ordered map of the { value, frequency }.

There are more implementation details to consider. For instance, Aces have a face value of 1, but 10s, Jacks, Queens and Kings all have a face value of 10. Keeping all the requirements in order is key.

No one task is difficult on its own, but implementing all three without writing a bug is the challenge! I overlooked the "length 3 or more" requirement for counting runs on my first try. Took a minute to catch.

#include <iostream>
#include <algorithm>
#include <numeric>
#include <map>
#include <functional>
#include <vector>
using ll = long long;
/**
 * Count all the ways to sum to `k` with the values in `arr`.
 * Complexity: O(|arr|^2)
 * */
ll count_sums_to_k(ll k, const std::vector<ll>& arr) {
    // `sum[i]` = the number of subsets of `arr` that sum to `i`
    std::vector<ll> sum (k+1, 0);
    sum[0] = 1; // We can sum to 0 by adding 0 elements together :)
    for (ll x : arr) {
        for (int i = k; i >= 0; --i) {
            if (sum[i] != 0 && i+x <= k) {
                // Since `sum[i]` subsets already sum to `i`, 
                // we can add `x` to each of those subsets, 
                // summing to `i+x` in `sum[i]` different ways!
                sum[i+x] += sum[i]; 
            }
        }
    }
    return sum[k];
}
/**
 * Count all disjoint 'runs' of length 3 or more.
 * */
ll count_runs(const std::map<ll, ll>& counts) {
    ll score = 0;
    ll len = 1;
    ll card = -1;
    ll mul = 1;
    for (const auto& [v, k] : counts) {
        if (card == -1) { card = v; mul = k; continue; }
        if (v == card+1) {
            mul *= k;
            len++;
        } else {
            score += (len > 2 ? mul * len : 0LL);
            len = 1;
            mul = k;
        }
        card = v;
    }
    return score + (len > 2 ? mul * len : 0LL);
}
/**
 * AKA count the pairs that can be made from `n` identical elements.
 **/
ll n_choose_2(ll n) {
    return (n*n - n)/2;
}
int main () {
    // map each card to a number that reflects the order of the ranks
    const auto encode = [] (char card) -> ll {
        if (card == 'A') return 1LL;
        if (card == 'T') return 10LL;
        if (card == 'J') return 11LL;
        if (card == 'Q') return 12LL;
        if (card == 'K') return 13LL;
        return card - '0';
    };
    int n;
    std::cin >> n;
    std::vector<char> cards (n);
    std::map<ll, ll> counts;
    for (auto& card : cards) {
        std::cin >> card;
        counts[encode(card)]++;
    }
    // Ace through 9 map to 1 through 9. 10s, Jacks, Queens and Kings are worth 10.
    const auto face_value = [] (ll encoding) -> ll {
        if (encoding >= 1 && encoding <= 9) return encoding;
        return 10LL;
    };
    std::vector<ll> values (n);
    std::transform(cards.begin(), cards.end(), values.begin(), 
            [&] (char card) { 
                return face_value(encode(card));
            });
    ll to15 = count_sums_to_k(15, values);
    ll pairs = std::accumulate(counts.begin(), counts.end(), 0LL,
            [] (ll acc, const auto& p) {
                return acc + n_choose_2(p.second);
            });
    ll runs = count_runs(counts);
    std::cout << 2 * (to15 + pairs) + runs << '\n';
}

If you found this solution helpful, consider leaving a star!