объяснение

Befunge - это двумерная программа, использующая стеки .

Это означает, что для выполнения 5 + 6 вы пишете 56+, что означает:

56+
5    push 5 into stack
 6   push 6 into stack
  +  pop the first two items in the stack and add them up, and push the result into stack

(to those of you who do not know stacks, "push" just means add and "pop" just means take off)

Тем не менее, мы не можем вставить номер 56прямо в стек.

Чтобы сделать это, мы должны написать 78*вместо этого, который умножает 7и 8и помещает продукт в стек.

Детали

Для каждого числа от 1доn найдите строку, состоящую только из этих символов: 0123456789+-*/:(я бы не использовал %по модулю.)

Цель состоит в том, чтобы найти короткую строку, которая может представлять число, используя формат, описанный выше.

Например, если вход 123 , то выход будет 67*9:*+. Результат должен оцениваться слева направо.

Если имеется более одного приемлемого выхода (например, 99*67*+ , также приемлемо), любой может быть напечатан (без бонуса за печать всех из них).

Дальнейшее объяснение

Если вы все еще не понимаете, как 67*9:*+оценивать 123, вот подробное объяснение.

stack    |operation|explanation
          67*9:*+
[6]       6         push 6 to stack
[6,7]      7        push 7 to stack
[42]        *       pop two from stack and multiply, then put result to stack
[42,9]       9      push 9 to stack
[42,9,9]      :     duplicate the top of stack
[42,81]        *    pop two from stack and multiply, then put result to stack
[123]           +   pop two from stack and add, then put result to stack

TL; DR

Программа должна найти самый короткий строку, которая может представлять ввод (число), используя формат, указанный выше.

SCORING

• Мы уже сделали это в кратчайшем количестве кода . На этот раз размер не имеет значения.
• На выбранном вами языке должен быть бесплатный компилятор / интерпретатор для моей операционной системы (Windows 7 Enterprise).
• Бонус, если вы включите ссылку на компилятор / интерпретатор (я слишком ленив).
• Если возможно, пожалуйста, включите таймер для моего удобства. Выход от таймера действителен.
• Счет будет самым большим n за 1 минуту.
• Это означает, что программа должна распечатать требуемое представление из 1 далее.
• Нет жесткого кодирования, кроме 0как 9.

(больше) СПЕЦИФИКАЦИЯ

• Программа недействительна, если она выводит строку длиннее, чем необходимо для любого числа.
• 1/0=ERROR
• 5/2=2, (-5)/2=-2, (-5)/(-2)=2,5/(-2)=-2

Disambiguation

-Это second-top minus topозначает , что 92-возвращается7 .

Аналогично, /это second-top divide topозначает, что 92/возвращает4 .

Пример программы

Lua

Использует поиск в глубину.

local function div(a,b)
    if b == 0 then
        return "error"
    end
    local result = a/b
    if result > 0 then
        return math.floor(result)
    else
        return math.ceil(result)
    end
end

local function eval(expr)
    local stack = {}
    for i=1,#expr do
        local c = expr:sub(i,i)
        if c:match('[0-9]') then
            table.insert(stack, tonumber(c))
        elseif c == ':' then
            local a = table.remove(stack)
            if a then
                table.insert(stack,a)
                table.insert(stack,a)
            else
                return -1
            end
        else
            local a = table.remove(stack)
            local b = table.remove(stack)
            if a and b then
                if c == '+' then
                    table.insert(stack, a+b)
                elseif c == '-' then
                    table.insert(stack, b-a)
                elseif c == '*' then
                    table.insert(stack, a*b)
                elseif c == '/' then
                    local test = div(b,a)
                    if test == "error" then
                        return -1
                    else
                        table.insert(stack, test)
                    end
                end
            else
                return -1
            end
        end
    end
    return table.remove(stack) or -1
end

local samples, temp = {""}, {}

while true do
    temp = {}
    for i=1,#samples do
        local s = samples[i]
        if eval(s) ~= -1 or s == "" then for n in ("9876543210+-*/:"):gmatch(".") do
            table.insert(temp, s..n)
        end end
    end
    for i=1,#temp do
        local test = eval(temp[i])
        if input == test then
            print(temp[i])
            return
        end
    end
    samples = temp
end

C ++, взрывая всю память на компьютере рядом с вами

