Problem 191: Prize Strings

Project Euler Problem 191 Solution

EulerSolve provides an optimized solution for Project Euler Problem 191, Prize Strings, with C++, Python, Java, and a step-by-step mathematical explanation.

Problem Summary We want the number of length-30 attendance records over $\{O,A,L\}$, where $O$ means on time, $A$ absent, and $L$ late. A record is prize-eligible if it uses at most one $L$ in total and never contains three consecutive $A$'s. The two restrictions have different flavors. The late condition is global, because a single $L$ can be used only once anywhere in the string. The absence condition is local, because only the current trailing run of $A$'s matters when we decide whether another $A$ is legal. Mathematical Approach The implementations exploit exactly that structure. Instead of remembering the whole prefix, they remember only the pieces of information that affect the next day. The six relevant states For $n \ge 0$, let $S_n^{\ell,a}$ denote the number of valid length-$n$ prefixes such that $\ell \in \{0,1\}$ records whether a late day has already appeared, and $a \in \{0,1,2\}$ is the number of consecutive trailing absences. These two quantities are sufficient. Any earlier part of the string becomes irrelevant once we know whether the unique $L$ has already been spent and whether the current suffix ends with 0, 1, or 2 copies of $A$. That gives exactly $2 \times 3 = 6$ states....

Detailed mathematical approach

Problem Summary

Over $n$ school days a child's attendance forms a string of $n$ letters, one per day: $\mathtt O$ for on time, $\mathtt L$ for late and $\mathtt A$ for absent. The child forfeits the cash prize if the string has more than one $\mathtt L$ or contains three consecutive $\mathtt A$'s; all other strings are prize strings. For $n=4$ there are $3^4=81$ strings, and the statement lists the $43$ prize strings among them. We must count the prize strings for $n=30$. ^[1] A late day interrupts a run of absences: $\mathtt{AALA}$, with absences on days $1$, $2$ and $4$, is on the official list.

The whole solution in one sentence: reading a string from left to right, we only need to remember whether the single allowed late day has been used and whether the string ends in zero, one or two absences, so six running counts, updated once per day, count all prize strings without listing any of them.

Mathematical Approach

1. Short strings by hand

Let $T_n$ be the number of prize strings of length $n$. The empty string breaks no rule, so $T_0=1$; all three strings of length $1$ are prize strings, so $T_1=3$; of the nine strings of length $2$ only $\mathtt{LL}$ fails, so $T_2=8$. For $n=4$, $2^4=16$ strings have no $\mathtt L$ and $4\cdot2^3=32$ have one, and five of these $48$ strings contain $\mathtt{AAA}$: $\mathtt{OAAA}$, $\mathtt{AAAO}$, $\mathtt{AAAA}$, $\mathtt{LAAA}$ and $\mathtt{AAAL}$. So $T_4=48-5=43$, as stated. Longer strings need a method that does not test all $3^n$ strings one by one.

2. What the beginning of a string has to remember

Every beginning, or prefix, of a prize string is a prize string, since a forbidden pattern in the prefix would be one of the whole string. For a prize string $x$ let $\ell(x)\in\{0,1\}$ be its number of $\mathtt L$'s and $a(x)\in\{0,1,2\}$ the number of $\mathtt A$'s at its end; $\mathtt{OAA}$, for example, has $\ell=0$ and $a=2$.

Claim. If prize strings $x$ and $y$ have $\ell(x)=\ell(y)$ and $a(x)=a(y)$, then for every string $z$, $xz$ is a prize string exactly when $yz$ is.

Proof. $xz$ and $yz$ have the same number of $\mathtt L$'s. A block of three consecutive $\mathtt A$'s in $xz$ cannot lie inside the prize string $x$. So it lies inside $z$, or it consists of the last $j$ letters of $x$ and the first $3-j$ letters of $z$, with $j=1$ or $2$, where the last $j$ letters of $x$ are all $\mathtt A$ exactly when $a(x)\ge j$. Both cases depend only on $z$ and on $a(x)=a(y)$, so $yz$ contains such a block exactly when $xz$ does. $\square$

