Algorithm to generate mountain ranges with upstrokes and down-strokes (java)

Question

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?

Answer 1

Interesting task. The calculation can be done in parallel. I'll show the code within "not answer" tags, as it doesn't match the question's language criterion (made in the parallel array processing language Dyalog APL which in fact it does the job with one row of code). Please ignore that part as you wish. However, i'll show the data and what happens. It's rather intuitive.

< not answer >

fn←{(∧/(0≤+\a-~a),(⍵÷2)=+/a)⌿a←⍉(⍵⍴2)⊤⍳2*⍵} // Dynamic function, generates boolean matrix

format←{⍉↑(-1+(0.5×⍴⍵)-+\⍵-0,¯1↓~⍵)↑¨'\/'[1+⍵]} // Dirty format function

< /not answer >

Say the argument (the width of the mountains) is n=6.

Step 1. Generate all numbers between 0 and (2^6 - 1)

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63

Step 2: Grab the 2-base of each (they are vertically below. 0 is leftmost, then 1, etc):

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1
0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1
0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1
0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1

<sub>1. In fact, one only needs to generate numbers from 32 to 63, since we only want 2-base's that begin with 1. See topmost row in data above. Columns (numbers) with zeroes at top shouldn't really even be generated.)
2. In fact one only needs to generate even numbers, since last bit must be 0. See downmost row in data above. Columns (numbers) with ones at bottom shouldn't really even be generated.)</sub>

Step 3: Calculate the number of ones in each column:

0 1 1 2 1 2 2 3 1 2 2 3 2 3 3 4 1 2 2 3 2 3 3 4 2 3 3 4 3 4 4 5 1 2 2 3 2 3 3 4 2 3 3 4 3 4 4 5 2 3 3 4 3 4 4 5 3 4 4 5 4 5 5 6

and do a boolean marking = 1 where the sum is half of N, that is 3 (ie. in total we must have as many uphills as downhills). This is our 1st boolean result:

0 0 0 0 0 0 0 1 0 0 0 1 0 1 1 0 0 0 0 1 0 1 1 0 0 1 1 0 1 0 0 0 0 0 0 1 0 1 1 0 0 1 1 0 1 0 0 0 0 1 1 0 1 0 0 0 1 0 0 0 0 0 0 0

Step 4: Ensure that we do not go "below horizon":

This means we must calculate a cumulative sum of each column, first:

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3
0 0 0 0 1 1 1 1 1 1 1 1 2 2 2 2 1 1 1 1 2 2 2 2 2 2 2 2 3 3 3 3 1 1 1 1 2 2 2 2 2 2 2 2 3 3 3 3 2 2 2 2 3 3 3 3 3 3 3 3 4 4 4 4
0 0 1 1 1 1 2 2 1 1 2 2 2 2 3 3 1 1 2 2 2 2 3 3 2 2 3 3 3 3 4 4 1 1 2 2 2 2 3 3 2 2 3 3 3 3 4 4 2 2 3 3 3 3 4 4 3 3 4 4 4 4 5 5
0 1 1 2 1 2 2 3 1 2 2 3 2 3 3 4 1 2 2 3 2 3 3 4 2 3 3 4 3 4 4 5 1 2 2 3 2 3 3 4 2 3 3 4 3 4 4 5 2 3 3 4 3 4 4 5 3 4 4 5 4 5 5 6

and then for the shifted bits (0's turned into 1's, and vice versa):

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
3 3 3 3 3 3 3 3 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0
4 4 4 4 3 3 3 3 3 3 3 3 2 2 2 2 3 3 3 3 2 2 2 2 2 2 2 2 1 1 1 1 3 3 3 3 2 2 2 2 2 2 2 2 1 1 1 1 2 2 2 2 1 1 1 1 1 1 1 1 0 0 0 0
5 5 4 4 4 4 3 3 4 4 3 3 3 3 2 2 4 4 3 3 3 3 2 2 3 3 2 2 2 2 1 1 4 4 3 3 3 3 2 2 3 3 2 2 2 2 1 1 3 3 2 2 2 2 1 1 2 2 1 1 1 1 0 0
6 5 5 4 5 4 4 3 5 4 4 3 4 3 3 2 5 4 4 3 4 3 3 2 4 3 3 2 3 2 2 1 5 4 4 3 4 3 3 2 4 3 3 2 3 2 2 1 4 3 3 2 3 2 2 1 3 2 2 1 2 1 1 0

