There are few things more exciting than a code challenge. So here is a problem similar to Highest total sum path problem. I say similar because the initial problem constraints were a bit fuzzy.

The problem is to plan an orthogonal route on a 2D rectangular grid in order to maximise point collection from the cells of the grid and minimise the distance travelled from a specified starting cell to a finishing cell. Points can be positive or negative integers (or zero). The added twist is that moving from A to B can be done in a "normal" mode where points are collected from intermediate cells (A+1 , .., B-1). Alternatively, moving can be done in a "sliding" mode where the points on said squares are not collected (perhaps to avoid negative points which will reduce the total score). But the distance counts.

If people want to modify these initial rules either because they can make the problem more generic, more useful or aid the original poster in his/her quest, please feel free to make a suggestion.

I am not sure how to post a grid here so I will assume that all our Perls native RNG will produce the same sequence given the seed 42. So, here is a grid and a path (again if people know a better way then suggest it):

srand 42;
my $W = 1024;
my $H = 1024;
my $maxscore = 10;
my $Grid = [];
for(my $i=0;$i<$W;$i++){
  $Grid->[$i] = [(0)x$H];
  for(my $j=0;$j<$H;$j++){
    $Grid->[$i]->[$j] = $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 $i=0;$i<$W;$i++){
  $Grid->[$i]->[int(rand($H))] = $highscore;
}

[download]

bw, bliako

In reply to Code challenge: Route planning on a 2D grid by bliako

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post, it's "PerlMonks-approved HTML":


  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.