#include <iostream>
#pragma mark - Tape
constexpr int Blank = -1;
template<int... xs>
class Tape {
public:
using type = Tape<xs...>;
constexpr static int length = sizeof...(xs);
};
#pragma mark - Print
template<class T>
void print(T);
template<>
void print(Tape<>) {
std::cout << std::endl;
}
template<int x, int... xs>
void print(Tape<x, xs...>) {
if (x == Blank) {
std::cout << "_ ";
} else {
std::cout << x << " ";
}
print(Tape<xs...>());
}
#pragma mark - Concatenate
template<class, class>
class Concatenate;
template<int... xs, int... ys>
class Concatenate<Tape<xs...>, Tape<ys...>> {
public:
using type = Tape<xs..., ys...>;
};
#pragma mark - Invert
template<class>
class Invert;
template<>
class Invert<Tape<>> {
public:
using type = Tape<>;
};
template<int x, int... xs>
class Invert<Tape<x, xs...>> {
public:
using type = typename Concatenate<
typename Invert<Tape<xs...>>::type,
Tape<x>
>::type;
};
#pragma mark - Read
template<int, class>
class Read;
template<int n, int x, int... xs>
class Read<n, Tape<x, xs...>> {
public:
using type = typename std::conditional<
(n == 0),
std::integral_constant<int, x>,
Read<n - 1, Tape<xs...>>
>::type::type;
};
#pragma mark - N first and N last
template<int, class>
class NLast;
template<int n, int x, int... xs>
class NLast<n, Tape<x, xs...>> {
public:
using type = typename std::conditional<
(n == sizeof...(xs)),
Tape<xs...>,
NLast<n, Tape<xs...>>
>::type::type;
};
template<int, class>
class NFirst;
template<int n, int... xs>
class NFirst<n, Tape<xs...>> {
public:
using type = typename Invert<
typename NLast<
n, typename Invert<Tape<xs...>>::type
>::type
>::type;
};
#pragma mark - Write
template<int, int, class>
class Write;
template<int pos, int x, int... xs>
class Write<pos, x, Tape<xs...>> {
public:
using type = typename Concatenate<
typename Concatenate<
typename NFirst<pos, Tape<xs...>>::type,
Tape<x>
>::type,
typename NLast<(sizeof...(xs) - pos - 1), Tape<xs...>>::type
>::type;
};
#pragma mark - Move
template<int, class>
class Hold;
template<int pos, int... xs>
class Hold<pos, Tape<xs...>> {
public:
constexpr static int position = pos;
using tape = Tape<xs...>;
};
template<int, class>
class Left;
template<int pos, int... xs>
class Left<pos, Tape<xs...>> {
public:
constexpr static int position = typename std::conditional<
(pos > 0),
std::integral_constant<int, pos - 1>,
std::integral_constant<int, 0>
>::type();
using tape = typename std::conditional<
(pos > 0),
Tape<xs...>,
Tape<Blank, xs...>
>::type;
};
template<int, class>
class Right;
template<int pos, int... xs>
class Right<pos, Tape<xs...>> {
public:
constexpr static int position = pos + 1;
using tape = typename std::conditional<
(pos < sizeof...(xs) - 1),
Tape<xs...>,
Tape<xs..., Blank>
>::type;
};
#pragma mark - States
template <int>
class Stop {
public:
constexpr static int write = -1;
template<int pos, class tape> using move = Hold<pos, tape>;
template<int x> using next = Stop<x>;
};
#define ADD_STATE(_state_) \
template<int> \
class _state_ { };
#define ADD_RULE(_state_, _read_, _write_, _move_, _next_) \
template<> \
class _state_<_read_> { \
public: \
constexpr static int write = _write_; \
template<int pos, class tape> using move = _move_<pos, tape>; \
template<int x> using next = _next_<x>; \
};
#pragma mark - Machine
template<template<int> class, int, class>
class Machine;
template<template<int> class State, int pos, int... xs>
class Machine<State, pos, Tape<xs...>> {
constexpr static int symbol = typename Read<pos, Tape<xs...>>::type();
using state = State<symbol>;
template<int x>
using nextState = typename State<symbol>::template next<x>;
using modifiedTape = typename Write<pos, state::write, Tape<xs...>>::type;
using move = typename state::template move<pos, modifiedTape>;
constexpr static int nextPos = move::position;
using nextTape = typename move::tape;
public:
using step = Machine<nextState, nextPos, nextTape>;
};
#pragma mark - Run
template<class>
class Run;
template<template<int> class State, int pos, int... xs>
class Run<Machine<State, pos, Tape<xs...>>> {
using step = typename Machine<State, pos, Tape<xs...>>::step;
public:
using type = typename std::conditional<
std::is_same<State<0>, Stop<0>>::value,
Tape<xs...>,
Run<step>
>::type::type;
};
ADD_STATE(A);
ADD_STATE(B);
ADD_STATE(C);
ADD_STATE(D);
ADD_RULE(A, Blank, 1, Right, B);
ADD_RULE(A, 1, 1, Left, B);
ADD_RULE(B, Blank, 1, Left, A);
ADD_RULE(B, 1, Blank, Left, C);
ADD_RULE(C, Blank, 1, Right, Stop);
ADD_RULE(C, 1, 1, Left, D);
ADD_RULE(D, Blank, 1, Right, D);
ADD_RULE(D, 1, Blank, Right, A);
using tape = Tape<Blank>;
using machine = Machine<A, 0, tape>;
using result = Run<machine>::type;
int main() {
print(result());
return 0;
}
I2luY2x1ZGUgPGlvc3RyZWFtPgoKI3ByYWdtYSBtYXJrIC0gVGFwZQoKY29uc3RleHByIGludCBCbGFuayA9IC0xOwoKdGVtcGxhdGU8aW50Li4uIHhzPgpjbGFzcyBUYXBlIHsKcHVibGljOgogICAgdXNpbmcgdHlwZSA9IFRhcGU8eHMuLi4+OwogICAgY29uc3RleHByIHN0YXRpYyBpbnQgbGVuZ3RoID0gc2l6ZW9mLi4uKHhzKTsKfTsKCiNwcmFnbWEgbWFyayAtIFByaW50Cgp0ZW1wbGF0ZTxjbGFzcyBUPgp2b2lkIHByaW50KFQpOwoKdGVtcGxhdGU8Pgp2b2lkIHByaW50KFRhcGU8PikgewogICAgc3RkOjpjb3V0IDw8IHN0ZDo6ZW5kbDsKfQoKdGVtcGxhdGU8aW50IHgsIGludC4uLiB4cz4Kdm9pZCBwcmludChUYXBlPHgsIHhzLi4uPikgewogICAgaWYgKHggPT0gQmxhbmspIHsKICAgICAgICBzdGQ6OmNvdXQgPDwgIl8gIjsKICAgIH0gZWxzZSB7CiAgICAgICAgc3RkOjpjb3V0IDw8IHggPDwgIiAiOwogICAgfQogICAgcHJpbnQoVGFwZTx4cy4uLj4oKSk7Cn0KCiNwcmFnbWEgbWFyayAtIENvbmNhdGVuYXRlCgp0ZW1wbGF0ZTxjbGFzcywgY2xhc3M+CmNsYXNzIENvbmNhdGVuYXRlOwoKdGVtcGxhdGU8aW50Li4uIHhzLCBpbnQuLi4geXM+CmNsYXNzIENvbmNhdGVuYXRlPFRhcGU8eHMuLi4+LCBUYXBlPHlzLi4uPj4gewpwdWJsaWM6CiAgICB1c2luZyB0eXBlID0gVGFwZTx4cy4uLiwgeXMuLi4+Owp9OwoKI3ByYWdtYSBtYXJrIC0gSW52ZXJ0Cgp0ZW1wbGF0ZTxjbGFzcz4KY2xhc3MgSW52ZXJ0OwoKdGVtcGxhdGU8PgpjbGFzcyBJbnZlcnQ8VGFwZTw+PiB7CnB1YmxpYzoKICAgIHVzaW5nIHR5cGUgPSBUYXBlPD47Cn07Cgp0ZW1wbGF0ZTxpbnQgeCwgaW50Li4uIHhzPgpjbGFzcyBJbnZlcnQ8VGFwZTx4LCB4cy4uLj4+IHsKcHVibGljOgogICAgdXNpbmcgdHlwZSA9IHR5cGVuYW1lIENvbmNhdGVuYXRlPAogICAgICAgIHR5cGVuYW1lIEludmVydDxUYXBlPHhzLi4uPj46OnR5cGUsCiAgICAgICAgVGFwZTx4PgogICAgPjo6dHlwZTsKfTsKCiNwcmFnbWEgbWFyayAtIFJlYWQKCnRlbXBsYXRlPGludCwgY2xhc3M+CmNsYXNzIFJlYWQ7Cgp0ZW1wbGF0ZTxpbnQgbiwgaW50IHgsIGludC4uLiB4cz4KY2xhc3MgUmVhZDxuLCBUYXBlPHgsIHhzLi4uPj4gewpwdWJsaWM6CiAgICB1c2luZyB0eXBlID0gdHlwZW5hbWUgc3RkOjpjb25kaXRpb25hbDwKICAgICAgICAobiA9PSAwKSwKICAgICAgICBzdGQ6OmludGVncmFsX2NvbnN0YW50PGludCwgeD4sCiAgICAgICAgUmVhZDxuIC0gMSwgVGFwZTx4cy4uLj4+CiAgICA+Ojp0eXBlOjp0eXBlOwp9OwoKI3ByYWdtYSBtYXJrIC0gTiBmaXJzdCBhbmQgTiBsYXN0Cgp0ZW1wbGF0ZTxpbnQsIGNsYXNzPgpjbGFzcyBOTGFzdDsKCnRlbXBsYXRlPGludCBuLCBpbnQgeCwgaW50Li4uIHhzPgpjbGFzcyBOTGFzdDxuLCBUYXBlPHgsIHhzLi4uPj4gewpwdWJsaWM6CiAgICB1c2luZyB0eXBlID0gdHlwZW5hbWUgc3RkOjpjb25kaXRpb25hbDwKICAgICAgICAobiA9PSBzaXplb2YuLi4oeHMpKSwKICAgICAgICBUYXBlPHhzLi4uPiwKICAgICAgICBOTGFzdDxuLCBUYXBlPHhzLi4uPj4KICAgID46OnR5cGU6OnR5cGU7Cn07Cgp0ZW1wbGF0ZTxpbnQsIGNsYXNzPgpjbGFzcyBORmlyc3Q7Cgp0ZW1wbGF0ZTxpbnQgbiwgaW50Li4uIHhzPgpjbGFzcyBORmlyc3Q8biwgVGFwZTx4cy4uLj4+IHsKcHVibGljOgogICAgdXNpbmcgdHlwZSA9IHR5cGVuYW1lIEludmVydDwKICAgICAgICB0eXBlbmFtZSBOTGFzdDwKICAgICAgICAgICAgbiwgdHlwZW5hbWUgSW52ZXJ0PFRhcGU8eHMuLi4+Pjo6dHlwZQogICAgICAgID46OnR5cGUKICAgID46OnR5cGU7Cn07CgojcHJhZ21hIG1hcmsgLSBXcml0ZQoKdGVtcGxhdGU8aW50LCBpbnQsIGNsYXNzPgpjbGFzcyBXcml0ZTsKCnRlbXBsYXRlPGludCBwb3MsIGludCB4LCBpbnQuLi4geHM+CmNsYXNzIFdyaXRlPHBvcywgeCwgVGFwZTx4cy4uLj4+IHsKcHVibGljOgogICAgdXNpbmcgdHlwZSA9IHR5cGVuYW1lIENvbmNhdGVuYXRlPAogICAgICAgIHR5cGVuYW1lIENvbmNhdGVuYXRlPAogICAgICAgICAgICB0eXBlbmFtZSBORmlyc3Q8cG9zLCBUYXBlPHhzLi4uPj46OnR5cGUsCiAgICAgICAgICAgIFRhcGU8eD4KICAgICAgICA+Ojp0eXBlLAogICAgICAgIHR5cGVuYW1lIE5MYXN0PChzaXplb2YuLi4oeHMpIC0gcG9zIC0gMSksIFRhcGU8eHMuLi4+Pjo6dHlwZQogICAgPjo6dHlwZTsKfTsKCiNwcmFnbWEgbWFyayAtIE1vdmUKCnRlbXBsYXRlPGludCwgY2xhc3M+CmNsYXNzIEhvbGQ7Cgp0ZW1wbGF0ZTxpbnQgcG9zLCBpbnQuLi4geHM+CmNsYXNzIEhvbGQ8cG9zLCBUYXBlPHhzLi4uPj4gewpwdWJsaWM6CiAgICBjb25zdGV4cHIgc3RhdGljIGludCBwb3NpdGlvbiA9IHBvczsKICAgIHVzaW5nIHRhcGUgPSBUYXBlPHhzLi4uPjsKfTsKCnRlbXBsYXRlPGludCwgY2xhc3M+CmNsYXNzIExlZnQ7Cgp0ZW1wbGF0ZTxpbnQgcG9zLCBpbnQuLi4geHM+CmNsYXNzIExlZnQ8cG9zLCBUYXBlPHhzLi4uPj4gewpwdWJsaWM6CiAgICBjb25zdGV4cHIgc3RhdGljIGludCBwb3NpdGlvbiA9IHR5cGVuYW1lIHN0ZDo6Y29uZGl0aW9uYWw8CiAgICAgICAgKHBvcyA+IDApLAogICAgICAgIHN0ZDo6aW50ZWdyYWxfY29uc3RhbnQ8aW50LCBwb3MgLSAxPiwKICAgICAgICBzdGQ6OmludGVncmFsX2NvbnN0YW50PGludCwgMD4KICAgID46OnR5cGUoKTsKCiAgICB1c2luZyB0YXBlID0gdHlwZW5hbWUgc3RkOjpjb25kaXRpb25hbDwKICAgICAgICAocG9zID4gMCksCiAgICAgICAgVGFwZTx4cy4uLj4sCiAgICAgICAgVGFwZTxCbGFuaywgeHMuLi4+CiAgICA+Ojp0eXBlOwp9OwoKdGVtcGxhdGU8aW50LCBjbGFzcz4KY2xhc3MgUmlnaHQ7Cgp0ZW1wbGF0ZTxpbnQgcG9zLCBpbnQuLi4geHM+CmNsYXNzIFJpZ2h0PHBvcywgVGFwZTx4cy4uLj4+IHsKcHVibGljOgogICAgY29uc3RleHByIHN0YXRpYyBpbnQgcG9zaXRpb24gPSBwb3MgKyAxOwoKICAgIHVzaW5nIHRhcGUgPSB0eXBlbmFtZSBzdGQ6OmNvbmRpdGlvbmFsPAogICAgICAgIChwb3MgPCBzaXplb2YuLi4oeHMpIC0gMSksCiAgICAgICAgVGFwZTx4cy4uLj4sCiAgICAgICAgVGFwZTx4cy4uLiwgQmxhbms+CiAgICA+Ojp0eXBlOwp9OwoKI3ByYWdtYSBtYXJrIC0gU3RhdGVzCgp0ZW1wbGF0ZSA8aW50PgpjbGFzcyBTdG9wIHsKcHVibGljOgogICAgY29uc3RleHByIHN0YXRpYyBpbnQgd3JpdGUgPSAtMTsKICAgIHRlbXBsYXRlPGludCBwb3MsIGNsYXNzIHRhcGU+IHVzaW5nIG1vdmUgPSBIb2xkPHBvcywgdGFwZT47CiAgICB0ZW1wbGF0ZTxpbnQgeD4gdXNpbmcgbmV4dCA9IFN0b3A8eD47Cn07CgojZGVmaW5lIEFERF9TVEFURShfc3RhdGVfKSAgICAgIFwKdGVtcGxhdGU8aW50PiAgICAgICAgICAgICAgICAgICBcCmNsYXNzIF9zdGF0ZV8geyB9OwoKI2RlZmluZSBBRERfUlVMRShfc3RhdGVfLCBfcmVhZF8sIF93cml0ZV8sIF9tb3ZlXywgX25leHRfKSAgICAgICAgICBcCnRlbXBsYXRlPD4gICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgXApjbGFzcyBfc3RhdGVfPF9yZWFkXz4geyAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIFwKcHVibGljOiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICBcCiAgICBjb25zdGV4cHIgc3RhdGljIGludCB3cml0ZSA9IF93cml0ZV87ICAgICAgICAgICAgICAgICAgICAgICAgICAgXAogICAgdGVtcGxhdGU8aW50IHBvcywgY2xhc3MgdGFwZT4gdXNpbmcgbW92ZSA9IF9tb3ZlXzxwb3MsIHRhcGU+OyAgIFwKICAgIHRlbXBsYXRlPGludCB4PiB1c2luZyBuZXh0ID0gX25leHRfPHg+OyAgICAgICAgICAgICAgICAgICAgICAgICBcCn07CgojcHJhZ21hIG1hcmsgLSBNYWNoaW5lCgp0ZW1wbGF0ZTx0ZW1wbGF0ZTxpbnQ+IGNsYXNzLCBpbnQsIGNsYXNzPgpjbGFzcyBNYWNoaW5lOwoKdGVtcGxhdGU8dGVtcGxhdGU8aW50PiBjbGFzcyBTdGF0ZSwgaW50IHBvcywgaW50Li4uIHhzPgpjbGFzcyBNYWNoaW5lPFN0YXRlLCBwb3MsIFRhcGU8eHMuLi4+PiB7CiAgICBjb25zdGV4cHIgc3RhdGljIGludCBzeW1ib2wgPSB0eXBlbmFtZSBSZWFkPHBvcywgVGFwZTx4cy4uLj4+Ojp0eXBlKCk7CiAgICB1c2luZyBzdGF0ZSA9IFN0YXRlPHN5bWJvbD47CgogICAgdGVtcGxhdGU8aW50IHg+CiAgICB1c2luZyBuZXh0U3RhdGUgPSB0eXBlbmFtZSBTdGF0ZTxzeW1ib2w+Ojp0ZW1wbGF0ZSBuZXh0PHg+OwoKICAgIHVzaW5nIG1vZGlmaWVkVGFwZSA9IHR5cGVuYW1lIFdyaXRlPHBvcywgc3RhdGU6OndyaXRlLCBUYXBlPHhzLi4uPj46OnR5cGU7CiAgICB1c2luZyBtb3ZlID0gdHlwZW5hbWUgc3RhdGU6OnRlbXBsYXRlIG1vdmU8cG9zLCBtb2RpZmllZFRhcGU+OwoKICAgIGNvbnN0ZXhwciBzdGF0aWMgaW50IG5leHRQb3MgPSBtb3ZlOjpwb3NpdGlvbjsKICAgIHVzaW5nIG5leHRUYXBlID0gdHlwZW5hbWUgbW92ZTo6dGFwZTsKCnB1YmxpYzoKICAgIHVzaW5nIHN0ZXAgPSBNYWNoaW5lPG5leHRTdGF0ZSwgbmV4dFBvcywgbmV4dFRhcGU+Owp9OwoKI3ByYWdtYSBtYXJrIC0gUnVuCgp0ZW1wbGF0ZTxjbGFzcz4KY2xhc3MgUnVuOwoKdGVtcGxhdGU8dGVtcGxhdGU8aW50PiBjbGFzcyBTdGF0ZSwgaW50IHBvcywgaW50Li4uIHhzPgpjbGFzcyBSdW48TWFjaGluZTxTdGF0ZSwgcG9zLCBUYXBlPHhzLi4uPj4+IHsKICAgIHVzaW5nIHN0ZXAgPSB0eXBlbmFtZSBNYWNoaW5lPFN0YXRlLCBwb3MsIFRhcGU8eHMuLi4+Pjo6c3RlcDsKCnB1YmxpYzoKICAgIHVzaW5nIHR5cGUgPSB0eXBlbmFtZSBzdGQ6OmNvbmRpdGlvbmFsPAogICAgICAgIHN0ZDo6aXNfc2FtZTxTdGF0ZTwwPiwgU3RvcDwwPj46OnZhbHVlLAogICAgICAgIFRhcGU8eHMuLi4+LAogICAgICAgIFJ1bjxzdGVwPgogICAgPjo6dHlwZTo6dHlwZTsKfTsKCkFERF9TVEFURShBKTsKQUREX1NUQVRFKEIpOwpBRERfU1RBVEUoQyk7CkFERF9TVEFURShEKTsKCkFERF9SVUxFKEEsIEJsYW5rLCAxLCBSaWdodCwgQik7CkFERF9SVUxFKEEsIDEsIDEsIExlZnQsIEIpOwoKQUREX1JVTEUoQiwgQmxhbmssIDEsIExlZnQsIEEpOwpBRERfUlVMRShCLCAxLCBCbGFuaywgTGVmdCwgQyk7CgpBRERfUlVMRShDLCBCbGFuaywgMSwgUmlnaHQsIFN0b3ApOwpBRERfUlVMRShDLCAxLCAxLCBMZWZ0LCBEKTsKCkFERF9SVUxFKEQsIEJsYW5rLCAxLCBSaWdodCwgRCk7CkFERF9SVUxFKEQsIDEsIEJsYW5rLCBSaWdodCwgQSk7Cgp1c2luZyB0YXBlID0gVGFwZTxCbGFuaz47CnVzaW5nIG1hY2hpbmUgPSBNYWNoaW5lPEEsIDAsIHRhcGU+Owp1c2luZyByZXN1bHQgPSBSdW48bWFjaGluZT46OnR5cGU7CgppbnQgbWFpbigpIHsKICAgIHByaW50KHJlc3VsdCgpKTsKICAgIHJldHVybiAwOwp9Cg==