////////////Catalan numbers form a sequence of integers that appear in various counting problems, particularly those involving recursion and binary trees.The nth Catalan number, denoted as Cn, is the solution to many combinatorial problems.The sequence starts with 1, 1, 2, 5, 14, 42, 132, 429...
////////////Definition and Formula:
////////////The nth Catalan number, Cn, can be calculated using the following formula:
////////////Cn = (2n)! / ((n + 1)! * n!)
////////////Alternatively, it can be defined recursively:
////////////C0 = 1
////////////Cn+1 = Σ(Ci* Cn-i) for i from 0 to n
////////////Applications:
////////////Balanced Parentheses:
////////////Cn represents the number of ways to arrange n pairs of parentheses such that they are correctly matched.
////////////Binary Trees:
////////////Cn counts the number of full binary trees with n+1 leaves.
////////////Triangulations:
////////////Cn-2 represents the number of ways to triangulate a convex polygon with n sides.
////////////Dyck Paths:
////////////Cn counts the number of paths on an n x n grid that stay above the main diagonal.
////////////Other Applications:
////////////Catalan numbers also appear in problems related to matrix chain multiplication, Young tableaux, and more.
///https://en.wikipedia.org/wiki/Catalan_number
///https://en.wikipedia.org/wiki/Matrix_chain_multiplication
// // // // // // Matrix chain multiplication (or the matrix chain ordering problem[1]) is an optimization problem concerning the most efficient way to multiply a given sequence of matrices. The problem is not actually to perform the multiplications, but merely to decide the sequence of the matrix multiplications involved. The problem may be solved using dynamic programming.
// // // // // // There are many options because matrix multiplication is associative. In other words, no matter how the product is parenthesized, the result obtained will remain the same. For example, for four matrices A, B, C, and D, there are five possible options:
// // // // // // ((AB)C)D = (A(BC))D = (AB)(CD) = A((BC)D) = A(B(CD)).
// // // // // // Although it does not affect the product, the order in which the terms are parenthesized affects the number of simple arithmetic operations needed to compute the product, that is, the computational complexity. The straightforward multiplication of a matrix that is X × Y by a matrix that is Y × Z requires XYZ ordinary multiplications and X(Y − 1)Z ordinary additions. In this context, it is typical to use the number of ordinary multiplications as a measure of the runtime complexity.
// // // // // // If A is a 10 × 30 matrix, B is a 30 × 5 matrix, and C is a 5 × 60 matrix, then
// // // // // // computing (AB)C needs (10×30×5) + (10×5×60) = 1500 + 3000 = 4500 operations, while
// // // // // // computing A(BC) needs (30×5×60) + (10×30×60) = 9000 + 18000 = 27000 operations.
// // // // // // Clearly the first method is more efficient. With this information, the problem statement can be refined as "how to determine the optimal parenthesization of a product of n matrices?" The number of possible parenthesizations is given by the (n–1)th Catalan number, which is O(4n / n3/2), so checking each possible parenthesization (brute force) would require a run-time that is exponential in the number of matrices, which is very slow and impractical for large n. A quicker solution to this problem can be achieved by breaking up the problem into a set of related subproblems.
// // // // // // A dynamic programming algorithm
// // // // // // To begin, let us assume that all we really want to know is the minimum cost, or minimum number of arithmetic operations needed to multiply out the matrices. If we are only multiplying two matrices, there is only one way to multiply them, so the minimum cost is the cost of doing this. In general, we can find the minimum cost using the following recursive algorithm:
// // // // // // Take the sequence of matrices and separate it into two subsequences.
// // // // // // Find the minimum cost of multiplying out each subsequence.
// // // // // // Add these costs together, and add in the cost of multiplying the two result matrices.
// // // // // // Do this for each possible position at which the sequence of matrices can be split, and take the minimum over all of them.
// // // // // // For example, if we have four matrices ABCD, we compute the cost required to find each of (A)(BCD), (AB)(CD), and (ABC)(D), making recursive calls to find the minimum cost to compute ABC, AB, CD, and BCD. We then choose the best one. Better still, this yields not only the minimum cost, but also demonstrates the best way of doing the multiplication: group it the way that yields the lowest total cost, and do the same for each factor.
// // // // // // However, this algorithm has exponential runtime complexity making it as inefficient as the naive approach of trying all permutations. The reason is that the algorithm does a lot of redundant work. For example, above we made a recursive call to find the best cost for computing both ABC and AB. But finding the best cost for computing ABC also requires finding the best cost for AB. As the recursion grows deeper, more and more of this type of unnecessary repetition occurs.
// // // // // // One simple solution is called memoization: each time we compute the minimum cost needed to multiply out a specific subsequence, we save it. If we are ever asked to compute it again, we simply give the saved answer, and do not recompute it. Since there are about n2/2 different subsequences, where n is the number of matrices, the space required to do this is reasonable. It can be shown that this simple trick brings the runtime down to O(n3) from O(2n), which is more than efficient enough for real applications. This is top-down dynamic programming.
// // // // // // The following bottom-up approach[2] computes, for each 2 ≤ k ≤ n, the minimum costs of all subsequences of length k using the costs of smaller subsequences already computed. It has the same asymptotic runtime and requires no recursion.
// // // // // // Pseudocode:
// // // // // // // Matrix A[i] has dimension dims[i-1] x dims[i] for i = 1..n
// // // // // // MatrixChainOrder(int dims[])
// // // // // // {
// // // // // // // length[dims] = n + 1
// // // // // // n = dims.length - 1;
// // // // // // // m[i,j] = Minimum number of scalar multiplications (i.e., cost)
// // // // // // // needed to compute the matrix A[i]A[i+1]...A[j] = A[i..j]
// // // // // // // The cost is zero when multiplying one matrix
// // // // // // for (i = 1; i <= n; i++)
// // // // // // m[i, i] = 0;
// // // // // // for (len = 2; len <= n; len++) { // Subsequence lengths
// // // // // // for (i = 1; i <= n - len + 1; i++) {
// // // // // // j = i + len - 1;
// // // // // // m[i, j] = MAXINT;
// // // // // // for (k = i; k <= j - 1; k++) {
// // // // // // cost = m[i, k] + m[k+1, j] + dims[i-1]*dims[k]*dims[j];
// // // // // // if (cost < m[i, j]) {
// // // // // // m[i, j] = cost;
// // // // // // s[i, j] = k; // Index of the subsequence split that achieved minimal cost
// // // // // // }
// // // // // // }
// // // // // // }
// // // // // // }
// // // // // // }
// // // // // // Note: The first index for dims is 0 and the first index for m and s is 1.
// // // // // // A Python implementation using the memoization decorator from the standard library:
// // // // // // from functools import cache
// // // // // // def matrix_chain_order(dims: list[int]) -> int:
// // // // // // @cache
// // // // // // def a(i, j):
// // // // // // return min((a(i, k) + dims[i] * dims[k] * dims[j] + a(k, j)
// // // // // // for k in range(i + 1, j)), default=0)
// // // // // // return a(0, len(dims) - 1)
//////////////////using System;
//////////////////using System.Collections.Generic;
//////using System.Text;
public class WaterDistributor___OR_MILLIS_DISTRIBUTIONS
{
public static StringBuilder PUBLIC_STATIC_STRINGBUILDER_FOR_WATER_DISTRIBUTIONS_MILLIS_DISTRIBUTIONS_REPORTS = new StringBuilder();
public static StringBuilder PUBLIC_STATIC_STRINGBUILDER_FOR_WATER_OR_MILLIS_ALLOCATED_TOKENS = new StringBuilder();
//STRICT NOTE WE CANNOT SWAP POSITIONS OF THE SYMBOLS /ALPHABETS INSIDE THE TREE SYNTAX SINCE THESE ARE NON COMMUTATIVE LIKE MATRIXES MULTIPLICATIONS ORDERS REMAIN FIXED ... WE CAN ONLY REGROUP EXHAUSTIVELY FOR ALL POSSIBLE CASES TO GENERATE AND CHECK THE EXHAUSTIVE LIST OF LIST ASSOCIATED GROUPING OF MATRIX MULTIPLICATIONS 2 TOATHER ... THREE TOGATHER ...K TOGATHER ALL POSSIBLE CASES OF GROUPING WITHIN THE TREE List<Node> in the Forest to resupply waters in different styles of schemes
//SUPPOSE THE TREE OBJECTS ARE List<Node> and these are syntactically written as |...((... a )b) ..(. ..). ... (c ..(..(...).).) z| these syntaxes represent the "(" means one new branch starts and the balancing corresponding bracket ")" means the branch completes ... obviously all the nested branches are sub branches of that current branch ... which means whenever one "(" appears during left to right parsing we understand one sub branch is starting and when we get corresponding balancing bracket closing ")" we understand that we are coming out of the nesting depth of the branch So the nesting depths are always calculable from the nested orders of (...) pairs ... We can have the balancing brackets checkers within the trees pairs of pipe symbols that is like this are trees |......| the whole string is first tokenized with "|" symbols to count total number of trees in the forest (the whole text syntax. Then we go deeper and deeper into the nested pairs of "(...)" to understand depths of branches obviously the balancing brackets checking are necessary first
// NOW WE HAVE MODIFIED AND ENHANCED THE CAPACITY OF nODE CLASS TO STORE MORE KINDS OF INFORMATIONS SUCH THAT WE CAN REARRANGE THE WHOLE FOREST lIST<nODE> WITH DIFFERENT KINDS OF REORDERING AS PER DIFFERENT KINDS OF WATER DISTRIBUTION SCHEMES AND WE NEED TO REWRITE THE WHOLE FOREST CONSTRUCTION SYNTAX REWRITTEN FROM THE lIST<nODE> PREPARED AS PER DIFFERENT RE ORDERING SCHEMES... wHATEVER THE REORDERING SCHEMES ARE THERE WE WILL NEVER CHANGE THE NUMBER OF LEAVES IN THE TREES BUT WE CAN CHANGE THE LEAVES TO BRANCHES OR BRANCHES INTO LEAVES IN THE THIRD TIME SCANNING OR ONWARRDS... UPTO SECOND TIME RE SCANNING WE WILL NOT CHANGE ANYTHING IN THE TREES STRUCTURES ... WE WILL SIMPLY TRY TO DISTRIBUTE EQUAL AMOUNT OF WATER TO ALL LEAVES IN THE FOREST IN THE SECOND TIME RE SCANNING PROCESS
// IN THE THIRD RE SCANNING ONWARDS WE WILL TRY TO RECONSTRUCT THE TREES (KEEPING TOTAL NUMBER OF TREES FIXED) BUT WE WILL TRY TO SHUFFLE ALL THE BRANCHES AND LEAVES KEEPING TOTAL NUMBER OF NODES IN THAT TREE FIXED... THAT IS WE WILL REGROUP "(" ...")" PLACEMENTS DIFFERENT LY WITH DIFFERENT PARTITIONING SCHEMES ON THE UNPERMUTED PARTITIONS |...((... a )b) ..(. ..). ... (c ..(..(...).).) z| WHERE UNPERMUTED PARTITIONING MEANS WE CANNOT SHUFFLE THE PRE EXISTING ORDERS OF THE SYMBOLS/ALPHABETS BUT WE CAN GENERATE ALL POSSIBLE GROUPING REGROUPING OF THE FIXED ORDERED ALPHABETS/SYMBOLS DIFFERENTLY WITH ALL POSSIBLE CONDITIONS OF GROUPING AND REGROUPING AS PER CATALAN CONDITIONS WITHIN THE TOKENIZED |...|
// THE NEW VARIABLES ARE ALLOCATED TO LOG AND TO KEEP TRACK ON THE REBUILDING THE FOREST CONDITIONALLY WITH DIFFERENT KINDS OF PRIORITY OF WATER SUPPLY SYSTEMS OBVIOUSLY WE WILL NEED NEW KINDS OF BALANCING BRACKETS FOREST STRING RECONSTRUCTIONS NECESSARY SYNTAX RECONSTRUCTIONS REWRITING SYSTEMS TO GET DIFFERENT KINDS OF SYMMETRIES AND DIFFERENT KINDS OF AESTHETICS ORDERING REORDERING SYSTEMS AFTER SECOND TIMES SCANNING , THIRD TIME RESCANNING ETC...
////// //THE HIGHER ORDER SCANNING WILL TREAT THE THINGS AS THE ALPHABET SEQUENCES ARE STRICTLY FIXED (NON COMMUTATIVE BUT ASSOCIATIVE) MATRIX CHAIN MULTIPLICATIONS REGROUPING PROBLEMS
////// The matrix chain multiplication problem generalizes to solving a more abstract problem: given a linear sequence of objects, an associative binary operation on those objects, and a way to compute the cost of performing that operation on any two given objects(as well as all partial results), compute the minimum cost way to group the objects to apply the operation over the sequence.[11] A practical instance of this comes from the ordering of join operations in databases; see Query optimization § Join ordering.
////// Another somewhat contrived special case of this is string concatenation of a list of strings.In C, for example, the cost of concatenating two strings of length m and n using strcat is O(m + n), since we need O(m) time to find the end of the first string and O(n) time to copy the second string onto the end of it.Using this cost function, we can write a dynamic programming algorithm to find the fastest way to concatenate a sequence of strings. However, this optimization is rather useless because we can straightforwardly concatenate the strings in time proportional to the sum of their lengths. A similar problem exists for singly linked lists.
//////Another generalization is to solve the problem when parallel processors are available.In this case, instead of adding the costs of computing each factor of a matrix product, we take the maximum because we can do them simultaneously. This can drastically affect both the minimum cost and the final optimal grouping; more "balanced" groupings that keep all the processors busy are favored.There are even more sophisticated approaches.[12]
public static List<Node> PUBLIC_STATIC_LIST_OF_NODE_AS_FOREST_OBJECT_AS_LIST_OF_ADDRESSED_NODE_OBJECTS_SUCH_THAT_WE_CAN_PRESERVE_THE_STRUCTURE_OF_FOREST_AS_THE_ANT_SCANS_IT_FOR_FIRST_TIME_RECURSIVELY_AND_ADDRESSING_ALL_ITS_NODE_OBJECTS_STAGEWISE = new List<Node>();
public static List<Node> PUBLIC_STATIC_LIST_OF_NODE_AS_FOREST_OBJECT_AS_LIST_OF_ADDRESSED_NODE_OBJECTS_AND_READDRESSED_NODE_OBJECTS_TO_POPULATE_AT_SECOND_RESCANNING_THE_PRE_PRESERVED_LIST_OF_NOTE_OBJECTS_WHERE_ALL_LEAVES_ARE_GETTING_SAME_AMOUNT_OF_WATER_AFTER_SECOND_TIMES_RESCANNING = new List<Node>();
public static StringBuilder PUBLIC_STATIC_STRINGBUILDER_FOR_DESCENDING_ORDER_SINGLE_UNBRANCHED_LEAVES_COUNT_SORTED_TREES_IN_THE_RENUMBERED_TREES_IN_THE_FOREST_IN_SECOND_TIME_RESCANNING_WHEN_THE_ANT_KNOWS_NUMBER_OF_PENDANT_NODES_LEAVES_IN_EACH_TREES = new StringBuilder();
public class Node
{
public string Symbol;
public List<Node> Children = new List<Node>();
public double Water_OR_MILLIS = 0;
public bool IsFixedToken = false; // to mark special characters for fixed allocation
// THESE ARE NEW VARIABLES TO ACCUMULATE THE INFORMATIONS SUCH THAT WE CAN HANDLE THE WHOLE THING MORE POWERFULLY AND SUCH THAT WE CAN DO MORE NUMBER OF SCANNING TO REBUILD THE FOREST WITH DIFFERENT KINDS OF SORTING WITH DIFFERENT KINDS OF PROPERTIES OF THE NODES
// OBVIOUSLY THE FIRST TIME RECURSIVE SCANNING WILL NOT HAVE COMPLETE INFORMATION REGARDING TEH FOREST
public int PUBLIC_INT_DEPTH_OF_THIS_NODE_FROM_THE_LEVEL_ZERO = 0;//I NEED THESE REPORTS ALSO
public int PUBLIC_INT_LEAF_NUMBER_ASSIGNED____AS_COUNTER_FROM_THE_ZEROTH_LEAF_FOUND_TO_N_TH_LEAF_FOUND_IN_WHOLE_FOREST_OF_N_LEAVES_TOTAL = 0;//I NEED THESE REPORTS ALSO
public int PUBLIC_INT_LEAF_NUMBER_IN_CURRENT_TREE_WHEN_THE_ANT_IS_SCANNING_THE_TREE_FOR_FIRST_TIME_SCANNING_RECURSIVELY = 0;
public double PUBLIC_DOUBLE_TOTAL_EQUAL_AMOUNT_OF_WATER_RECIEVED_FOR_EACH_LEAVES_WHILE_IN_SECOND_SCANNING_WHEN_THE_ANT_HAS_ALREADY_SCANNED_WHOLE_FOREST_IN_FIRST_SCANNING_PROCESS = 0;// WE NEED A SECOND SCANNING SYSTEM TO GENERATE REALLOCATION OF WATERS EQUAL FOR ALL LEAVES AFTER THE ANT HAS DISTRIBUTED ALL ITS W LITRES OF TOTAL WATER AMOND TOTAL N LEAVES FOUND(AND COUNTED IN FIRST SCANNING) UNTIL THE FIRST RECURSIVE SSCANNING IS COMPLETED THE ANT DONT KNOW HOW MANY TOTAL LEAVES ARE THERE IN THE FOREST
public string PUBLIC_STRING_DOT_SEPERATED_ADDRESS_OF_THE_CURRENT_NODE_ASSIGNED_DURING_FIRST_SCANNING = "0.0.0.0.0.0....";// WHILE THE ANT IS SCANNING FOR THE FIRST TIME IT DONT KNOW WHICH IS THE PENDANT NODE OR INTERMEDIATE NODE... SO IF IT IS INTERMEDIATE NODE THEN IT PUTS 0 AT END AND PUTS NON DOT PURE LEVEL NUMBER AT END WHEN IT IS THE PENDANT NODE... THE ADDRESS IS SCHEMED LIKE TREE_NUMBER.FIRST_LEVEL_BRANCH_NUMBER.SECOND_LEVEL_BRANCH_NUMBER. ETC...
public double PUBLIC_DOUBLE_TOTAL_AMOUNT_OF_WATER_THE_CURRENT_NODE_AND_ALL_ITS_SUB_BRANCH_RECIEVED_DURING_FIRST_TIME_RECURSIVE_SCANNING = 0; // THE PARSE FOREST FIRST TIME RECURSIVE SCANNER NEED TO LOG THE TOTAL AMOUNT OF RECURSIVE WATER THE CURRENT NODE( ALL ITS SUB BRANCES GET TOTAL AMOUNT OF WATER FROM THIS NODES WATER) WHILE THE ANT IS DISTRIBUTING ITS WATER RECURSIVELY (WHEN THE GLOBAL PICTURE OF THE WHOLE FOREST IS NOT CLEAR TO THE ANT WHO IS DISTRIBUTING W LITRES OF WATER TO ALL THE NODES , BRANCES AND AND LEAVES OF THE TREES IN THE WHOLE FOREST
public double PUBLIC_DOUBLE_READJUSTED_TOTAL_AMOUNT_OF_WATER_THE_CURRENT_NODE_AND_ALL_ITS_SUB_BRANCHES_RECIEVED_IN_SECOND_SCAN_OF_PARSE_FOREST_WHEN_THE_ANT_KNOWS_AND_HAS_ALREADY_COUNTED_ALL_GLOBAL_INFORMATION_UPTO_ALL_LEAVES_OF_WHOLE_FOREST = 0;
public int PUBLIC_INT_TREE_NUMBER_FOR_CURRENT_NODE = 0; //THE FIRST ADDRESS VALUE(IN DOT DELIMITED STRING IN THE VARIABLE PUBLIC_STRING_DOT_SEPERATED_ADDRESS_OF_THE_CURRENT_NODE_ASSIGNED_DURING_FIRST_SCANNING) IS THE TREE NUMBER FOR THE CURRENT NODE
public double PUBLIC_DOUBLE_TOTAL_AMOUNT_OF_WATER_THE_CURRENT_TREE_OF_CURRENT_NODE_RECIEVES_IN_FIRST_RECURSIVE_SCANNING_WHEN_THE_ANT_WAS_DISTRIBUTING_ITS_WATER_RECURSIVELY = 0;// OBVIOUSLY DURING THE FIRST SCANNING THE WHOLE STRING WITHIN THE TWO PIPE SYMBOLS WERE GETTING SAME AMOUNT OF WATER SINCE DURING THE FIRST RECURSIVE SCANNING OF THE WHOLE FOREST THE ANT DID NOT KNOW HOW MANY TOTAL LEAVES ARE THERE SO IT DISTRIBUTES EQUAL AMOUNT OF WATER W / k TO ALL TREES (IRRESPECTIVE OF NUMBER OF LEAVES THAT TREE HAS) BECAUSE THE ANT DID NOT KNOW HOE MANY TOTAL LEAVES ARE THERE IN THAT TREE DURING THE FIRST TIME RECURSIVE SCANNING OF THE FOREST STRING INPUT | a b c ( d (e ...)... ) ...| kind of input string are there where |...| represents the tree objects and several such pipe delimeted tree objects togather forms the whole forest and the task is allocated to the ant (who cannot see whole forest leaves branches etc in first time parsing scanning while parsing this forest input string)
public double PUBLIC_DOUBLE_TOTAL_AMOUNT_OF_WATER_THE_CURRENT_TREE_OF_CURRENT_NODE_RECIEVES_IN_SECOND_TIME_SCANNING_WHEN_THE_ANT_HAS_ALREADY_COUNTED_ALL_THE_LEAVES_IN_THE_FOREST_AND_WHEN_THE_ANT_ALREADY_KNOWS_WHICH_TREE_HAS_HOW_MANY_BRANCHES_AND_ALSO_KNOWS_WHICH_TREE_HAS_HOW_MANY_LEAVES_IN_TOTAL_AND_IN_SECOND_SCAN_THE_ANT_ALLOCATES_EQUAL_AMOUNT_OF_ITS_WATER_TO_ALL_LEAVES_IN_THE_FOREST = 0; //OBVIOUSLY THE List<Node> is the tree
public Node PUBLIC_NODE_THE_PENDANT_NODE_WHICH_IS_LEAF_OBJECT_WHICH_HAS_ONLY_ONE_DEGREE = new Node();//
public bool PUBLIC_BOOL_IS_THIS_PENDANT_NODE_THAT_IS_IS_IT_LEAF_OBJECT = false;
public int PUBLIC_INT_TOTAL_NUMBER_OF_CATALAN_REGROUPING_PARTITIONS_POSSIBLE_ON_THE_FIXED_SEQUENCE_OF_ALPHABETS_SYMBOLS_WITHIN_PIPE_DELIMETED_TREE_OBJECT = 0;// STRICT NOTE THE ORDERING OF SYMBOLS WITHIN THE INPUT STRING BETWEEN THE TOKENIZED |...| WILL REMAIN FIXED ONLY THE UNIQUE EXHAUSTIVE CATALAN REDISTRIBUTIONS OF BALANCED BRACKETS POSSIBILITIES OF PARTITIONING OR GROUPING OF ALPHABETS /SYMBOLS CONDITIONS ARE CHECKED , COUNTED AND ENLISTED IN THIRD SCANNING AND DIFFERENT UNIQUE POSSIBLE TREE STRUCTURES ARE CONSTRUCTED DURING THIRD SCANNING OF THE TREE OBJECTS... STRICT NOTE THAT TOTAL NUMBER OF TREES IN THE FOREST REMAIN FIXED FOR ANY KIND OF REORDERING. STRICT NOTE TOTAL NUMBER OF NODE REMAIN FIXED AFTER ANY NUMBER OF RESCANNING ARE DONE
}//class Node
//IN THE FIRST SCAN THE ANT DONT HAVE THE GLOBAL PICTURE CLEAR SO IT DISTRIBUTES ALL ITS WATER RECURSIVELY AND DURING THE FIRST TIME SCANNING THE ANT DONT HAVE OVERALL INFORMATION REGARDING THE WHOLE FOREST NOR THE ANT KNOWS HOW MANY BRANCHES ARE THERE IN WHICH TREES... NOR THE ANT HAS CLARITY OF HOW MANY SUB BRANCHES IN THE TREE , NOR THE ANT KNOWS HOW MANY TOTAL LEAVES ARE THERE IN WHICH TREES. SO IT HAS STARTED DISTRIBUTING ITS WATER EQUALLY ENOUGH AS PER THE LEVEL WISE INFORMATION IT GETS AT EVERY STAGE (RECURSIVE STAGE) WHERE IT IS STANDING...OBVIOUSLY THE DISTRIBUTIONS ARE NOT GETTING FAIR ENOUGH BUT THE CODE WRITEN UPTO NOW IS WORKING FINE AS PER THE EQUALITY OF SHORT TERM VISION (STAGE WISE VISION AT THE CURRENT STATES OF RECURSIONS)
////// Suppose an ant is distributing W litres of water to whole forest… First it sees n number of trees so it allocates W / n amount of water to all trees equally irrespective of sizes of the trees.Then enters into a tree t_0 with W/ n litres of water and sees there are n_t0_k0 number of level 0 branches so it allocates(W/ n_t0_ / n_k0) amount of water to each level 0 branch of that tree … then enter next one branch of level0 and until it enters there it cannot understand how many level 1 branches are there for that particular level0 branch of that tree and when it finds for that particular branch there are n_t0_k0_k1 number of level 1 sub branches for that particular branch n_t0_k0 so it distributes(W / n_t0_ / n_t0_k0 / n_t0_k0_k1) amount of water to all the sub branches for that branch … recursively in this way it can count number of subbranches only after entering there inside … it is like recursively file searching inside folders then sub folders … etc… until the crawler enters into a branch it cannot know how many sub entries are present there inside… the counts are not always same at every level so distributions are not same for all same level entries… The forest is written as string input = "| a b ( c d ( e f ) g ) h | a b ( c (d ( e f ) g )) h | (a b) ( c (d ( e (f) ) g )) h"; | delimits the trees and(…) denotes the branches and nested(…) denotes the sub branches… write a c sharp program to allocate water distributions mechanisms recursively for every leafs level(conditionally changes as per the order of(…) present in the string
// THE CURRRENT static List<Node> ParseForest(string input) function is working best for the first time scanning (recursively distributing the waters to all the nodes. Upto now the code is not keeping records , logging at each level of nodes but now i have enhanced the data structure of Node class to keep track for all other informations regarding the distribution process
public static void WaterDistributor___MILLIS_DISTRIBUTIONS_Main(string input_string_for_whole_forest, double total_water_or_total_millis_W_for_each_tree_pipes_delimeted)
{
// we have new variables now with additional kinds of tasks to do... current recursive scanning of first time scanning works OK and distributing the water properly
PUBLIC_STATIC_LIST_OF_NODE_AS_FOREST_OBJECT_AS_LIST_OF_ADDRESSED_NODE_OBJECTS_SUCH_THAT_WE_CAN_PRESERVE_THE_STRUCTURE_OF_FOREST_AS_THE_ANT_SCANS_IT_FOR_FIRST_TIME_RECURSIVELY_AND_ADDRESSING_ALL_ITS_NODE_OBJECTS_STAGEWISE = new List<Node>();
PUBLIC_STATIC_LIST_OF_NODE_AS_FOREST_OBJECT_AS_LIST_OF_ADDRESSED_NODE_OBJECTS_AND_READDRESSED_NODE_OBJECTS_TO_POPULATE_AT_SECOND_RESCANNING_THE_PRE_PRESERVED_LIST_OF_NOTE_OBJECTS_WHERE_ALL_LEAVES_ARE_GETTING_SAME_AMOUNT_OF_WATER_AFTER_SECOND_TIMES_RESCANNING = new List<Node>();
PUBLIC_STATIC_STRINGBUILDER_FOR_WATER_DISTRIBUTIONS_MILLIS_DISTRIBUTIONS_REPORTS.Clear();
PUBLIC_STATIC_STRINGBUILDER_FOR_WATER_OR_MILLIS_ALLOCATED_TOKENS.Clear();
PUBLIC_STATIC_STRINGBUILDER_FOR_DESCENDING_ORDER_SINGLE_UNBRANCHED_LEAVES_COUNT_SORTED_TREES_IN_THE_RENUMBERED_TREES_IN_THE_FOREST_IN_SECOND_TIME_RESCANNING_WHEN_THE_ANT_KNOWS_NUMBER_OF_PENDANT_NODES_LEAVES_IN_EACH_TREES.Clear();
string input = input_string_for_whole_forest;
PUBLIC_STATIC_STRINGBUILDER_FOR_WATER_DISTRIBUTIONS_MILLIS_DISTRIBUTIONS_REPORTS
.AppendLine("Input string:\n" + input + "\nTotal millis per tree: " + total_water_or_total_millis_W_for_each_tree_pipes_delimeted);
// var trees = ParseForest(input);
List<Node> trees = ParseForest(input);
double waterPerTree = total_water_or_total_millis_W_for_each_tree_pipes_delimeted;
foreach (var tree in trees)
{ DistributeWater(tree, waterPerTree); }
foreach (var tree in trees)
{ PrintWaterDistribution(tree, "ROOT"); }
}//public static void WaterDistributor___MILLIS_DISTRIBUTIONS_Main(string input_string_for_whole_forest, double total_water_or_total_millis_W_for_each_tree_pipes_delimeted)
public static List<Node> ParseForest(string input)
{
var trees = new List<Node>();
var treeStrings = input.Split('|');
foreach (var treeStr in treeStrings)
{
string trimmed = treeStr.Trim();
if (!string.IsNullOrEmpty(trimmed))
{
var tokens = Tokenize(trimmed);
int index = 0;
var root = new Node { Symbol = "ROOT" };
while (index < tokens.Count)
{
root.Children.Add(ParseNode(tokens, ref index));
}
trees.Add(root);
}
}
return trees;
}
public static List<string> Tokenize(string input)
{
var tokens = new List<string>();
string current = "";
foreach (char c in input)
{
if (c == '(' || c == ')')
{
if (!string.IsNullOrWhiteSpace(current))
{
tokens.AddRange(current.Trim().Split(' '));
current = "";
}
tokens.Add(c.ToString());
}
else
{
current += c;
}
}
if (!string.IsNullOrWhiteSpace(current))
{
tokens.AddRange(current.Trim().Split(' '));
}
return tokens;
}
public static Node ParseNode(List<string> tokens, ref int index)
{
if (tokens[index] == "(")
{
index++;
var parent = new Node { Symbol = "BRANCH" };
while (index < tokens.Count && tokens[index] != ")")
{
parent.Children.Add(ParseNode(tokens, ref index));
}
index++;
return parent;
}
else
{
string sym = tokens[index++];
return new Node
{
Symbol = sym,
IsFixedToken = sym == "|" || sym == "@" || sym == "[" || sym == "]" || sym == "{" || sym == "}" || sym == ";" || sym == "," || sym == "~" || sym == "!" || sym == "" || sym == "^" || sym == "&"
};
}
}// public static Node ParseNode(List<string> tokens, ref int index)
public static void DistributeWater(Node node, double water)
{
if (node.Children.Count == 0)
{
node.Water_OR_MILLIS = node.IsFixedToken ? 30.0 : water;
return;
}//if (node.Children.Count == 0)
int fixedCount = 0;
double remainingWater = water;
foreach (var child in node.Children)
{
if (child.IsFixedToken)
fixedCount++;
}//foreach (var child in node.Children)
double fixedAllocation = 30.0 * fixedCount;
double distributable = Math.Max(0, water - fixedAllocation);
int nonFixedCount = node.Children.Count - fixedCount;
double perNode = nonFixedCount > 0 ? distributable / nonFixedCount : 0;
foreach (var child in node.Children)
{
if (child.IsFixedToken)
{
DistributeWater(child, 30.0);
}
else
{
DistributeWater(child, perNode);
}//end of else of if (child.IsFixedToken)
}//foreach (var child in node.Children)
node.Water_OR_MILLIS = water;
}//public static void DistributeWater(Node node, double water)
public static void PrintWaterDistribution(Node node, string path)
{
if (node.Symbol != "ROOT" && node.Symbol != "BRANCH")
{
Console.WriteLine($"{path}/{node.Symbol} -> {node.Water_OR_MILLIS:F2} milliseconds");
PUBLIC_STATIC_STRINGBUILDER_FOR_WATER_DISTRIBUTIONS_MILLIS_DISTRIBUTIONS_REPORTS
.AppendLine($"{path}/{node.Symbol} -> {node.Water_OR_MILLIS:F2} milliseconds");
PUBLIC_STATIC_STRINGBUILDER_FOR_WATER_OR_MILLIS_ALLOCATED_TOKENS
.AppendLine(node.Symbol + "_DISTRIBUTED_" + node.Water_OR_MILLIS.ToString("F2"));
}// if (node.Symbol != "ROOT" && node.Symbol != "BRANCH")
foreach (var child in node.Children)
{
PrintWaterDistribution(child, path + "/" + (node.Symbol == "ROOT" ? "" : node.Symbol));
}//foreach (var child in node.Children)
}// public static void PrintWaterDistribution(Node node, string path)
} // public class WaterDistributor___OR_MILLIS_DISTRIBUTIONS
No comments:
Post a Comment