# Perl Weekly Challenge: Find Possible Paths

by Abigail ## Challenge

You are given size of a triangle.

Write a script to find all possible paths from top to the bottom right corner.

In each step, we can either move horizontally to the right (H), or move downwards to the left (L) or right (R).

BONUS: Try if it can handle triangle of size 10 or 20.

### Examples

Input: $N = 2 S / \ / _ \ /\ /\ /__\ /__\ E Output: RR, LHR, LHLH, LLHH, RLH, LRH Input:$N = 1

S
/ \
/ _ \ E

Output: R, LH


## Discussion

The number of possible paths grows rapidly with the height of the triangle. These are known as the large Schröder numbers. For a height of 10, there are 1,037,718 possible paths, for a height of 20, this is a whopping 17,518,619,320,890 different paths. And while the solutions below are all able to handle that in theory, one probably doesn't have the stamina to watch them all scroll by. The Perl solution below takes (on my computer) about 4.7 seconds to list all the paths of a triangle of size 10. Extrapolating this gives an estimated running time of over 2.5 years to list all the paths of a triangle of size 20. Even the C solution is estimated to take more than 1.5 years to complete.

## Solution

First, we give the points in the triangle coordinates; the first coordinate (x) is the vertical distance from the bottow row, the second coordinate (y) is the horizontal distance from the right diagonal. So, the start point has coordinates ($N, 0), and the end point has coordinates (0, 0). For instance, a triangle of height 3 looks like this:  (3, 0) / \ (2, 1) -- (2, 0) / \ / \ (1, 2) -- (1, 1) -- (1, 0) / \ / \ / \ (0, 3) -- (0, 2) -- (0, 1) -- (0, 0)  We can now express the three transitions into changes of the coordinates: • L: (x, y) => (x - 1, y + 1) • R: (x, y) => (x - 1, y) • H: (x, y) => (x, y - 1) Furthermore, there are some conditions for each transition to happen: • For an L or R condition we need x > 0 (that is, we can only do an L or R transition if we are not at the bottom of the triangle). • For an H transition, we need y > 0 (that is, we can only do an H transition if we are not at the right edge of the triangle). Given this, we can now easily make a recursive function which gets three arguments: the x and y coordinates of a point, and a path how we got there. Initially, this will be called with ($N, 0) as the coordinates of the top vertex, and the empty string as the path to get there. If we are at (0, 0), we print the path on how we got there. Else, we recurse using all the possible steps we can take from that point.

say    $path if$x == $y == 0; steps ($x - 1, $y,$path . "R") if $x > 0; steps ($x - 1, $y + 1,$path . "L") if $x > 0; steps ($x,     $y - 1,$path . "H") if $y > 0; }  Which we will call as: steps (<>, 0, "");  Find the full program on GitHub. ### AWK Recursive function: function steps (x, y, path) { if (x == 0 && y == 0) { print path return } if (x > 0) { steps(x - 1, y, path "R") steps(x - 1, y + 1, path "L") } if (y > 0) { steps(x, y - 1, path "H") } }  Called as: { steps($1, 0, "")
}


Find the full program on GitHub.

### Bash

Recursive function:

function steps () {
local x=$1 local y=$2
local path=$3 if ((x == 0 && y == 0)) then echo$path
return
fi
if   ((x > 0))
then steps $((x - 1))$y         ${path}R steps$((x - 1)) $((y + 1))${path}L
fi
if   ((y > 0))
then steps $x$((y - 1)) ${path}H fi }  Reading input and calling the function: read number steps$number 0 ""


### C

Recursive function:

void steps (int x, int y, char * path, size_t l) {
if (x == 0 && y == 0) {
printf ("%s\n", path);
return;
}
if (x > 0) {
path [l]     = 'R';
path [l + 1] = '\0';
steps (x - 1, y,     path, l + 1);
path [l]     = 'L';
path [l + 1] = '\0';
steps (x - 1, y + 1, path, l + 1);
}
if (y > 0) {
path [l]     = 'H';
path [l + 1] = '\0';
steps (x,     y - 1, path, l + 1);
}
}


Since C doesn't make it easy to concatenate strings, we're modifying the path string in place. Therefore, we need to pass in the length of the current path, and we need to allocate enough space. It's easy to see that the length of a path is at most twice the height of a triangle. This leads to:

int main (void) {
int size;
if (scanf ("%d", &size) == 1) {
char * path;
if ((path = (char *) malloc ((size + 1) * sizeof (char))) == NULL) {
perror ("Malloc failed");
exit (1);
}
path  = '\0';
steps (size, 0, path, 0);
}
return (0);
}


Find the full program on GitHub.

### Go

Recursive function:

func steps (x int, y int, path string) {
if (x == 0 && y == 0) {
fmt . Println (path)
}
if (x > 0) {
steps (x - 1, y + 1, path + "L")
steps (x - 1, y,     path + "R")
}
if (y > 0) {
steps (x,     y - 1, path + "H")
}
}


Reading input and calling the function:

func main () {
var x int
var n, err = fmt . Scanf ("%d", &x)
if (n == 1 && err == nil) {
steps (x, 0, "")
}
}


Find the full program on GitHub.

### Java

Recursive function:

static void steps (int x, int y, String path) {
if (x == 0 && y == 0) {
System . out . println (path);
}
if (x > 0) {
steps (x - 1, y + 1, path + "L");
steps (x - 1, y,     path + "R");
}
if (y > 0) {
steps (x,     y - 1, path + "H");
}
}


Reading input, and calling this function:

public static void main (String [] args) {
Scanner scanner = new Scanner (System . in);
int size = scanner . nextInt ();
steps (size, 0, "");
}


Find the full program on GitHub.

### Lua

Recursive function:

function steps (x, y, path)
if   x == 0 and y == 0
then print (path)
return
end
if  x > 0
then steps (x - 1, y,     path .. "R")
steps (x - 1, y + 1, path .. "L")
end
if  y > 0
then steps (x,     y - 1, path .. "H")
end
end


Reading input and calling this function:

steps (tonumber (io . read ()), 0, "")


Find the full program on GitHub.

### Node.js

Recursive function:

function steps (x, y, path) {
if (x == 0 && y == 0) {
console . log (path)
return
}
if (x > 0) {
steps (x - 1, y,     path + "R")
steps (x - 1, y + 1, path + "L")
}
if (y > 0) {
steps (x,     y - 1, path + "H")
}
}


Reading input and calling this function:

  require         ('readline')
. createInterface ({input: process . stdin})
. on              ('line', number => steps (+number, 0, ""))


Find the full program on GitHub.

### Python

Recursive function:

def steps (x, y, path):
if x == 0 and y == 0:
print (path)
return
if x > 0:
steps (x - 1, y,     path + "R")
steps (x - 1, y + 1, path + "L")
if y > 0:
steps (x,     y - 1, path + "H")


Reading input and calling this function:

import sys
steps (int (sys . stdin . readline ()), 0, "")


Find the full program on GitHub.

### Ruby

Recursive function:

def steps (x, y, path)
if   x == 0 && y == 0
then puts (path)
return
end
if   x > 0
then steps(x - 1, y,     path + "R")
steps(x - 1, y + 1, path + "L")
end
if   y > 0
then steps(x,     y - 1, path + "H")
end
end


Reading input and calling this function:

steps(\$stdin . read . to_i, 0, "")


Find the full program on GitHub.