Problem 114: Counting Block Combinations I

Project Euler Problem 114 Solution

EulerSolve provides an optimized solution for Project Euler Problem 114, Counting Block Combinations I, with C++, Python, Java, and a step-by-step mathematical explanation.

Problem Summary We have a row of 50 cells. Each cell is either left grey or covered by a red block, and every red block must have length at least 3. If two red blocks both appear, they must be separated by at least one grey cell. The all-grey arrangement is allowed, so the question is to count every valid coloring of the row under those rules. The natural quantity to compute is $F(n)$, the number of valid arrangements for a row of length $n$. The goal of the problem is $F(50)$. Mathematical Approach The key is to choose a state that remembers only the remaining row length. Because every legal continuation depends solely on how many cells are left, dynamic programming gives an exact count with no overcounting. The right state variable Let $F(n)$ be the number of valid fillings of a row of length $n$. There is exactly one way to fill an empty row, so $$F(0)=1.$$ For $n=1$ and $n=2$, no red block can fit, so the only arrangement is still the all-grey one: $$F(1)=F(2)=1.$$ This already captures the most important invariant in the problem: once the left part of the row has been fixed legally, the remainder is just a smaller copy of the same counting problem. A unique decomposition by the leftmost decision To count $F(n)$, inspect the leftmost cell. If that cell is grey, the rest of the row is any valid arrangement of length $n-1$, contributing $F(n-1)$....

Detailed mathematical approach

Problem Summary

A row of unit squares is filled by placing red blocks on it. Every red block covers at least $3$ neighbouring squares, blocks may have different lengths, and any two red blocks must be separated by at least one grey square; every square that no block covers is grey. A row of seven squares can be filled in exactly $17$ ways, and lengths may be mixed: a row of eight squares may carry a red block of $3$, one grey square and a red block of $4$. We must find the number of ways to fill a row of fifty squares. ^[1] We write $W(n)$ for the number of fillings of a row of $n$ squares, so $W(7)=17$ is given and $W(50)$ is asked for; the row that stays entirely grey is one of the seventeen, as Section 2 shows.

The whole solution in one sentence: the leftmost square is either grey or the first square of a red block, which must be followed by a grey square unless it reaches the end of the row, so $W(n)$ is a sum of the counts for shorter rows, and a table filled from the empty row up to fifty squares gives the answer after about a thousand additions. Sections 6 to 9 go further and prove that $2W(n)$ is a Fibonacci number plus $1$, $0$ or $-1$, in a pattern that repeats every six lengths.

Mathematical Approach

We start with rows short enough to fill by hand, turn the leftmost square into the rule that the programs compute, and then count the same fillings in two more ways, which lead to a closed formula.

1. Small rows

Write $\mathtt R$ for a red square and $\mathtt G$ for a grey one, so that a filling is a word such as $\mathtt{GRRRG}$. Only the finished row matters, not the order in which the blocks were put down, and a row and its mirror image, such as $\mathtt{RRRG}$ and $\mathtt{GRRR}$, are different fillings. A row of $1$ or $2$ squares is too short for a block, so its only filling is all grey: $W(1)=W(2)=1$. A row of $3$ squares gives $\mathtt{GGG}$ and $\mathtt{RRR}$, so $W(3)=2$, and a row of $4$ gives $\mathtt{GGGG}$, $\mathtt{RRRG}$, $\mathtt{GRRR}$ and $\mathtt{RRRR}$, so $W(4)=4$. Two blocks need at least $3+1+3=7$ squares. We also count the empty row of length $0$: it has exactly one filling, the one with nothing in it, so $W(0)=1$.

2. Fillings are colourings

Two red blocks never touch, so every block is a maximal run of red squares, with a grey square or the end of the row on each side. Conversely, every maximal red run of at least $3$ squares is one block. So a filling is the same thing as a red and grey colouring of the $n$ squares in which every maximal red run has at least $3$ squares. This is why mixing lengths causes no double counting: $\mathtt{RRRRRRR}$ is one block of $7$, not a block of $3$ next to a block of $4$, which would need a grey square between them, as in the statement's $\mathtt{RRRGRRRR}$.

For $n=7$ we can now list everything: the all-grey row; a single block of length $b$, which can start at $8-b$ places, giving $5+4+3+2+1=15$ rows for $b=3,\dots,7$; and two blocks, which fit only as $\mathtt{RRRGRRR}$. Together $1+15+1=17$, the number of the statement. The colourings also give the most direct method, checking all $2^n$ of them; it confirms every value below up to $n=22$, but fifty squares have $2^{50}\approx1.13\cdot10^{15}$ colourings, far too many to list.

