Explication

Befunge est un programme en deux dimensions qui utilise des piles .

Cela signifie que pour faire 5 + 6, vous écrivez 56+, ce qui signifie:

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)

Cependant, nous ne pouvons pas pousser le nombre 56directement dans la pile.

Pour ce faire, il faut écrire à la 78*place, qui se multiplie 7et 8et pousse le produit dans la pile.

Détails

Pour chaque numéro de 1àn , trouver une chaîne composée de seulement ces caractères: 0123456789+-*/:(je n'utiliser modulo.)%

Le but est de trouver la chaîne la plus courte pouvant représenter le nombre, en utilisant le format décrit ci-dessus.

Par exemple, si l'entrée est 123, alors la sortie le serait 67*9:*+. La sortie doit être évaluée de gauche à droite.

S'il y a plus d'une sortie acceptable (par exemple, elle 99*67*+est également acceptable), n'importe laquelle peut être imprimée (pas de bonus pour toutes les imprimer).

Plus d'explications

Si vous ne comprenez toujours pas comment est 67*9:*+évalué 123, voici une explication détaillée.

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

Le programme doit trouver la chaîne la plus courte pouvant représenter l'entrée (nombre), en utilisant le format spécifié ci-dessus.

NOTATION

Nous l'avons déjà fait en un minimum de code . Cette fois, la taille n'a pas d'importance.
La langue de votre choix doit avoir un compilateur / interprète gratuit pour mon système d'exploitation (Windows 7 Enterprise).
Bonus si vous incluez le lien vers le compilateur / interprète (je suis trop paresseux).
Si possible, veuillez inclure une minuterie pour ma commodité. La sortie du temporisateur est valide.
Le score sera le plus élevé nen 1 minute.
Cela signifie que le programme doit imprimer la représentation requise à 1partir de maintenant.
Pas de codage en dur, sauf 0pour 9.

(plus) SPÉCIFIQUE

Le programme n'est pas valide s'il génère une chaîne plus longue que nécessaire pour n'importe quel nombre.
1/0=ERROR
5/2=2, (-5)/2=-2, (-5)/(-2)=2,5/(-2)=-2

Désambiguïsation

Le -est second-top minus top, ce qui signifie que 92-revient 7.

De même, le /est second-top divide top, ce qui signifie que 92/revient 4.

Exemple de programme

Lua

Utilise la recherche en profondeur.

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

fastest-code Leaky Nun
la source

Attendez, si nous ne pouvons pas pousser 56directement dans la pile, comment pouvons-nous pousser 78dans la pile?

R. Kap

Nous ne pouvons pas pousser 56cinquante-six directement dans la pile, mais nous pouvons pousser 7sept et 8huit séparément dans la pile.

Leaky Nun

@ R.Kap: Lorsque vous faites quelque chose comme 56dans Befunge, vous poussez les chiffres , vous vous retrouvez donc avec une pile de [5, 6]. Pour obtenir le numéro 56, vous devez pousser 7, puis 8sur la pile, puis les multiplier pour obtenir le numéro 56 sur la pile.

El'endia Starman

:rend les choses beaucoup plus délicates, donc je recommanderais de fournir une bonne liste de cas de test, par exemple86387

Sp3000

le plus grand entier en 5 secondes est une mauvaise métrique. le temps de calcul pour les grands nombres n'augmentera pas de façon monotone, de nombreuses solutions peuvent donc rester bloquées sur le même nombre difficile à calculer, bien que certaines soient beaucoup plus rapides ou plus lentes sur les nombres proches.

Sparr

C ++, exploser toute la mémoire sur un ordinateur près de chez vous

Génère la chaîne la plus courte où le calcul ne provoque aucun débordement d'un entier signé 32 bits (donc tous les résultats intermédiaires sont dans la plage [-2147483648, 2147483647]

Sur mon système, cela génère une solution pour tous les numéros jusqu'à et y compris 483432en 30 secondes lors de l'utilisation de la mémoire 1.8G. Des nombres encore plus élevés exploseront rapidement l'utilisation de la mémoire. Le nombre le plus élevé que je peux gérer sur mon système est 5113906. Le calcul prend près de 9 minutes et 24 Go. Quand il termine, il a en interne une solution pour les 398499338valeurs, environ 9% de tous les entiers 32 bits (positifs et négatifs)

Nécessite un compilateur C ++ 11. Sous Linux, compilez avec:

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

Ajoutez -DINT64une option pour utiliser une plage entière de 64 bits au lieu de 32 bits pour les résultats intermédiaires (cela utilisera environ 50% de temps et de mémoire en plus). Cela nécessite un type 128 bits intégré. Vous devrez peut-être modifier le type de gcc __int128. Aucun résultat dans au moins la plage [1..483432]change en permettant des résultats intermédiaires plus importants.

Ajoutez -DOVERFLOWcomme option pour ne pas utiliser un type entier plus grand pour vérifier le débordement. Cela a pour effet d'autoriser le débordement et l'encapsulation de valeur.

Si votre système dispose de tcmalloc ( https://github.com/gperftools/gperftools ), vous pouvez créer un lien avec celui-ci, ce qui donne un programme qui est généralement un peu plus rapide et utilise un peu moins de mémoire. Sur certains systèmes UNIX, vous pouvez utiliser une précharge, par exemple

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

Utilisation de base: générer et imprimer tous les nombres jusqu'à la cible:

befour target

Options:

-a Imprimez également tous les nombres générés lors de l'élaboration de la cible
-c Imprimez également tous les nombres générés en commençant par un "carry" (dup)
-f Rechercher et imprimer le premier nombre au-delà de la cible qui n'a pas été généré
-s Arrêter si la cible est générée même si tous les numéros précédents n'ont pas été générés
-SComme -set -fdans une boucle automatique. Dès que la cible est générée, trouvez le premier numéro non encore généré et faites que la nouvelle cible
-ENe quittez pas immédiatement lorsque l'objectif est atteint. Terminez d'abord toutes les cordes de la longueur actuelle
-ONe sortez pas les chaînes pour tous les nombres jusqu'à la cible. juste la chaîne pour la cible
-o Instructions autorisées (par défaut à +-*/:
-b numLittéral le plus bas pouvant être poussé (par défaut 0)
-B numLittéral le plus élevé pouvant être poussé (par défaut 9)
-r numLe résultat intermédiaire le plus bas autorisé. Utilisé pour éviter les débordements. (par défaut INT32_MIN,-2147483648
-R numLe résultat intermédiaire le plus élevé autorisé. Utilisé pour éviter les débordements. (par défaut INT32_MAX,2147483647
-m memory (linux uniquement) quitte quand approximativement autant de mémoire supplémentaire a été allouée

Quelques combinaisons d'options intéressantes:

Générez tous les nombres jusqu'à la cible et calculez le plus petit nombre qui nécessite un générateur plus long que tous ces nombres:

befour -fE target

Générer uniquement la cible (-s), imprimer uniquement la cible (-O)

befour -sO target

Trouvez le nombre le plus élevé qui peut être généré sur votre système en fonction des contraintes de temps et / ou de mémoire (cela entraînera une insuffisance de mémoire de votre système si vous le laissez en cours d'exécution. Soustrayez 1 de la dernière sortie "recherche" que vous voyez comme la dernière valeur sûre ):

befour -S 1

Générez des solutions sans jamais utiliser de résultats intermédiaires négatifs ( 30932est la première valeur qui nécessite des résultats intermédiaires négatifs pour la chaîne la plus courte):

befour -r0 target

Générez des solutions sans jamais pousser 0(cela ne semble pas conduire à des solutions sous-optimales):

befour -b1 target

Générez des solutions comprenant a..f (10..15):

befour -B15 target

Générer des solutions sans utiliser dup :(ajouter -r0car les valeurs intermédiaires négatives ne sont jamais intéressantes dans ce cas)

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

Trouvez la première valeur qui ne peut être générée pour une longueur de chaîne donnée en utilisant seulement +, -, *et /:

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

Cela générera en fait les premiers termes de https://oeis.org/A181898 , mais commencera à diverger 14771car nous utilisons la division tronquée afin que le nombre puisse être fait avec une chaîne de longueur 13 au lieu de 15 comme la série OEIS attend:

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

au lieu de

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

Étant donné que sans division de troncature semble inutile, la série OEIS peut être mieux générée en utilisant

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

En supposant que la division reste inutile, cela m'a donné 3 termes supplémentaires avant de perdre la mémoire:

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

Une autre version de ce programme stockant une partie des données dans des fichiers externes ajoute 135153107 et 675854293, après quoi tous les entiers 32 bits ont été générés.

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

Quelques cas de test:

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*:*+

Ton Hospel
la source

Beau travail, c'est incroyablement rapide étant donné la difficulté du problème! Un peu de problème cependant: pour 38950002votre programme donne 89*7+:::**1-*, ce qui est assez bon, mais vous pouvez le faire 299*-::*:*+pour plus court. Je pense que cela confirme les doutes que j'avais sur les nombres négatifs ...

Sp3000

@ Sp3000: Bummer, je n'avais considéré que des nombres positifs. Il n'est pas difficile d'étendre le programme pour qu'il gère également les nombres négatifs, mais je m'attends à ce que cela prenne un grave coup de mémoire et de vitesse

Ton Hospel

@ Sp3000 Mis à jour pour les temporaires négatifs. La gamme accessible a en effet beaucoup baissé

Ton Hospel

int main(int argc, char const* const* argv)Je ne connais pas mieux C que le Joe moyen mais qu'est-ce que c'est? un pointeur const vers un pointeur const vers un caractère? Ne devrait-il pas en être char const *argv[]ainsi (ou char const **argvsi vous êtes aussi hardcore)?

chat

@cat C'est un pointeur vers (un tableau de) pointeurs constants vers (un tableau de) char constant. Pour que le pointeur de niveau supérieur soit constant, je devrais également ajouter un autre const directement devant argv (ce qui fonctionnerait puisque je ne change pas argv non plus). Fondamentalement, je promets de ne pas modifier les arguments ou les pointeurs vers les arguments.

Ton Hospel

Exprimez rapidement un nombre avec seulement 0-9 et les quatre opérations, plus un supplémentaire

Explication

Détails

Plus d'explications

TL; DR

NOTATION

(plus) SPÉCIFIQUE

Désambiguïsation

Exemple de programme

Lua

Réponses:

C ++, exploser toute la mémoire sur un ordinateur près de chez vous

`befour.cpp`

Node JavaScript Brute Force

Fichier programme bfCodes.js

Sous Windows

Optimisation

Le problème de la force brute

Quelques chiffres.

Génération de code optimale

Javascript