# Quickly express a number with only 0-9 and the four operations, plus one more extra

## Explanation

Befunge is a two-dimensional program that uses stacks.

That means, to do 5 + 6, you write 56+, meaning:

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)


However, we cannot push the number 56 directly into the stack.

To do so, we must write 78* instead, which multiplies 7 and 8 and pushes the product into the stack.

## Details

For each number from 1 to n, find a string consisting of only these characters: 0123456789+-*/: (I would not use % modulo.)

The goal is to find the shortest string that can represent the number, using the format described above.

For example, if the input is 123, then the output would be 67*9:*+. The output should be evaluated from left to right.

If there are more than one acceptable outputs (e.g. 99*67*+ is also acceptable), any one can be printed (no bonus for printing all of them).

## Further Explanation

If you still do not understand how 67*9:*+ evaluates to 123, here is a detailed explanation.

stack    |operation|explanation
67*9:*+
       6         push 6 to stack
[6,7]      7        push 7 to stack
        *       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
           +   pop two from stack and add, then put result to stack


## TL;DR

The program needs to find the shortest string that can represent the input (number), using the format specified above.

## SCORING

• We have already done it in the shortest amount of code. This time, size does not matter.
• Your language of choice has to have a free compiler/interpreter for my operating system (Windows 7 Enterprise).
• Bonus if you include the link to the compiler/interpreter (I am too lazy).
• If possible, please include a timer for my convenience. The output from the timer is valid.
• The score will be the largest n in 1 minute.
• That means, the program needs to print the required representation from 1 onward.
• No hard-coding, except 0 to 9.

## (more) SPECIFICS

• The program is invalid if it outputs a string longer than needed for any number.
• 1/0=ERROR
• 5/2=2, (-5)/2=-2, (-5)/(-2)=2, 5/(-2)=-2

## Disambiguation

The - is second-top minus top, meaning that 92- returns 7.

Likewise, the / is second-top divide top, meaning that 92/ returns 4.

# Lua

Uses depth-first search.

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

• Wait, if we can't push 56 directly into the stack, how can we push 78 into the stack? – R. Kap Apr 17 '16 at 1:52
• We can't push 56 fifty-six directly into the stack, but we can push 7 seven and 8 eight separately into the stack. – Leaky Nun Apr 17 '16 at 1:54
• @R.Kap: When you do something like 56 in Befunge, you're pushing the digits, so you end up with a stack of [5, 6]. To get the number 56, you have to push 7, then 8 onto the stack, and then multiply them to get the number 56 on the stack. – El'endia Starman Apr 17 '16 at 1:57
• : makes things a lot trickier, so I'd recommend supplying a good list of test cases, e.g. 86387 – Sp3000 Apr 17 '16 at 2:26
• largest integer in 5 seconds is a bad metric. the computational time for larger numbers will not increase monotonically, so many solutions can get stuck at the same hard-to-calculate number, despite some of them being much faster or slower on nearby numbers. – Sparr Apr 17 '16 at 3:38

# C++, exploding all memory on a computer near you

Generates the shortest string where the calculation nowhere causes an overflow of a signed 32-bit integer (so all intermediate results are in the range [-2147483648, 2147483647]

On my system this generates a solution for all numbers up to and including 483432 in 30 seconds while using 1.8G memory. Even higher numbers will quickly explode the memory usage. The highest number I can handle on my system is 5113906. The calculation takes almost 9 minutes and 24GB. When it finishes it internally has a solution for 398499338 values, about 9% of all 32 bit integers (positive and negative)

Needs a C++11 compiler. On linux compile with:

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


Add -DINT64 as an option to use a 64-bit integer range instead of 32-bit for intermediate results (this will use about 50% more time and memory). This needs a builtin 128 bit type. You may need to change the gcc type __int128. No result in at least the range [1..483432] changes by allowing larger intermediate results.

Add -DOVERFLOW as an option to not use a bigger integer type to check for overflow. This has the effect of allowing overflow and value wrapping.

If your system has tcmalloc (https://github.com/gperftools/gperftools) you can link with that resulting in a program that is generally a little faster and uses slightly less memory. On some UNIX systems you can use a preload, e.g.

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


Basic usage: generate and print all numbers up to target:

befour target


Options:

• -a Also print all numbers that were generated while working out target
• -c Also print all numbers that were generated starting with a "carry" (dup)
• -f Find and print the first number beyond target that was not generated
• -s Stop if target is generated even if not all numbers before were generated
• -S Like -s and -f in an automatic loop. As soon as target is generated find the first number not yet generated and make that the new target
• -E Don't immediately exit when the goal is reached. First finish all strings of the current length
• -O Don't output the strings for all numbers up to target. just the string for target
• -o Allowed instructions (defaults to +-*/:
• -b num Lowest literal that can be pushed (defaults to 0)
• -B num Highest literal that can be pushed (defaults to 9)
• -r num The lowest allowed intermediate result. Used to avoid underflow. (defaults to INT32_MIN, -2147483648
• -R num The highest allowed intermediate result. Used to avoid overflow. (defaults to INT32_MAX, 2147483647
• -m memory (linux only) exit when approximately this much extra memory has been allocated

Some interesting option combinations:

Generate all numbers up to target and calculate the smallest number that needs a longer generator than all these numbers:

befour -fE target


Generate only target (-s), print only target (-O)

befour -sO target


Find the highest number that can be generated on your system given time and/or memory constraints (This will run your system out of memory if you leave it running. Subtract 1 from the last "looking for" output you see as the last safe value):

befour -S 1


Generate solutions without ever using negative intermediate results (30932 is the first value that needs negative intermediate results for the shortest string):

befour -r0 target


Generate solutions without ever pushing 0 (this doesn't seem to lead to any suboptimal solutions):

befour -b1 target


Generate solutions including a..f (10..15):

befour -B15 target


Generate solutions without using dup : (add -r0 since negative intermediate values are never interesting for this case)

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


Find the first value that can not be generated for a given string length using just +, -, * and /:

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


This will in fact generate the first few terms of https://oeis.org/A181898, but will start to diverge at 14771 because we use truncating division so that number can be done with a length 13 string instead of length 15 as the OEIS series expects:

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


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


Since without truncation division seems pointless the OEIS series can be better generated by using

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


Assuming division remains useless this gave me 3 extra terms before I went out of memory:

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


Another version of this program storing part of the data in external files adds 135153107 and 675854293 after which all 32-bit integers have been generated.

## 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;

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] != '-' ||
argv[optind] == 0) return ch = 0;
if (argv[optind] == '-' && argv[optind] == 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 == ':' ? ':' : '?';
}
++optind;
nextchar = 0;
}
return ch;
}
}
};