3. Deciding the leftmost square

Every filling of a row of $n\ge1$ squares belongs to exactly one of three cases:

the leftmost square is grey, and the other $n-1$ squares form any filling: $W(n-1)$ fillings;
the row starts with a red block of length $b$, where $3\le b\le n-1$; the square after it cannot be red, since it would lengthen the block or start a block touching it, so it is grey, and the remaining $n-b-1$ squares form any filling: $W(n-b-1)$ fillings;
the whole row is one red block, $b=n$, with no separator: one filling, possible only when $n\ge3$.

The filling determines its leftmost square and, if that square is red, the length of its block, so the cases do not overlap. Conversely, a grey square, or a block and a grey square, put in front of any filling of the shorter row gives a legal filling, so nothing is missed; longer gaps are covered because the shorter row may start with grey squares. The last case looks like the middle one with a row of length $-1$ left over, so we set $W(-1)=1$, as if the separator stuck out beyond the end of the row. Then the three cases become one rule:

$$W(n)=W(n-1)+\sum_{b=3}^{n}W(n-b-1)\qquad(n\ge1).$$

For $n=1$ and $n=2$ the sum is empty. The rule works because after a complete block and its separator the rest is a fresh row, described by its length alone; placing red squares one at a time would also require remembering the length of the current red run. Solving each smaller problem once, from the smallest up, and storing the results in a table is called dynamic programming; ^[2] every entry is right by strong induction on $n$, since the rule only reads entries of shorter rows. A plain recursion without the table would make at least $W(n)$ calls, one ending in $W(0)$ or $W(-1)$ for every filling.

4. Worked example: the table up to seven squares

Starting from $W(-1)=W(0)=1$, the rule gives

$W(1)=W(0)=1$ and $W(2)=W(1)=1$;
$W(3)=W(2)+W(-1)=2$;
$W(4)=W(3)+W(0)$${}+W(-1)=4$;
$W(5)=W(4)+W(1)$${}+W(0)+W(-1)=7$;
$W(6)=W(5)+W(2)+W(1)$${}+W(0)+W(-1)=11$.

For seven squares the six terms of

$$W(7)=W(6)+W(3)+W(2)+W(1)+W(0)+W(-1)$$

are $11+2+1+1+1+1=17$, the value of the statement. They count the fillings that start with a grey square, with a block of $3$, $4$, $5$ or $6$ and its separator, and the single block of $7$. For example, the term $W(3)=2$ holds $\mathtt{RRRGGGG}$ and $\mathtt{RRRGRRR}$: a block of $3$, the separator, and one of the two fillings of three squares. Continuing gives $27, 44, 72, 117, 189$ for $n=8,\dots,12$.

5. A shorter recurrence

With $r=n-b-1$ the rule reads $W(n)=W(n-1)+\sum_{r=-1}^{n-4}W(r)$. From $n-1$ to $n$ the sum gains exactly one term, $W(n-4)$, so subtracting the rule for $n-1$ leaves $W(n)-W(n-1)$${}=W(n-1)-W(n-2)$${}+W(n-4)$, that is,

$$W(n)=2W(n-1)-W(n-2)+W(n-4)\qquad(n\ge3).$$

For example $W(8)=2\cdot17-11+4=27$. Each value now costs three operations. A rule in which every term is a fixed combination of the terms just before it is a linear recurrence with constant coefficients, here of order $4$. ^[6]

6. Counting by the number of blocks

A second count fixes the number $k\ge1$ of blocks. A filling with $k$ blocks is given by the block lengths $b_1,\dots,b_k\ge3$ and the lengths of the grey stretches, $g_0\ge0$ before the first block, $g_1,\dots,g_{k-1}\ge1$ between blocks and $g_k\ge0$ after the last one, which add up to $n$; the filling and these $2k+1$ numbers determine each other. Removing the compulsory squares, $3$ from every block and $1$ from every inner stretch, leaves $2k+1$ numbers that only have to be at least $0$, with the sum $n-3k-(k-1)=n+1-4k$. Such sums are counted by stars and bars: ^[3] to write $s$ as an ordered sum of $r$ numbers that are at least $0$, put $s$ stars and $r-1$ bars in a row and read off the numbers of stars between the bars, so that *|**| stands for $1+2+0$. Choosing which $r-1$ of the $s+r-1$ places hold bars gives $\binom{s+r-1}{r-1}$ sums, where the binomial coefficient $\binom ab$ is the number of ways to choose $b$ of $a$ places; for $s=r=3$ there are $\binom52=10$. With $s=n+1-4k$ and $r=2k+1$ there are $\binom{n+1-2k}{2k}$ fillings with $k$ blocks, and the same expression gives the all-grey filling for $k=0$. Hence

