I tried to do the classical problem to implement an algorithm to print all valid combinations of n pairs of parentheses. And I found this program (which works perfectly) :
public static void addParen(ArrayList<String> list, int leftRem, int rightRem, char[] str, int count) {
if (leftRem < 0 || rightRem < leftRem) return; // invalid state
if (leftRem == 0 && rightRem == 0) { /* all out of left and right parentheses */
String s = String.copyValueOf(str);
list.add(s);
} else {
if (leftRem > 0) { // try a left paren, if there are some available
str[count] = '(';
addParen(list, leftRem - 1, rightRem, str, count + 1);
}
if (rightRem > leftRem) { // try a right paren, if there’s a matching left
str[count] = ')';
addParen(list, leftRem, rightRem - 1, str, count + 1);
}
}
}
public static ArrayList<String> generateParens(int count) {
char[] str = new char[count*2];
ArrayList<String> list = new ArrayList<String>();
addParen(list, count, count, str, 0);
return list;
}
Then, when I was searching for applications of Catalan Numbers, I found a very interresting application here : https://en.wikipedia.org/wiki/Catalan_number#Applications_in_combinatorics It saids that:
We can use catalan numbers to form mountain ranges with n upstrokes and n down-strokes that all stay above the original line. The mountain range interpretation is that the mountains will never go below the horizon
Consequently, I tried to reuse the code above to implement a solution to this problem. I'm not sure, but I think that we can reuse this code since it seems that they have the same "logic". Unfortunately, I tried a lot of things to replace the brackets with '/' and '\' but I failed.
I tried to do something like that :
str[count] = '/';
addParen(list, leftRem - 1, rightRem, str, count + 1);
}
if (rightRem > leftRem) { // try a right paren, if there’s a matching left
str[count] = '\\';
str[count+1] = '\n';
addParen(list, leftRem, rightRem - 1, str, count + 2);
For me, they have the same logic, like in brackets, we add the left bracket '(' EACH time is possible, but for right bracket ')' we add it only if the number of right brackets is greater than the left. We can do the same raisoning here no? We add '/' EACH time is possible but for '\' we have to count the number of '/' before...
Which I found particularly difficult here is how can we insert the new lines here to have all the correct mountains?
Can you help me to reuse this code if it's possible? Or should I start another code from scratch?
There are more possible approaches for using the available parentheses generation code.
Use it exactly as it is, and convert the resulting set of parentheses strings into mountain representations.
Update it in order to directly generate the mountain strings. This is the alternative detailed in this answer.
This prevents dealing with complications of inserting newlines while constructing the solution. A new string will be generated from this matrix once a solution is complete.
Concatenate the strings associated to each row of the matrix, adding newlines after each row. Additionally (not implemented in the solution below), the trailing spaces of each row could be removed.
We use two position parameters, denoted row and col, as we are moving in two dimensions now, and they are the correspondents of the count parameter in the old code. The row and col indicate the corner where the mountain line has led us so far. The col (column) parameter increases by 1 after each character we add. The row parameter is changed according to whether the current character corresponds to climbing or descending.
This was implicit in the 1D case, because we always ended up with strings of a fixed length and every new solution overwrote the previous ones. However, in the 2D case, if we don't clean up the path generated for a solution, we might see parts of it in the following solutions.
The size of the matrix is count rows (because this is the maximum height of a solution that will be generated) and 2 * count columns (because this is the length when using count pairs of strokes). The matrix is initially filled with white spaces.
Below is the Java code that was updated according to the ideas above. Despite the modifications enumerated, the core logic is the same (the recursive structure is the same - the decision of whether to attempt adding an up-stroke / down-stroke and the termination criteria are not altered).
public static void addParen(ArrayList<String> list, int leftRem, int rightRem, char[][] str, int row, int col) {
if (leftRem < 0 || rightRem < leftRem) return; // invalid state
if (leftRem == 0 && rightRem == 0) { /* all out of left and right parentheses */
StringBuilder sb = new StringBuilder();
for (int i = 0; i < str.length; i++) {
sb.append(String.copyValueOf(str[i]));
sb.append(System.lineSeparator());
}
list.add(sb.toString());
} else {
if (leftRem > 0) { // try a left paren, if there are some available
str[row][col] = '/';
addParen(list, leftRem - 1, rightRem, str, row - 1, col + 1);
str[row][col] = ' ';
}
if (rightRem > leftRem) { // try a right paren, if there’s a matching left
str[row + 1][col] = '\\';
addParen(list, leftRem, rightRem - 1, str, row + 1, col + 1);
str[row + 1][col] = ' ';
}
}
}
public static ArrayList<String> generateParens(int count) {
char[][] str = new char[count][count * 2];
for (int i = 0; i < str.length; i++) {
Arrays.fill(str[i], ' ');
}
ArrayList<String> list = new ArrayList<>();
addParen(list, count, count, str, count - 1, 0);
return list;
}
Below are the resulting mountains when the input is 3 (i.e. the width of the string is 6, because we have 3 up-strokes and 3 down-strokes):
/\
/ \
/ \
/\/\
/ \
/\
/ \/\
/\
/\/ \
/\/\/\
There are a few interesting questions that now can be answered about these strings.
(Q1) how many valid strings are there for a specific width?
(Q2) what is the probability of a random sequence of '/' and '\' to be a valid mountain?
(Q3) what is the probability of a random sequence containing equal number of '/' and '\' to be a valid mountain?
The table below answers to these questions for various string lengths:
Length Valid Total Prob. Q2 Equal / and \ Prob. Q3
2 1 4 25.0000% 2 50.0000%
4 2 16 12.5000% 6 33.3333%
6 5 64 7.8125% 20 25.0000%
8 14 256 5.4688% 70 20.0000%
10 42 1,024 4.1016% 252 16.6667%
12 132 4,096 3.2227% 924 14.2857%
14 429 16,384 2.6184% 3,432 12.5000%
16 1,430 65,536 2.1820% 12,870 11.1111%
18 4,862 262,144 1.8547% 48,620 10.0000%
20 16,796 1,048,576 1.6018% 184,756 9.0909%
22 58,786 4,194,304 1.4016% 705,432 8.3333%
24 208,012 16,777,216 1.2398% 2,704,156 7.6923%
26 742,900 67,108,864 1.1070% 10,400,600 7.1429%
28 2,674,440 268,435,456 0.9963% 40,116,600 6.6667%
30 9,694,845 1,073,741,824 0.9029% 155,117,520 6.2500%