Weekly Challenge 117

Challenge, My solutions

TASK #1 › Missing Row

Task

You are given text file with rows numbered 1-15 in random order but there is a catch one row in missing in the file.

My solution

This is relatively straight forward, and can be broken down to two sub-tasks. The first is to read the file, and put any line numbers found in the %lines hash. I then have a counter that finds the first key in the hash that does not exist.

Example

$ ./ch-1.pl input.txt 
12

TASK #2 › Find Possible Paths

Task

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.

My solution

For this task I used a recursive subroutine _make_move to walk the path of all possible solutions. The inputs to the subroutine are the target size, the current x and y position, and a string representing the current path to get to that point.

The rules are pretty simple:

1. If $y is less than $size, then we can move both diagonally left and right.
2. if $x is less than $y, we can also walk horizontally to the right.

As we output as we go, this allows us to go big without using too much memory. Right now my screen is spewing out all the solutions when the size is 20 rows.

This sequence is documented in OEIS A006318, also known as Schröder number. With 20 rows there are 17,518,619,320,890 possible solutions. Even at 1000 results per second, it would take over 200 days to print the list. My solution will print out all the solutions, just don't expect the list by the time you read this :)

Examples

Because I do the walking in a different order (left, right and then sidewides), the solutions differ from the examples. It still results in the same solution.

$ ./ch-2.pl 1
Output: LH, R
A total of 2 paths found

$ ./ch-2.pl 2
Output: LLHH, LRH, LHLH, LHR, RLH, RR
A total of 6 paths found

$ ./ch-2.pl 10
... about 19 MB of text skipped ...
A total of 1037718 paths found