$$W(n)=\sum_{k\ge0}\binom{n+1-2k}{2k},$$

where the terms with $4k\gt n+1$ are $0$. For $n=7$ this is $\binom80+\binom62+\binom44=1+15+1=17$, the groups of Section 2. For $n=8$ it is $\binom90+\binom72+\binom54=1+21+5=27$: the five rows with two blocks, $\mathtt{GRRRGRRR}$, $\mathtt{RRRRGRRR}$, $\mathtt{RRRGGRRR}$, $\mathtt{RRRGRRRR}$ and $\mathtt{RRRGRRRG}$, add one square to $\mathtt{RRRGRRR}$ in each of its five parts.

7. Squares and dominoes

The same binomial coefficients count tilings. Cover a strip of $L$ cells with squares $\mathtt S$, covering one cell, and dominoes $\mathtt D$, covering two. A tiling with $j$ dominoes has $L-j$ tiles, and choosing which of them are dominoes gives $\binom{L-j}{j}$ tilings. All tilings together are counted by the Fibonacci numbers $F_0=0$, $F_1=1$, $F_{i+1}=F_i+F_{i-1}$, which run $0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55,\dots$: a strip of $L$ cells has $F_{L+1}$ tilings. Indeed, the empty strip and a single cell have one tiling each, as $F_1=F_2=1$, and for $L\ge2$ the first tile is a square followed by a tiling of $L-1$ cells or a domino followed by a tiling of $L-2$ cells, so the counts follow the Fibonacci rule. ^[4] By Section 6 with $L=n+1$, a row of $n$ squares has exactly as many fillings as a strip of $n+1$ cells has tilings with an even number $2k$ of dominoes.

A direct pairing shows why. Append a grey square to the row, so that every block is followed by one; replace each block of length $b$ and the grey square after it by a domino, $b-3$ squares and a domino, again $b+1$ cells, and every other grey square by a square. For any tiling with an even number of dominoes, pairing the dominoes in order, first with second, third with fourth, undoes this: a pair with $a$ squares inside gives a block of length $a+3$ and a grey square, every other square gives a grey square, and the appended cell, always grey, is dropped again. For $n=7$, the tilings $\mathtt{DDSSSS}$, $\mathtt{SSSDSD}$ and $\mathtt{DDDD}$ of eight cells give $\mathtt{RRRGGGG}$, $\mathtt{GGGRRRR}$ and $\mathtt{RRRGRRR}$.

8. Even against odd

Let $E(L)$ and $O(L)$ count the tilings of $L$ cells with an even and with an odd number of dominoes, so that $W(n)=E(n+1)$ and $E(L)+O(L)=F_{L+1}$. Their difference $s_L=E(L)-O(L)$ counts every tiling with the sign $+1$ or $-1$. Splitting by the first tile, a first square keeps the number of dominoes and a first domino adds one, which flips the sign, so

$$s_L=s_{L-1}-s_{L-2}\qquad(L\ge2),$$

with $s_0=s_1=1$, because the empty tiling and the single square have no domino. This gives $1, 1, 0, -1, -1, 0, 1, 1, 0,\dots$, which repeats with period $6$: applying the rule twice gives $s_{L+3}=s_{L+2}-s_{L+1}$${}=(s_{L+1}-s_L)-s_{L+1}=-s_L$, and doing that twice gives $s_{L+6}=s_L$. For $L=8$, $E(8)=1+15+1=17$ and $O(8)=\binom71+\binom53=7+10=17$, so $s_8=0=s_2$.

9. The closed form

Adding $E(L)+O(L)=F_{L+1}$ and $E(L)-O(L)=s_L$ gives $E(L)=\tfrac12\bigl(F_{L+1}+s_L\bigr)$, and with $L=n+1$

$$W(n)=\frac{F_{n+2}+s_{n+1}}{2}.$$

The correction $s_{n+1}$ is $1, 0, -1, -1, 0, 1$ when $n$ leaves the remainder $0, 1, 2, 3, 4, 5$ after division by $6$. A check against Section 4:

