Task — Find possible paths

You are given size of a triangle. Write a script to find all possible paths from the top to the bottom right corner.

In each step, you 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

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

Example 2
Input: $N = 1
           S
          / \
         / _ \ E
Output: R, LH

Analysis

The obvious way to do this is by recursion, checking for the paths from S to E. As N increases at some point you need the statement no warnings 'recursion' to avoid Perl complaining.

This works for me in a few seconds up to about N = 10 (1,037,718 paths), in about 30 seconds for N = 11 (5,293,446 paths) and a couple of minutes for N = 12 (27,297,738 paths) and I gave up waiting for N = 13.

The shortest path for any N is a set of N 'R's. The longest paths are 2N long, such as N 'L's followed by N 'H's, but there are many more.

I feel sure that someone who studied maths more recently than me (ie since 1969) can work out the formula for the number of paths for a triangle of height N but there's nothing like trying it.

Try it 

#!/usr/bin/perl

# Blog: http://ccgi.campbellsmiths.force9.co.uk/challenge

use v5.26;    # The Weekly Challenge - 2021-06-14
use utf8;     # Week 117 - task 2 - Find possible paths
use warnings; # Peter Campbell Smith
no warnings 'recursion';
binmode STDOUT, ':utf8';
use Encode;

my ($N, $count, $output);

find_possible_paths($_) for 1 .. 4;

sub find_possible_paths {
    
    # initialise
    $N = $_[0];
    $count = 0;
    $output = '';
    say qq[\nInput:  $N];
    
    one_step(0, 0, ''); 
    say qq[Output: paths = $count];
    say substr($output, 0, -2) if $count <= 2000;
}

sub one_step {
    
    my ($x, $y, $path);
    ($x, $y, $path) = @_;
    
    # are we there?
    if ($x == $N and $y == $N) {
        $count ++;
        $output .= qq[$path, ];
        return;
    }
        
    # move one step and recurse 
    one_step($x + 1, $y, $path . 'H') if $x < $y;
    one_step($x + 1, $y + 1, $path . 'R') unless $x == $N or $y == $N;
    one_step($x, $y + 1, $path . 'L') unless $y == $N;
}

last updated 2026-03-24 — 18 lines of code

Output

Input:  1
Output: paths = 2
R, LH

Input:  2
Output: paths = 6
RR, RLH, LHR, LHLH, LRH, LLHH

Input:  3
Output: paths = 22
RRR, RRLH, RLHR, RLHLH, RLRH, RLLHH, LHRR, LHRLH, LHLHR,
   LHLHLH, LHLRH, LHLLHH, LRHR, LRHLH, LRRH, LRLHH, LLHHR,
   LLHHLH, LLHRH, LLHLHH, LLRHH, LLLHHH

Input:  4
Output: paths = 90
RRRR, RRRLH, RRLHR, RRLHLH, RRLRH, RRLLHH, RLHRR, RLHRLH,
   RLHLHR, RLHLHLH, RLHLRH, RLHLLHH, RLRHR, RLRHLH, RLRRH,
   RLRLHH, RLLHHR, RLLHHLH, RLLHRH, RLLHLHH, RLLRHH,
   RLLLHHH, LHRRR, LHRRLH, LHRLHR, LHRLHLH, LHRLRH,
   LHRLLHH, LHLHRR, LHLHRLH, LHLHLHR, LHLHLHLH, LHLHLRH,
   LHLHLLHH, LHLRHR, LHLRHLH, LHLRRH, LHLRLHH, LHLLHHR,
   LHLLHHLH, LHLLHRH, LHLLHLHH, LHLLRHH, LHLLLHHH, LRHRR,
   LRHRLH, LRHLHR, LRHLHLH, LRHLRH, LRHLLHH, LRRHR,
   LRRHLH, LRRRH, LRRLHH, LRLHHR, LRLHHLH, LRLHRH,
   LRLHLHH, LRLRHH, LRLLHHH, LLHHRR, LLHHRLH, LLHHLHR,
   LLHHLHLH, LLHHLRH, LLHHLLHH, LLHRHR, LLHRHLH, LLHRRH,
   LLHRLHH, LLHLHHR, LLHLHHLH, LLHLHRH, LLHLHLHH, LLHLRHH,
   LLHLLHHH, LLRHHR, LLRHHLH, LLRHRH, LLRHLHH, LLRRHH,
   LLRLHHH, LLLHHHR, LLLHHHLH, LLLHHRH, LLLHHLHH, LLLHRHH,
   LLLHLHHH, LLLRHHH, LLLLHHHH