Problem 948: Left vs Right

View on Project Euler

Project Euler Problem 948 Solution

EulerSolve provides an optimized solution for Project Euler Problem 948, Left vs Right, with C++, Python, Java, and a step-by-step mathematical explanation.

Problem Summary Consider a row of \(n\) cells, each marked \(L\) or \(R\). If only one cell remains, the player named on that cell wins. On a longer interval, the Left player may delete one or more cells from the left end, leaving a non-empty suffix, and the Right player may delete one or more cells from the right end, leaving a non-empty prefix. The quantity of interest is \(F(n)\), the number of length-\(n\) words for which both opening players can force a win on the full row. The implementations do not search the full game tree for \(n=60\). Instead, they reduce the game to an interval recurrence, discover a prefix-balance invariant, and then count the exceptional path classes with ballot numbers and Catalan numbers. Mathematical Approach Write the word as \(a_1a_2\dots a_n\) with each \(a_m\in\{L,R\}\). For any interval \(a_i\dots a_j\), let \(\mathcal{L}(i,j)\) mean that Left to move can force a win, and let \(\mathcal{R}(i,j)\) mean that Right to move can force a win. These interval states are the mathematical core of the solver....

Detailed mathematical approach

Problem Summary

Consider a row of \(n\) cells, each marked \(L\) or \(R\). If only one cell remains, the player named on that cell wins. On a longer interval, the Left player may delete one or more cells from the left end, leaving a non-empty suffix, and the Right player may delete one or more cells from the right end, leaving a non-empty prefix. The quantity of interest is \(F(n)\), the number of length-\(n\) words for which both opening players can force a win on the full row.

The implementations do not search the full game tree for \(n=60\). Instead, they reduce the game to an interval recurrence, discover a prefix-balance invariant, and then count the exceptional path classes with ballot numbers and Catalan numbers.

Mathematical Approach

Write the word as \(a_1a_2\dots a_n\) with each \(a_m\in\{L,R\}\). For any interval \(a_i\dots a_j\), let \(\mathcal{L}(i,j)\) mean that Left to move can force a win, and let \(\mathcal{R}(i,j)\) mean that Right to move can force a win. These interval states are the mathematical core of the solver.

Interval Recurrence for the Game

On a single cell, the label decides the winner immediately:

$$\mathcal{L}(i,i)=1 \iff a_i=L,\qquad \mathcal{R}(i,i)=1 \iff a_i=R.$$

On a longer interval, Left wins exactly when she can cut to a suffix on which Right loses, and Right wins exactly when he can cut to a prefix on which Left loses:

$$\mathcal{L}(i,j)=1 \iff \exists\, t\in\{i+1,\dots,j\}\text{ such that }\mathcal{R}(t,j)=0,$$

$$\mathcal{R}(i,j)=1 \iff \exists\, t\in\{i,\dots,j-1\}\text{ such that }\mathcal{L}(i,t)=0.$$

This recurrence is what the small-\(n\) verifier fills by dynamic programming. The closed form comes from understanding which words make an interval lose for one side.

The Prefix-Balance Invariant

Assign \(+1\) to each \(L\) and \(-1\) to each \(R\), and define the prefix balance

$$s_m=\#\{q\le m:a_q=L\}-\#\{q\le m:a_q=R\},\qquad s_0=0.$$

An induction on interval length shows that the non-both-winning words fall into three very specific classes.

Left wins and Right loses exactly when every prefix is left-heavy:

$$s_m \gt 0\qquad (1\le m\le n).$$

Right wins and Left loses by the mirror condition: the final balance is the unique minimum, so

$$s_m \gt s_n\qquad (0\le m \lt n),\qquad s_n \lt 0.$$

There is also a balanced class in which neither player can force a win:

$$s_m \gt 0\qquad (1\le m \lt n),\qquad s_n=0.$$