$n=0,\dots,3$: $\tfrac{1+1}2=1$, $\tfrac{2+0}2=1$, $\tfrac{3-1}2=1$ and $\tfrac{5-1}2=2$;
$n=4,\dots,7$: $\tfrac{8+0}2=4$, $\tfrac{13+1}2=7$, $\tfrac{21+1}2=11$ and $\tfrac{34+0}2=17$;
$n=8,\dots,12$: $\tfrac{55-1}2=27$, $\tfrac{89-1}2=44$, $\tfrac{144+0}2=72$, $\tfrac{233+1}2=117$ and $\tfrac{377+1}2=189$.

Since $W(n)$ is a whole number, $F_{n+2}$ must be even exactly when the correction is $0$, that is when $n+2$ is a multiple of $3$; indeed every third Fibonacci number is even. ^[4] The On-Line Encyclopedia of Integer Sequences lists $W(n)$, shifted by one place, as A005252, with this formula. ^[5]

10. Golden ratio, period six and a rounding trap

The recurrence of Section 5 predicts the shape of this formula. Putting $x^n$ in place of $W(n)$ and dividing by $x^{n-4}$ gives its characteristic polynomial, a difference of two squares:

$$x^4-2x^3+x^2-1=(x^2-x-1)(x^2-x+1).$$

The first factor has the roots $\varphi=(1+\sqrt5)/2\approx1.618$, the golden ratio, and $\psi=(1-\sqrt5)/2\approx-0.618$, which belong to the Fibonacci numbers; the second divides $x^3+1$, so its roots satisfy $x^6=1$. As the four roots are distinct, every solution is a combination of their $n$-th powers, ^[6] and Binet's formula $F_i=(\varphi^i-\psi^i)/\sqrt5$ ^[4] shows the three parts:

$$W(n)=\frac{\varphi^{n+2}}{2\sqrt5}+\frac{s_{n+1}}{2}-\frac{\psi^{n+2}}{2\sqrt5}.$$

Since $|\psi|\lt1$, the last term fades quickly, so $W(n)$ grows by about the factor $\varphi$ per square, as in $W(11)/W(10)=117/72=1.625$, and gains a decimal digit about every $1/\log_{10}\varphi\approx4.8$ squares. The Fibonacci numbers are the nearest integers to $\varphi^i/\sqrt5$, so it is tempting to round $\varphi^{n+2}/(2\sqrt5)$ to get $W(n)$. But the error $\tfrac12\bigl(s_{n+1}-\psi^{n+2}/\sqrt5\bigr)$ exceeds one half in size exactly when $s_{n+1}$ and $\psi^{n+2}$ have opposite signs, that is, when $n$ leaves the remainder $2$ after division by $3$: $\varphi^4/(2\sqrt5)\approx1.53$ rounds to $2$, but $W(2)=1$, and $\varphi^7/(2\sqrt5)\approx6.49$ rounds to $6$, but $W(5)=7$. The row of fifty squares is one of these cases.

11. Other minimum lengths

The leftmost square, the subtraction of Section 5 and stars and bars work for every minimum length; only the Fibonacci form of Sections 7 to 10 needs the number $3$. If every block needs at least $m$ squares, the leftmost square gives $W_m(n)=W_m(n-1)$${}+\sum_{b=m}^{n}W_m(n-b-1)$ with $W_m(-1)=W_m(0)=1$, and the subtraction of Section 5 gives

$$W_m(n)=2W_m(n-1)-W_m(n-2)+W_m(n-m-1)$$

for $n\ge m$. In stars and bars, $k$ blocks now leave $s=n+1-(m+1)k$ free squares, which must not be negative, so $k$ runs up to $K=\lfloor(n+1)/(m+1)\rfloor$, the largest number of blocks that fit with their separators, and

$$W_m(n)=\sum_{k=0}^{K}\binom{n+1-(m-1)k}{2k}.$$

For $m=1$ every colouring is allowed, and the sum indeed gives $2^n$. Problem 115 writes $F(m,n)$ for this count and gives $F(3,29)=673135$, $F(3,30)=1089155$, $F(10,56)=880711$ and $F(10,57)=1148904$; ^[7] the rule and the sum reproduce all four.

12. Pitfalls

Each of these slips already shows at $n=7$, where the count must be $17$:

letting blocks follow each other without a separator gives $21$: $\mathtt{RRRRRRR}$ is then counted as $7$, $3+4$ and $4+3$, and each of the two runs of six squares as $6$ and $3+3$;
forgetting the block that reaches the end of the row, the term $W(-1)$, gives $11$, the fillings that end with a grey square;
starting the table with $W(0)=0$, as if the empty row had no filling, gives $6$, the fillings that end with a red square, because every other filling ends in a call of $W(0)$.

