Problem 116: Red, Green or Blue Tiles

Project Euler Problem 116 Solution

EulerSolve provides an optimized solution for Project Euler Problem 116, Red, Green or Blue Tiles, with C++, Python, Java, and a step-by-step mathematical explanation.

Problem Summary We start with a row of 50 grey unit squares. In one tiling we are allowed to use tiles of exactly one non-grey color: red tiles have length 2, green tiles have length 3, and blue tiles have length 4. Grey squares may remain anywhere, colored tiles may touch each other, colors may not be mixed, and the all-grey row is excluded. If $B_m(n)$ denotes the number of valid tilings of a row of length $n$ using grey unit squares and tiles of one fixed length $m$, with at least one colored tile, then the required quantity is $$B_2(50)+B_3(50)+B_4(50).$$ The three colors do not interact, so the problem is really three separate counting problems that are added at the end. Mathematical Approach Fix a tile length $m\in\{2,3,4\}$, and let $A_m(n)$ be the number of tilings of a row of length $n$ when grey squares of length 1 and colored tiles of length $m$ are both allowed, including the all-grey tiling. Then $B_m(n)=A_m(n)-1$. The mathematics comes from counting $A_m(n)$ in two equivalent ways: directly by the number of colored tiles, and recursively by looking at the end of the row....

Detailed mathematical approach

Problem Summary

A row of grey unit squares is to have some of its squares replaced by coloured oblong tiles: red tiles of length two, green of length three or blue of length four. A tile covers as many neighbouring squares as its length; tiles may touch but not overlap, and moving a tile gives a different way. Colours cannot be mixed, and at least one coloured tile must be used. A row of five units allows $7$ ways with red tiles, $3$ with green and $2$ with blue, $7+3+2=12$ in all; we must count the ways for a row of fifty units. ^[1]

The whole solution in one sentence: for tiles of length $m$, the last piece of a row is either a grey square or a coloured tile, so the number of rows of length $n$ is the number for length $n-1$ plus the number for length $n-m$; starting from the empty row, which counts once, running this rule up to fifty units for $m=2$, $3$ and $4$, removing the all-grey row from each count and adding the three counts gives the answer.

Mathematical Approach

We count short rows by hand, then count the rows of one colour by listing them, with a step-by-step rule and with a formula, and see why the three agree.

1. Rows of five units by hand

We write a row as the lengths of its pieces from left to right: $1$ for a grey square and $m$ for a coloured tile of length $m$. So $2+1+1+1$ is a red tile followed by three grey squares, and $1+2+2$ is a grey square followed by two red tiles that touch. With red tiles a row of five units can be filled in seven ways:

one red tile, starting on any of the first four squares: $2+1+1+1$, $1+2+1+1$, $1+1+2+1$ and $1+1+1+2$;
two red tiles: $2+2+1$, $2+1+2$ and $1+2+2$;
three red tiles would need six units.

With green tiles there are three rows, $3+1+1$, $1+3+1$ and $1+1+3$, and with blue tiles two, $4+1$ and $1+4$: together the $7+3+2=12$ of the statement. Left out are the all-grey row $1+1+1+1+1$, which has no coloured tile, and the rows $2+3$ and $3+2$, which mix two colours.

2. Three separate counts

Fix a tile length $m\in\{2,3,4\}$, and let $A_m(n)$ be the number of rows of length $n$ made of grey squares and tiles of length $m$, the all-grey row included. In other words, $A_m(n)$ counts the compositions of $n$ with parts $1$ and $m$: the ways to write $n$ as an ordered sum of these two numbers. ^[2] Without the all-grey row,

$$B_m(n)=A_m(n)-1$$

rows with at least one coloured tile remain. Since colours cannot be mixed, every allowed row is counted by exactly one of $B_2(n)$, $B_3(n)$ and $B_4(n)$, so the answer for a row of length $n$ is

$$T(n)=B_2(n)+B_3(n)+B_4(n),$$

and we need $T(50)$.

3. First method: listing every row

The most direct method fills the row from the left: the leftmost free square gets a grey square or, if there is room, the left end of a coloured tile. Trying both choices at every step produces every row exactly once, since two different rows first differ at some piece, where different choices were made. It is a good check but visits the rows one by one: for $40$ units there are already $A_2(40)=165580141$ rows of grey squares and red tiles, and each extra unit multiplies their number by about $1.618$ (Section 7). Worse, many different beginnings leave the same number of units to fill, and the listing fills them again after each one.

