Hey, no fair changing the rules in the middle...

#!/usr/bin/perl

use strict; # https://perlmonks.org/?node_id=11114231
use warnings;

my ($startrow, $startcol, $destrow, $destcol);
my @m;
my @visited;
my $maxrow;
my $maxcol;
my $maxscore;
my $minlength;
my $best;

for my $SIZE ( 2, 3 )             # add in 1024 and be prepared to wai
+t :)
  {
# srand 42;                     # uncomment for the specified problem 
+grid
  my $W = $SIZE;
  my $H = $SIZE;
  my $maxscore = 10;
  my $Grid = [];
  for my $row ( 0 .. $H - 1 )
    {
    $Grid->[$row] = [(0)x$W];
    for my $col ( 0 .. $W - 1 )
      {
      $Grid->[$row]->[$col] = $maxscore - int(rand(2*$maxscore+1))
      }
    }
  # now add a highscore to stand out for just 1 cell in each column
  my $highscore = 21;
  for my $row ( 0 .. $H - 1 )
    {
    $Grid->[$row]->[int(rand($W))] = $highscore;
    }

  for my $row ( 0 .. $H-1 )
    {
    printf "%4d" x $W . "\n", @{ $Grid->[$row] };
    }
  print "\n";

  ($startrow, $startcol, $destrow, $destcol) = (0, 0, $H-1, $W-1);
  @m = @$Grid;
  @visited = ();
  $maxrow = $W-1;
  $maxcol = $H-1;
  $maxscore = undef;
  $minlength = undef;
  $best = undef;
  $visited[$startrow][$startcol] = 1;

  try( $startrow, $startcol, $m[$startrow][$startcol] );

  $best or die "no best found";
# print "\n$best\n\n";
  my @best = split ' ', $best;
  my @values;
  print "best path:\n";
  for ( my $i = 0; $i < @best - 4; $i += 3 )
    {
    print directions(@best[$i .. $i+5]), ' ';
#   push @values, $m[$best[$i]][$best[$i+1]];
    push @values, $best[$i+2] eq '00' ? '00' : $m[$best[$i]][$best[$i+
+1]];
    }
  print "\n= ";
  print join '+', @values, $m[$best[-3]][$best[-2]];
  print "\n= $best[-1]\n\n";
  }

sub try
  {
  my ($row, $col, $score) = @_[-3 .. -1];
# print "$row $col $score\n";
  if( $row == $destrow && $col == $destcol )
    {
    if( $maxscore )
      {
      if( $score > $maxscore or
        $score == $maxscore and $minlength > @_)
        {
        $maxscore = $score;
        $minlength = @_;
        $best = "@_";
        }
      }
    else
      {
      $maxscore = $score;
      $minlength = @_;
      $best = "@_";
      }
    return;
    }
  for my $r ( 0 .. $maxrow )
    {
    if( ++$visited[$r][$col] == 1 )
      {
#     if( $m[$r][$col] >= 0 ||
#       $r == $destrow && $col == $destcol )
        {
        if( $r < $row - 1 )
          {
          my @slide = map {($_, $col, '00') } reverse $r + 1 .. $row -
+ 1;
          try( @_, @slide, $r, $col, $score + $m[$r][$col] );
          }
        elsif( $r > $row + 1 )
          {
          my @slide = map {($_, $col, '00') } $row + 1 .. $r - 1;
          try( @_, @slide, $r, $col, $score + $m[$r][$col] );
          }
        else
          {
          try( @_, $r, $col, $score + $m[$r][$col] );
          }
        }
      }
    --$visited[$r][$col];
    }
  for my $c ( 0 .. $maxcol )
    {
    if( ++$visited[$row][$c] == 1 )
      {
#     if( $m[$row][$c] >= 0 ||
#       $row == $destrow && $c == $destcol )
        {
        if( $c < $col - 1 )
          {
          my @slide = map {($row, $_, '00') } reverse $c + 1 .. $col -
+ 1;
          try( @_, @slide, $row, $c, $score + $m[$row][$c] );
          }
        elsif( $c > $col + 1 )
          {
          my @slide = map {($row, $_, '00') } $col + 1 .. $c - 1;
          try( @_, @slide, $row, $c, $score + $m[$row][$c] );
          }
        else
          {
          try( @_, $row, $c, $score + $m[$row][$c] );
          }
        }
      }
    --$visited[$row][$c];
    }
  }

sub directions
  {
  my ($rowfrom, $colfrom, $fromscore, $rowto, $colto, $toscore) = @_;
  return +($rowfrom != $rowto ?
    $rowfrom < $rowto ? 'down' : 'up' :
    $colfrom < $colto ? 'right' : 'left') .
    ($toscore eq '00' ? '-slide' : '');
  }
[download]

Sample Output:

  21  -8
   5  21

best path:
down right 
= 21+5+21
= 47

   3  21  -6
   9  21  10
  -7   7  21

best path:
down right-slide right left up down-slide down right 
= 3+9+00+10+21+21+00+7+21
= 92
[download]

For a size of 1024 x 1024, run time is estimated to be either the twelfth of never, or three days after the heat death of the universe, whichever comes last.

Your output for the 3x3 grid looks weird

Neither do cells with 00 appear nor is it possible to go right after a right-slide.

Could it be that you coded slides as a one cell no move with weight 00?

Update:

Ok this Re^7: Code challenge: Route planning on a 2D grid makes it clearer.

Cheers Rolf
_{(addicted to the Perl Programming Language :)
Wikisyntax for the Monastery}

Yes, slides show for each cell, and the values for that cell is the special flag 00, which is a value of zero separate from an actual 0 cell.

> no fair changing the rules

Which rules do you apply?

> For a size of 1024 x 1024, run time is estimated to be either the twelfth of never,

Depends on the rules.

Cheers Rolf
_{(addicted to the Perl Programming Language :)
Wikisyntax for the Monastery}

The original rules.

I'd define the length of a path by number of necessary moves. Hence length is 0 if start and end are identical. (This facilitates adding partial solutions)

I think allowing back-moves is necessary to "solve" a 1024 x 1024 grid with an approach based on probability.

Compare this Re: Highest total sum path problem

I hope it's obvious now that this makes it pretty much

O(n**2)

with

n = length = #rows= #columns

because the number of optimal solutions is "bigger" than eternity.

Counting the distance of slides makes this far more complicated, such that you should change the challenge to "best solution so far" instead of "optimal solution".

It's also important to understand that optimal sum is easy, shortest (Hamilton) path is problematic.

My approach would be a two dimensional divide and conquer.

Like for n=1024=2**10 solving 32 smaller grids with n=32=2**5 side length.

One could also divide further to 5 stages since 4**5=1024.

The basic idea is still probabilistic.

Because of your randomization there is a probability of roughly .5 that a cell is positive.

Hence two neighboring cells (minimal distance) have the probability of .25 to be both positive.

This means that if you need to find a minimal transit between two areas with m neighboring cells, then the there is a 1-0.75**m to find it.

Hence finding very good solutions is not that difficult.

It's the optimal solution which is on another page.

But in terms of a coding challenge this should be a big plus, because the crowd loves rankings and hates math. ;)

just have fun or as Tuco said in The Good, the Bad and the Ugly: When you have to shoot, shoot. Don't talk.

As I said the crowd hates math.

And I hate changing rules ... ;)

> just have fun

I did!

Cheers Rolf
_{(addicted to the Perl Programming Language :)
Wikisyntax for the Monastery}