How the Code Works

All three programs build the table of Section 4 with loops, without recursion. The C++ program ^[8] starts in main with an Options record: the row length $50$, the minimum block length $3$ and the checkpoint switch, which --length=, --min-block= and --skip-checkpoints change. parse_arguments compares each argument with --skip-checkpoints and otherwise hands it to parse_int_after_prefix, first with the prefix --length= and then with --min-block=. That function accepts only a nonempty string of decimal digits after the prefix and does not check its size, so a number too large for an int overflows, which is undefined behaviour: ^[9] in a test with Clang and GCC, --length=99999999999 was accepted as a length of about $1.2\cdot10^9$, the value modulo $2^{32}$, but nothing guarantees this. An unknown or malformed argument, such as --length=-5, is reported and ends the program with exit code $1$, and so, silently, does a parsed minimum below $2$. Then, unless the checkpoints are switched off, run_checkpoints compares count_ways(7, 3) with the statement's $17$, stopping with exit code $2$ on a mismatch, and the program prints count_ways for the chosen length and minimum.

count_ways(length, min_block) is the dynamic programme. It creates a vector dp of signed 64-bit integers, the type i64, for the lengths $0$ to length, with dp[0] = 1 for the empty row. For each n from $1$ up it starts with dp[n - 1], a grey first square, and loops over block from the minimum to n: a block that fills the rest of the row adds $1$, the term $W(-1)$, so the table needs no entry for the length $-1$, and a shorter block adds dp[n - block - 1], the fillings after the block and its separator. Every entry read has a smaller index and is already final. The last entry is returned.

The Python program does the same in solve, with $50$ and $3$ written into the code; range(3, n + 1) stops before n + 1, so it includes the block length n. ^[11] The Java program puts both loops on one line of main, with the conditional expression (b==n)?1:dp[n-b-1] and a long array. Neither has options or a check. Python's integers have unlimited precision, while C++ and Java use signed 64-bit integers, up to $2^{63}-1$. Every filling is a colouring, so $W(n)\le2^n$ and the length $50$ is safe, and every partial sum in the loop is at most the finished entry; in fact $W(91)\lt2^{63}\lt W(92)$. In a test, --length=92 made the C++ program print a negative number; signed overflow is undefined behaviour in C++, ^[9] so no result at all is guaranteed, and Java's long would overflow without any warning. ^[10]

Complexity and Verification

For a row of $n\ge1$ squares the inner loop runs over the block lengths $3,\dots,k$ for every $k\le n$, which makes $(n-1)(n-2)/2$ additions: $1176$ for $n=50$, plus $15$ for the check at $n=7$ when the C++ program runs it; with the minimum $m$ it makes $(n-m+1)(n-m+2)/2$ when $n\ge m$ and none when $n\lt m$. The time grows like $n^2$ and the memory, $n+1$ numbers, like $n$; for fifty squares the run is instantaneous. This counts an addition as one step and a number as one unit of memory, which is fair for 64-bit numbers; for huge $n$, Python's integers grow by about $0.69$ bits per square, so the table holds of the order of $n^2$ bits and the loop costs of the order of $n^3$ bit operations. Faster methods exist but are not needed: the recurrence of Section 5 costs a fixed number of operations per square and keeps four values, and the closed form needs one Fibonacci number, which powers of a $2\times2$ matrix or doubling identities give with a number of arithmetic operations proportional to $\log n$. ^[4] The number of colourings to check, $2^n$, doubles with every square.

Unless --skip-checkpoints is given, the C++ program checks $W(7)=17$ before it prints a count. For this article the methods were programmed separately. A brute force over all colourings matches the table for every $n\le22$; the recurrence of Section 5, the sum of Section 6 and the closed form of Section 9 match it for every $n\le130$, and at $n=50$ they match the number printed by all three published programs. The pairing of Section 7 was checked on every tiling of up to $16$ cells, the rounding claim of Section 10 for every $n\lt400$ with $300$ digits, and Section 11 for every $m\le7$ and $n\le60$, by brute force for $m\le4$ and $n\le14$. The C++ options give the table's values for every minimum from $2$ to $7$ and every length up to $40$, and the four values of Problem 115; built with the address and undefined-behaviour sanitizers, the program runs cleanly for the length $50$ and reports both overflows of the previous section. These finite checks back up the proofs, which hold for every length.