4. Second method: look at the last piece

Instead of listing the rows, we sort them by their last piece. In a row of length $n\ge m$ the last piece is either a grey square, and removing it leaves a row of length $n-1$, or a coloured tile, and removing it leaves a row of length $n-m$. Conversely, adding a grey square to a row of length $n-1$, or a tile to a row of length $n-m$, gives a row of length $n$, and different rows stay different. Hence

$$A_m(n)=A_m(n-1)+A_m(n-m)\qquad(n\ge m).$$

For $1\le n\lt m$ only a grey square can come last, so $A_m(n)=A_m(n-1)=\dots$${}=A_m(0)=1$, where the empty row counts once; then the rule is right at $n=m$ too, where $A_m(m)=A_m(m-1)+A_m(0)=2$ counts the all-grey row and the row of one tile. Computing $A_m(0),A_m(1),\dots$ in this order, each from two stored values, is a small case of dynamic programming: a question is answered by first answering smaller questions of the same kind and remembering their answers. ^[3] By induction on $n$, which proves a first case and then each case from the smaller ones, every computed value is right. For $n=0,1,\dots,12$ the rule gives:

red, $m=2$: $1, 1, 2, 3, 5, 8, 13,$ $21, 34, 55, 89, 144, 233$;
green, $m=3$: $1, 1, 1, 2, 3, 4, 6,$ $9, 13, 19, 28, 41, 60$;
blue, $m=4$: $1, 1, 1, 1, 2, 3, 4,$ $5, 7, 10, 14, 19, 26$.

For instance $A_2(5)=A_2(4)+A_2(3)=5+3=8$: the five rows of length $4$ with a grey square added, and the three rows of length $3$ with a red tile added. Removing the all-grey rows gives $B_2(5)=7$, $B_3(5)=3$ and $B_4(5)=2$.

5. Fibonacci, Narayana and a cousin

The red counts are the Fibonacci numbers $F_1=F_2=1$, $F_{k+1}=F_k+F_{k-1}$, shifted by one place: $A_2(n)=F_{n+1}$, since both start with $1,1$ and follow the same rule. Indian scholars of poetry already counted the $F_{n+1}$ rhythms of length $n$ made of short syllables of one unit and long ones of two, ^[4] exactly these rows. The green counts are Narayana's cows sequence, named after a fourteenth-century Indian mathematician and listed in the On-Line Encyclopedia of Integer Sequences (OEIS) as the compositions with parts $1$ and $3$; ^[5] the blue counts appear there, shifted by one place, as those with parts $1$ and $4$. ^[6]

6. Third method: choose the coloured pieces

Now count the rows with exactly $k$ coloured tiles. The tiles cover $mk$ units, so $n-mk$ grey squares remain, and the row has

$$p=n-mk+k=n-(m-1)k$$

pieces. Shrink every coloured tile to a single marked square: the row becomes $p$ squares, $k$ of them marked, as the green row $1+3+1+3$ becomes four squares with the second and fourth marked. Stretching the marked squares back restores the row, and every choice of marked squares gives a valid row. So the rows are the choices of $k$ of the $p$ places, counted by the binomial coefficient $\binom pk$, the number of $k$-element subsets of a set with $p$ elements. ^[7] Hence

$$A_m(n)=\sum_{k=0}^{\lfloor n/m\rfloor}\binom{n-(m-1)k}{k},$$

and $B_m(n)$ is the same sum from $k=1$ on, as the term $k=0$ is the all-grey row. For red tiles and $n=5$ the terms $\binom41=4$ and $\binom32=3$ are the two groups of Section 1, and $\binom42=6$ counts the green rows of eight units with two tiles. For $n=10$ the red terms $1, 9, 28, 35, 15, 1$ add up to $89=A_2(10)$; they lie on a "shallow" diagonal of Pascal's triangle, and the sums of these diagonals are the Fibonacci numbers. ^[4]

Pascal's rule $\binom pk=\binom{p-1}{k}+\binom{p-1}{k-1}$, with $\binom ab=0$ for $b\gt a$ and for $b\lt0$, ^[7] shows directly that this formula obeys the rule of Section 4. Since

