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.
Input: $N = 2 S / \ / _ \ /\ /\ /__\ /__\ E Output: RR, LHR, LHLH, LLHH, RLH, LRH Input: $N = 1 S / \ / _ \ E Output: R, LH
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.
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:
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).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.
For all solutions, we assume we read $N from standard input.
We have the following recursive function:
sub steps ($x, $y, $path) {
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.
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.
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 ""
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] = '\0';
steps (size, 0, path, 0);
}
return (0);
}
Find the full program on GitHub.
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.
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.
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.
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.
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.
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.