DEV Community

loading...

Weekly Challenge 112

Simon Green
・2 min read

Challenge, My solutions

TASK #1 › Canonical Path

Tasks

You are given a string path, starting with a slash /.

Write a script to convert the given absolute path to the simplified canonical path.

My solution

Outside the challenge, I would use the swiss army-knife of Path::Tiny to do this. Regularly readers of my blog post will know that I don't use modules outside Perl core in completing a task.

Therefore I split the supplied path by each forward slash into @parts. I then take three actions depending on the part.

  • If it is empty, do nothing. This handles the first slash, the trailing slash, and any double slashes in the path.
  • If the part is .., pop the last value from the canonical path. Even if we are already at the root (the canonical path is the root folder) it still has a .. file referencing itself.
  • Any all other cases, push the part into the canonical path.

Finally, I join the canonical parts together to generate a string separated by slashes.

Examples

» ./ch-1.pl /a/
/a

» ./ch-1.pl /a/b//c/
/a/b/c

» ./ch-1.pl /a/b/c/../../
/a
Enter fullscreen mode Exit fullscreen mode

TASK #2 › Climb Stairs

Task

You are given $n steps to climb.

Write a script to find out the distinct ways to climb to the top. You are allowed to climb either 1 or 2 steps at a time.

My solution

This one got me thinking about the best way to code it. And like other challenges, I'll be very interesting to see how other Team PWC members do it.

My first though was a recursive function, but I have been criticised in the past for using it. Then I though about some binary function where false (0) representing one step, and true (1) represented two steps.

However in the end I went with the good old recursive function called _climb. It has three arguments, the steps remaining, the current climb, and an array of arrays of all climbs. Like with the first tasks, I take different action depending on the remaining steps.

  • If there is only one step remaining, add the current climb + 1 to the list of climbs.
  • If there are two steps remaining, add the current climb + 2 × 1 step, and the current_climb + 2 steps to the list of climbs.
  • If there are more than two steps remaining, call the recursive function again twice. The first call is with one step and the second call is with two steps.

Finally I output the number of possible steps there are and each way the stairs can be climbed.

Interesting fact (assuming my code is correct): With 20 steps, there are 10,946 ways to climb them. And there are 121,393 ways to climb 25 steps.

Examples

» ./ch-2.pl 3
Output: 3

Option 1: 1 step + 1 step + 1 step
Option 2: 1 step + 2 steps
Option 3: 2 steps + 1 step

» ./ch-2.pl 4
Output: 5

Option 1: 1 step + 1 step + 1 step + 1 step
Option 2: 1 step + 1 step + 2 steps
Option 3: 1 step + 2 steps + 1 step
Option 4: 2 steps + 1 step + 1 step
Option 5: 2 steps + 2 steps
Enter fullscreen mode Exit fullscreen mode

Discussion (0)