$$\begin{aligned}p-1&=(n-1)-(m-1)k\\&=(n-m)-(m-1)(k-1),\end{aligned}$$

for $n\ge m$ the term with $k$ tiles for length $n$ is the term with $k$ tiles for length $n-1$, a grey square last, plus the term with $k-1$ tiles for length $n-m$, a tile last; adding over $k$ gives the rule again.

7. The generating function and an exact formula

This section explains how fast the counts grow; the programs do not need it. A generating function keeps a whole sequence in one power series, ^[8]

$$G_m(x)=\sum_{n\ge0}A_m(n)\,x^n,$$

whose coefficient of $x^n$, the number in front of it, is the count for length $n$. Give a grey square the weight $x$ and a tile the weight $x^m$: the weights of the pieces of a row of length $n$ multiply to $x^n$, and multiplying out $(x+x^m)^j$ lists every row of $j$ pieces once, ^[2] so the geometric series $1+q+q^2+\dots=1/(1-q)$ gives

$$G_m(x)=\sum_{j\ge0}(x+x^m)^j=\frac{1}{1-x-x^m}.$$

The binomial theorem expands $(x+x^m)^j$ into the terms $\binom jk x^{j+(m-1)k}$; those with $j+(m-1)k=n$ are the terms of Section 6.

The rule of Section 4 is a linear recurrence with constant coefficients. A power $z^n$ obeys it exactly when $z^m=z^{m-1}+1$, the characteristic equation, and when its $m$ roots $z_i$ are distinct, every solution is a sum $\sum_ia_iz_i^n$ with constants fixed by the first values. ^[9] They are distinct: a double root would also solve $mz^{m-1}=(m-1)z^{m-2}$, so it would be $0$ or $(m-1)/m$, and neither is a root. As $1-x-x^m=\prod_i(1-z_ix)$, both sides having degree $m$, the roots $1/z_i$ and the constant term $1$, $G_m$ splits into partial fractions $a_i/(1-z_ix)$, geometric series with the coefficients $a_iz_i^n$. Multiplying $G_m$ by $1-z_ix$ and letting $x$ tend to $1/z_i$, where numerator and denominator both vanish and the limit is the quotient of their derivatives, gives $a_i=z_i/(1+mz_i^{1-m})$, and $z_i^{1-m}=z_i-1$ by the characteristic equation. So

$$A_m(n)=\sum_{i=1}^{m}\frac{z_i^{\,n+1}}{mz_i-m+1}.$$

For red tiles the roots are the golden ratio $\varphi=(1+\sqrt5)/2\approx1.618$ and $-1/\varphi$, and this is Binet's formula: ^[4]

$$F_{n+1}=\frac{\varphi^{n+1}-(-1/\varphi)^{n+1}}{\sqrt5}.$$

For green tiles the only real root is the supergolden ratio $r_3\approx1.4656$, and the complex pair has absolute value $1/\sqrt{r_3}\approx0.8260$; ^[10] for blue tiles the real roots are $r_4\approx1.3803$ and $-0.8192$, and the complex pair has absolute value $0.9404$. So one root $r_m$, with $r_2=\varphi$, exceeds $1$ while the others are smaller than $1$ in absolute value; their powers die out, and

$$A_m(n)\approx c_m\,r_m^{\,n},\qquad c_m=\frac{r_m}{mr_m-m+1},$$

with $c_2\approx0.7236$, $c_3\approx0.6115$ and $c_4\approx0.5475$. The red rows dominate: for $40$ units $A_2(40)=165580141$, but $A_3(40)=2670964$ and $A_4(40)=217286$.

In fact $A_m(n)$ is the integer nearest to $c_mr_m^n$ for every $n\ge0$ and all three colours. The error is at most the sum of $|a_i|\,|z_i|^n$ over the other roots; with every constant rounded up, this is at most $0.2764\cdot0.6181^n$ for red and $0.4594\cdot0.8261^n$ for green, below $\tfrac12$ from $n=0$ on, and $0.1306\cdot0.8192^n$${}+0.4448\cdot0.9405^n$ for blue, below $\tfrac12$ from $n=2$ on, while $c_4\approx0.5475$ and $c_4r_4\approx0.756$ round to $1$. For red this is the classical rule that $F_k$ is the integer nearest to $\varphi^k/\sqrt5$; ^[4] the same kind of rule is known for green and blue. ^[10] ^[6] The formula explains the growth but is no shortcut: the roots are irrational, and longer rows need more of their digits.