The recurrence explains these conditions. If every prefix stays strictly above zero, Right can never cut to a prefix where Left is already dead, so Right loses. If the walk returns to zero only at the very end, Left also fails, because every suffix begins below its own starting level somewhere along the way. If the walk finishes above zero instead, Left can cut to the suffix that starts just after the last time the balance was \(1\), and that suffix again traps Right.

Counting the One-Sided Words

Call \(A_n\) the number of words for which Left wins and Right loses. These are exactly the walks with strictly positive partial sums. Deleting the first \(L\) turns such a walk into a walk of length \(n-1\) that never goes below zero. By the classical ballot/reflection count,

$$A_{2k+1}=\binom{2k}{k},\qquad A_{2k}=\binom{2k-1}{k-1}.$$

By symmetry, the same numbers count the words for which Right wins and Left loses.

The Even-Length Catalan Correction

The balanced class can only occur when \(n=2k\). In that case the walk stays strictly positive until the final step and then returns to zero. Removing the first \(L\) and the last \(R\) produces a Dyck path of semilength \(k-1\), so the number of such words is

$$B_{2k}=\operatorname{Cat}_{k-1}=\frac{1}{k}\binom{2k-2}{k-1}.$$

Therefore the desired count is obtained by subtracting the two one-sided classes and, for even length, the balanced neither-winning class:

$$F(2k+1)=2^{2k+1}-2\binom{2k}{k},$$

$$F(2k)=2^{2k}-2\binom{2k-1}{k-1}-\operatorname{Cat}_{k-1}.$$

Worked Example: Why \(F(8)=181\)

For \(n=8\) we have \(k=4\). The Left-only words are counted by

$$A_8=\binom{7}{3}=35,$$

and the Right-only words contribute the same amount. The neither-winning words are the balanced positive-prefix walks, so

$$B_8=\operatorname{Cat}_3=5.$$

Since there are \(2^8=256\) total \(L/R\) words, the final count is

$$F(8)=256-35-35-5=181,$$

which is exactly the check used in the implementations. As a concrete path example, the word \(LLRLRR\) has balances \(1,2,1,2,1,0\); all proper prefixes are positive and the total balance is \(0\), so it belongs to the balanced neither-winning class.

How the Code Works

Closed-Form Evaluation

The C++, Python, and Java implementations compute binomial coefficients multiplicatively, so no factorial tables or floating-point arithmetic are needed. The Catalan term is obtained from a binomial coefficient by exact division, and the power \(2^n\) is produced directly with integer shifts. After a parity test on \(n\), the program evaluates the appropriate closed formula.

Small-\(n\) Verifier

The implementations also contain an exhaustive verifier for small \(n\). It enumerates all \(2^n\) words, initializes the singleton interval states from the cell labels, and then fills all longer intervals in increasing length order using the same two recurrence relations written above. The brute-force counts are compared with the closed form for \(n=1\) through \(12\), and the sample values \(F(3)=4\) and \(F(8)=181\) are checked explicitly before the final evaluation at \(n=60\).

Complexity Analysis

The production path is the closed-form computation. With multiplicative binomial evaluation, it uses \(O(n)\) arithmetic steps and \(O(1)\) auxiliary storage apart from the integer object itself. For the Project Euler input \(n=60\), this is tiny.

The verifier is intentionally much more expensive. It enumerates \(2^n\) words, fills \(O(n^2)\) interval states for each word, and each state scans up to \(O(n)\) cut positions. That gives \(O(2^n n^3)\) time and \(O(n^2)\) memory, which is why the verifier is only used for very small \(n\).

Footnotes and References

  1. Problem page: Project Euler 948
  2. Bertrand's ballot theorem: Wikipedia - Bertrand's ballot theorem
  3. Catalan number: Wikipedia - Catalan number
  4. Dyck path: Wikipedia - Dyck path
  5. Reflection principle: Wikipedia - Reflection principle

Problem 948 source code

C++

#include <cassert>
#include <cstdint>
#include <iostream>
#include <vector>

