| Bytes | Lang | Time | Link |
|---|---|---|---|
| 034 | Jelly | 250530T111415Z | Jonathan |
| 199 | C gcc | 250531T165118Z | matteo_c |
| 120 | JavaScript V8 | 250529T103009Z | Arnauld |
| 215 | Maple | 250530T224613Z | dharr |
| 113 | Ruby | 250529T202600Z | Level Ri |
| 040 | 05AB1E | 250530T125832Z | Kevin Cr |
| 213 | Python 3.8 prerelease | 250529T005809Z | Lucenapo |
| 160 | Perl 5 MListUtil=max | 250529T191228Z | Xcali |
| 174 | Python 3 | 250529T073943Z | tata |
| 042 | Charcoal | 250529T072454Z | Neil |
| 950 | JavaScript Node.js | 250529T021342Z | Ahamad |
| 315 | Python3 | 250528T221114Z | Ajax1234 |
Jelly, 37 34 bytes
ḤØ+ṗSÐḟÄAƑ$ƇµIHŻ⁸_ÄṬ€a"z0Ṛị“/\ ”Y)
A monadic Link that accepts a positive integer and returns a list of strings.
How?
ḤØ+ṗSÐḟÄAƑ$ƇµIHŻ⁸_ÄṬ€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
⁸_ - 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
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);}
Brief explanation
Function
q is a recursive function that at each step:
- if the current height
sis negative, that is, the path goes below the initial height, discard the current path; - if the length
cof the current path is twice the input, i.e. the goal length has been reached, and the current heightsis equal to zero, i.e. the final and initial heights of the path are the same, output the bufferoand terminate; - otherwise, adds a new straight line, either
/or\\, to the current path and recursively callq.
Variables
- before the first call of
q,nis the input; after, it is equal to the length of the final path + 1; ois the output buffer, initialized in the first call ofq;cis the length of the current path;sis the height of the current path;dis the direction of the new line, either+1or-1;iis an auxiliary variable.
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
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
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.
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}}
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)}}
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
05AB1E, 40 bytes
®1‚I·ãʒO_}ʒηOdP}εDê„\/‡yγε¦0ª}˜.¥ú€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
0ª # 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¤Ā(ªdP}/ʒηO¤_sd`P}/ʒηOd`yO_P}/etc. for the same byte-count.
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]
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
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]
Charcoal, 42 bytes
NθFE…⊘X⁴θX⁴θ↨ι²¿∧⁼θΣι⬤ι›⊗Σ…ι⊕λλ«Fι¿κ↗¹¶\D⎚
Try it online! Link is to verbose version of code. Explanation:
Nθ
Input n.
FE…⊘X⁴θX⁴θ↨ι²
Loop over all binary numbers of length 2n.
¿∧⁼θΣι⬤ι›⊗Σ…ι⊕λλ«
If this number corresponds to a valid path, then...
Fι¿κ↗¹¶\D⎚
... output the corresponding path.
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));
}
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)]