Print Dyck paths

Question

Definition

A Dyck path of length \2ドルn\$ can be defined as a two-dimensional path such that:

• The path consists of straight lines of equal length.
• The path goes left to right while moving either up or down. Each step is an up-right or down-right slanted line.
• The final and initial heights of the path are the same, and the path never goes below that height.

Here is an example for \$n=4\$:

 /\/\
/ \/\

The number of Dyck paths of length \2ドルn\$, \$n \geq 1\$ is the \$n\$-Catalan number: \1ドル\$, \2ドル\$, \5ドル\$, \14ドル\$, \42,ドル \ldots\$

The challenge

Given \$n \geq 1\$, draw all Dyck paths of length \2ドルn\$ in ASCII art, using characters /, \, space and newline.

Blank space around the path is fine.

The paths can be output in any order, without repetitions.

Additional rules

• Input and output means are flexible as usual. For example, the paths can be directly displayed, or output as a string with newlines, or as an array of strings where each string is line of output. If the paths are directly displayed, they should be clearly separated by blank space.
• Programs or functions are allowed.
• Standard loopholes are forbidden.
• The shortest code in bytes wins.

Test cases

Additional test cases can be generated with this program (not golfed).

\$n=1\$:

/\

\$n=2\$:

/\/\
 
 /\ 
/ \

\$n=3\$:

/\/\/\
 
 /\ 
/\/ \
 
 /\ 
/ \/\
 
 /\/\ 
/ \
 
 /\ 
 / \ 
/ \

\$n=4\$:

/\/\/\/\
 
 /\ 
/\/\/ \
 
 /\ 
/\/ \/\
 
 /\/\ 
/\/ \
 
 /\ 
 / \ 
/\/ \
 
 /\ 
/ \/\/\
 
 /\ /\ 
/ \/ \
 
 /\/\ 
/ \/\
 
 /\/\/\ 
/ \
 
 /\ 
 /\/ \ 
/ \
 
 /\ 
 / \ 
/ \/\
 
 /\ 
 / \/\ 
/ \
 
 /\/\ 
 / \ 
/ \
 
 /\ 
 / \ 
 / \ 
/ \

• Luis Mendo: Loosely related: 1, 2, 3
• Unrelated String: Pretty shocked this isn't a dupe, but you've done your due dilligence! Granted, this is extremely related, but my gut tells me there should be some ways to do this that aren't just directly composing generating Dyck words with pathifying them.
• Luis Mendo: @UnrelatedString I missed that one, thanks!
• DLosc: Superficially related

Answer 1

Jelly, (削除) 37 (削除ここまで) 34 bytes

ḤØ+ṗSÐḟÄAƑ$ƇμIHŻ8_ÄṬ€a"z0Ṛị"/\ "Y)

A monadic Link that accepts a positive integer and returns a list of strings.

Try it online!

How?

ḤØ+ṗSÐḟÄAƑ$ƇμIHŻ8_ÄṬ€a"z0Ṛị"/\ "Y) - Link: positive integer, N
ḤØ+ṗ - [-1,1] Cartisian power 2N
 SÐḟ - discard those with non-zero sum
 ÄAƑ$Ƈ - keep only those with all non-negative cumulative sums
 μ ) - for each UpDownSeq in that:
 I - deltas of UpDownSeq -> [v2-v1, v3-v2, ...]
 H - halve
 Ż - prefix with a zero
 8_ - subtract from UpDownSeq
 -> UpDownSeq with zeros replacing the first of each non-leading run of equal values
 Ä - cumulative sums
 Ṭ€ - untruth each (e.g. 3 -> [0,0,1])
 a" - zipwise logical AND with UpDownSeq
 z0 - transpose with filler zero
 Ṛ - reverse
 ị"/\ " - 1-index, cyclically into "/\ "
 Y - join with newline characters

Answer 2

Charcoal, 42 bytes

NθFE...⊘X4θX4θ↨ι2¿∧=θΣι⬤ι›⊗Σ...ι⊕λλ«Fι¿κ↗1¶\D⎚

Try it online! Link is to verbose version of code. Explanation:

Nθ

Input n.

FE...⊘X4θX4θ↨ι2

Loop over all binary numbers of length 2n.

¿∧=θΣι⬤ι›⊗Σ...ι⊕λλ«

If this number corresponds to a valid path, then...

Fι¿κ↗1¶\D⎚

... output the corresponding path.

Answer 3

Python 3, 174 bytes

lambda w:map("\n".join,g(w))
p=lambda s:[' '+i for i in s]
g=lambda w,s=[]:sum([g(w+~W,p(S)+['/'+' '*W+'\\'+(s or" ")[-1]])for W in range(w)for S in g(W,p(s[:-1]))],[])or[s]

Try it online!

