The Weekly Challenge #291

Middle Index • Poker Hand Rankings
Official Challenge • My Solutions on GitHub

Task 1: Middle Index

You are given an array of integers, @ints. Write a script to find the leftmost index where the sum of numbers to its left equals the sum of numbers to its right. If no such index exists, return -1.

Method Explanation

A naive recalculation of left and right sums for each index takes quadratic $O(N^2)$ time. Instead, we can solve this in linear $O(N)$ time and $O(1)$ extra space:

  1. Compute the total_sum of all elements in the array.
  2. Maintain a running left_sum (initially 0).
  3. For each index $i$, the sum of elements strictly to its right is: $$\text{right\_sum} = \text{total\_sum} - \text{left\_sum} - \text{ints}[i]$$
  4. If left_sum == right_sum, return the current index $i$ immediately (guaranteeing the leftmost match).
  5. Otherwise, update left_sum += ints[i] and proceed.

Perl Implementation

sub find_middle_index ($ints) {
    ($ints) = $INTS_CHECK->($ints);
    return -1 if !@$ints;

    my $total_sum = 0;
    $total_sum += $_ for @$ints;

    my $left_sum = 0;

    for my $i ( 0 .. $#$ints ) {
        my $right_sum = $total_sum - $left_sum - $ints->[$i];

        if ( $left_sum == $right_sum ) {
            return $i;
        }

        $left_sum += $ints->[$i];
    }

    return -1;
}

Python Implementation

def find_middle_index(ints: Sequence[int]) -> int:
    """Find the leftmost index where sum of left elements equals sum of right elements."""
    total_sum = sum(ints)
    left_sum = 0

    for i, val in enumerate(ints):
        right_sum = total_sum - left_sum - val

        if left_sum == right_sum:
            return i

        left_sum += val

    return -1

Task 2: Poker Hand Rankings

A draw poker hand consists of 5 cards, drawn from a pack of 52 cards (no jokers, no wild cards; Ace ranks high or low). Determine:

  1. How many different 5-card hands can be dealt?
  2. How many different hands of each of the 10 ranks can be dealt?
  3. Verify the sum of the 10 rank counts equals the total number of hands.

Combinatorial Derivation

The total number of 5-card hands is $\binom{52}{5} = 2,598,960$. The 10 mutually exclusive categories are calculated as follows:

  • Royal Flush: 4 suits $\times 1 = 4$.
  • Straight Flush: 9 sequences (A-2-3-4-5 up to 9-10-J-Q-K) $\times 4\text{ suits} = 36$.
  • Four of a Kind: $\binom{13}{1} \times \binom{4}{4} \times \binom{48}{1} = 13 \times 1 \times 48 = 624$.
  • Full House: $\binom{13}{1} \times \binom{4}{3} \times \binom{12}{1} \times \binom{4}{2} = 13 \times 4 \times 12 \times 6 = 3,744$.
  • Flush: $4 \times \binom{13}{5} - \text{Royal} - \text{Straight Flush} = 5,148 - 40 = 5,108$.
  • Straight: $10 \times 4^5 - \text{Royal} - \text{Straight Flush} = 10,240 - 40 = 10,200$.
  • Three of a Kind: $\binom{13}{1} \times \binom{4}{3} \times \binom{12}{2} \times 4^2 = 13 \times 4 \times 66 \times 16 = 54,912$.
  • Two Pair: $\binom{13}{2} \times \binom{4}{2}^2 \times \binom{11}{1} \times 4 = 78 \times 36 \times 11 \times 4 = 123,552$.
  • One Pair: $\binom{13}{1} \times \binom{4}{2} \times \binom{12}{3} \times 4^3 = 13 \times 6 \times 220 \times 64 = 1,098,240$.
  • High Card: Total minus all above $= 1,302,540$.

Sum of all 10 hand ranks $= 4 + 36 + 624 + 3744 + 5108 + 10200 + 54912 + 123552 + 1098240 + 1302540 = 2,598,960$.

Perl Implementation

sub calculate_poker_hands () {
    my $total_hands = nCr( 52, 5 );
    my %counts;

    $counts{'Royal Flush'}     = Math::BigInt->new(4);
    $counts{'Straight Flush'}  = Math::BigInt->new( 9 * 4 );
    $counts{'Four of a Kind'}  = Math::BigInt->new(13)->bmul( nCr( 48, 1 ) );
    $counts{'Full House'}      = Math::BigInt->new(13)->bmul( nCr( 4, 3 ) )->bmul(12)->bmul( nCr( 4, 2 ) );

    my $all_flushes            = Math::BigInt->new(4)->bmul( nCr( 13, 5 ) );
    $counts{'Flush'}           = $all_flushes->bsub( $counts{'Royal Flush'} )->bsub( $counts{'Straight Flush'} );

    my $all_straights          = Math::BigInt->new(10)->bmul( Math::BigInt->new(4)->bpow(5) );
    $counts{'Straight'}        = $all_straights->bsub( $counts{'Royal Flush'} )->bsub( $counts{'Straight Flush'} );

    $counts{'Three of a Kind'} = Math::BigInt->new(13)->bmul( nCr( 4, 3 ) )->bmul( nCr( 12, 2 ) )->bmul( Math::BigInt->new(4)->bpow(2) );
    $counts{'Two Pair'}        = nCr( 13, 2 )->bmul( nCr( 4, 2 )->bpow(2) )->bmul(11)->bmul(4);
    $counts{'One Pair'}        = Math::BigInt->new(13)->bmul( nCr( 4, 2 ) )->bmul( nCr( 12, 3 ) )->bmul( Math::BigInt->new(4)->bpow(3) );

    my $sum_non_high = Math::BigInt->new(0);
    $sum_non_high->badd( $counts{$_} ) for keys %counts;
    $counts{'High Card'}       = Math::BigInt->new($total_hands)->bsub($sum_non_high);

    return ( $total_hands, \%counts );
}

Python Implementation

def calculate_poker_hands() -> tuple[int, dict[str, int]]:
    """Calculate the total number of 5-card hands and frequency of each poker rank."""
    total_hands = nCr(52, 5)
    counts: dict[str, int] = {}

    counts["Royal Flush"] = 4
    counts["Straight Flush"] = 9 * 4
    counts["Four of a Kind"] = 13 * nCr(48, 1)
    counts["Full House"] = 13 * nCr(4, 3) * 12 * nCr(4, 2)

    total_flushes = 4 * nCr(13, 5)
    counts["Flush"] = total_flushes - counts["Royal Flush"] - counts["Straight Flush"]

    total_straights = 10 * (4**5)
    counts["Straight"] = total_straights - counts["Royal Flush"] - counts["Straight Flush"]

    counts["Three of a Kind"] = 13 * nCr(4, 3) * nCr(12, 2) * (4**2)
    counts["Two Pair"] = nCr(13, 2) * (nCr(4, 2) ** 2) * 11 * 4
    counts["One Pair"] = 13 * nCr(4, 2) * nCr(12, 3) * (4**3)

    sum_other = sum(counts.values())
    counts["High Card"] = total_hands - sum_other

    return total_hands, counts