Neither number can be dropped: $\mathtt{OA}$ and $\mathtt{AA}$ both end in $\mathtt A$, yet only $\mathtt{OAA}$ is a prize string, and $\mathtt O$ and $\mathtt L$ both end without an absence, yet only $\mathtt{OL}$ is one.

3. Six states and their moves

We call $(\ell,a)$ the state of a prize string; the empty string has the state $(0,0)$. Appending a letter changes the state as follows, and the result is again a prize string exactly in the cases stated:

$\mathtt O$ ends any run of absences: $(\ell,a)\to(\ell,0)$;
$\mathtt A$ lengthens the run: $(\ell,a)\to(\ell,a+1)$, only for $a\le1$;
$\mathtt L$ uses up the late day and ends the run: $(0,a)\to(1,0)$, only for $\ell=0$.

So $13$ of the $18$ pairs of a state and a letter are allowed. With a seventh state for forfeited strings, which every forbidden move leads to and no letter leaves, these rules form a deterministic finite automaton: a machine that starts in a fixed state, here $(0,0)$, and reads a string letter by letter, each letter fixing the next state. ^[2] The prize strings are the strings that do not end in the seventh state; the counts below leave it out, since a forfeited string stays forfeited.

4. Counting by dynamic programming

Let $S_n(\ell,a)$ be the number of prize strings of length $n$ in the state $(\ell,a)$; thus $S_0(0,0)=1$, the other five values for $n=0$ are $0$, and $T_n$ is the sum of the six values for length $n$. Collecting the allowed moves into each state gives, for every $n\ge0$,

$$\begin{aligned}S_{n+1}(0,0)&=\sum_{a=0}^{2}S_n(0,a),\\S_{n+1}(1,0)&=T_n,\\S_{n+1}(\ell,a+1)&=S_n(\ell,a).\end{aligned}$$

The first line collects $\mathtt O$ after the three states with $\ell=0$, and the third, for $a=0,1$, is the move $\mathtt A$. The second holds because every prize string has exactly one letter leading to $(1,0)$: $\mathtt L$ if it has no late day yet, $\mathtt O$ otherwise. Nothing is counted twice or missed, because deleting the last letter of a prize string of length $n+1$ leaves a prize string of length $n$ together with an allowed move from its state into the new state, and appending the letter undoes the deletion. This is dynamic programming: the six values of each length are computed once from those of the previous length, and no string is ever listed. ^[3]

5. Worked example: the first five days

Write the six values as two triples, first $S_n(0,a)$ for $a=0,1,2$, the strings without $\mathtt L$, then $S_n(1,a)$, the strings with one $\mathtt L$:

$n=0$: $(1,0,0)$ and $(0,0,0)$, total $1$;
$n=1$: $(1,1,0)$ and $(1,0,0)$, total $3$;
$n=2$: $(2,1,1)$ and $(3,1,0)$, total $8$;
$n=3$: $(4,2,1)$ and $(8,3,1)$, total $19$;
$n=4$: $(7,4,2)$ and $(19,8,3)$, total $43$;
$n=5$: $(13,7,4)$ and $(43,19,8)$, total $94$.

For $n=2$ the six numbers count, state by state, $\{\mathtt{OO},\mathtt{AO}\}$, $\{\mathtt{OA}\}$, $\{\mathtt{AA}\}$, $\{\mathtt{LO},\mathtt{OL},\mathtt{AL}\}$, $\{\mathtt{LA}\}$ and no string. From $n=3$ to $n=4$, the first line of Section 4 gives $4+2+1=7$, the second $T_3=19$, and the third shifts $4,2$ and $8,3$ one place to the right; the new triples add up to the $43$ of the statement. For $n=6,7,8,9,10$ the totals are $200$, $418$, $861$, $1753$ and $3536$.

