Problem 208: Robot Walks

Project Euler Problem 208 Solution

EulerSolve provides an optimized solution for Project Euler Problem 208, Robot Walks, with C++, Python, Java, and a step-by-step mathematical explanation.

Problem Summary The robot starts at the origin, facing north, and makes $70$ moves. Each move is a circular arc of angle $72^\circ$: at every step the robot turns either clockwise or anticlockwise, so the heading changes by $\pm72^\circ$ and the endpoint shifts by the chord of that arc. The task is to count how many turn sequences produce a closed walk. A brute-force search would inspect all $2^{70}$ instruction strings, so the real problem is to encode the geometry in a form that can be counted exactly. Mathematical Approach The implementations avoid floating-point trigonometry entirely. The walk is rewritten as exact arithmetic in a five-dimensional integer state, and then a layered dynamic program counts how many sequences reach each state. Encoding a $72^\circ$ arc as an algebraic step Let $$\lambda=e^{i\pi/5}.$$ Then $\lambda^{10}=1$ and $\lambda^5=-1$. The endpoint displacement of one $72^\circ$ arc has a fixed length $2\sin(\pi/5)$, so for closure counting we may divide every displacement by that common nonzero factor. After this normalization, an anticlockwise arc contributes $\lambda$ in the current frame, while a clockwise arc contributes $\lambda^{-1}$. Rotating the heading by $\pm72^\circ$ multiplies future directions by $\lambda^{\pm2}$, because $72^\circ=2\cdot36^\circ$....

Detailed mathematical approach

Problem Summary

A robot drives along circular arcs of one common radius. Each arc is one fifth of a circle, so it turns the robot through $72^\circ$, and for every arc the robot chooses freely between clockwise and anticlockwise; it never turns on the spot. Starting facing north, we must count the journeys of $70$ arcs after which the robot is back at its starting point; only the position counts, not the final heading, and arcs may be traversed repeatedly. The statement says that $70932$ closed journeys of $25$ arcs start northward. ^[1]

The whole solution in one sentence: once every arc is replaced by its straight chord, the robot's position, measured in axes that turn with the robot, is given exactly by five integers, and we count, arc after arc, how many journeys lead to each such five-tuple, keeping at the end the tuples that describe the starting point.

Mathematical Approach

We turn the arcs into straight steps, describe a journey by five integers and count with them.

1. An arc ends where its chord ends

Let an arc of radius $r$ run from $A$ to $B$ around the centre $O$. The triangle $OAB$ is isosceles with the angle $72^\circ$ at $O$, so its angles at $A$ and $B$ are $54^\circ$. At $A$ the robot moves along the tangent, which is perpendicular to $OA$, so the chord $AB$ points $90^\circ-54^\circ=36^\circ$ away from the heading, towards the side of the turn. Its length is $d=2r\sin36^\circ$ for every arc, ^[2] and at $B$ the heading has turned through $72^\circ$. Only the end points of the arcs matter, so a clockwise arc acts as a straight step of length $d$ in the direction $36^\circ$ clockwise from the heading, together with a clockwise turn of $72^\circ$; an anticlockwise arc is the mirror image. Different choice sequences give different paths, since at their first difference the two arcs bend to opposite sides.

2. Five headings and five directions

We measure directions by their bearing, the angle turned clockwise from north. The robot starts with the bearing $0^\circ$, and every arc changes it by $72^\circ$ one way or the other, so only five headings occur: $0^\circ$, $72^\circ$, $144^\circ$, $216^\circ$ and $288^\circ$. Think of them as the corners of a pentagon; every arc moves the heading to a neighbouring corner. By Section 1 the chord points exactly halfway between the headings before and after the arc, so its direction depends only on the side of the pentagon that is crossed, and only five chord directions occur: $36^\circ$, $108^\circ$, $180^\circ$, $252^\circ$ and $324^\circ$.

3. The smallest closed journeys