Answer 4

Ruby, 113 bytes

->n{(1<<n*=2).times{|i|q=r=0
s=(" "*n+$/)*n
n.times{|j|s[j-(-q-q-=~0**k=i[j])/2*~n]='\/'[k];r|=q}
-q|r>0&&$><<s}}

Try it online!

Saved 3 bytes by replacing puts with alternate output method. Also r>0 means q has never been (and is not) negative. So 0 is the only possible value of q that will leave -q|r positive.

Changed q+= to q-= to eliminate ~ in [k]. Reversed signs: j+(1+q+q..)/2 -> j-(-q-q..)/2 rounding toward negative infinity so the 1 is no longer needed.

Ruby, 121 bytes

->n{(1<<n*=2).times{|i|q=r=0
s=(" "*n+$/)*n
n.times{|j|s[j+(1+q+q+=~0**k=i[j])/2*~n]='\/'[~k];r|=q}
r>0&&q==0&&(puts s)}}

Try it online!

Generates all 1<<2n possible paths and discards those that don't finish at the same height they started at or have any negative excursion. q is the current height and r keeps track of negative excursions. q is ORed with r. If q is ever negative, r will become negative.

Commnented code

->n{(1<<n*=2).times{|i| #Double n. Iterate 1<<n times
 q=r=0 #Setup a row pointer q and a row sign checker r. First row will be row 1.
 s=(" "*n+$/)*n #Make a canvas of n rows each of n spaces plus newline
 n.times{|j| #Iterate left to right
 s[j+ #Modify a character in column j
 (1+q+q+=~0**k=i[j])/2* #Vertical index from bottom (1 + old q + new q)/2. q increased/decreased by 1 depending on bit j of i 
 ~n]='\/'[~k] #Multiply vertical index by ~n giving a negative number (in ruby, index -1 is the last char in a string)
 r|=q} #OR q with r. r will become negative if q is ever negative
 r>0&&q==0&&(puts s) #If r still positive and q==0 back on 1st row, output.
}} #Close i loop an return from function

Answer 5

JavaScript (V8), 120 bytes

f=(n,y=N=n|=o=[],d=0,r=o[y]||`
`)=>y>N?0:o[o[y]=r.padEnd(N-+--n)+"/\\"[d],n+N?f(n,y-!d)|f(n,y+d,1):y-N||print(...o),y]=r

Try it online!

Commented

f = ( // f is a recursive function taking:
 n, // n = input
 y = // y = vertical position, initially set to n
 N = n |= // N = copy of input
 o = [], // o[] = output (array of strings)
 d = 0, // d = direction (0 = upwards, 1 = downwards)
 r = o[y] || `\n` // r = current row, or a newline if undefined
) => //
y > N ? // if y goes below the starting row:
 0 // abort
: // else:
 o[ //
 o[y] = // update the current row:
 r.padEnd // pad r with spaces to reach a width of
 (N - +--n) // N - n, where n is decremented beforehand
 + "/\\"[d], // append either '/' or '\' according to d
 n + N ? // if n not equal to -N:
 f( // do a 1st recursive call:
 n, y - !d // decrement y if d was already set to 0
 // go upwards (d undefined -> d = 0)
 ) | // end of recursive call
 f( // do a 2nd recursive call:
 n, y + d, // increment y if d was already set to 1
 1 // go downwards (d = 1)
 ) // end of recursive call
 : // else (n = -N):
 y - N || // abort if y is not equal to N
 print(...o), // otherwise, print the output
 y // restore the current row ...
 ] = r // ... to r

Answer 6

JavaScript (Node.js), 950 bytes

Golfed version. Attempt This Online!

eval(function(p,a,c,k,e,r){e=function(c){return(c<a?'':e(parseInt(c/a)))+((c=c%a)>35?String.fromCharCode(c+29):c.toString(36))};if(!''.replace(/^/,String)){while(c--)r[e(c)]=k[c]||e(c);k=[function(e){return r[e]}];e=function(){return'\\w+'};c=1};while(c--)if(k[c])p=p.replace(new RegExp('\\b'+e(c)+'\\b','g'),k[c]);return p}('3 h={\'/\':[[0,1,\'\\\\\'],[-1,1,\'/\']],\'\\\\\':[[1,1,\'\\\\\'],[0,1,\'/\']]};u f(a){3 9=i(2*a).j().k(()=>i(2*a).j(\' \'));9[a][0]=\'/\';3 6=[[7.l(7.m(9)),2*a-1,a,0,\'/\']];v(6.w>0){3[b,8,c,o,p]=6.x();d(8===0&&c===a){y.z(b.k(q=>q.r(\'\')).r(\'\\n\'));A}d(8){B(3[s,t,e]C h[p]){3 4=c+s;3 5=o+t;d(4<=a&&4>=0&&5>=0&&5<2*a){3 g=7.l(7.m(b));g[4][5]=e;6.D([g,8-1,4,5,e])}}}}}',40,40,'|||const|newX|newY|queue|JSON|remainingLength|grid||currentGrid|xPos|if|newChar||newGrid|transformations|Array|fill|map|parse|stringify||yPos|lastChar|row|join|dx|dy|function|while|length|shift|console|log|continue|for|of|push'.split('|'),0,{}))

