bunch of S5's :nerd:

kingMonkeh · Apr 18, 2023 · ebd0018 · ebd0018
1 parent a2830e3
commit ebd0018
Show file tree

Hide file tree

Showing 10 changed files with 999 additions and 0 deletions.
diff --git a/2006 S5 - Origin of Life.cpp b/2006 S5 - Origin of Life.cpp
@@ -0,0 +1,160 @@
+/*
+
+2006 S5 - Origin of Life
+
+Difficulty: Hard
+
+Basically, since the grid is only like 20 cells at max
+You can actually just generate every single possible cell arrangement
+Afterward, you find the next generation for each arrangement
+
+What you've essentially done, is created a graph
+Where each arrangement is a node, and an edge shows that this generation comes from the previous generation
+
+Therefore from this graph, we can just perform a breadth first search from the starting arrangement
+Until we find a garden of eden since it would have no nodes after it
+
+The main problem however is that its not really possible to use a 2-D array as a node
+Notice that each cell can only have 2 states, alive or dead
+We can represent these as true or false, or as 1's and 0's
+What else can we represent using 1's and 0's? Binary.
+
+Essentially, we will view the 2-D array as a binary number and we will convert it into base 10 decimal to represent it as a single integer which will act as our nodes
+
+From here, it's very easy
+
+*/
+
+#include <iostream>
+#include <math.h>
+#include <queue>
+#include <vector>
+#include <string.h>
+
+int m, n, a, b, c;
+
+std::vector<int> previous [1048576 + 1];
+
+//Find next generation given an arrangement
+void findNextGen(int binary){
+
+    int original = binary; //Make copy for later
+    int current [m + 2][n + 2];
+    memset(current, 0, sizeof(current));
+
+    //Pad the array with a border so that we don't have to manually check border ourselves
+    //Convert decimal back to binary
+    for (int i = 1; i < m + 1; i++){
+        for (int j = 1; j < n + 1; j++){
+            current[i][j] = binary % 2;
+            binary /= 2;
+        }
+    }
+
+    int nextGen = 0;
+    int power = 1;
+
+    //Find next gen    
+    for (int i = 1; i < m + 1; i++){
+        for (int j = 1; j < n + 1; j++){
+
+            //Count alive neighbours
+            int alive = 0;
+            alive += current[i - 1][j]; //Up
+            alive += current[i + 1][j]; //Down
+            alive += current[i][j - 1]; //Left
+            alive += current[i][j + 1]; //Right
+            alive += current[i - 1][j - 1]; //Top Left
+            alive += current[i - 1][j + 1]; //Top right
+            alive += current[i + 1][j - 1]; //Bottom left
+            alive += current[i + 1][j + 1]; //Bottom right
+
+            //If the cell was already alive
+            if (current[i][j]){
+                if (alive >= a && alive <= b){
+                    nextGen += power;
+                }
+            }
+
+            //If the cell was previously dead
+            else{
+                if (alive > c){
+                    nextGen += power;
+                }
+            }
+
+            power *= 2;
+
+        }
+    }
+
+    //Add to graph
+    previous[nextGen].push_back(original);
+
+}
+
+int main(){
+
+    std::cin >> m >> n >> a >> b >> c;
+
+    //Get decimal of starting node
+    int start = 0;
+    int powOf2 = 1;
+    for (int i = 0; i < m; i++){
+        for (int j = 0; j < n; j++){
+            char x;
+            std::cin >> x;
+            //Cell is alive
+            if (x == '*'){
+                start += powOf2;
+            }
+            powOf2 *= 2;
+        }
+    }   
+
+    //Generate graph
+    for (int i = 0; i <= pow(2, m * n); i++){
+        findNextGen(i);
+        //;
+    }
+
+    //BFS
+    std::vector<int> visited (1048576 + 1, 0);
+    std::vector<int> distance (1048576 + 1, 0);
+    std::queue<int> q;
+    q.push(start);
+    visited[start] = true;
+
+    //DEBUGGING
+    //for (auto& prev: previous[start]){
+    //        std::cout << prev << ' ';
+    //}
+
+    int steps = 0;
+    while (!q.empty()){
+        int curr = q.front(); q.pop();
+        //If garden of eden
+        if (previous[curr].size() == 0){
+            std::cout << distance[curr] << '\n';
+            return 0;
+        }
+        for (auto& prev: previous[curr]){
+            if (!visited[prev]){
+                q.push(prev);
+                distance[prev] = distance[curr] + 1;
+                visited[prev] = true;
+            }
+        }
+        //funny cheat, basically if it takes more than 50 nodes, then theres no garden of eden
+        steps++;
+        if (steps == 50){
+            std::cout << -1 << '\n';
+            return 0;
+        }
+    }
+
+    std::cout << -1 << '\n';
+
+    return 0;
+
+}
diff --git a/2010 S5 - Nutrient Tree.cpp b/2010 S5 - Nutrient Tree.cpp
@@ -0,0 +1,171 @@
+/*
+
+2010 S5 - Nutrient Tree
+
+Difficulty: Very Hard
+
+Basically for each non-leaf node
+It has 2 children
+
+  N
+ / \
+L   R
+
+Basically, we make dp array where dp[i][j] tells us the max nutrients, node i can transport with j growth agents given to it
+To calculate this value for non leaf nodes, its the dp[i][j] values of its 2 children added together
+Note that the edge may be limiting, so take into account the edge as well
+If its a leaf node, you just try every amount of growth agent on the node itself and on its edge
+
+for this problem, i think its easier to explain with actual code
+
+*/
+
+#include <iostream>
+#include <string>
+#include <stack>
+
+#define leftChild node * 2
+#define rightChild node * 2 + 1
+
+int X;
+int tree [10000];
+int dp[10000][2501];
+int leftRight[10000][2501];
+int answer = 0;
+
+void dfs(int node){
+
+    //Leaf node
+    if (tree[node]){
+
+        //For every growth agent amount
+        for (int i = 0; i <= X; i++){
+            //From the current amount of growth agent that can be used, try giving every possible value to the edge
+            for (int e = 0; e <= i; e++){
+                int nodeGrowth = i - e; //Total growth agents - agents given to edge = growth agents left for node
+                //Remember that the edge may be limiting, so you have to take min
+                //dp[node][i] = max(itself, min(node + growth, edge capacity))
+                dp[node][i] = std::max(dp[node][i], std::min(tree[node] + nodeGrowth, (1 + e) * (1 + e)));
+            }
+        }
+
+    }
+
+    //Not leaf node
+    else{
+
+        //Solve its children first,
+        dfs(leftChild);
+        dfs(rightChild);
+
+        //For every growth agent amount
+        for (int i = 0; i <= X; i++){
+            //For every growth agent amount that can be given to the left child
+            for (int l = 0; l <= i; l++){
+                //Growth agent to right child = total amount to be used - amount given to left child
+                int r = i - l;
+                //leftRight[node][i] basically tells us the max amount of nutrients that can be produced by the children of the node given i growth agents
+                //Note that this does not take into account the edge yet, that is in the next loop
+                leftRight[node][i] = std::max(leftRight[node][i], dp[leftChild][l] + dp[rightChild][r]); //max(itself, its 2 children combined)
+
+                //Note that if the current node is the root, then this would also be the answer
+                if (node == 1){
+                    answer = std::max(answer, leftRight[node][i]);
+                }
+            }
+        }
+
+        //For every growth agent amount
+        for (int i = 0; i <= X; i++){
+            //From the current amount of growth agent that can be used, try giving every possible value to the edge
+            for (int e = 0; e <= i; e++){
+                int nodeGrowth = i - e; //Amount given to edge
+                //Same idea, max(itself, min(total nutrients from node, edge))
+                dp[node][i] = std::max(dp[node][i], std::min(leftRight[node][nodeGrowth], (1 + e) * (1 + e)));
+            }
+        }
+
+    }
+
+}
+
+int main() {
+
+    std::string input;
+    getline(std::cin, input);
+    std::cin >> X;
+
+    //If it's just a root, no subtrees
+    if (input[0] != '('){
+        std::cout << std::stoi(input) + X << '\n';
+        return 0;
+    }
+
+    //Otherwise, we have to deal with this atrocious input format
+    std::stack<std::string> s; s.push("(");
+    int node = 1;
+    int i = 1;
+    while (!s.empty()){
+
+        //Skip blank space
+        if (input[i] == ' '){
+            i++;
+            continue;
+        }
+
+        //Opening bracket
+        if (input[i] == '('){
+
+            //Determine if left or right subtree
+            if (s.top() == "("){
+                node = leftChild;
+            }
+
+            else{
+                node = rightChild;
+            }
+
+            s.push("(");
+            i++;
+
+        }
+
+        //End of a subtree
+        else if (input[i] == ')'){
+            int right = std::stoi(s.top()); s.pop();
+            int left = std::stoi(s.top()); s.pop();
+            s.pop(); //Get rid of the opening bracket
+            tree[leftChild] = left;
+            tree[rightChild] = right; 
+            if(!s.empty()) s.push("0"); //Basically used for filler if the node isnt a leaf node
+            node /= 2; //return to parent
+            i++;
+        }
+
+        //Get number
+        else{
+            std::string num = "";
+            while (true){
+                num += input[i];
+                i++;
+                if(input[i] == '(' || input[i] == ')' || input[i] == ' '){
+                    s.push(num);
+                    break;
+                }
+            }
+        }
+
+    }
+
+    /* INPUT DEBUGGING
+    for (int i = 0 ; i < 20; i++){
+        std::cout << "Tree[" << i << "] = " << tree[i] << '\n';
+    }
+    */
+
+    dfs(1);
+    std::cout << answer << '\n';
+
+    return 0;
+
+}