The weekly challenge 295 - Task 2: Jump Game

 1 #!/usr/bin/env perl
 2 # https://theweeklychallenge.org/blog/perl-weekly-challenge-295/#TASK2
 3 #
 4 # Task 2: Jump Game
 5 # =================
 6 #
 7 # You are given an array of integers, @ints.
 8 #
 9 # Write a script to find the minimum number of jumps to reach the last element.
10 # $ints[$i] represents the maximum length of a forward jump from the index $i.
11 # In case last element is unreachable then return -1.
12 #
13 ## Example 1
14 ##
15 ## Input: @ints = (2, 3, 1, 1, 4)
16 ## Output: 2
17 ##
18 ## Jump 1 step from index 0 then 3 steps from index 1 to the last element.
19 #
20 ## Example 2
21 ##
22 ## Input: @ints = (2, 3, 0, 4)
23 ## Output: 2
24 #
25 ## Example 3
26 ##
27 ## Input: @ints = (2, 0, 0, 4)
28 ## Output: -1
29 #
30 ############################################################
31 ##
32 ## discussion
33 ##
34 ############################################################
35 #
36 # We call a recursive function that carries the current index inside
37 # the array and the array itself. If the index is still inside the
38 # bounds of the array:
39 # - return 0 if the index points to the last element in the array
40 # - return undef if the index is out of bounds
41 # - otherwise call the function recursively for all possible jumps
42 #   from the current position; if any of those values exists, add
43 #   one to each of those and return the minimum value of all those
44 #   values.
45 
46 use strict;
47 use warnings;
48 use List::Util qw(min);
49 
50 jump_game(2, 3, 1, 1, 4);
51 jump_game(2, 3, 0, 4);
52 jump_game(2, 0, 0, 4);
53 
54 sub jump_game {
55    my @ints = @_;
56    print "Input: (" . join(", ", @ints) . ")\n";
57    my $result = jump_game_(0, @ints);
58    if(defined($result)) {
59       print "Output: $result\n";
60    } else {
61       print "Output: -1\n";
62    }
63 }
64 
65 sub jump_game_ {
66    my ($index, @ints) = @_;
67    return 0 if $index == $#ints;
68    return undef if $index > $#ints;
69    return undef if $ints[$index] <= 0;
70    my @possible_values = ();
71    foreach my $i (1..$ints[$index]) {
72       my $v = jump_game_($index + $i, @ints);
73       if(defined($v)) {
74          push @possible_values, 1+$v;
75       }
76    }
77    return undef unless @possible_values;
78    return min(@possible_values);
79 }
80