then subtract the 2nd from the 1st, and get

¯1 ¯1 ¯1 ¯1 ¯1 ¯1 ¯1 ¯1 ¯1 ¯1 ¯1 ¯1 ¯1 ¯1 ¯1 ¯1 ¯1 ¯1 ¯1 ¯1 ¯1 ¯1 ¯1 ¯1 ¯1 ¯1 ¯1 ¯1 ¯1 ¯1 ¯1 ¯1  1  1  1  1  1  1  1  1  1  1 1 1 1 1 1 1  1  1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
¯2 ¯2 ¯2 ¯2 ¯2 ¯2 ¯2 ¯2 ¯2 ¯2 ¯2 ¯2 ¯2 ¯2 ¯2 ¯2  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0 0 0 0 0 0 0  2  2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
¯3 ¯3 ¯3 ¯3 ¯3 ¯3 ¯3 ¯3 ¯1 ¯1 ¯1 ¯1 ¯1 ¯1 ¯1 ¯1 ¯1 ¯1 ¯1 ¯1 ¯1 ¯1 ¯1 ¯1  1  1  1  1  1  1  1  1 ¯1 ¯1 ¯1 ¯1 ¯1 ¯1 ¯1 ¯1  1  1 1 1 1 1 1 1  1  1 1 1 1 1 1 1 3 3 3 3 3 3 3 3
¯4 ¯4 ¯4 ¯4 ¯2 ¯2 ¯2 ¯2 ¯2 ¯2 ¯2 ¯2  0  0  0  0 ¯2 ¯2 ¯2 ¯2  0  0  0  0  0  0  0  0  2  2  2  2 ¯2 ¯2 ¯2 ¯2  0  0  0  0  0  0 0 0 2 2 2 2  0  0 0 0 2 2 2 2 2 2 2 2 4 4 4 4
¯5 ¯5 ¯3 ¯3 ¯3 ¯3 ¯1 ¯1 ¯3 ¯3 ¯1 ¯1 ¯1 ¯1  1  1 ¯3 ¯3 ¯1 ¯1 ¯1 ¯1  1  1 ¯1 ¯1  1  1  1  1  3  3 ¯3 ¯3 ¯1 ¯1 ¯1 ¯1  1  1 ¯1 ¯1 1 1 1 1 3 3 ¯1 ¯1 1 1 1 1 3 3 1 1 3 3 3 3 5 5
¯6 ¯4 ¯4 ¯2 ¯4 ¯2 ¯2  0 ¯4 ¯2 ¯2  0 ¯2  0  0  2 ¯4 ¯2 ¯2  0 ¯2  0  0  2 ¯2  0  0  2  0  2  2  4 ¯4 ¯2 ¯2  0 ¯2  0  0  2 ¯2  0 0 2 0 2 2 4 ¯2  0 0 2 0 2 2 4 0 2 2 4 2 4 4 6

and see which columns have no negative values; this is the 2nd boolean result:

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1

Step 5: Grab an AND from the two boolean results above:

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 1 0 1 0 0 0 1 0 0 0 0 0 0 0

These are the locations for columns of the binary data that create the good mountains. Below column-wise to left, then transposed (for readability) to right. 1 is uphills, 2 edit:0 is downhills:

 1 1 1 1 1  1 0 1 0 1 0 // 1 0 1 0 1 0 means /\/\/\
 0 0 1 1 1  1 0 1 1 0 0 
 1 1 0 0 1  1 1 0 0 1 0 
 0 1 0 1 0  1 1 0 1 0 0 // means //\/\\
 1 0 1 0 0  1 1 1 0 0 0 
 0 0 0 0 0              

That is the good answer. If needed, we can apply a formatting:

