brusselSearch.cpp

#include <iostream>
#include <unordered_map>
#include <queue>
#include <vector>
#include <algorithm>
#include "32baseten.h"
#include <cstdint>

using namespace std;

unordered_map<unsigned int, tuple<uint8_t, uint8_t, bool >> steps; // steps[num] offset, length, operation(0=dobl 1=half)

// Function to find the minimal number of steps to reach m from n using Choix de Bruxelles rules
vector<unsigned int> brusselSearch(unsigned int n, unsigned int m, double l) {
    queue<unsigned int> branch;

    steps[m]={0,m,1};
    branch.push(m);

    //biggest possible value
    unsigned int largest = n>m ? n : m ;
    //speeds up significantly, but if too low this can skip good paths
    //21 of numbers from 1 to 1000 have steps that are 10-20x larger than n or m
    //4 of the numbers: 539 389 3 and 289 has steps 20x to 39x
    //999 has an optimal path that has a step of 92x. But also has an optimal path that's <10x
    //these anomalies become even rarer the bigger m or n gets
    //1599 ratio: 69.536
    //10x is good starting point. Increase to confirm optimal path for a specific number.
    largest*=l;

    unsigned long long iters = 0;

    while (!branch.empty()) {
        unsigned int curr = branch.front();
        branch.pop();

        if (curr == n) {
            // Reconstruct the steps sequence, repeat steps in reverse
            vector<unsigned int> sequence;
            while (curr != m) {
                sequence.push_back(curr);
                bool operation = get<2>(steps[curr]);
                if (operation==0) {
                    curr = brusselDouble(curr, get<0>(steps[curr]), get<1>(steps[curr]));
                } else if (operation==1) {
                    curr = brusselDivide(curr, get<0>(steps[curr]), get<1>(steps[curr]));
                }
            }
            sequence.push_back(m);

            cout << iters << " Brussel operations\n";
            return sequence;
        }

        // Generate new numbers by doubling or dividing substrings
        int currLen = logt10(curr);
        for (uint8_t i = 0; i < currLen; i++) {
            for (uint8_t j = i + 1; j <= currLen; j++) {

                unsigned int newNum = brusselDouble(curr, i, j-i);
                bool tooBig = newNum>largest;
                bool overflow = newNum<curr;
                if ( !tooBig && steps.find(newNum) == steps.end() && !overflow) {
                    iters++;
                    int magDif = ( (int)logt10(newNum)-(int)logt10(curr) ); // magnitude difference for reconstructing sequence, 0 or doubling +1 or halving -1
                    steps[newNum] = {i, j-i+magDif, 1}; //{offset, len+magdif, inverse operation} rules to go back from newNum to curr
                    branch.push(newNum); //insert to queue
                }

                newNum = brusselDivide(curr, i, j-i);
                if (newNum && steps.find(newNum) == steps.end()) {
                    iters++;
                    int magDif = ( (int)logt10(newNum)-(int)logt10(curr) );
                    steps[newNum] = {i, j-i+magDif, 0};
                    branch.push(newNum);
                }

            }
        }
    }

    // If no path is found
    return vector<unsigned int>();
}

int main(int argc, char** argv){
    unsigned int start = 999;
    unsigned int target = 1;
    double maxmult = 10;

    if( argc>1 ){
        start = stoll(argv[1]);
    }
    if( argc>2 ){
        target = stoll(argv[2]);
    }
    if( argc>3 ){
        maxmult = stoll(argv[3]);
    }

    if( (start%5==0) != (target%5==0) ){
        cout << "Can't be reached\n";
        return 0;
    }

    vector<unsigned int> sequence = brusselSearch(start,target,maxmult);

    if (!sequence.empty()) {
        cout << "Steps: " << sequence.size()-1 << "\n";
        if(start>target){
            for (auto it = sequence.begin(); it != sequence.end(); ++it) {
                cout << *it << "\n";
            }
        }else{
            for (auto it = sequence.rbegin(); it != sequence.rend(); ++it) {
                cout << *it << "\n";
            }
        }

        cout << "\n";

        start = start>target ? start : target; //bigger of the starting values

        auto big = max_element(sequence.begin(), sequence.end()); //biggest in sequence

        cout << "ratio: " << (double)*big/start << "\n";
    } else {
        cout << "No path found \n";
    }

    return 0;
}