Collatz Conjecture

The challenge: Implement an an algorithm that simulates all numbers reaching the collatz conjecture using Dynamic Programming.

Take any positive integer n. If n is even, divide it by 2 to get n / 2. If n is odd, multiply it by 3 and add 1 to obtain 3n + 1. Repeat the process indefinitely. The conjecture is that no matter what number you start with, you will always eventually reach 1.

https://www.wikiwand.com/en/Collatz_conjecture

class Node {
public:
    Node(int val, int w) : connected_to(val), weight(w) {
        next = nullptr;
    }
    int connected_to;
    int weight; // weight of edge
    Node *next;
};

class LinkedList_edges {
public:
    LinkedList_edges() {
        front = end = nullptr;
    }

    void insert(int vertex, int weight) {
        Node *newNode = new Node(vertex, weight);

        if (isEmpty()) {
            front = end = newNode;
        }
        else {
            end->next = newNode;
            end = newNode;
        }
    }

    void traverse() {
        Node *temp = front;
        while (temp != nullptr) {
            cout << temp->connected_to << " -> ";
            temp = temp->next;
        }
        cout << endl;
    }


    // tranversing linked list to see if element exists
    bool exists(int number) {
        Node *temp = front;
        while (temp != nullptr) {
            if (number == temp->connected_to) {
                return true;
            }
            temp = temp->next;
        }
        return false;
    }

private:
    Node *front, *end;

    bool isEmpty() {
        return front == nullptr;
    }
};

// simulating friend network
class Graph {
public:
    Graph(bool dir) : directed(dir), n_verticies(0), n_edges(0) {
    }

    void addNumber(int number) {
        // error checking
        if (numberExists(number)) {
            cout << "number already exists" << endl;
            return;
        }

        // create new vertex
        LinkedList_edges *newnumber = new LinkedList_edges();
        // add to network
        graph.insert({ { number },{ newnumber } });
        ++n_verticies;
    }

    void removenumber(int number) {
        // error checking
        if (!numberExists(number) || graph.empty()) {
            cout << "number does not exist" << endl;
            return;
        }

        // removing a number will remove all connections
        // remove linked list, to avoid memory link
        delete graph.find(number)->second;
        graph.erase(number);
        --n_verticies;
    }

    void connectnumber(int source, int dest) {
        // error checking
        if (!numberExists(dest) || !numberExists(source)) {
            cout << "number(s) does not exists" << endl;
            return;
        }

        // are already friends
        if (graph.find(source)->second->exists(dest)) {
            cout << "number A is already friends with number B" << endl;
            return;
        }

        // add to network by adding to the linked list of friend
        const int weight = 1;
        graph.find(source)->second->insert(dest, weight);
        ++n_edges;
    }

    // check if number exists in the graph
    bool findNumber(int number) {
        if (graph.empty()) return false;
        // side note: This graph traversal is very slow
        // because we look at a visited node more than once


        // need to do a full graph traversal
        // I want to be able to tranverse in descending order
        // because then ill save time looking down the tree.
        // for each number in graph

        for (std::map<int, LinkedList_edges*>::reverse_iterator iter = graph.rbegin(); iter != graph.rend(); ++iter) {
            // first check all the the graph node itself
            if (iter->first == number) return true;

            // then check all its connections to see if the number exists in the graph
            if (iter->second->exists(number)) {
                return true;
            }
        }

        // exhausted all search
        return false;
    }


    void traverse() {
        for (auto& i : graph) {
            cout << i.first << ": ";
            graph.find(i.first)->second->traverse();
        }
    }

    int getNumVert() { return n_verticies; }
    int getNumEdges() { return n_edges; }

private:
    bool directed;
    int n_verticies, n_edges;

    // changed from unordered->map, because
    // when I iterate, I want to be able to
    // start from the largest number, and
    // iterate down the graph
    map<int, LinkedList_edges*> graph;

    bool numberExists(int number) {
        if (graph.find(number) == graph.end()) {
            return false;
        }
        return true;
    }
};


int main()
{
    Graph *number_network = new Graph(true);

    vector<int> sequence;

    // building the collatz graph
    for (int i = 2; i < 5000; i++) {
        // if the number exists in the network, then
        // we dont have to look further down the tree
        // otherwise we take that number, and follow the conjecture

        int newNum = i;
        int newNumCopy = newNum;
        bool found = number_network->findNumber(newNum);
        cout << "New Sequence: " << endl << endl;
        while (!found && newNum != 1) {
            cout << "Searching for number: " << newNum << endl;
            sequence.push_back(newNum);
            //pause();
            if (newNum % 2 == 0)
                newNum /= 2;
            else 
                newNum = (3 * newNum) + 1;

            found = number_network->findNumber(newNum);
        }
        sequence.push_back(newNum);

        // once newNum has proved to converge to 1, then
        // we can insert it's 'sequence' into the graph network

        // the number may have also been found, which we then must
        // insert the sequence of numbers that have not been found
        // and connect that sequence the number that has been found

        // in both cases, the algorithm is the same

        cout << newNumCopy << " has converged to " << newNum << endl;
        //pause();
        int src, dest;
        src = sequence.at(0);
        cout << "adding " << src << " to network" << endl;
        number_network->addNumber(src);

        for (int i = 0; i < sequence.size() - 1; i++) {
            src = sequence.at(i);
            dest = sequence.at(i + 1);

            number_network->addNumber(dest);
            cout << "adding " << dest << " to network" << endl;
            number_network->connectnumber(src, dest);
            cout << "connecting " << src << " -> " << dest << " to network" << endl;
            // 1 2
            // 1 -> 2
            // 1 -> 2 3
            // 1 -> 2 -> 3
        }
        sequence.clear();
        // look at the next number
    }
}