Project Euler

Freefarea

Let S = {A, E, F, R}. For n >= 0, let S^(n) denote the set of words of length n consisting of letters from S. The four keywords are: FREE, FARE, AREA, and REEF. Let f(n) be the number of words in S...

Source sync Apr 19, 2026

Problem #0679

Level Level 14

Solved By 1,100

Languages C++, Python

Answer 644997092988678

Length 397 words

dynamic_programminggeometrylinear_algebra

Let $S$ be the set consisting of the four letters $\{\texttt {`A'},\texttt {`E'},\texttt {`F'},\texttt {`R'}\}$.

For $n\ge 0$, let $S^*(n)$ denote the set of words of length $n$ consisting of letters belonging to $S$.

We designate the words $\texttt {FREE}, \texttt {FARE}, \texttt {AREA}, \texttt {REEF}$ as keywords.

Let $f(n)$ be the number of words in $S^*(n)$ that contains all four keywords exactly once.

This first happens for $n=9$, and indeed there is a unique 9 lettered word that contain each of the keywords once: $\texttt {FREEFAREA}$

So, $f(9)=1$.

You are also given that $f(15)=72863$.

Find $f(30)$.

Problem 679: Freefarea

Mathematical Analysis

Approach: Aho-Corasick Automaton + Dynamic Programming

This is a classic string combinatorics problem that can be solved by combining the Aho-Corasick multi-pattern matching automaton with dynamic programming.

Key Idea: Build an Aho-Corasick automaton from the four keywords. The automaton tracks partial matches of all keywords simultaneously. We augment the DP state with a bitmask recording which keywords have been fully matched.

State Space

Automaton node $v$ : encodes the longest suffix of the current string that is a prefix of some keyword. The trie has approximately 13 nodes.
Bitmask $m \in \{0, 1, \ldots, 15\}$ : bit $i$ is set if keyword $i$ has been seen exactly once.

A transition on character $c$ from state $(v, m)$ :

Compute the new automaton node $v' = \delta(v, c)$ .
Check the output function $\text{out}(v')$ — a bitmask of keywords ending at $v'$ .
If $\text{out}(v') \cap m \ne \emptyset$ , discard this transition (a keyword would appear twice).
Otherwise, transition to $(v', m \cup \text{out}(v'))$ .

Final Count

f(n) = \sum_{\substack{v \\ m = 15}} \text{dp}[v][m]

where the sum is over all automaton nodes $v$ with all four keywords matched.

Editorial

Project Euler 679: Freefarea Count words of length n over {A, E, F, R} containing each of FREE, FARE, AREA, REEF exactly once. We use a DFA-based DP approach. Track: Since we need exactly one occurrence of each, we track a bitmask of which keywords have appeared, and reject any state where a keyword appears a second time. Keywords: FREE, FARE, AREA, REEF Alphabet: {A, E, F, R} We use Aho-Corasick automaton to track all four patterns simultaneously. We build the Aho-Corasick trie from the four keywords. We then compute failure links and output functions via BFS. Finally, run DP for $n = 30$ steps, transitioning through all 4 characters at each step.

Pseudocode

Build the Aho-Corasick trie from the four keywords
Compute failure links and output functions via BFS
Run DP for $n = 30$ steps, transitioning through all 4 characters at each step
Sum counts over all states with mask $= 15$

Correctness

Theorem. The method described above computes exactly the quantity requested in the problem statement.

Proof. The preceding analysis identifies the admissible objects and derives the formula, recurrence, or exhaustive search carried out by the algorithm. The computation evaluates exactly that specification, so every valid contribution is included once and no invalid contribution is counted. Therefore the returned value is the required answer. $\square$

Complexity Analysis

States: $O(|V| \cdot 2^4) = O(13 \cdot 16) = O(208)$ states.
Transitions per state: 4 characters.
Steps: 30.
Total: $O(30 \cdot 208 \cdot 4) = O(24960)$ operations.

Answer

\boxed{644997092988678}

C++ project_euler/problem_679/solution.cpp

#include <bits/stdc++.h>
using namespace std;

// Aho-Corasick automaton for multiple pattern matching
struct AhoCorasick {
    vector<map<char, int>> go;
    vector<int> fail, out;

    AhoCorasick() {
        go.push_back({});
        fail.push_back(0);
        out.push_back(0);
    }

    void addPattern(const string& s, int idx) {
        int cur = 0;
        for (char ch : s) {
            if (go[cur].find(ch) == go[cur].end()) {
                go[cur][ch] = go.size();
                go.push_back({});
                fail.push_back(0);
                out.push_back(0);
            }
            cur = go[cur][ch];
        }
        out[cur] |= (1 << idx);
    }

    void build(const string& alpha) {
        queue<int> q;
        for (char ch : alpha) {
            if (go[0].count(ch)) {
                fail[go[0][ch]] = 0;
                q.push(go[0][ch]);
            } else {
                go[0][ch] = 0;
            }
        }
        while (!q.empty()) {
            int r = q.front(); q.pop();
            for (char ch : alpha) {
                if (go[r].count(ch)) {
                    int s = go[r][ch];
                    q.push(s);
                    int st = fail[r];
                    while (st && !go[st].count(ch)) st = fail[st];
                    fail[s] = go[st].count(ch) ? go[st][ch] : 0;
                    if (fail[s] == s) fail[s] = 0;
                    out[s] |= out[fail[s]];
                } else {
                    int st = fail[r];
                    while (st && !go[st].count(ch)) st = fail[st];
                    go[r][ch] = go[st].count(ch) ? go[st][ch] : 0;
                }
            }
        }
    }
};

int main() {
    vector<string> keywords = {"FREE", "FARE", "AREA", "REEF"};
    string alpha = "AEFR";
    int N = 30;

    AhoCorasick ac;
    for (int i = 0; i < 4; i++) ac.addPattern(keywords[i], i);
    ac.build(alpha);

    int numNodes = ac.go.size();

    // dp[node][mask] = count
    map<pair<int,int>, long long> dp;
    dp[{0, 0}] = 1;

    for (int step = 0; step < N; step++) {
        map<pair<int,int>, long long> ndp;
        for (auto& [state, cnt] : dp) {
            auto [node, mask] = state;
            for (char ch : alpha) {
                int nn = ac.go[node][ch];
                int no = ac.out[nn];
                if (no & mask) continue; // keyword seen twice
                int nm = mask | no;
                ndp[{nn, nm}] += cnt;
            }
        }
        dp = ndp;
    }

    long long ans = 0;
    for (auto& [state, cnt] : dp) {
        if (state.second == 15) ans += cnt;
    }

    cout << ans << endl;
    return 0;
}

Python project_euler/problem_679/solution.py

"""
Project Euler 679: Freefarea

Count words of length n over {A, E, F, R} containing each of FREE, FARE, AREA, REEF exactly once.

We use a DFA-based DP approach. Track:
- Which of the 4 keywords have been completed (bitmask 0-15)
- The current suffix state for partial matches of each keyword
- The count of each keyword that has been completed

Since we need exactly one occurrence of each, we track a bitmask of which keywords
have appeared, and reject any state where a keyword appears a second time.

Keywords: FREE, FARE, AREA, REEF
Alphabet: {A, E, F, R}

We use Aho-Corasick automaton to track all four patterns simultaneously.
"""

from collections import deque

def solve():
    keywords = ["FREE", "FARE", "AREA", "REEF"]
    alphabet = ['A', 'E', 'F', 'R']

    # Build Aho-Corasick automaton
    # Each node: dict of children, failure link, output (set of keyword indices)
    goto = [{}]  # goto function
    fail = [0]   # failure function
    output = [0] # bitmask of keywords ending at this node

    # Build trie
    for ki, kw in enumerate(keywords):
        cur = 0
        for ch in kw:
            if ch not in goto[cur]:
                goto[cur][ch] = len(goto)
                goto.append({})
                fail.append(0)
                output.append(0)
            cur = goto[cur][ch]
        output[cur] |= (1 << ki)

    # Build failure links using BFS
    queue = deque()
    for ch in alphabet:
        if ch in goto[0]:
            s = goto[0][ch]
            fail[s] = 0
            queue.append(s)
        else:
            goto[0][ch] = 0  # loop back to root

    while queue:
        r = queue.popleft()
        for ch in alphabet:
            if ch in goto[r]:
                s = goto[r][ch]
                queue.append(s)
                state = fail[r]
                while state != 0 and ch not in goto[state]:
                    state = fail[state]
                fail[s] = goto[state].get(ch, 0)
                if fail[s] == s:
                    fail[s] = 0
                output[s] |= output[fail[s]]
            else:
                # Create goto for missing transitions
                state = fail[r]
                while state != 0 and ch not in goto[state]:
                    state = fail[state]
                goto[r][ch] = goto[state].get(ch, 0)

    num_nodes = len(goto)

    # DP state: (aho_node, keyword_bitmask)
    # keyword_bitmask tracks which keywords have been seen exactly once
    # If a keyword is seen twice, that state is invalid (discard)

    # For "exactly once", we need to handle overlapping matches carefully.
    # When we enter a state that outputs keyword k:
    # - If k is already in the bitmask, this path is invalid (more than once)
    # - Otherwise, add k to bitmask

    # But we also need to track if we're about to complete a keyword for the second time.
    # The Aho-Corasick output tells us which keywords end at each position.
    # However, for "exactly once" we need: each keyword appears as a substring exactly once.

    # State: (node, seen_mask) where seen_mask is a 4-bit mask
    # We need to count strings where at end, seen_mask = 15 (all 4 keywords seen)
    # and no keyword was seen more than once.

    # To track "more than once": if at any step we would add a keyword already in seen_mask,
    # that string is invalid. We mark it with a special "dead" state or simply don't count it.

    # But there's a subtlety: a keyword might be detected at multiple positions.
    # We need to count strings where each keyword occurs as a substring exactly once.
    # The Aho-Corasick approach detects every occurrence, so if a keyword appears twice,
    # we'll see it twice in the output, and we can discard that path.

    # DP: dp[node][mask] = number of strings
    # Transition: for each character, compute new_node, check output of new_node,
    # if any keyword in output is already in mask -> dead state
    # otherwise, mask |= output

    N = 30

    # Initialize: dp[0][0] = 1
    dp = {}
    dp[(0, 0)] = 1

    for step in range(N):
        new_dp = {}
        for (node, mask), count in dp.items():
            for ch in alphabet:
                new_node = goto[node][ch]
                new_out = output[new_node]

                # Check if any keyword in new_out is already in mask
                if new_out & mask:
                    continue  # This would mean a keyword appears more than once

                new_mask = mask | new_out
                key = (new_node, new_mask)
                new_dp[key] = new_dp.get(key, 0) + count

        dp = new_dp

    # Sum all states where mask == 15 (all 4 keywords seen)
    result = sum(count for (node, mask), count in dp.items() if mask == 15)
    print(result)

solve()