6. Two patterns in the table

The second triple for $n=5$, $(43,19,8)$, repeats the totals for $n=4,3,2$, and the first triple, $(13,7,4)$, repeats the sums of the first triples for $n=4,3,2$. Both patterns follow from Section 4. Let $F_n$ be the number of prize strings of length $n$ without $\mathtt L$, the sum of the first triple. For $n\ge3$ and $a=0,1,2$, the first and third lines give $S_n(0,a)=F_{n-1-a}$, and the second and third give $S_n(1,a)=T_{n-1-a}$. So, for every $n\ge3$, adding up the first triple yields $F_n=F_{n-1}+F_{n-2}+F_{n-3}$, and adding all six values yields

$$T_n=T_{n-1}+T_{n-2}+T_{n-3}+F_n;$$

for instance $T_5=43+19+8+24=94$. With $F_0=1$, $F_1=2$ and $F_2=4$, the numbers $F_0,\dots,F_8$ are the Tribonacci numbers $1,2,4,7,13$, $24,44,81$ and $149$: $F_n$ is the term $a(n+3)$ of OEIS A000073, which counts the binary sequences of length $n$ without three consecutive zeros. ^[4]

7. Where the late day stands

A second count, without states, confirms the result. A prize string of length $n$ has either no $\mathtt L$, in $F_n$ ways, or one $\mathtt L$ on some day $r$. Then the days before and after day $r$ form strings of lengths $r-1$ and $n-r$ without $\mathtt L$ and without three consecutive absences, and any two such strings can be combined, because a run of absences cannot pass over the late day. Hence

$$T_n=F_n+\sum_{r=1}^{n}F_{r-1}F_{n-r},$$

$$\begin{aligned}T_4&=13+1\cdot7+2\cdot4+4\cdot2+7\cdot1\\&=13+30=43,\end{aligned}$$

matching the $13$ strings without $\mathtt L$ and the $30$ with one $\mathtt L$ in the statement's list.

Generating functions turn this into one formula. ^[5] Write the counts as the coefficients of the power series $F(x)=F_0+F_1x+F_2x^2+\cdots$, where $x$ only marks the length. Multiplying it by $1-x-x^2-x^3$ leaves $F_0=1$, $F_1-F_0=1$ and $F_2-F_1-F_0=1$ as the coefficients of $1$, $x$ and $x^2$ and, by the recurrence, cancels all later ones, so

$$F(x)=\frac{1+x+x^2}{1-x-x^2-x^3}.$$

In $xF(x)^2$, a term $F_ix^i$ of one factor and a term $F_jx^j$ of the other give $F_iF_jx^{i+j+1}$: a string of length $i$, the late day and a string of length $j$. With $i=r-1$ and $j=n-r$, the sum over $r$ is therefore the coefficient of $x^n$ in $xF(x)^2$. Since $x(1+x+x^2)=x+x^2+x^3$, adding $1$ to $xF(x)$ gives $1+xF(x)=1/(1-x-x^2-x^3)$, and so

$$\begin{aligned}\sum_{n\ge0}T_nx^n&=F(x)\bigl(1+xF(x)\bigr)\\&=\frac{1+x+x^2}{(1-x-x^2-x^3)^2}.\end{aligned}$$

8. How large the numbers become

No count exceeds the number of all strings, so $T_{30}\le3^{30}\approx2.06\cdot10^{14}$, far below the largest signed 64-bit integer $2^{63}-1\approx9.22\cdot10^{18}$. Nor does any number computed on the way exceed $T_{30}$: each value for length $k$ counts some of the $T_k$ prize strings, each partial sum is at most its complete sum, and $T_k\le T_{k+1}$, since appending $\mathtt O$ maps prize strings one to one to longer prize strings. 64-bit integers would first overflow at $66$ days: $T_{65}$ fits, $T_{66}$ does not.

How the Code Works