Генерирует самую короткую строку, где вычисление нигде не вызывает переполнения 32-разрядного целого числа со знаком (поэтому все промежуточные результаты находятся в диапазоне [-2147483648, 2147483647]

В моей системе это генерирует решение для всех чисел до 48343230 секунд включительно при использовании памяти 1.8G. Еще большее число быстро взорвет использование памяти. Самое большое число, которое я могу обработать в моей системе, это 5113906. Расчет занимает почти 9 минут и 24ГБ. Когда это заканчивается, у него есть решение для398499338 значений, около 9% всех 32-битных целых (положительных и отрицательных)

Требуется компилятор C ++ 11. На Linux скомпилируйте с:

g++ -Wall -O3 -march=native -std=gnu++11 -s befour.cpp -o befour

Добавьте -DINT64в качестве опции использование 64-разрядного целочисленного диапазона вместо 32-разрядного для промежуточных результатов (это будет использовать примерно на 50% больше времени и памяти). Это требует встроенного 128-битного типа. Возможно, вам придется изменить тип GCC __int128. Нет результата по крайней мере в диапазоне[1..483432] изменении , позволяя получить более крупные промежуточные результаты.

добавлять -DOVERFLOW в качестве опции, чтобы не использовать больший целочисленный тип для проверки на переполнение. Это дает эффект переполнения и переноса значений.

Если в вашей системе есть tcmalloc ( https://github.com/gperftools/gperftools ), вы можете связать ее с программой, которая, как правило, немного быстрее и использует немного меньше памяти. В некоторых системах UNIX вы можете использовать предварительную загрузку, например

LD_PRELOAD=/usr/lib/libtcmalloc_minimal.so.4 befour 5

Основное использование: сгенерируйте и напечатайте все числа до цели:

befour target

Параметры:

• -a Также распечатайте все числа, которые были сгенерированы при разработке цели
• -c Также напечатайте все числа, которые были сгенерированы, начиная с «переноса» (dup)
• -f Найдите и напечатайте первое число за пределами цели, которое не было сгенерировано
• -s Остановиться, если цель сгенерирована, даже если не все числа до того были сгенерированы
• -SКак -sи-f в автоматическом цикле. Как только цель сгенерирована, найдите первый номер, который еще не сгенерирован, и сделайте его новой целью.
• -EНе выходите сразу, когда цель достигнута. Сначала закончите все строки текущей длины
• -OНе выводите строки для всех чисел вплоть до цели. просто строка для цели
• -o Разрешенные инструкции (по умолчанию +-*/:
• -b num Самый низкий литерал, который можно сдвинуть (по умолчанию 0 )
• -B num Наибольший литерал, который может быть выдвинут (по умолчанию 9 )
• -r numМинимально допустимый промежуточный результат. Используется для избежания недостаточного заполнения. ( по умолчанию INT32_MIN,-2147483648
• -R numМаксимально допустимый промежуточный результат. Используется, чтобы избежать переполнения. ( по умолчанию INT32_MAX,2147483647
• -m memory (только для Linux) выход, когда примерно столько дополнительной памяти выделено

Несколько интересных вариантов комбинаций:

Сгенерируйте все числа до цели и вычислите наименьшее число, для которого требуется более длинный генератор, чем все эти числа:

befour -fE target

Генерация только цели (-s), печать только цели (-O)

befour -sO target

Найдите наибольшее число, которое может быть сгенерировано в вашей системе с учетом времени и / или ограничений памяти (это приведет к тому, что вашей системе будет не хватать памяти, если вы оставите ее работающей. Вычтите 1 из последнего результата "поиска", который вы видите как последнее безопасное значение ):

befour -S 1

Генерируйте решения без использования отрицательных промежуточных результатов ( 30932это первое значение, которое требует отрицательных промежуточных результатов для самой короткой строки):

befour -r0 target

Генерируйте решения без каких-либо усилий 0(кажется, это не приводит к каким-либо неоптимальным решениям):

befour -b1 target

Генерация решений, в том числе a..f (10..15):

befour -B15 target

Генерируйте решения без использования dup :(добавьте, -r0так как в этом случае отрицательные промежуточные значения никогда не будут интересны)

befour -r0 -o "+-*/" target

Найти первое значение , которое не может быть создано для заданной длины строки , используя только +, -, *и /:

befour -ES -r0 -o "+-*/" 1

Фактически это сгенерирует первые несколько членов https://oeis.org/A181898 , но начнет расходиться, 14771потому что мы используем усеченное деление, так что число может быть выполнено со строкой длиной 13 вместо длины 15 в качестве серии OEIS. ожидает:

14771: 13: 99*9*9*4+9*4/

вместо того

14771: 15: 19+5*6*7*9+7*8+

Поскольку разделение без усечения кажется бессмысленным, ряд OEIS можно лучше генерировать с помощью

befour -ES -r0 -o"+-*" 1

Предполагая, что разделение остается бесполезным, это дало мне 3 дополнительных условия, прежде чем мне не хватило памяти:

10, 19, 92, 417, 851, 4237, 14771, 73237, 298609, 1346341, 6176426, 25622578

Другая версия этой программы, хранящая часть данных во внешних файлах, добавляет 135153107 и 675854293, после чего были сгенерированы все 32-битные целые числа.

befour.cpp

/*
  Compile using something like:
g++ -Wall -O3 -march=native -std=gnu++11 -s  befour.cpp -o befour
*/
#include <iostream>
#include <fstream>
#include <sstream>
#include <stdexcept>
#include <string>
#include <vector>
#include <limits>
#include <climits>
#include <cstdint>
#include <cstdlib>
#include <chrono>
#include <unordered_map>

using namespace std;

#ifdef __GNUC__
# define HOT        __attribute__((__hot__))
# define COLD       __attribute__((__cold__))
# define NOINLINE   __attribute__((__noinline__))
# define LIKELY(x)  __builtin_expect(!!(x),1)
# define UNLIKELY(x)    __builtin_expect(!!(x),0)
#else // __GNUC__
# define HOT
# define COLD
# define NOINLINE
# define LIKELY(x)  (x)
# define UNLIKELY(x)    (x)
#endif // __GNUC__

#ifdef INT64
using Int  = int64_t;       // Supported value type
# ifndef OVERFLOW
using Int2 = __int128;      // Do calculations in this type. Check overflow
# endif // OVERFLOW
#else // INT64
using Int  = int32_t;       // Supported value type
# ifndef OVERFLOW
using Int2 = int64_t;       // Do calculations in this type. Check overflow
# endif // OVERFLOW
#endif // INT64
#ifdef OVERFLOW
using Int2 = Int;
#endif // OVERFLOW

// Supported value range
Int2 MIN = numeric_limits<Int>::lowest();
Int2 MAX = numeric_limits<Int>::max();
Int HALF_MIN, HALF_MAX;

// The initial values we can push
Int ATOM_MIN = 0;
Int ATOM_MAX = 9;

bool all    = false;    // Output all reached values
bool all_carry  = false;    // Output all values reachable using carry
bool early_exit = true;     // Exit before finishing level if goal reached
bool find_hole  = false;    // Look for first unconstructed > target
bool output = true;     // Output [1..target] instead of just target
bool single = false;    // Only go for target instead of [1..target]
bool explore    = false;    // Don't stop, increase N until out of memory
bool do_dup = false;    // Use operator :
bool do_multiply= false;    // Use operator *
bool do_add = false;    // Use operator +
bool do_subtract= false;    // Use operator -
bool do_divide  = false;    // Use operator /
char const* operators = "+-*/:"; // Use these operators
size_t max_mem  = SIZE_MAX; // Stop if target memory reached

size_t const MEM_CHECK = 1000000;

chrono::steady_clock::time_point start;

NOINLINE size_t get_memory(bool set_base_mem = false) {
static size_t base_mem = 0;
size_t const PAGE_SIZE = 4096;

// Linux specific. Won't hurt on other systems, just gets no result
size_t mem = 0;
std::ifstream statm;
statm.open("/proc/self/statm");
statm >> mem;
mem *= PAGE_SIZE;
if (set_base_mem) base_mem = mem;
else mem -= base_mem;
return mem;
}

// Handle commandline options.
// Simplified getopt for systems that don't have it in their library (Windows..)
class GetOpt {
  private:
string const options;
char const* const* argv;
int nextchar = 0;
int optind = 1;
char ch = '?';
char const* optarg = nullptr;

  public:
int ind() const { return optind; }
char const* arg() const { return optarg; }
char option() const { return ch; }

GetOpt(string const options_, char const* const* argv_) :
options(options_), argv(argv_) {}
char next() {
while (1) {
    if (nextchar == 0) {
    if (!argv[optind] ||
        argv[optind][0] != '-' ||
        argv[optind][1] == 0) return ch = 0;
    if (argv[optind][1] == '-' && argv[optind][2] == 0) {
        ++optind;
        return ch = 0;
    }
    nextchar = 1;
    }
    ch = argv[optind][nextchar++];
    if (ch == 0) {
    ++optind;
    nextchar = 0;
    continue;
    }
    auto pos = options.find(ch);
    if (pos == string::npos) ch = '?';
    else if (options[pos+1] == ':') {
    if (argv[optind][nextchar]) {
        optarg = &argv[optind][nextchar];
    } else {
        optarg = argv[++optind];
        if (!optarg) return ch = options[0] == ':' ? ':' : '?';
    }
    ++optind;
    nextchar = 0;
    }
    return ch;
}
}
};

using ms = chrono::milliseconds;

Int missing, N;
size_t cached, cached_next;

uint8_t const CARRY_MASK = '\x80';
uint8_t const LITERAL    = 0;
struct How {
// Describes how to construct a number
Int left;
Int right;
uint8_t ops, op;

How(uint8_t ops_, uint8_t op_, Int carry_=0, Int left_=0, Int right_=0) :
left(left_),
right(right_),
ops(ops_),
op(carry_ ? CARRY_MASK | op_ : op_)
{}
How() = default;
How(How&&) = default;
How& operator=(How&&) = default;
static How const* predict(Int carry, Int value, int& ops);
static void print_predicted(ostream& out, Int carry, Int value, How const* Value = nullptr);
void print(ostream& out, Int carry = 0, bool length = false) const;
};

ostream& operator<<(ostream& out, How const& how) {
how.print(out, 0, true);
return out;
}

using NumSet  = vector<Int>;
using NumSets = vector<NumSet>;

struct Known: public unordered_map<Int, How>
{
void store(NumSet& L, Int accu, uint8_t ops, uint8_t op,
       Int left=0, Int carry_right=0, Int right=0) {
++cached;
emplace(accu, How(ops, op, carry_right, left, right));
// operator[](accu) = How(ops, op, carry_right, left, right);
L.emplace_back(accu);
}
void maybe_store(Known const& known0, NumSet& L,
         Int accu, uint8_t ops, uint8_t op,
         Int carry_left, Int left, Int carry_right, Int right) {
if (count(accu)) return;
if (carry_left) {
    auto found = known0.find(accu);
    // If we can do as good or better without carry use that
    if (found != known0.end() && found->second.ops <= ops) return;
}
store(L, accu, ops, op, left, carry_right, right);
if (carry_left) return;
if (single) {
    if (UNLIKELY(accu == N)) known0.maybe_explore();
} else if (1 <= accu && accu <= N) --missing;
}
NOINLINE void maybe_explore() const COLD {
--missing;
if (explore && early_exit) do_explore();
}
NOINLINE void do_explore() const COLD {
auto i = N;
while (i < MAX && count(++i));
auto end = chrono::steady_clock::now();
auto elapsed = chrono::duration_cast<ms>(end-start).count();

cerr << "Found " << N << " at " << elapsed / 1000. << " s";
auto mem = get_memory();
if (mem) cerr << " (" << mem / 1000 / 1000.  << " MB)";
if (i < MAX || !count(i)) {
    cerr << ", now looking for " << i << endl;
    N = i;
    ++missing;
} else
    cerr << ", every value has now been generated" << endl;
}
};

struct KnowHow {
// Describes all numbers we know how to construct
NumSets num_sets;
Known known;

KnowHow() = default;
~KnowHow() = default;
KnowHow(KnowHow const&) = delete;
KnowHow& operator=(KnowHow const&) = delete;
};
// Describes all numbers we know how to construct for a given carry
// Key 0 is special: the numbers we can construct without carry (the solutions)
unordered_map<Int, KnowHow> known_how;

// Try to predict if a subtree is a delayed How and avoid descending
// into it (since it may not exist yet)
How const* How::predict(Int carry, Int value, int& ops) {
How* Value;
if (carry) {
if (value == carry) {
    Value = nullptr;
    ops = 0;
} else {
    Value = &known_how.at(carry).known.at(value);
    ops = Value->ops;
}
} else {
if (ATOM_MIN <= value && value <= ATOM_MAX) {
    Value = nullptr;
    ops = 0;
} else {
    Value = &known_how.at(0).known.at(value);
    ops = Value->ops;
}
}
return Value;
}

void How::print_predicted(ostream& out, Int carry, Int value, How const* Value) {
if (Value) Value->print(out, carry);
else if (carry) out << ":";
else if (value > 9) out << static_cast<char>(value-10+'a');
else out << value;
}

void How::print(ostream& out, Int carry_left, bool length) const {
if (length) out << 2*ops+1 << ": ";

Int carry_right = 0;
auto op_ = op;

switch(op_) {
case LITERAL:
  How::print_predicted(out, 0, left);
  break;
case '*' | CARRY_MASK:
case '/' | CARRY_MASK:
case '+' | CARRY_MASK:
case '-' | CARRY_MASK:
  carry_right = left;
  op_ &= ~CARRY_MASK;
  // Intentional drop through
case '*':
case '/':
case '+':
case '-':
  {
      int left_ops, right_ops;
      auto Left  = How::predict(carry_left,  left,  left_ops);
      // Int right = 0;
      auto Right = How::predict(carry_right, right, right_ops);

      // Sanity check: tree = left_tree + root + right_tree
      if (ops != left_ops + right_ops +1) {
      char buffer[80];
      snprintf(buffer, sizeof(buffer),
           "Broken number %d %c %d, length %d != %d + %d + 1",
           static_cast<int>(left), op_, static_cast<int>(right),
           ops, left_ops, right_ops);
      throw(logic_error(buffer));
      }

      How::print_predicted(out, carry_left,  left,  Left);
      How::print_predicted(out, carry_right, right, Right);
  }
  // Intentional drop through
case ':':
  out << op_;
  break;
default:
  throw(logic_error("Unknown op " + string{static_cast<char>(op_)}));
  break;
}
}

// carryX indicates Xv was reached using carry. If not we also know [L, known] is known_how[0]
// carryY indicates Y was reached using carry (carryY == Xv if so)
void combine(NumSet& L, Known& known, Known const& known0, int ops, Int carryX, Int2 Xv, Int carryY, NumSet const&Y) HOT;
void combine(NumSet& L, Known& known, Known const& known0, int ops, Int carryX, Int2 Xv, Int carryY, NumSet const&Y) {
for (Int Yv: Y) {
// Yv == 0 can never lead to an optimal calculation
if (Yv == 0) continue;

Int2 accu;

if (do_multiply) {
    accu = Xv * Yv;
    if (accu <= MAX && accu >= MIN)
    known.maybe_store(known0, L, accu, ops, '*', carryX, Xv, carryY, Yv);
}

if (do_add) {
    accu = Xv + Yv;
    if (accu <= MAX && accu >= MIN)
    known.maybe_store(known0, L, accu, ops, '+', carryX, Xv, carryY, Yv);
}

if (do_subtract) {
    accu = Xv - Yv;
    if (accu <= MAX && accu >= MIN)
    known.maybe_store(known0, L, accu, ops, '-', carryX, Xv, carryY, Yv);
}

if (do_divide) {
    accu = Xv / Yv;
    if (accu <= MAX && accu >= MIN)
    known.maybe_store(known0, L, accu, ops, '/', carryX, Xv, carryY, Yv);
}
}
}

// value was constructed using a carry if and only if value != 0
NumSet const& level(KnowHow& known_how0, Int value, int ops) HOT;
NumSet const& level(KnowHow& known_how0, Int value, int ops) {
auto& from_value = known_how[value];
if (from_value.num_sets.size() <= static_cast<size_t>(ops)) {
auto& known = from_value.known;
if (from_value.num_sets.size() != static_cast<size_t>(ops)) {
    if (value == 0 || ops != 1)
    throw(logic_error("Unexpected level skip"));
    // This was because of delayed carry creation.
    // The delay is over. Create the base case
    from_value.num_sets.resize(ops+1);
    known.store(from_value.num_sets[0], value, 0, ':', value);
} else
    from_value.num_sets.resize(ops+1);
auto& L = from_value.num_sets[ops];
if (ops == 0) {
    if (value) {
    known.store(L, value, ops, ':', value);
    } else {
    for (auto i = ATOM_MIN; i <= ATOM_MAX; ++i) {
        if (single) {
        if (i == N) --missing;
        } else {
        if (0 < i && i <= N) --missing;
        }
        known.store(L, i, 0, LITERAL, i);
    }
    }
} else {
    auto& known0 = known_how0.known;
    // for (auto k=ops-1; k>=0; --k) {
    for (auto k=0; k<ops; ++k) {
    auto const& X = from_value.num_sets[ops-1-k];
    auto const& Y = known_how0.num_sets[k];

    for (Int Xv: X) {
        // Plain combine must come before carry combine so a plain
        // solution will prune a same length carry solution
        combine(L, known, known0, ops, value, Xv, 0, Y);
        if (!missing && early_exit) goto DONE;
        if (do_dup && (Xv > ATOM_MAX || Xv < ATOM_MIN)) {
        // Dup Xv, construct something using k operators, combine
        if (k == 0 && Xv != 0) {
            // Delay creation of carry known_how[Xv] for 1 level
            // This is purely a memory and speed optimization

            // Subtraction gives 0 which is never optimal
            // Division    gives 1 which is never optimal

            // Multiplication gives Xv ** 2
            // Could be == Xv if Xv== 0 or Xv == 1, but will be
            // pruned by atom - atom or atom / atom
            Int2 accu = Xv;
            accu *= accu;
            if (accu <= MAX && accu >= MIN) {
            known.maybe_store(known0, L, accu, ops, '*',
                      value, Xv, Xv, Xv);
            }

            // Addition gives Xv * 2 (!= Xv)
            if (HALF_MIN <= Xv && Xv <= HALF_MAX)
            known.maybe_store(known0, L, 2*Xv, ops, '+',
                      value, Xv, Xv, Xv);
        } else {
            auto& Z = level(known_how0, Xv, k);
            combine(L, known, known0, ops, value, Xv, Xv, Z);
        }
        if (!missing && early_exit) goto DONE;
        }
        if (max_mem != SIZE_MAX && cached > cached_next) {
        cached_next = cached + MEM_CHECK;
        if (get_memory() >= max_mem) goto DONE;
        }
    }
    }
}
// L.shrink_to_fit();
}
  DONE:
return from_value.num_sets[ops];
}

void my_main(int argc, char const* const* argv) {
GetOpt options("acfm:sSEOo:b:B:r:R:", argv);
while (options.next())
switch (options.option()) {
    case 'a': all    = true;  break;
    case 'b': {
    auto tmp = atoll(options.arg());
    ATOM_MIN = static_cast<Int>(tmp);
    if (static_cast<long long int>(ATOM_MIN) != tmp)
        throw(range_error("ATOM_MIN is out of range"));
    break;
    }
    case 'B': {
    auto tmp = atoll(options.arg());
    ATOM_MAX = static_cast<Int>(tmp);
    if (static_cast<long long int>(ATOM_MAX) != tmp)
        throw(range_error("ATOM_MAX is out of range"));
    break;
    }
    case 'c': all_carry  = true;  break;
    case 'f': find_hole  = true;  break;
    case 'm': max_mem = atoll(options.arg()); break;
    case 'S': explore    = true;  // intended drop through to single
    case 's': single     = true;  break;
    case 'o': operators  = options.arg(); break;
    case 'E': early_exit = false; break;
    case 'r': {
    auto tmp = atoll(options.arg());
    MIN = static_cast<Int>(tmp);
    if (static_cast<long long int>(MIN) != tmp)
        throw(range_error("MIN is out of range"));
    break;
    }
    case 'R': {
    auto tmp = atoll(options.arg());
    MAX = static_cast<Int>(tmp);
    if (static_cast<long long int>(MAX) != tmp)
        throw(range_error("MAX is out of range"));
    break;
    }
    case 'O': output     = false; break;
    default:
      cerr << "usage: " << argv[0] << " [-a] [-c] [-f] [-D] [-E] [-O] [-s] [-b atom_min] [-B atom_max] [r range_min] [-R range_max] [-m max_mem] [max]" << endl;
      exit(EXIT_FAILURE);
}

// Avoid silly option combinations
if (MIN > MAX) throw(logic_error("MIN above MAX"));
if (ATOM_MIN > ATOM_MAX) throw(logic_error("ATOM_MIN above ATOM_MAX"));
if (ATOM_MIN < 0)  throw(range_error("Cannot represent negative atoms"));
if (ATOM_MAX > 35) throw(range_error("Cannot represent atoms > 35"));
if (ATOM_MIN < MIN) throw(range_error("ATOM_MIN is out of range"));
if (ATOM_MAX > MAX) throw(range_error("ATOM_MAX is out of range"));

HALF_MIN = MIN / 2;
HALF_MAX = MAX / 2;

for (auto ops=operators; *ops; ++ops)
switch(*ops) {
    case '*': do_multiply = true; break;
    case '/': do_divide   = true; break;
    case '+': do_add      = true; break;
    case '-': do_subtract = true; break;
    case ':': do_dup      = true; break;
    default:
      throw(logic_error("Unknown operator"));
}
long long int const NN =
options.ind() < argc ? atoll(argv[options.ind()]) : 1;
if (NN < MIN || NN > MAX)
throw(range_error("Target number is out of range"));
N = NN;
if (N < 1) {
single = true;
output = false;
}
cerr << "N=" << N << ", using " << sizeof(Int) * CHAR_BIT << " bits without overflow" << endl;

missing = single ? 1 : N;
cached = cached_next = 0;
auto& known_how0 = known_how[0];
auto& known = known_how0.known;
auto mem = get_memory(true);
if (!mem && max_mem != SIZE_MAX)
throw(runtime_error("Cannot get memory usage on this system"));

// Start calculation
start = chrono::steady_clock::now();

// Fill in initial values [0..9]
level(known_how0, 0, 0);

// Grow number of allowed operations until all requested numbers are reached
// for (auto ops=1; ops <=5; ++ops) {
for (auto ops=1;;++ops) {
if (missing == 0) {
    if (!explore) break;
    known_how0.known.do_explore();
    if (missing == 0) break;
}
if (max_mem != SIZE_MAX && get_memory() >= max_mem) break;
auto end = chrono::steady_clock::now();
auto elapsed = chrono::duration_cast<ms>(end-start).count();
cerr << "Reaching for " << 2*ops+1 << " instructions at " << elapsed/1000. << " s";
if (mem) cerr << " (" << get_memory() / 1000 / 1000.  << " MB)";
cerr << endl;

auto old_cached = cached;
level(known_how0, 0, ops);
if (cached == old_cached) {
    cerr << "Oops, all possible numbers have been generated and we still weren't finished"  << endl;
    break;
}
}

// We are done generating all numbers.
auto end = chrono::steady_clock::now();

// Report the result
// length = 2*ops + 1
Int limit = known_how0.num_sets.size()*2-1;
cerr << "Some numbers needed " << limit << " instructions" << endl;

auto elapsed = chrono::duration_cast<ms>(end-start).count();
start = end;
stringstream out;
out << "Calculation: " << elapsed/1000.  << " s\n";
for (auto i = output ? 1 : N; i <= N; ++i) {
if (single || missing) {
    auto got = known.find(i);
    if (got != known.end())
    cout << i << ": " << got->second << "\n";
    else
    cout << i << " not generated\n";
} else
    cout << i << ": " << known.at(i) << "\n";
}
if (output) {
end = chrono::steady_clock::now();
elapsed = chrono::duration_cast<ms>(end-start).count();
start = end;
out << "Printing:    " << elapsed/1000. << " s\n";
}

if (find_hole) {
Int hole;
for (auto i = single ? 1 : N+1; 1; ++i) {
    if (!known_how0.known.count(i) || i == 0) {
    hole = i;
    break;
    }
}
out << "First missing value " << hole << "\n";
end = chrono::steady_clock::now();
elapsed = chrono::duration_cast<ms>(end-start).count();
start = end;
out << "Missing:     " << elapsed/1000. << " s\n";
}

if (all) {
for (auto const& entry: known_how0.known) {
    cout << entry.first << ": " << entry.second << "\n";
}
end = chrono::steady_clock::now();
elapsed = chrono::duration_cast<ms>(end-start).count();
start = end;
out << "All:         " << elapsed/1000. << " s\n";
}

if (all_carry) {
for (auto const& carry: known_how) {
    auto carry_left = carry.first;
    if (carry_left == 0) continue;
    cout << "Carry " << carry_left << "\n";
    for (auto const& how: carry.second.known) {
    cout << "    " << how.first << ": ";
    how.second.print(cout, carry_left, true);
    cout << "\n";
    }
}
end = chrono::steady_clock::now();
elapsed = chrono::duration_cast<ms>(end-start).count();
start = end;
out << "All carry:   " << elapsed/1000. << " s\n";
}

mem = get_memory();
if (mem) cerr << "used about " << mem / 1000 / 1000.  << " MB\n";

cerr << out.str();
cerr << "Cached " << cached << " results = " << known.size() << " plain + " << cached - known.size() << " carry" << endl;
}

int main(int argc, char const* const* argv) {
try {
my_main(argc, argv);
} catch(exception& e) {
cerr << "Error: " << e.what() << endl;
quick_exit(EXIT_FAILURE);
}
// Cleaning up the datastructures can take ages
quick_exit(EXIT_SUCCESS);
}

Некоторые тестовые случаи:

• 1: 1: 1
• 11: 3: 29+
• 26: 5: 29*8+
• 27: 3: 39*
• 100: 5: 19+:*
• 2431: 9: 56*9*9*1+
• 3727: 9: 69*7+:*6+
• 86387: 11: 67*:*1-7*7*
• 265729: 11: 39*:*:*2/9+
• 265620: 13: 99*::*6/*7+3*
• 1921600: 9: 77*:*:*3/
• 21523360: 9: 99*:*:*2/
• 57168721: 11: 99*6+:*8-:*
• 30932: 11: 159*-:4*:*+

JavaScript узел грубой силы

Программный файл bfCodes.js

function bfCodes( n)
{   var odo = [0], valid = true, valCount=1;

    const vDUP = 10, vADD = 11, vSUB = 12, vMUL=13, vDIV = 14, vMAX = vDIV;
    const vCHARS = "0123456789:+-*/";

    function inc(sd) // increment significant digit, lsd = 0
    {   if(sd >= odo.length) { odo.push(0); console.log("length: " + (sd+1)); ++valCount; return;}
        var v = ++odo[sd]; // increment and read the base 15 odometer digit
        if( v == vDUP)
            if( valCount) {++valCount; return}
            else { odo[ sd] = vMAX; --valCount; valid = false; return;}

        if( v == vADD)
        {    if( (--valCount) < 1) { valid = false; odo[ sd] = vMAX; return;};
        }
        if( v > vMAX) { odo[sd] = 0; ++valCount; valid = true; inc(sd+1); return;}
    }

    function bfDecode( odo)
    {   var a,b,stack = [];
        for(var i = odo.length; i--;)
        {   var v = odo[ i];
            if( v < 10) { stack.push( v); continue;};
            switch(v) {
            case vDUP: stack.push( stack[stack.length-1]); continue;
            case vADD: b=stack.pop(); stack.push( stack.pop()+b); continue;
            case vMUL: b=stack.pop(); stack.push(stack.pop()*b); continue;
            case vDIV: b=stack.pop(); if(!b) return undefined; a = stack.pop(); 
                stack.push( (a < 0 ? b < 0 : b > 0) ? (a/b)>>0 : -(-a/b >>0)); continue;
            }
        }
        return stack[0];
    }
    var codes = [], value;
    for( var got = 0; got < n;)
    {   inc(0);
        if(!valid) continue;
        if(!(value = bfDecode( odo))) continue;
        if( value <= 0 || value > n || codes[ value]) continue;
        ++got;
        for(var i = odo.length, s=""; i--;)  s+=vCHARS[ odo[i]];
        codes[ value] = s;
    }
    return codes;
}

function main( args) // node, script, number
{   n = parseInt( args[2]);
    if(isNaN(n)){ console.log("\nTry:  node bfCodes number\nfor script saved as bfCodes.js"); return;}
    console.log("\ngenerating befunge code for numbers up to " + n);
    var start = Date.now();
    var codes = bfCodes(n);
    var end = Date.now();
    console.log("befunge codes:");
    for( var i = 1; i <=n; ++i) console.log( i + ": " + codes[i]);
    console.log(end-start + " msec");
}
main( process.argv);

Работает под Windows

1. Загрузите и установите Nodejs , реализацию движка Chromes V8 JavaScript.
2. Сохраните указанный выше файл программы в рабочем каталоге, используя имя файла "bfCodes.js" (имена файлов Windows не чувствительны к регистру).
3. Щелкните правой кнопкой мыши в рабочем каталоге и создайте ярлык для программы командной оболочки (окно DOS для старых версий) с целью cmd.exe
4. Отредактируйте свойства ярлыка и установите рабочую папку с именем вашего рабочего каталога (нажмите в строке адреса и скопируйте).
5. Откройте cmd.exeс помощью ярлыка и проверьте, что приглашение DOS начинается с рабочего каталога
6. Введите «node bfCodes» без кавычек и введите - запуск узла в первый раз может занять больше времени, чем запуск его снова.
7. Введите "node bfCodes 16", чтобы показать коды до 16. Не используйте большое число!

оптимизация

Алгоритм циклически перебирает все комбинации символов befunge, начиная с строки кода длиной 1. Думайте о нем, как о вращении базового одометра 15 из наименее значащей цифры. Цифры высшего порядка перебираются с увеличением медленности. bfCodesне оценивает сгенерированный код, который сделал бы длину стека нулевой или отрицательной или оставил бы более одного числа в стеке в попытке оптимизировать скорость выполнения.

Проблема грубой силы

Для кодового набора из 15 символов время, необходимое для прохождения всех комбинаций заданной длины, определяется как

Т _лен = 15 * Т _лен-1

это означает, что если ваша программа работает в пятнадцать раз быстрее, чем моя, вы сможете проверить только одну дополнительную строку символов в одно и то же время. Для одновременной проверки еще двух символов программа должна работать в 225 раз быстрее. Время, затрачиваемое при использовании метода грубой силы, увеличивается экспоненциально по мере увеличения длины строк кода. И величина числа обязательно указывает количество байтов, необходимых для его генерации.

Некоторые цифры.

Приблизительное время создания списков кодов в 32-битном блокноте Windows 7 для целых чисел до

• 9: 1 мс
• 10: 16 мс
• 32: 156 мсек
• 81: 312 мсек
• 93: 18,5 секунд
• 132: 28 секунд

Генерация befunge для 3727 (что составляет 66 в квадрате плюс 6) сама по себе заняла 1 час 47 минут и сгенерировала 578*+:*6+

Оптимальная генерация кода

Генерация befunge для чисел без проверки на самые короткие длины является относительно простой. Используя рекурсивный алгоритм, который использовал целочисленные квадратные корни и остатки, кодирование для чисел до 132 заняло около 3 мсек вместо 28 секунд. Они не были оптимальными. Из-за того, как он работал, этот конкретный алгоритм 638:*-:*+генерировал для 3727 примерно 1 мсек (вместо часа или около того), что оказалось оптимальным.

Проблема с предоставлением метода не грубой силы доказывает, что он оптимален в каждом случае. Удачи!

JavaScript

Что можно сделать с помощью фрагмента JS? На моей машине Firefox 64 бит, 416 за 60 секунд

function go() {
    B.disabled=true
    O.textContent = '...wait...'
    setTimeout(run, 100)
}

function run()
{
	var o=[0],	
	t0=performance.now(),	
	te=t0+T.value*1000,
	k=[],t=[...'0123456789'],i=0,n=0,e,v,j,l,x,h
	MainLoop:
	for(;;)
	{
	  for(;!k[n] && (e=t[i++]);) 
	  {
	    if(performance.now()>te)break MainLoop
	    
	    for(v=[],j=0;x=e[j++];l=x)
	      1/x?h=v.push(+x):(b=v.pop(),x>'9'?h=v.push(b,b):(a=v.pop(),h=v.push(x<'+'?a*b:x<'-'?a+b:x<'/'?a-b:a/b|0)))
	    if(!k[v])
	    {
	      k[v]=e
	      //if(!e[10])
	      {
	        if (l==':')
	          t.push(e+'+',e+'*')
	        else if (h>1)
	        {
	          if (l == '1') t.push(e+'+',e+'-')
	          else if (l != '0') t.push(e+'+',e+'-',e+'*',e+'/')
	        }  
	        if (h<4)
	        {
	          if (l<'0'|l>'9') t.push(e+':');
	          [...'0123456789'].forEach(x => t.push(e+x))
	        }
	      }  
	    }
	  }
	  o.push([n,k[n]])
    ++n;
	}  
	o[0]='Run time sec '+(performance.now()-t0)/1000+'\nTried '+t.length+'\nRange 0..'+(n-1)+'\nTop '+k.pop()+' '+k.length
	O.textContent=o.join`\n`
    B.disabled=false
}

Time limit sec:<input id=T type=number value=60><button id=B onclick='go()'>GO</button>
<pre id=O></pre>