Write $\mathtt C$ for a clockwise arc and $\mathtt A$ for an anticlockwise one. Arcs that turn the same way stay on the same circle, so $\mathtt{CCCCC}$ runs once around a circle and returns to the start, using each chord direction once; $\mathtt{AAAAA}$ does the same on the circle to the left. For $10$ arcs there are $12$ closed journeys: the double circles $\mathtt C^{10}$ and $\mathtt A^{10}$, and ten figure eights $\mathtt C^j\mathtt A^5\mathtt C^{5-j}$ and $\mathtt A^j\mathtt C^5\mathtt A^{5-j}$ with $0\le j\le4$, in which the robot leaves its circle after $j$ arcs, runs once around the touching circle on the other side and then completes the first circle. A search through all $2^n$ journeys of $n\le25$ arcs finds

no closed journey at all when $n$ is not a multiple of $5$;
$2$, $12$, $188$, $3400$ and $70932$ closed journeys for $n=5,10,15,20,25$, the last as in the statement.

Each of these closed journeys uses the five chord directions equally often; Sections 4 to 8 explain why.

4. Directions as complex numbers

We describe a point of the floor by the complex number $x+iy$, where $x$ and $y$ are its signed distances north and east of the start. The direction with bearing $\beta$ is then $e^{i\beta}=\cos\beta+i\sin\beta$, and since multiplication by $i$ turns north into east, multiplication by $e^{i\varphi}$ turns a direction clockwise through the angle $\varphi$. Let

$$\lambda=e^{i\pi/5},\qquad\lambda^5=-1,\qquad\lambda^{10}=1,$$

so that multiplication by $\lambda$ is a clockwise turn through $36^\circ$. Let $p_t$ be the position and $h_t$ the heading after $t$ arcs, with $p_0=0$ and $h_0=1$, which is north. By Section 1,

an arc $\mathtt C$ gives $p_{t+1}=p_t+d\lambda h_t$ and $h_{t+1}=\lambda^2h_t$;
an arc $\mathtt A$ gives $p_{t+1}=p_t+d\lambda^{-1}h_t$ and $h_{t+1}=\lambda^{-2}h_t$.

So the headings are even powers of $\lambda$, and the chords point along odd powers.

5. Looking from the robot

The programs never store the heading. Instead they store the robot's displacement from the start in axes that turn with the robot, so that the current heading always points north, measured in units of $d$:

$$w_t=\frac{p_t}{d\,h_t}.$$

Inserting the rules of Section 4, an arc $\mathtt C$ gives

$$w_{t+1}=\frac{p_t+d\lambda h_t}{d\lambda^2h_t}=\lambda^{-2}w_t+\lambda^{-1},$$

and in the same way an arc $\mathtt A$ gives $w_{t+1}=\lambda^2w_t+\lambda$. The heading has disappeared: the new value depends only on the old one and on the turn, and the journey is closed exactly when $w_n=0$, that is, when $p_n=0$.

6. Five integers per position

Starting from $w_0=0$, every $w_t$ is a sum of powers of $\lambda$ with integer coefficients, and $\lambda^5=-1$ brings every power down to one of $1,\lambda,\dots,\lambda^4$. The programs therefore store the five integers $s=(s_0,\dots,s_4)$ in

$$w_t=s_0+s_1\lambda+s_2\lambda^2+s_3\lambda^3+s_4\lambda^4.$$

Multiplying by $\lambda^{-2}$ moves every coefficient two places down, and the two lowest ones wrap around to the top with a change of sign, because $\lambda^{-2}=-\lambda^3$ and $\lambda^{-1}=-\lambda^4$; adding $\lambda^{-1}=-\lambda^4$ then subtracts $1$ from the last coefficient. Multiplying by $\lambda^2$ moves the coefficients two places up, with $\lambda^5=-1$ and $\lambda^6=-\lambda$, and adding $\lambda$ adds $1$ to the coefficient of $\lambda$. So the two arcs act on the tuple by

$$\begin{aligned}\mathtt C&:\ s\mapsto(s_2,\,s_3,\,s_4,\,-s_0,\,-s_1-1),\\ \mathtt A&:\ s\mapsto(-s_3,\,-s_4+1,\,s_0,\,s_1,\,s_2),\end{aligned}$$

which are exactly the two transitions in all three programs. Only integers are added and negated, so nothing is ever rounded.

