Wyjaśnienie

Befunge to dwuwymiarowy program, który wykorzystuje stosy .

Oznacza to, że aby zrobić 5 + 6, piszesz 56+, co oznacza:

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)

Nie możemy jednak wcisnąć liczby 56bezpośrednio na stos.

Aby to zrobić, musimy napisać 78*zamiast, który mnoży 7i 8i popycha produkt na stosie.

Detale

Dla każdej liczby od 1don , znaleźć ciąg składający się tylko z tych znaków: 0123456789+-*/:(I byłoby nie wykorzystać %modulo).

Celem jest znalezienie najkrótszego ciągu, który może reprezentować liczbę, przy użyciu formatu opisanego powyżej.

Na przykład, jeśli dane wejściowe to 123, dane wyjściowe będą67*9:*+ . Dane wyjściowe należy oceniać od lewej do prawej.

Jeśli istnieje więcej niż jeden akceptowalny wynik (np 99*67*+ Jest również akceptowalny), można wydrukować dowolny z nich (bez premii za wydrukowanie wszystkich).

Dalsze wyjaśnienia

Jeśli nadal nie rozumiesz, jak 67*9:*+oceniać 123, oto szczegółowe wyjaśnienie.

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

Program musi znaleźć najkrótszy ciąg znaków, który może reprezentować dane wejściowe (liczbę), przy użyciu formatu określonego powyżej.

PUNKTACJA

• Zrobiliśmy to już przy użyciu jak najmniejszej ilości kodu . Tym razem rozmiar nie ma znaczenia.
• Twój wybrany język musi mieć darmowy kompilator / tłumacz dla mojego systemu operacyjnego (Windows 7 Enterprise).
• Bonus, jeśli podasz link do kompilatora / tłumacza (jestem zbyt leniwy).
• Jeśli to możliwe, proszę podać licznik czasu dla mojej wygody. Dane wyjściowe z timera są prawidłowe.
• Wynik będzie największy nw ciągu 1 minuty.
• Oznacza to, że program musi wydrukować wymaganą reprezentację 1 .
• Nie trudno kodowania, z wyjątkiem 0do 9.

(więcej) SPECYFIKACJA

• Program jest nieprawidłowy, jeśli generuje ciąg dłuższy niż wymagany dla dowolnej liczby.
• 1/0=ERROR
• 5/2=2, (-5)/2=-2, (-5)/(-2)=2,5/(-2)=-2

Ujednoznacznienie

-Jest second-top minus top, co oznacza, że 92-zyski7 .

Podobnie /jest second-top divide top, co oznacza, że 92/zwraca4 .

Przykładowy program

Lua

Używa wyszukiwania w pierwszej kolejności.

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 ++, wybuchając całą pamięcią na komputerze w pobliżu