Ungolfed version. Attempt This Online!

// Define transformation rules for each character
// Each rule defines possible next coordinates and characters
const transformations = {
 '/': [[0, 1, '\\'], [-1, 1, '/']], // For '/' character: can go right or up-left
 '\\': [[1, 1, '\\'], [0, 1, '/']] // For '\' character: can go down-right or right
};
function generatePattern(size) {
 // Create a 2D grid filled with spaces
 const grid = Array(2 * size).fill().map(() => Array(2 * size).fill(' '));
 
 // Place the starting character '/' at position [size, 0]
 grid[size][0] = '/';
 
 // Initialize queue with [grid, remaining_length, x_position, y_position, last_character]
 const queue = [[JSON.parse(JSON.stringify(grid)), 2 * size - 1, size, 0, '/']];
 
 while (queue.length > 0) {
 const [currentGrid, remainingLength, xPos, yPos, lastChar] = queue.shift();
 
 // If we've reached the target position (remaining_length=0, x=size), print the result
 if (remainingLength === 0 && xPos === size) {
 console.log(currentGrid.map(row => row.join('')).join('\n'));
 continue;
 }
 
 // If we still have length remaining, explore possible next moves
 if (remainingLength) {
 for (const [dx, dy, newChar] of transformations[lastChar]) {
 const newX = xPos + dx;
 const newY = yPos + dy;
 
 // Check if the new position is valid (not going below the middle line)
 // Also ensure we're not accessing out of bounds
 if (newX <= size && newX >= 0 && newY >= 0 && newY < 2 * size) {
 // Create a deep copy of the grid
 const newGrid = JSON.parse(JSON.stringify(currentGrid));
 
 // Place the new character
 newGrid[newX][newY] = newChar;
 
 // Add new state to the queue
 queue.push([newGrid, remainingLength - 1, newX, newY, newChar]);
 }
 }
 }
 }
}
// Generate and print patterns for sizes 1 through 5
for (let i = 1; i <= 5; i++) {
 generatePattern(i);
 console.log('-'.repeat(50));
}

• Lucenaposition: That is unusually long code.
• doubleunary: "950 bytes" — perhaps that could be made shorter still. Terser converts the ungolfed version to 469 bytes, and that can be golfed further.

Answer 7

Python 3.8 (pre-release), (削除) 235 (削除ここまで) (削除) 234 (削除ここまで) 213 bytes

n=int(input())
for t in range(4**n):
 s=[1];q=[2*n*[' ']for _ in'.'*n]
 for e in q[0]:s+=s[-1]+t%2*2-1,;t//=2
 for a,b in zip(s,s[1:]):q[-min(a,b)%n][t]='/\\'[a>b];t+=1
 [print(*_,sep='')for _ in(all(s)==s[-1])*q]

Try it online!

Answer 8

05AB1E, 40 bytes

®1‚I·ãʒO_}ʒηOdP}εDê„\/‡yγε¦0a} ̃.\ú€SζJR»

Outputs as a list of multi-line strings.

Try it online or verify all test cases (with additional "\n\n" join in the footer to pretty-print the list).

Explanation:

®1‚ # Push pair [-1,1]
 I· # Push the input, and double it
 ã # Take the cartesian product of [-1,1] with 2*input
ʒ # Filter this list of lists:
 O # Where the sum
 _ # Equals 0
}ʒ # Filter it further by:
 ηO # Get the cumulative sums:
 η # Get the prefixes
 O # Sum each prefix
 d # Check for each whether it's non-negative (>=0)
 P # Check that's truthy for all of them
 }ε # After the filters: map over the valid lists:
 Dê„\/‡ # Transform all -1s to "\" and 1s to "/":
 D # Duplicate the list
 ê # Uniquify and sort this copy: [-1,1]
 „\/ # Push string "\/"
 ‡ # Transliterate all -1 to "\" and 1 to "/" in the list
 y # Push the current list again
 γ # Group it into sublists of adjacent equal values
 ε # Map over each group:
 ¦ # Remove the first item
 0a # And append a 0 instead
 } ̃ # After the inner map: flatten the list of modified groups
 .\ # Undelta it (cumulative sum with additional prepended 0)
 ú # Pad that many leading spaces to the "/" and "\",
 # at the same positions in both lists
 €S # Convert each inner string to a list of characters
 ζ # Zip/transpose; swapping rows/columns,
 # with " " as filler for unequal length rows
 J # Join each inner list of characters back together
 R # Reverse the list of lines
 » # Join this list of strings with newline-delimiter
 # (after which the list is output implicitly as result)