8. Worked example: a row of ten units

For ten units the rule of Section 4 gives

$$\begin{aligned}A_2(10)&=A_2(9)+A_2(8)=55+34=89,\\A_3(10)&=A_3(9)+A_3(7)=19+9=28,\\A_4(10)&=A_4(9)+A_4(6)=10+4=14.\end{aligned}$$

The formula of Section 6 agrees: $1+9+28+35+15+1=89$ for red, $\binom{10}{0}+\binom81+\binom62+\binom43$${}=1+8+15+4=28$ for green and $\binom{10}{0}+\binom71+\binom42$${}=1+7+6=14$ for blue. So do the rounded powers of Section 7: $c_2\varphi^{10}\approx89.00$, $c_3r_3^{10}\approx27.96$ and $c_4r_4^{10}\approx13.74$. Without the all-grey rows,

$$T(10)=88+27+13=128.$$

The totals $T(n)$ for $n=1,\dots,12$ are $0, 1, 3, 7, 12, 20,$ $32, 51, 81, 128, 201, 316$.

9. Pitfalls

Keeping the all-grey row counts it once per colour and gives $T(n)+3$, $15$ instead of $12$ for five units. Removing it at the end is simplest: counted directly, the rows with a tile obey $B_m(n)=B_m(n-1)$${}+B_m(n-m)+1$ for $n\ge m$, the extra $1$ being the row whose only tile comes last, as in $B_2(5)=4+2+1=7$.
The empty row must count once: starting from $A_m(0)=0$ and $A_m(1)=1$ loses the rows that begin with a tile, which the rule reaches through the empty row, here $2+1+1+1$, $2+1+2$ and $2+2+1$, and leaves $4$ red rows of five units instead of $7$.
Tiles of the same colour may touch, and they are all alike: $2+2+1$ is one row. If tiles had to be separated by grey squares, five units would allow only $4+1=5$ red rows; the $7$ of the statement rules this reading out.
Mixing colours gives Problem 117, with the rule $A(n)=A(n-1)+A(n-2)$${}+A(n-3)+A(n-4)$ and the all-grey row included: for five units $15$ rows, our $12$, the all-grey row and the mixed rows $2+3$ and $3+2$. ^[11]
The counts outgrow 32-bit integers: $A_2(n)=F_{n+1}$ exceeds $2^{31}-1$ from $n=46$ on, as $F_{47}=2971215073$. That 64-bit integers suffice for fifty units needs no computation: a row is fixed by its set of coloured squares, whose runs split into tiles in only one way, so $A_m(n)\le2^n$, and every number the programs form is below $3\cdot2^{50}\lt2^{63}$. In fact they suffice up to $n=91$ and overflow at $n=92$, as $F_{93}\gt2^{63}-1$.

10. Very long rows

The rule of Section 4 takes $n$ steps, far too many for, say, $n=10^{18}$ with the counts taken modulo some number. Keep the last $m$ counts, newest first, in a column. One step multiplies it by the $m\times m$ matrix $M$ whose first row has ones in its first and last places, with ones just below the diagonal and zeros elsewhere: the first row adds the two counts of the rule, and the other rows shift the column down. ^[9] With $A_m(j)=0$ for $-m\lt j\lt0$, which leaves the rule true for every $n\ge1$, the column for length $0$ is $(1,0,\dots,0)$, so $A_m(n)$ is the top left entry of $M^n$. Exponentiation by squaring builds $M^n$ from $M^2,M^4,M^8,\dots$ along the binary digits of $n$, with $\lfloor\log_2n\rfloor$ squarings and one product fewer than the number of digits $1$: ^[12] $59$ squarings and $23$ products for $n=10^{18}$. For red tiles this is the matrix form of the Fibonacci numbers, ^[4]

$$\begin{pmatrix}1&1\\1&0\end{pmatrix}^{n}=\begin{pmatrix}F_{n+1}&F_n\\F_n&F_{n-1}\end{pmatrix};$$