namespace {

using u64 = std::uint64_t;
using u128 = unsigned __int128;

u128 binom_u128(u64 n, u64 k) {
    if (k > n) {
        return 0;
    }
    if (k > n - k) {
        k = n - k;
    }

    u128 result = 1;
    for (u64 i = 1; i <= k; ++i) {
        result = (result * static_cast<u128>(n - k + i)) / static_cast<u128>(i);
    }
    return result;
}

u128 catalan_u128(u64 k) {
    return binom_u128(2 * k, k) / static_cast<u128>(k + 1);
}

u128 pow2_u128(u64 n) {
    return static_cast<u128>(1) << n;
}

u128 F_formula(u64 n) {
    if (n % 2ULL == 1ULL) {
        const u64 k = (n - 1ULL) / 2ULL;
        return pow2_u128(n) - 2ULL * binom_u128(2ULL * k, k);
    }

    const u64 k = n / 2ULL;
    return pow2_u128(n) - 2ULL * binom_u128(2ULL * k - 1ULL, k - 1ULL) - catalan_u128(k - 1ULL);
}

bool bit_is_r(u64 mask, int i) {
    return ((mask >> i) & 1ULL) != 0ULL;
}

u64 F_bruteforce(int n) {
    u64 count = 0;
    const u64 total = 1ULL << n;

    for (u64 mask = 0; mask < total; ++mask) {
        std::vector<std::vector<unsigned char>> wl(n, std::vector<unsigned char>(n, 0));
        std::vector<std::vector<unsigned char>> wr(n, std::vector<unsigned char>(n, 0));

        for (int i = 0; i < n; ++i) {
            const bool r = bit_is_r(mask, i);
            wl[i][i] = static_cast<unsigned char>(!r);
            wr[i][i] = static_cast<unsigned char>(r);
        }

        for (int len = 2; len <= n; ++len) {
            for (int i = 0; i + len - 1 < n; ++i) {
                const int j = i + len - 1;

                unsigned char left_win = 0;
                for (int t = i + 1; t <= j; ++t) {
                    if (!wr[t][j]) {
                        left_win = 1;
                        break;
                    }
                }
                wl[i][j] = left_win;

                unsigned char right_win = 0;
                for (int t = i; t < j; ++t) {
                    if (!wl[i][t]) {
                        right_win = 1;
                        break;
                    }
                }
                wr[i][j] = right_win;
            }
        }

        if (wl[0][n - 1] && wr[0][n - 1]) {
            ++count;
        }
    }

    return count;
}

void run_validations() {
    assert(F_formula(3) == 4);
    assert(F_formula(8) == 181);

    for (int n = 1; n <= 12; ++n) {
        assert(F_formula(static_cast<u64>(n)) == F_bruteforce(n));
    }
}

void print_u128(u128 x) {
    if (x == 0) {
        std::cout << '0';
        return;
    }

    std::string s;
    while (x > 0) {
        const int digit = static_cast<int>(x % 10);
        s.push_back(static_cast<char>('0' + digit));
        x /= 10;
    }

    for (auto it = s.rbegin(); it != s.rend(); ++it) {
        std::cout << *it;
    }
}

}  // namespace

int main() {
    run_validations();
    constexpr u64 kN = 60;
    print_u128(F_formula(kN));
    std::cout << '\n';
    return 0;
}

Python

def binom(n, k):
    if k > n:
        return 0
    if k > n - k:
        k = n - k
    result = 1
    for i in range(1, k + 1):
        result = (result * (n - k + i)) // i
    return result

def catalan(k):
    return binom(2 * k, k) // (k + 1)

def F_formula(n):
    if n % 2 == 1:
        k = (n - 1) // 2
        return (1 << n) - 2 * binom(2 * k, k)
    
    k = n // 2
    return (1 << n) - 2 * binom(2 * k - 1, k - 1) - catalan(k - 1)

def bit_is_r(mask, i):
    return ((mask >> i) & 1) != 0