Generuje najkrótszy ciąg, w którym obliczenia nigdzie nie powodują przepełnienia 32-bitowej liczby całkowitej ze znakiem (więc wszystkie wyniki pośrednie znajdują się w zakresie [-2147483648, 2147483647]

W moim systemie generuje to rozwiązanie dla wszystkich liczb do 48343230 sekund włącznie przy użyciu pamięci 1.8G. Nawet wyższe liczby szybko zwiększą zużycie pamięci. Najwyższą liczbą, jaką mogę obsłużyć w moim systemie, jest 5113906. Obliczenie zajmuje prawie 9 minut i 24 GB. Po zakończeniu ma wewnętrznie rozwiązanie398499338 wartości, około 9% wszystkich 32-bitowych liczb całkowitych (dodatnich i ujemnych)

Potrzebuje kompilatora C ++ 11. Na Linux-ie skompiluj z:

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

Dodaj -DINT64jako opcję użycia 64-bitowego zakresu liczb całkowitych zamiast 32-bitowego dla wyników pośrednich (zajmie to około 50% więcej czasu i pamięci). To wymaga wbudowanego 128-bitowego typu. Może być konieczna zmiana typu gcc __int128. Brak wyników w co najmniej zakresie[1..483432] zmiany przez umożliwienie większych wyników pośrednich.

Dodaj -DOVERFLOW jako opcję, aby nie używać większego typu liczby całkowitej do sprawdzania przepełnienia. Pozwala to na przepełnienie i zawijanie wartości.

Jeśli twój system ma tcmalloc ( https://github.com/gperftools/gperftools ), możesz połączyć się z tym, co powoduje, że program jest na ogół nieco szybszy i zużywa nieco mniej pamięci. W niektórych systemach UNIX można użyć wstępnego ładowania, np

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

Podstawowe użycie: generuj i drukuj wszystkie liczby do celu:

befour target

Opcje:

• -a Wydrukuj również wszystkie liczby, które zostały wygenerowane podczas opracowywania celu
• -c Wydrukuj również wszystkie liczby, które zostały wygenerowane, zaczynając od „carry” (dup)
• -f Znajdź i wydrukuj pierwszą liczbę poza celem, która nie została wygenerowana
• -s Zatrzymaj, jeśli cel zostanie wygenerowany, nawet jeśli nie wszystkie liczby zostały wcześniej wygenerowane
• -SJak -siw -fautomatycznej pętli. Po wygenerowaniu celu znajdź pierwszy numer, który nie został jeszcze wygenerowany i uczyń go nowym celem
• -ENie wychodź natychmiast po osiągnięciu celu. Najpierw zakończ wszystkie ciągi bieżącej długości
• -ONie wyprowadzaj ciągów dla wszystkich liczb do celu. tylko ciąg dla celu
• -o Dozwolone instrukcje (domyślnie +-*/:
• -b numNajniższy literał, który można przesunąć (domyślnie 0)
• -B numNajwyższy literał, który można wcisnąć (domyślnie 9)
• -r numNajniższy dozwolony wynik pośredni. Służy do uniknięcia niedomiaru. (domyślnie INT32_MIN,-2147483648
• -R numNajwyższy dozwolony wynik pośredni. Służy do uniknięcia przepełnienia. (domyślnie INT32_MAX,2147483647
• -m memory (tylko linux) kończy się, gdy w przybliżeniu tyle pamięci zostanie przydzielone

Kilka interesujących kombinacji opcji:

Wygeneruj wszystkie liczby do celu i oblicz najmniejszą liczbę, która potrzebuje dłuższego generatora niż wszystkie te liczby:

befour -fE target

Generuj tylko cel (-s), drukuj tylko cel (-O)

befour -sO target

Znajdź najwyższą liczbę, jaką można wygenerować w systemie, biorąc pod uwagę ograniczenia czasowe i / lub pamięciowe (spowoduje to brak pamięci w systemie, jeśli pozostawisz go uruchomioną. Odejmij 1 z ostatniego wyjścia „szukającego”, które widzisz jako ostatnią bezpieczną wartość ):

befour -S 1

Generuj rozwiązania bez użycia negatywnych wyników pośrednich ( 30932jest to pierwsza wartość, która wymaga negatywnych wyników pośrednich dla najkrótszego ciągu):

befour -r0 target

Generuj rozwiązania bez wypychania 0(wydaje się, że nie prowadzi to do nieoptymalnych rozwiązań):

befour -b1 target

Generuj rozwiązania, w tym a..f (10..15):

befour -B15 target

Generuj rozwiązania bez użycia dup :(dodaj, -r0ponieważ ujemne wartości pośrednie nigdy nie są interesujące w tym przypadku)

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

Znajdź pierwszą wartość, która nie może być generowany dla danej długości łańcucha przy użyciu tylko +, -, *i /:

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

To faktycznie wygeneruje kilka pierwszych haseł https://oeis.org/A181898 , ale zacznie się różnić, 14771ponieważ używamy podziału obcięcia, dzięki czemu liczba może być wykonana za pomocą łańcucha 13 zamiast długości 15 jako serii OEIS oczekuje:

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

zamiast

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

Ponieważ bez podziału na obcinanie wydaje się bezcelowe, można lepiej wygenerować serię OEIS za pomocą

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

Zakładając, że podział pozostaje bezużyteczny, to dało mi 3 dodatkowe warunki, zanim straciłem pamięć:

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

Inna wersja tego programu przechowująca część danych w plikach zewnętrznych dodaje 135153107 i 675854293, po czym zostały wygenerowane wszystkie 32-bitowe liczby całkowite.

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);
}

Niektóre przypadki testowe:

• 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 Node Brute Force

Plik programu 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);

Działa w systemie Windows

1. Pobierz i zainstaluj Nodejs , samodzielną implementację silnika JavaScript Chromes V8.
2. Zapisz powyższy plik programu w katalogu roboczym, używając nazwy pliku „bfCodes.js” (nazwy plików systemu Windows nie uwzględniają wielkości liter).
3. Kliknij katalog roboczy prawym przyciskiem myszy i utwórz skrót do programu powłoki poleceń (pole DOS dla starych) z celem cmd.exe
4. Edytuj właściwości skrótu i ​​ustaw folder roboczy na nazwę katalogu roboczego (kliknij pasek lokalizacji i skopiuj).
5. Otwórz cmd.exeza pomocą skrótu i ​​sprawdź, czy monit DOS zaczyna się od katalogu roboczego
6. Wpisz „node bfCodes” bez cudzysłowów i po raz pierwszy uruchom węzeł - może potrwać dłużej niż ponowne uruchomienie.
7. Wpisz „node bfCodes 16”, aby wyświetlić kody do 16. Nie używaj dużej liczby!

Optymalizacja

Algorytm przełącza wszystkie kombinacje znaków befunge, zaczynając od ciągu kodu o długości 1. Pomyśl o tym jak o obracaniu podstawowego 15-metrowego przebiegu od najmniej znaczącej cyfry. Cyfry wyższego rzędu klikają z rosnącym spowolnieniem. bfCodesnie ocenia wygenerowanego kodu, który spowodowałby, że długość stosu byłaby zerowa lub ujemna, lub pozostawiłaby na stosie więcej niż jedną liczbę, próbując zoptymalizować szybkość wykonywania.

Problem brutalnej siły

W przypadku zestawu kodów złożonego z 15 znaków czas potrzebny na przejście przez wszystkie kombinacje danej długości jest równy

T _len = 15 * T _len-1

co oznacza, że ​​jeśli twój program działa piętnaście razy szybciej niż mój, będziesz mógł sprawdzić tylko jeden dodatkowy ciąg znaków w tym samym czasie. Aby sprawdzić dwa kolejne znaki w tym samym czasie, program musiałby działać 225 razy szybciej. Czas potrzebny na brutalne podejście rośnie wykładniczo wraz ze wzrostem długości ciągów kodu. Wielkość liczby niekoniecznie wskazuje liczbę bajtów befunge potrzebnych do jej wygenerowania.

Niektóre liczby.

Przybliżony czas wygenerowania list kodów w 32-bitowym notatniku systemu Windows 7 dla liczb całkowitych do

• 9: 1 milisekunda
• 10: 16 ms
• 32: 156 milisekund
• 81: 312 ms
• 93: 18,5 sekundy
• 132: 28 sekund

Samo wygenerowanie befunge dla 3727 (czyli 66 do kwadratu plus 6) zajęło 1 godzinę 47 minut i wygenerowano 578*+:*6+

Optymalne generowanie kodu

Generowanie befunge dla liczb bez sprawdzania najkrótszych długości jest stosunkowo proste. Przy użyciu algorytmu rekurencyjnego, który używał całkowitych pierwiastków kwadratowych i reszt, kodowanie liczb do 132 zajęło około 3 ms zamiast 28 sekund. Nie były optymalne. Ze względu na sposób, w jaki działał ten konkretny algorytm wyprodukowany 638:*-:*+dla 3727 w około 1 ms (zamiast godziny), który okazał się optymalny.

Problem z dostarczeniem metody nie brutalnej siły dowodzi, że jest ona optymalna w każdym przypadku. Powodzenia!

JavaScript

Co można zrobić za pomocą fragmentu kodu JS? Na moim komputerze Firefox 64-bitowy, 416 w 60 sekund

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>