Task — Jump game

You are given an array of integers, @ints. Write a script to find the minimum number of jumps to reach the last element. $ints[$i] is the maximum length of a forward jump from the index $i. If the last element is unreachable then return -1.

Examples

Example 1
Input: @ints = (2, 3, 1, 1, 4)
Output: 2
Jump 1 step from index 0 then 3 steps from index 1 
   to the last element.

Example 2
Input: @ints = (2, 3, 0, 4)
Output: 2

Example 3
Input: @ints = (2, 0, 0, 4)
Output: -1

Analysis

This is another challenge where the obvious answer uses recursion, which works, but is quite slow in Perl. A better solution might be to maintain a stack, pushing the critical variables onto it and collapsing the recursion into a loop. Maybe I'll try that next time.

However, in this case recursion is fast enough: it completes my randomised 50 member array usually in under a second, though there's probably a pathological case that takes much longer.

Crucially, at each point I try the longest possible jump first and work down, and for every chain of jumps, I abandon the search as soon the number of jumps in this chain exceeds the best number found already. For my 50 member array this usually reduces the time taken by about 99%.

Try it 

#!/usr/bin/perl

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

use v5.26;    # The Weekly Challenge - 2024-11-11
use utf8;     # Week 295 - task 2 - Jump game
use warnings; # Peter Campbell Smith
binmode STDOUT, ':utf8';

my (@ints, $best, $path, $best_path);

jump_game(2, 3, 1, 1, 4, 1, 1, 1, 8);
jump_game(2, 3, 0, 4);
jump_game(2, 0, 0, 4);
jump_game(0);
jump_game(10, 0, 0, 0, 0, 0);

# longer example
@ints = ();
push @ints, int(rand(10)) + 1 for 0 .. 49;
jump_game(@ints);

sub jump_game {
    
    my ($start_at);
    
    # initialise
    @ints = @_;
    $best = 1e6;
    $path = '[0] → ';
    $best_path = '';
    
    # solve the challenge
    min_jumps(0, 0, $path);
    
    # report results
    say qq[\nInput:  \@ints = (] . join(', ', @ints) . ')';
    say qq[Output: ] . ($best == 1e6 ? '-1' : 
        qq[$best jump] . ($best == 1 ? '' : 's') . qq[: path = $best_path]);
    
}

sub min_jumps {
    
    my ($start_at, $jumps, $reached, $s, $path);
    
    ($start_at, $jumps, $path) = @_;
    
    # edge case
    if ($ints[$start_at] == 0 and $#ints == 0) {
        $best = 0;
        $best_path = '[0]';
        return;
    }
    
    # otherwise can't go any further if we've hit a 0
    return unless $ints[$start_at] > 0;
    
    # take a jump
    $jumps ++;
    
    # but no use proceeding if we've already found a better one
    return if $jumps >= $best;
    
    # try all possible jumps from here
    for ($s = $ints[$start_at]; $s >= 1; $s --) {
        $reached = $start_at + $s;
        
        # too far
        next if $reached > $#ints;
        
        # reached the last cell; is this the shortest route?
        if ($reached == $#ints) {
            if ($jumps < $best) {
                $best = $jumps;
                $best_path = $path . qq[[$reached]];
            }
            return;
        }
        
        # recurse from where we've reached
        min_jumps($reached + 0, $jumps + 0, $path . qq[[$reached] → ]);
    }
}

Output

Input:  @ints = (2, 3, 1, 1, 4, 1, 1, 1, 8)
Output: 3 jumps: path = [0] → [1] → [4] → [8]

Input:  @ints = (2, 3, 0, 4)
Output: 2 jumps: path = [0] → [1] → [3]

Input:  @ints = (2, 0, 0, 4)
Output: -1

Input:  @ints = (0)
Output: 0 jumps: path = [0]

Input:  @ints = (10, 0, 0, 0, 0, 0)
Output: 1 jump: path = [0] → [5]

Input:  @ints = (8, 9, 2, 4, 3, 4, 1, 5, 2, 7, 4, 5, 5, 9, 10, 4, 2, 9, 7, 9, 5, 3, 8, 4, 6, 2, 5, 4, 8, 9)
Output: 5 jumps: path = [0] → [8] → [10] → [14] → [24] → [29]