def F_bruteforce(n):
    count = 0
    total = 1 << n
    
    for mask in range(total):
        wl = [[0] * n for _ in range(n)]
        wr = [[0] * n for _ in range(n)]
        
        for i in range(n):
            r = bit_is_r(mask, i)
            wl[i][i] = 0 if r else 1
            wr[i][i] = 1 if r else 0
            
        for length in range(2, n + 1):
            for i in range(n - length + 1):
                j = i + length - 1
                
                left_win = 0
                for t in range(i + 1, j + 1):
                    if not wr[t][j]:
                        left_win = 1
                        break
                wl[i][j] = left_win
                
                right_win = 0
                for t in range(i, j):
                    if not wl[i][t]:
                        right_win = 1
                        break
                wr[i][j] = right_win
                
        if wl[0][n - 1] and wr[0][n - 1]:
            count += 1
            
    return count

def solve():
    return str(F_formula(60))

if __name__ == "__main__":
    assert F_formula(3) == 4
    assert F_formula(8) == 181
    
    for n in range(1, 13):
        assert F_formula(n) == F_bruteforce(n)
        
    print(solve())

Java

import java.math.BigInteger;

public class Euler948 {

    static BigInteger binom(long n, long k) {
        if (k > n) {
            return BigInteger.ZERO;
        }
        if (k > n - k) {
            k = n - k;
        }

        BigInteger result = BigInteger.ONE;
        for (long i = 1; i <= k; ++i) {
            result = result.multiply(BigInteger.valueOf(n - k + i)).divide(BigInteger.valueOf(i));
        }
        return result;
    }

    static BigInteger catalan(long k) {
        return binom(2 * k, k).divide(BigInteger.valueOf(k + 1));
    }

    static BigInteger pow2(long n) {
        return BigInteger.ONE.shiftLeft((int) n);
    }

    static BigInteger F_formula(long n) {
        if (n % 2 == 1) {
            long k = (n - 1) / 2;
            return pow2(n).subtract(binom(2 * k, k).multiply(BigInteger.valueOf(2)));
        }

        long k = n / 2;
        return pow2(n)
                .subtract(binom(2 * k - 1, k - 1).multiply(BigInteger.valueOf(2)))
                .subtract(catalan(k - 1));
    }

    static boolean bitIsR(long mask, int i) {
        return ((mask >> i) & 1L) != 0L;
    }

    static long F_bruteforce(int n) {
        long count = 0;
        long total = 1L << n;

        for (long mask = 0; mask < total; ++mask) {
            byte[][] wl = new byte[n][n];
            byte[][] wr = new byte[n][n];

            for (int i = 0; i < n; ++i) {
                boolean r = bitIsR(mask, i);
                wl[i][i] = (byte) (!r ? 1 : 0);
                wr[i][i] = (byte) (r ? 1 : 0);
            }

            for (int len = 2; len <= n; ++len) {
                for (int i = 0; i + len - 1 < n; ++i) {
                    int j = i + len - 1;

                    byte leftWin = 0;
                    for (int t = i + 1; t <= j; ++t) {
                        if (wr[t][j] == 0) {
                            leftWin = 1;
                            break;
                        }
                    }
                    wl[i][j] = leftWin;

                    byte rightWin = 0;
                    for (int t = i; t < j; ++t) {
                        if (wl[i][t] == 0) {
                            rightWin = 1;
                            break;
                        }
                    }
                    wr[i][j] = rightWin;
                }
            }

            if (wl[0][n - 1] == 1 && wr[0][n - 1] == 1) {
                ++count;
            }
        }

        return count;
    }

    public static String solve() {
        return F_formula(60).toString();
    }

    public static void main(String[] args) {
        if (!F_formula(3).equals(BigInteger.valueOf(4)) || !F_formula(8).equals(BigInteger.valueOf(181))) {
            System.out.println("Validation failed");
            return;
        }

        for (int n = 1; n <= 12; ++n) {
            if (!F_formula((long) n).equals(BigInteger.valueOf(F_bruteforce(n)))) {
                System.out.println("Validation failed for n = " + n);
                return;
            }
        }

        System.out.println(solve());
    }
}