Footnotes and References

The references below supply the background facts; the recurrences, the two counts and the closed form are derived in this article.

Project Euler 114 — Counting Block Combinations I. The official statement: red blocks at least three units long are placed on a row, any two separated by at least one grey square; a row of seven units can be filled in exactly seventeen ways, block sizes may be mixed, and the task asks in how many ways a row of fifty units can be filled.
Wikipedia — Dynamic programming. Dynamic programming breaks a problem into simpler sub-problems and solves each of them only once; the bottom-up approach computes the smaller values first, as the page shows for the Fibonacci numbers.
Wikipedia — Stars and bars (combinatorics). Theorem two: there are C(n + k − 1, k − 1) k-tuples of non-negative integers with sum n. The page reduces positive variables to this case by subtracting 1 from each of them; Section 6 makes the same shift with the minimum 3 of a block and the minimum 1 of an inner grey stretch.
Wikipedia — Fibonacci sequence. F_n counts the sequences of 1s and 2s with sum n − 1, and every third Fibonacci number is even; the page gives Binet's formula with ψ = (1 − √5)/2, F_n as the nearest integer to φⁿ/√5, and matrix and doubling identities that need O(log n) arithmetic operations.
OEIS A005252. The sequence a(n) = Σ C(n − 2k, 2k), over 0 ≤ k ≤ n/4, begins 1, 1, 1, 1, 2, 4, 7, 11, 17, 27; a comment notes that a(n + 1) is the number of n-bit sequences whose 1s appear in groups of three or more, so W(n) = a(n + 1). The formulas include a(n) = 2a(n − 1) − a(n − 2) + a(n − 4) and a(n) = Fibonacci(n + 1)/2 + A010892(n)/2, where A010892 has period 6.
Wikipedia — Linear recurrence with constant coefficients. The order of such a recurrence is its longest time lag; when the characteristic polynomial has distinct roots, every solution is a combination of their powers, with coefficients fitted to the initial values.
Project Euler 115 — Counting Block Combinations II. With red blocks of length at least m, F(m, n) is the number of ways to fill a row of length n; the statement gives F(3, 29) = 673135, F(3, 30) = 1089155, F(10, 56) = 880711 and F(10, 57) = 1148904.
C++ — Euler114.cpp. The linked immutable revision contains count_ways, run_checkpoints and the option parsing described above. It is the implementation record for this article.
C++ working draft — [expr.pre]. Paragraph 4: evaluating an arithmetic expression whose mathematical result is not in the range of representable values for its type has undefined behaviour.
Java Language Specification — Chapter 4. Section 4.2.1 gives the range of long, and Section 4.2.2 states that the integer operators do not indicate overflow or underflow in any way.
Python — Built-in Types. Integers have unlimited precision; for a positive step, a range holds the values start + step·i that are less than stop, so stop itself is excluded.

Problem 114 source code

C++

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

namespace {

using i64 = std::int64_t;

struct Options {
    int length = 50;
    int min_block = 3;
    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) ||
            parse_int_after_prefix(arg, "--min-block=", options.min_block)) {
            continue;
        }

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

i64 count_ways(const int length, const int min_block) {
    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)];

        for (int block = min_block; block <= n; ++block) {
            if (block == n) {
                ways += 1;
            } else {
                ways += dp[static_cast<std::size_t>(n - block - 1)];
            }
        }

        dp[static_cast<std::size_t>(n)] = ways;
    }

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

bool run_checkpoints() {
    if (count_ways(7, 3) != 17) {
        std::cerr << "Checkpoint failed for length=7, min_block=3" << '\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 << count_ways(options.length, options.min_block) << '\n';
    return 0;
}

Python

# Problem 114: Counting block combinations I
# Row of 50 units, fill with red blocks (min length 3) separated by gaps.

def solve():
    length = 50
    dp = [0] * (length + 1)
    dp[0] = 1
    for n in range(1, length + 1):
        dp[n] = dp[n - 1]
        for block in range(3, n + 1):
            if block == n:
                dp[n] += 1
            else:
                dp[n] += dp[n - block - 1]
    print(dp[length])

solve()

Java

public class Euler114 {
    public static void main(String[] args) {
        int len=50; long[] dp=new long[len+1]; dp[0]=1;
        for(int n=1;n<=len;n++){dp[n]=dp[n-1];for(int b=3;b<=n;b++)dp[n]+=(b==n)?1:dp[n-b-1];}
        System.out.println(dp[len]);
    }
}