7. What the five integers count

Seen from the current heading, every chord driven so far points along one of the directions $\lambda^e$ with odd $e$, an odd power divided by an even one, that is $36e^\circ$ clockwise from the heading: $36^\circ$ or $108^\circ$ to the right, straight back, or $108^\circ$ or $36^\circ$ to the left. If $c_e$ chords point along $\lambda^e$, then

$$(s_0,s_1,s_2,s_3,s_4)=(-c_5,\,c_1,\,-c_7,\,c_3,\,-c_9).$$

This holds at the start, where everything is $0$, and it survives every arc. After an arc $\mathtt C$, for example, every old chord is seen $72^\circ$ further anticlockwise, and the new chord points $36^\circ$ to the left, so the new counts in the directions $\lambda,\lambda^3,\lambda^5,\lambda^7,\lambda^9$ are $c_3,c_5,c_7,c_9$ and $c_1+1$. The formula turns them into $(-c_7,c_3,-c_9,c_5,-c_1-1)$, which is what the map $\mathtt C$ of Section 6 produces; the check for $\mathtt A$ is the same. Hence $|s_0|+\dots+|s_4|=t$ after $t$ arcs, every coordinate lies between $-t$ and $t$, and layer $t$ holds at most $\binom{t+4}{4}$ tuples, the number of ways to write $t$ as an ordered sum of five non-negative integers: choose the places of four separators among $t+4$ places in a row and fill the others with $t$ marks (stars and bars). ^[3]

8. The closing test

The starting point is described not only by the zero tuple, because

$$1-\lambda+\lambda^2-\lambda^3+\lambda^4=\frac{1+\lambda^5}{1+\lambda}=0.$$

There is no other relation: if integers $s_0,\dots,s_4$ satisfy $s_0+s_1\lambda+\dots+s_4\lambda^4=0$, then $(s_0,\dots,s_4)=s_4\,(1,-1,1,-1,1)$. Indeed, $\lambda$ is a primitive tenth root of unity, so its minimal polynomial over the rationals, the monic polynomial of least degree with the root $\lambda$, is the cyclotomic polynomial $\Phi_{10}(x)=x^4-x^3+x^2-x+1$ of degree $4$. ^[4] With $S(x)=s_0+s_1x+\dots+s_4x^4$, the polynomial $R=S-s_4\Phi_{10}$ has rational coefficients, degree at most $3$ and the root $\lambda$, so $R=0$ by the minimality of the degree.

Consequently $w_t=0$ exactly when $s_0=-s_1$, $s_2=-s_1$, $s_3=s_1$ and $s_4=-s_1$; the programs test this as $s_1+s_4=0$, $s_2+s_3=0$, $s_1+s_2=0$ and $s_0+s_1=0$. By Section 7 the condition says $c_1=c_3=c_5=c_7=c_9$: a journey is closed exactly when it uses each of the five chord directions equally often, seen from the robot or from the floor, which only renames the directions. This explains the search of Section 3: a closed journey has a multiple of $5$ arcs, and one of $70$ arcs uses each direction $14$ times, so after $70$ arcs the only tuple that passes the test is $(-14,14,-14,14,-14)$.

9. A worked example

Five clockwise arcs take the tuple through

$$\begin{aligned}(0,0,0,0,0)&\to(0,0,0,0,-1)\\&\to(0,0,-1,0,-1)\to(-1,0,-1,0,-1)\\&\to(-1,0,-1,1,-1)\to(-1,1,-1,1,-1).\end{aligned}$$

Each arc moves every earlier chord $72^\circ$ further anticlockwise, as seen from the robot, and adds a new chord at $36^\circ$ on the left, so after five arcs every relative direction holds one chord and the closing test holds with $s_1=1$. The journeys $\mathtt{CAAC}$ and $\mathtt{ACCA}$ both end with $(0,2,0,0,-2)$, two chords $36^\circ$ to the right of north and two $36^\circ$ to the left: they end at the same point facing north, and the programs keep them as one tuple with the count $2$. This is the first such merge: after $t=1,\dots,5$ arcs there are $2$, $4$, $8$, $15$ and $27$ tuples instead of $2^t$.