In the C++ program, ^[6] parse_arguments accepts --skip-checkpoints and --days= with decimal digits, read by parse_int_after_prefix, with $30$ days by default; any other argument, or fewer than one day, gives exit code $1$. Unless switched off, run_checkpoints requires solve(4) to return $43$, with exit code $2$ otherwise, before main prints solve(options.days).

solve keeps the six values $S_n(\ell,a)$ in the array dp[2][3] of i64, that is std::int64_t, indexed by $\ell$ and $a$ and started with dp[0][0] = 1. For each day it starts a fresh array next of zeros and, for each state with a nonzero count ways, adds ways along the allowed moves of Section 3: to next[late][0] for $\mathtt O$, to next[late][a + 1] if a < 2 for $\mathtt A$, and to next[1][0] if late == 0 for $\mathtt L$. This pushes each count forward instead of collecting the sums of Section 4, but every allowed move contributes exactly once either way, so next, copied back into dp, holds the values for the next length. At the end the six entries are added up to $T_n$; the test ways == 0 only skips empty states.

Python's solve and Java's main run the same loops for exactly $30$ days, without options or checkpoint, with nested lists dp and nxt in Python and long[][] arrays in Java. Python's integers are unbounded, and Java's long, like i64, has 64 bits, enough by Section 8. From $66$ days on, the signed sums of the C++ program overflow, which is undefined behaviour; ^[7] our build printed a negative number for $66$ days.

Complexity and Verification

Each day the transition loops visit six states and make one addition per allowed move, at most $13$. Counting an addition of two 64-bit numbers as one step, the time is linear in $n$, and the memory is two arrays of six numbers. For $n=30$ these loops make $180$ state visits and $374$ additions, besides the final sum and the copying.

Besides the C++ checkpoint $T_4=43$, all three programs were run for this article; they print the same number, which also equals the sum of Section 7 computed separately. A C program that tests every string directly found the same $T_n$ for every $n\le18$, and the $43$ strings in the statement's list are exactly the prize strings of length $4$ found by brute force. The recurrence of Section 6, the sum of Section 7 and the coefficients of the generating function agree with the dynamic programme for every $n\le80$, and the C++ program with --days=n is exact for every $1\le n\le65$. These checks are not part of the published solutions.

Footnotes and References

The references below supply the background facts used above; the states, the recurrences, the two counts and the bound on the numbers are derived in this article.

Project Euler 191 — Prize Strings. The official statement: a child forfeits the prize by being absent on three consecutive days or late more than once; the attendance over n days is a string of L (late), O (on time) and A (absent); 43 of the 81 strings for 4 days lead to a prize, and the task asks for the number of prize strings over 30 days.
Wikipedia — Deterministic finite automaton. A deterministic finite automaton has finitely many states, a start state, accept states and a transition function that assigns one next state to each state and input symbol; it reads its input one symbol at a time and accepts a string that ends in an accept state.
Wikipedia — Dynamic programming. Dynamic programming breaks a complicated problem down into simpler sub-problems and makes it possible to count the solutions without visiting them all.
OEIS A000073 — Tribonacci numbers. a(n) = a(n − 1) + a(n − 2) + a(n − 3) with a(0) = a(1) = 0 and a(2) = 1; a(n) is the number of binary sequences of length n − 3 that have no three consecutive 0's.
Wikipedia — Generating function. The ordinary generating function of a sequence aₙ is the power series with the coefficients aₙ; multiplying two of them yields the discrete convolution, or Cauchy product, of the sequences.
C++ — Euler191.cpp. The linked immutable C++ revision contains parse_arguments, solve and run_checkpoints. It is the implementation record for this article.
cppreference — Arithmetic operators. Signed integer overflow is undefined behaviour; one possible manifestation is a two's complement wrap-around.

Problem 191 source code

C++

#include <cstdint>
#include <iostream>
#include <string>
#include <vector>