for $n=5$ the power is $\begin{pmatrix}8&5\\5&3\end{pmatrix}$. This works for any set of tile lengths, as the rule stays a sum of earlier values.

How the Code Works

All three programs use the rule of Section 4 once for each colour. In the C++ program ^[13] the function count_single_color(length, tile) creates a vector dp of length + 1 numbers of type i64, that is std::int64_t, and sets dp[0] = 1 for the empty row. For $n=1,2,\dots$ in order it starts from dp[n - 1], the rows ending with a grey square, and adds dp[n - tile], the rows ending with a tile, when $n$ is at least tile, a test that also keeps the index inside the table. So dp[n] is $A_m(n)$ with $m$ equal to tile, and $A_m(n)=1$ for $n\lt m$ needs no special case. The function returns dp[length] - 1, that is $B_m(n)$, and solve(length) adds the results for the tile lengths $2$, $3$ and $4$, the sum $T(n)$ of Section 2.

main reads the options with parse_arguments into an Options record: the length is $50$ unless --length=N sets another one, which parse_int_after_prefix accepts as a nonempty string of decimal digits, and --skip-checkpoints turns the check off. Any other argument ends the program with an error message and exit code $1$, and so does the length $0$, silently. Unless skipped, run_checkpoints checks that solve(5) returns the $12$ of the statement, or ends the program with exit code $2$; then main prints solve for the chosen length.

The Python program has the same function count_single_color, with a list, and a function solve that prints the sum for fifty units; the Java program does the same in count and main with an array of long. Neither has options or a check. Python integers have no size limit; Java's long and std::int64_t have 64 bits, enough by Section 9. The C++ program, the only one that accepts other lengths, is exact only up to --length=91: from $92$ on the addition in count_single_color overflows, which is undefined behaviour in C++; the true counts no longer fit in 64 bits, so no printed number can be right. Nor are the digits after --length= range-checked, so a number beyond the range of int overflows while it is read.

Complexity and Verification

For a row of $n$ units and tiles of length $m$ the loop makes $n$ passes, $\max(0,n-m+1)$ of them with an addition: for fifty units $150$ passes and $49+48+47=144$ additions. Counting each addition as one step, time and memory are proportional to $n$; the last $m$ values would suffice, as the bottom-up Fibonacci computation keeps only two. ^[3] With Python's exact integers and a huge $n$, an addition is no longer one step: $A_2(n)$ has about $0.694\,n$ binary digits, as $\log_2\varphi\approx0.694$, so the loop takes time proportional to $n^2$ and the table memory proportional to $n^2$ bits. In our runs each program finished within a few hundredths of a second, mostly start-up time. Listing the rows takes time proportional to their exponentially growing number, the matrix powers of Section 10 about $m^3\log n$ operations.

Unless --skip-checkpoints is given, the C++ program checks the $12$ of the statement before every run. For this article the three programs were run: they print the same number for fifty units, which agrees with the formula of Section 6 in exact integers, and the C++ program runs cleanly under the compiler's undefined-behaviour checker. Listing the rows reproduces the counts of Section 4 for every length up to $22$, and so does trying every set of starting squares up to $16$; the formula of Section 6 agrees with the rule up to length $1000$, and for tile lengths $5$ to $8$ up to $200$; the series of Section 7 agrees up to $x^{100}$, and the rounding rule holds for every $n\le1000$ in $450$-digit arithmetic. With --length the C++ program gives $12$, $128$ and $12566$ for five, ten and twenty units and agrees with exact integers up to $91$; for every length from $92$ to $120$ the normal build prints a wrong number, and the checker reports the signed overflow.

Footnotes and References

These sources supply the background facts; everything else is derived above.