10. Counting layer by layer

Let $N_t(s)$ be the number of journeys of $t$ arcs that end with the tuple $s$. A journey of $t+1$ arcs is a journey of $t$ arcs followed by $\mathtt C$ or $\mathtt A$, and its tuple is the image of the old one under the map of Section 6. Hence, starting from $N_0(0,0,0,0,0)=1$,

$$N_{t+1}(s')=\sum_{T(s)=s'}N_t(s),$$

summed over both maps $T$ and all tuples $s$ of layer $t$ with $T(s)=s'$. The number of closed journeys of $n$ arcs is the sum of $N_n(s)$ over the tuples that pass the closing test. This is dynamic programming: ^[5] journeys that share a tuple share all their futures, so they are counted together. No layer holds more than $357174$ tuples, while there are $2^{70}\approx1.2\times10^{21}$ journeys of $70$ arcs.

11. A closed formula as a check

For $n=5k$ with $k\ge1$ there is also a formula. Call the heading $72j^\circ$ corner $j$, and let the side from corner $j$ to corner $j+1$, modulo $5$, be crossed $a_j$ times clockwise and $b_j$ times anticlockwise; by Sections 2 and 8, $a_j+b_j=k$. The heading leaves corner $j$ exactly $a_j+b_{j-1}$ times and arrives $a_{j-1}+b_j$ times. The difference, $(a_j-b_j)-(a_{j-1}-b_{j-1})$, is $0$ except at the first and the last corner, where it would be $1$ and $-1$ if these were different; but it is even, because every $a_j-b_j$ has the parity of $k$. So every closed journey ends facing north, all differences vanish, and $a_j=a$, $b_j=b=k-a$ for all sides. Now give the crossings of each side distinct labels. A labelled closed journey is an Eulerian circuit, a closed walk that uses every labelled arc exactly once, in a connected directed multigraph in which every corner has $k$ arcs out and $k$ in. With a fixed first arc leaving corner $0$, the BEST theorem ^[6] gives $t_0((k-1)!)^5$ such circuits, where $t_0$ counts the spanning trees directed towards corner $0$: each other corner picks one outgoing arc, so that following them always leads to corner $0$. Such a tree omits one side, say the one from corner $m$ to $m+1$; then the corners $1,\dots,m$ point anticlockwise and the others clockwise, through one of $b$ or $a$ parallel arcs, so $t_0=a^4+a^3b+a^2b^2+ab^3+b^4$. There are $k$ choices for the first arc, and every journey has exactly $(a!\,b!)^5$ labellings, because on each side the labels can be permuted among the $a$ clockwise and among the $b$ anticlockwise crossings. Since $k((k-1)!)^5=(k!)^5/k^4$, summing over $a$ gives

$$N(k)=\sum_{a+b=k}\binom{k}{a}^{5}\,\frac{a^4+a^3b+a^2b^2+ab^3+b^4}{k^4}.$$

For $k=5$ its six terms are $1$, $1705$, $33760$, $33760$, $1705$ and $1$, which add up to the $70932$ of the statement.

How the Code Works

The C++ program ^[7] stores a tuple as State, a std::array of five long long integers, and the counts as unsigned 64-bit integers u64. parse_arguments accepts --steps=N for another length and --skip-checkpoints; by default it counts journeys of $70$ arcs. solve(steps) keeps two ordered maps from tuples to counts, current and next, and starts with the zero tuple and the count $1$. In every round it clears next, computes for each entry of current the tuples clockwise and anticlockwise by the maps of Section 6, and adds the entry's count to both with next[...] += count, where the operator [] first inserts a missing tuple with the count $0$. ^[8] Then current.swap(next) makes it the new layer without copying. Finally is_closed applies the four equations of Section 8 and the counts of the tuples that pass are added up; for $70$ arcs this is the single tuple $(-14,14,-14,14,-14)$. Before the main run, run_checkpoints requires solve(25) to return $70932$, and the program stops with exit code $2$ otherwise.

