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

```cpp
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
    }
}
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://maksimdan.gitbook.io/interview-practice-problems/leetcode_sessions/mathematics/collatz-conjecture.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.