Project Euler 116 — Red, Green or Blue Tiles. The official statement: grey squares are replaced by red (length two), green (three) or blue (four) tiles, five units allow 7, 3 and 2 ways, 12 in all, and the task asks for the ways for fifty units when colours are not mixed and at least one coloured tile is used.
Wikipedia — Composition (combinatorics). A composition writes n as an ordered sum of positive integers; with parts from a set A, those with k parts are counted by the coefficient of xⁿ in the k-th power of the sum of xᵃ over a in A.
Wikipedia — Dynamic programming. Solutions of sub-problems are stored and reused; bottom-up, the Fibonacci numbers take linear time and constant memory.
Wikipedia — Fibonacci number. Rhythms of long (two units) and short (one unit) syllables of length m number F(m+1); the page also gives the shallow-diagonal sums of Pascal's triangle, Binet's formula, F(n) as the integer closest to φⁿ/√5, and the matrix form.
OEIS A000930 — Narayana's cows sequence. The sequence 1, 1, 1, 2, 3, 4, 6, … counts the compositions of n into parts 1 and 3, has the generating function 1/(1 − x − x³) and goes back to Narayana Pandita's Ganita Kaumudi (1356).
OEIS A003269. Its terms 0, 1, 1, 1, 1, 2, 3, … obey a(n) = a(n−1) + a(n−4); a(n+1) counts the compositions of n into parts 1 and 4, the generating function is x/(1 − x − x⁴), and a(n) is the integer nearest to d·cⁿ, with c = 1.3802775… the positive root of x⁴ = x³ + 1.
Wikipedia — Binomial coefficient. C(n, k) counts the k-element subsets of an n-element set and is 0 for k > n or k < 0; the page gives Pascal's rule and the binomial theorem.
Wikipedia — Generating function. The ordinary generating function of aₙ is the power series Σ aₙxⁿ; for 1, 1, 1, … it is the geometric series 1/(1 − x).
Wikipedia — Linear recurrence with constant coefficients. With distinct characteristic roots, every solution is a combination of their n-th powers with constants fixed by the initial values; the recurrence can be written as a first-order matrix equation.
Wikipedia — Supergolden ratio. The real solution ψ ≈ 1.46557 of x³ = x² + 1; its complex conjugates have absolute value 1/√ψ, and the terms of Narayana's cows sequence are the nearest integers to a constant times powers of ψ.
Project Euler 117 — Red, Green, and Blue Tiles. Grey squares and red, green and blue tiles combined in one row; a row of five units can then be tiled in fifteen ways.
Wikipedia — Exponentiation by squaring. Repeated squaring along the binary digits of n takes ⌊log₂ n⌋ squarings and one multiplication fewer than the number of ones in n; the method is often used for powers of matrices.
C++ — Euler116.cpp. The linked immutable revision contains count_single_color, solve, run_checkpoints and the options --length and --skip-checkpoints.

Problem 116 source code

C++

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

namespace {

using i64 = std::int64_t;

struct Options {
    int length = 50;
    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, "--length=", options.length)) {
            continue;
        }

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

i64 count_single_color(const int length, const int tile) {
    std::vector<i64> dp(static_cast<std::size_t>(length + 1), 0);
    dp[0] = 1;

    for (int n = 1; n <= length; ++n) {
        i64 ways = dp[static_cast<std::size_t>(n - 1)];
        if (n >= tile) {
            ways += dp[static_cast<std::size_t>(n - tile)];
        }
        dp[static_cast<std::size_t>(n)] = ways;
    }

    return dp[static_cast<std::size_t>(length)] - 1;
}

i64 solve(const int length) {
    return count_single_color(length, 2) +
           count_single_color(length, 3) +
           count_single_color(length, 4);
}

bool run_checkpoints() {
    if (solve(5) != 12) {
        std::cerr << "Checkpoint failed for length=5" << '\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.length) << '\n';
    return 0;
}

Python

# Problem 116: Red, green or blue tiles
# Replace grey tiles with colored tiles (red=2, green=3, blue=4). No mixing.

def count_single_color(length, tile):
    dp = [0] * (length + 1)
    dp[0] = 1
    for n in range(1, length + 1):
        dp[n] = dp[n - 1]
        if n >= tile:
            dp[n] += dp[n - tile]
    return dp[length] - 1

def solve():
    print(count_single_color(50, 2) + count_single_color(50, 3) + count_single_color(50, 4))

solve()

Java

public class Euler116 {
    static long count(int len, int tile) {
        long[] dp=new long[len+1]; dp[0]=1;
        for(int n=1;n<=len;n++){dp[n]=dp[n-1];if(n>=tile)dp[n]+=dp[n-tile];}
        return dp[len]-1;
    }
    public static void main(String[] args) { System.out.println(count(50,2)+count(50,3)+count(50,4)); }
}