The Python version does the same with a dictionary keyed by tuples and with unbounded integers, but without the checkpoint. The Java version packs each tuple into one long: encodeState adds $70$ to every coordinate and reads the results as digits of a base-$141$ number, which is valid because $|s_i|\le t\le70$ by Section 7, and decodeState unpacks it; the counts live in a HashMap<Long, Long> and are added with merge(..., Long::sum). No count of any tuple in any layer reaches $2^{59}$, so neither the u64 of C++ nor the signed long of Java can overflow.

Complexity and Verification

By Section 7 layer $t$ holds at most $\binom{t+4}{4}$ tuples, so $n$ arcs cost $O(n^5)$ map updates in total and $O(n^4)$ map entries for the two layers. An update costs $O(\log S)$ comparisons in a C++ std::map with $S$ entries, ^[8] which gives $O(n^5\log n)$ time for C++, and expected constant time in the hash tables of Python and Java. For $n=70$ the main computation expands the $4\,948\,057$ tuples of the layers $t=0,\dots,69$ and makes $9\,896\,114$ map updates, and the C++ checkpoint adds $67\,400$ more; the largest layer, after $70$ arcs, has $357\,174$ tuples, about a third of the bound $\binom{74}{4}=1\,150\,626$. On a current desktop computer each program finishes in about two seconds or less.

Checks run for this article, of which only the first is part of the published solutions:

the C++ program checks the value $70932$ for $25$ arcs before every run without --skip-checkpoints;
a floating-point brute force with unit radius over all $2^n$ journeys with $n\le25$, turning the robot about the centre of each real arc, finds the counts of Section 3: closed endpoints lie within $10^{-13}$ of the start and all others more than $0.1$ away, so its tolerance $10^{-7}$ is safe, and every closed journey ends facing north and uses each chord direction equally often;
the formula of Section 11 agrees with the dynamic program for every $1\le k\le14$, that is, for every positive multiple of $5$ up to $70$, and the C++, Python and Java programs print the same number;
every tuple of all $70$ layers has the sign pattern of Section 7 and $|s_0|+\dots+|s_4|=t$.

Footnotes and References

The references below supply the background facts; the chord description, the meaning of the five integers, the closing test and the closed formula are derived in this article.

Project Euler 208 — Robot Walks. The official statement: a robot moves in one-fifth circular arcs, clockwise or anticlockwise at every step and never turning on the spot; the page mentions the 70932 closed paths of 25 arcs that start northward and asks how many journeys of 70 arcs, starting northward, end where they started.
Wikipedia — Chord (geometry). A chord that subtends the central angle θ in a circle of radius r has length 2r sin(θ/2).
Wikipedia — Stars and bars (combinatorics). Theorem two: there are C(n + k − 1, k − 1) k-tuples of non-negative integers with the sum n.
Wikipedia — Cyclotomic polynomial. The n-th cyclotomic polynomial is irreducible over the rationals and is the minimal polynomial of every primitive n-th root of unity; the article lists Φ₁₀(x) = x⁴ − x³ + x² − x + 1.
Wikipedia — Dynamic programming. A complicated problem is broken down into simpler subproblems, each solved once; bottom-up, the results of the smaller subproblems build those of the larger ones.
Wikipedia — BEST theorem. The number of Eulerian circuits of a connected Eulerian directed graph is t_w(G) ∏ (deg(v) − 1)!, where t_w(G) counts the arborescences, trees directed towards a fixed root w.
C++ — Euler208.cpp. The linked immutable C++ revision contains solve, is_closed and run_checkpoints. It is the implementation record for this article.
cppreference — std::map::operator[]. For a missing key the operator inserts a value-initialized mapped value, zero for an integer, and returns a reference to it; its complexity is logarithmic in the size of the map.

Problem 208 source code

C++

#include <array>
#include <cstdint>
#include <iostream>
#include <map>
#include <string>

namespace {

using i64 = long long;
using u64 = std::uint64_t;
using State = std::array<i64, 5>;

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

        std::cerr << "Unknown argument: " << arg << '\n';
        return false;
    }

    return options.steps >= 0;
}

bool is_closed(const State& s) {
    return s[1] + s[4] == 0 &&
           s[2] + s[3] == 0 &&
           s[1] + s[2] == 0 &&
           s[0] + s[1] == 0;
}