using ms = chrono::milliseconds;

Int missing, N;
size_t cached, cached_next;

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 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;
carry_right = left;
// 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;
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
// 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);
}

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, 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 << " [-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;
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

// 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 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.

// 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) {
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";
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";
}
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";
}
}
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);
}


Some test cases:

• 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*:*+
• Nice work, this is impressively fast given the difficulty of the problem! Bit of trouble though: for 38950002 your program gives 89*7+:::**1-*, which is pretty good, but you can do 299*-::*:*+ for shorter. I think this confirms the doubts I had about negative numbers... – Sp3000 Apr 26 '16 at 15:04
• @Sp3000: Bummer, I had only considered positive numbers. It's not hard to extend the program to also handle negative numbers but I expect it will take a severe memory and speed hit – Ton Hospel Apr 26 '16 at 15:16
• @Sp3000 Updated for negative temporaries. The reachable range indeed went down quite a bit – Ton Hospel Apr 26 '16 at 17:20
• int main(int argc, char const* const* argv) I don't know C better than the average Joe but what's this? a const pointer to a const pointer to a char? Shouldn't it be char const *argv[] or so (or char const **argv if you're that hardcore)? – cat Apr 29 '16 at 22:29
• @cat It's a pointer to (an array of) constant pointers to (an array of) constant char. To make the top level pointer constant I would have to add yet another const directly in front of argv too (which would work since I don't change argv either). Basically I promise not to change the arguments or the pointers to the arguments. – Ton Hospel May 1 '16 at 20:27

# JavaScript Node Brute Force

### Program file bfCodes.js

function bfCodes( n)
{   var odo = , 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( (--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;
}
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);
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);


### Running under Windows

1. Download and install Nodejs, a stand alone implementation of Chromes V8 JavaScript engine.
2. Save the program file above in a working directory using file name "bfCodes.js" (Windows filenames are case insensitive).
3. Right click in the working directory and create a shortcut to the command shell program (DOS box for oldies) with target cmd.exe
4. Edit the shortcut's properties and set the working folder to the name of your working directory (click in the location bar and copy).
5. Open cmd.exe using the shortcut and check the DOS prompt starts with the working directory
6. Enter "node bfCodes" without quotes and enter - runing node the first time can take longer than running it again.
7. Enter "node bfCodes 16" to show codes up to 16. Do not use a large number!

## Optimization

The algorithm cycles through all combinations of befunge characters starting with a code string of length 1. Think of it as spinning a base 15 odometer from the least significant digit. Higher order digits click over with increasing slowness. bfCodes does not evaluate generated code that would make the stack length zero or negative or leave more than one number on the stack in an attempt to optimize speed of execution.

## The Brute Force Problem

For a code set of 15 characters, the time it takes to run through all combinations of a given length is give by

Tlen = 15 * Tlen-1

which is to say that if your program runs fifteen times faster than mine, you will only be able to check one additional character code strings in the same time. To check two more characters in the same time a program would need to run 225 times faster. Time taken with a brute force approach rises exponentially as the length of code strings increases. And the magnitude of a number does necessarily indicate the number of befunge bytes needed to generate it.

### Some figures.

Approximate times to generate a lists of codes on a Windows 7 32 bit notepad for integers up to

• 9: 1 msec
• 10: 16 msec
• 32: 156 msec
• 81: 312 msec
• 93: 18.5 seconds
• 132: 28 seconds

To generate befunge for 3727 (which is 66 squared plus 6) by itself took 1 hour 47 minutes and generated 578*+:*6+

## Optimal code generation

Generating befunge for numbers without checking for shortest lengths is relatively simple. Using a recursive algorithm which used integer square roots and remainders, encodings for numbers up to 132 took about 3 msec instead of 28 seconds. They were not optimal. Because of the way it worked this particular algorithm produced638:*-:*+ for 3727 in about 1 msec (instead of an hour or so) which happened to be optimal.

The issue with providing a non brute force method is proving it is optimal in every case. Good luck!

• You should be able to lower your exponent by a lot by observing that your string must represent a valid evaluation tree with +-*/ at the inner nodes and 0-9 and : at the leaves (and : cannot be leftmost). So generate and evaluate all valid tree of size 2*n+1 at step n (n starts from 0) and convert them to a strings when needed – Ton Hospel Apr 27 '16 at 22:33
• 3727 is 61 squared plus 6, not 66 :) – Tim Vermeulen Apr 28 '16 at 8:35

# JavaScript

Whant can be done with a JS snippet? In my machine, Firefox 64 bit, 416 in 60 seconds

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

function run()
{
var o=,
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)
{
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='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>