Minor note: the ʒO_}ʒηOdP} could alternatively be ʒηO¤Ā(adP}/ʒηO¤_sd`P}/ʒηOd`yO_P}/etc. for the same byte-count.

Answer 9

Python3, 315 bytes

T={'/':[(0,1,'\\'),(-1,1,'/')],'\\':[(1,1,'\\'),(0,1,'/')]}
def f(n):
 b=[[' ']*2*n for _ in range(2*n)];b[n][0]='/'
 q=[(b,2*n-1,n,0,'/')]
 for b,L,x,y,l in q:
 if[0,n]==[L,x]:print('\n'.join(map(''.join,b)));continue
 if L:
 for X,Y,c in T[l]:
 if x+X<=n:B=eval(str(b));B[x+X][y+Y]=c;q+=[(B,L-1,x+X,y+Y,c)]

Try it online!

• Luis Mendo: That was quick!
• Lucenaposition: 285 bytes (I hope it works)
• ceilingcat: Building on @Lucenaposition 279 bytes

Answer 10

Perl 5 -MList::Util=max,all , 160 bytes

map{$l=0;$z=1;$m=max@p=map{$l-$_||($z+=$_);$z*($l=$_)}/../g;{say map$m-abs?$":/-/?'\\':'/',@p;$m--&&redo}}grep{$t=0;(all{($t+=$_)+1}/../g)*!$t}glob"{+,-}1"x<>x2

Try it online!

Answer 11

C (gcc), (削除) 213 (削除ここまで) (削除) 208 (削除ここまで) (削除) 204 (削除ここまで) 199 bytes

• -4 bytes thanks to @ceilingcat

q(n,o,c,s,d,i)char*o;{if(!o)for(o=calloc(++n,n+=n);i<n*n/2;)o[i++]=i%n?32:10;(s+=d)<0||(o[i=c+((n+d)/2-s)*n]="\\\n/"[d+1],++c-n?q(n,o,c,s,-1)+q(n,o,c,s,1):s||puts(o+1),o[i]=32);}f(n){q(n,0,0,0,0,0);}

Try it online!

Brief explanation

Function

q is a recursive function that at each step:

• if the current height s is negative, that is, the path goes below the initial height, discard the current path;
• if the length c of the current path is twice the input, i.e. the goal length has been reached, and the current height s is equal to zero, i.e. the final and initial heights of the path are the same, output the buffer o and terminate;
• otherwise, adds a new straight line, either / or \\, to the current path and recursively call q.

Variables

• before the first call of q, n is the input; after, it is equal to the length of the final path + 1;
• o is the output buffer, initialized in the first call of q;
• c is the length of the current path;
• s is the height of the current path;
• d is the direction of the new line, either +1 or -1;
• i is an auxiliary variable.

• matteo_c: @ceilingcat whoops, trivial oversight

Answer 12

Maple, 215 bytes

proc(n)for d in Iterator:-NestedParentheses(n)do M:=Matrix(n,2*n);h:=n;M[h,1]:=1;X:=-2*d+~1;seq([(Z:=X[i+1]),`if`(Z=X[i],(h-=Z),NULL),(M[h,i+1]:=Z)][],i=1..2*n-1);printf("%{s}s\n",subs(1="/",-1="\\",0=" ",M))od end:

Ungolfed:

proc(n)
for d in Iterator:-NestedParentheses(n) do
 # d is an Array with 0 for "/" and 1 for "\"
 M:=Matrix(n,2*n); # height = n (extra lines of blanks allowed)
 h:=n; # start at last row (bottom of diagram)
 M[h,1]:=1; # first is "/"
 X:=-2*d+~1; # convert to +1/-1, i.e., 1 for "/", -1 for "\"
 for i to 2*n-1 do # for each step in the path
 Z:=X[i+1]; 
 if Z = X[i] then h-=Z fi; # two -1 or +1 in a row go down or up
 M[h,i+1]:=Z # store the -1 or 1 at the right height
 od;
 printf("%{s}s\n",subs(1="/",-1="\\",0=" ",M)) # output the path
od
end:

The NestedParentheses iterator iterates over properly balanced parentheses, which are in 1:1 correspondence with Dyck paths, e.g,. ()()()(()) would become /\/\/\//\\. Two // in a row means going up a level in the display, and two \\ means going down. The main golfing is to convert the inner for-do loop to a seq.

• Luis Mendo: Not many Maple answers around here; good to see one!