u64 solve(const int steps) {
    std::map<State, u64> current;
    std::map<State, u64> next;
    current[{0, 0, 0, 0, 0}] = 1;

    for (int round = 0; round < steps; ++round) {
        next.clear();

        for (const auto& entry : current) {
            const State& s = entry.first;
            const u64 count = entry.second;

            const State clockwise = {s[2], s[3], s[4], -s[0], -s[1] - 1};
            const State anticlockwise = {-s[3], -s[4] + 1, s[0], s[1], s[2]};

            next[clockwise] += count;
            next[anticlockwise] += count;
        }

        current.swap(next);
    }

    u64 answer = 0;
    for (const auto& entry : current) {
        if (is_closed(entry.first)) {
            answer += entry.second;
        }
    }
    return answer;
}

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

Python

# Problem 208: Robot Walks
# Robot makes 70 steps, each 1/5 of a circle, clockwise or anticlockwise.
# Count paths that return to start.

def solve():
    steps = 70
    # State = tuple of 5 values tracking cumulative position in each direction
    # Transitions: clockwise rotates state and decrements, anticlockwise rotates and increments
    current = {(0,0,0,0,0): 1}
    for _ in range(steps):
        nxt = {}
        for state, count in current.items():
            s = state
            # Clockwise: new_state = (s[2], s[3], s[4], -s[0], -s[1]-1)
            cw = (s[2], s[3], s[4], -s[0], -s[1]-1)
            nxt[cw] = nxt.get(cw, 0) + count
            # Anticlockwise: new_state = (-s[3], -s[4]+1, s[0], s[1], s[2])
            acw = (-s[3], -s[4]+1, s[0], s[1], s[2])
            nxt[acw] = nxt.get(acw, 0) + count
        current = nxt

    # is_closed: s[1]+s[4]==0 and s[2]+s[3]==0 and s[1]+s[2]==0 and s[0]+s[1]==0
    ans = 0
    for s, cnt in current.items():
        if s[1]+s[4]==0 and s[2]+s[3]==0 and s[1]+s[2]==0 and s[0]+s[1]==0:
            ans += cnt
    print(ans)

solve()

Java

import java.util.HashMap;
import java.util.Map;

public class Euler208 {
    public static void main(String[] args) {
        int steps = 70;
        Map<Long, Long> current = new HashMap<>();
        current.put(encodeState(0, 0, 0, 0, 0), 1L);
        for (int round = 0; round < steps; round++) {
            Map<Long, Long> next = new HashMap<>();
            for (var entry : current.entrySet()) {
                long key = entry.getKey();
                long count = entry.getValue();
                long[] s = decodeState(key);
                // Clockwise
                long cw = encodeState(s[2], s[3], s[4], -s[0], -s[1] - 1);
                next.merge(cw, count, Long::sum);
                // Anticlockwise
                long acw = encodeState(-s[3], -s[4] + 1, s[0], s[1], s[2]);
                next.merge(acw, count, Long::sum);
            }
            current = next;
        }
        long ans = 0;
        for (var entry : current.entrySet()) {
            long[] s = decodeState(entry.getKey());
            if (isClosed(s))
                ans += entry.getValue();
        }
        System.out.println(ans);
    }

    static boolean isClosed(long[] s) {
        return s[1] + s[4] == 0 && s[2] + s[3] == 0 && s[1] + s[2] == 0 && s[0] + s[1] == 0;
    }

    static long encodeState(long a, long b, long c, long d, long e) {
        return ((a + 70) * 141 * 141 * 141 * 141) + ((b + 70) * 141 * 141 * 141) + ((c + 70) * 141 * 141)
                + ((d + 70) * 141) + (e + 70);
    }

    static long[] decodeState(long key) {
        long e = key % 141 - 70;
        key /= 141;
        long d = key % 141 - 70;
        key /= 141;
        long c = key % 141 - 70;
        key /= 141;
        long b = key % 141 - 70;
        key /= 141;
        long a = key - 70;
        return new long[] { a, b, c, d, e };
    }
}