format [the boolean result]
┌──────┬──────┬──────┬──────┬──────┐
│      │      │      │      │  /\  │
│      │   /\ │ /\   │ /\/\ │ /  \ │
│/\/\/\│/\/  \│/  \/\│/    \│/    \│
└──────┴──────┴──────┴──────┴──────┘

A little bigger, n=10:

DISP format¨↓fn 10
┌──────────┬──────────┬──────────┬──────────┬──────────┬──────────┬──────────┬──────────┬──────────┬──────────┬──────────┬──────────┬──────────┬──────────┬──────────┬──────────┬──────────┬──────────┬──────────┬──────────┬──────────┬──────────┬──────────┬──────────┬──────────┬──────────┬──────────┬──────────┬──────────┬──────────┬──────────┬──────────┬──────────┬──────────┬──────────┬──────────┬──────────┬──────────┬──────────┬──────────┬──────────┬──────────┐
│          │          │          │          │          │          │          │          │          │          │          │          │          │          │          │          │          │          │          │          │          │          │          │          │          │          │          │          │          │          │          │          │          │          │          │          │          │          │          │          │          │    /\    │
│          │          │          │          │          │          │          │          │          │          │          │          │          │     /\   │          │          │          │          │          │          │          │          │          │          │          │          │          │     /\   │          │          │          │          │          │          │          │          │     /\   │   /\     │   /\     │   /\     │   /\/\   │   /  \   │
│          │          │          │          │      /\  │          │          │          │          │      /\  │    /\    │    /\    │    /\/\  │    /  \  │          │          │          │          │      /\  │          │          │          │          │      /\  │    /\    │    /\    │    /\/\  │    /  \  │  /\      │  /\      │  /\      │  /\      │  /\  /\  │  /\/\    │  /\/\    │  /\/\/\  │  /\/  \  │  /  \    │  /  \    │  /  \/\  │  /    \  │  /    \  │
│          │       /\ │     /\   │     /\/\ │     /  \ │   /\     │   /\  /\ │   /\/\   │   /\/\/\ │   /\/  \ │   /  \   │   /  \/\ │   /    \ │   /    \ │ /\       │ /\    /\ │ /\  /\   │ /\  /\/\ │ /\  /  \ │ /\/\     │ /\/\  /\ │ /\/\/\   │ /\/\/\/\ │ /\/\/  \ │ /\/  \   │ /\/  \/\ │ /\/    \ │ /\/    \ │ /  \     │ /  \  /\ │ /  \/\   │ /  \/\/\ │ /  \/  \ │ /    \   │ /    \/\ │ /      \ │ /      \ │ /    \   │ /    \/\ │ /      \ │ /      \ │ /      \ │
│/\/\/\/\/\│/\/\/\/  \│/\/\/  \/\│/\/\/    \│/\/\/    \│/\/  \/\/\│/\/  \/  \│/\/    \/\│/\/      \│/\/      \│/\/    \/\│/\/      \│/\/      \│/\/      \│/  \/\/\/\│/  \/\/  \│/  \/  \/\│/  \/    \│/  \/    \│/    \/\/\│/    \/  \│/      \/\│/        \│/        \│/      \/\│/        \│/        \│/        \│/    \/\/\│/    \/  \│/      \/\│/        \│/        \│/      \/\│/        \│/        \│/        \│/      \/\│/        \│/        \│/        \│/        \│
└──────────┴──────────┴──────────┴──────────┴──────────┴──────────┴──────────┴──────────┴──────────┴──────────┴──────────┴──────────┴──────────┴──────────┴──────────┴──────────┴──────────┴──────────┴──────────┴──────────┴──────────┴──────────┴──────────┴──────────┴──────────┴──────────┴──────────┴──────────┴──────────┴──────────┴──────────┴──────────┴──────────┴──────────┴──────────┴──────────┴──────────┴──────────┴──────────┴──────────┴──────────┴──────────┘

---

Edit: Naturally one can do all this in a loop as well. Just take one number at time, and do the checks above (number of ones == half of n, does not go below horizon). Jump out if either check fails.