namespace {

using i64 = std::int64_t;

struct Options {
    int days = 30;
    bool run_checkpoints = true;
};

bool parse_int_after_prefix(const std::string& arg, const std::string& prefix, int& value) {
    if (arg.rfind(prefix, 0U) != 0U) {
        return false;
    }

    const std::string tail = arg.substr(prefix.size());
    if (tail.empty()) {
        return false;
    }

    int parsed = 0;
    for (char c : tail) {
        if (c < '0' || c > '9') {
            return false;
        }
        parsed = parsed * 10 + static_cast<int>(c - '0');
    }
    value = parsed;
    return true;
}

bool parse_arguments(int argc, char** argv, Options& options) {
    for (int i = 1; i < argc; ++i) {
        const std::string arg(argv[i]);
        if (arg == "--skip-checkpoints") {
            options.run_checkpoints = false;
            continue;
        }
        if (parse_int_after_prefix(arg, "--days=", options.days)) {
            continue;
        }

        std::cerr << "Unknown argument: " << arg << '\n';
        return false;
    }
    return options.days >= 1;
}

i64 solve(const int days) {
    // dp[late_used][consecutive_absent]
    i64 dp[2][3] = {};
    dp[0][0] = 1;

    for (int day = 0; day < days; ++day) {
        i64 next[2][3] = {};
        for (int late = 0; late <= 1; ++late) {
            for (int a = 0; a <= 2; ++a) {
                const i64 ways = dp[late][a];
                if (ways == 0) {
                    continue;
                }

                // On time
                next[late][0] += ways;
                // Absent
                if (a < 2) {
                    next[late][a + 1] += ways;
                }
                // Late
                if (late == 0) {
                    next[1][0] += ways;
                }
            }
        }

        for (int late = 0; late <= 1; ++late) {
            for (int a = 0; a <= 2; ++a) {
                dp[late][a] = next[late][a];
            }
        }
    }

    i64 total = 0;
    for (int late = 0; late <= 1; ++late) {
        for (int a = 0; a <= 2; ++a) {
            total += dp[late][a];
        }
    }
    return total;
}

bool run_checkpoints() {
    if (solve(4) != 43LL) {
        std::cerr << "Checkpoint failed for days=4" << '\n';
        return false;
    }
    return true;
}

}  // namespace

int main(int argc, char** argv) {
    Options options;
    if (!parse_arguments(argc, argv, options)) {
        return 1;
    }
    if (options.run_checkpoints && !run_checkpoints()) {
        return 2;
    }

    std::cout << solve(options.days) << '\n';
    return 0;
}

Python

# Problem 191: Prize Strings
# Count attendance strings of length 30 with at most 1 L and no 3 consecutive A's.

def solve():
    days = 30
    # dp[late_used][consecutive_absent]
    dp = [[0]*3 for _ in range(2)]
    dp[0][0] = 1
    for day in range(days):
        nxt = [[0]*3 for _ in range(2)]
        for late in range(2):
            for a in range(3):
                w = dp[late][a]
                if w == 0: continue
                nxt[late][0] += w  # On time
                if a < 2: nxt[late][a+1] += w  # Absent
                if late == 0: nxt[1][0] += w  # Late
        dp = nxt
    print(sum(dp[l][a] for l in range(2) for a in range(3)))

solve()

Java

public class Euler191 {
    public static void main(String[] args) {
        int days = 30;
        long[][] dp = new long[2][3];
        dp[0][0] = 1;
        for (int day = 0; day < days; day++) {
            long[][] nxt = new long[2][3];
            for (int l = 0; l < 2; l++)
                for (int a = 0; a < 3; a++) {
                    long w = dp[l][a];
                    if (w == 0)
                        continue;
                    nxt[l][0] += w;
                    if (a < 2)
                        nxt[l][a + 1] += w;
                    if (l == 0)
                        nxt[1][0] += w;
                }
            dp = nxt;
        }
        long t = 0;
        for (int l = 0; l < 2; l++)
            for (int a = 0; a < 3; a++)
                t += dp[l][a];
        System.out.println(t);
    }
}