Just on the top of it, it does sound a bit homework-ish, but it interested me none the less.

You seem to indicate that you can jump multiple steps in the horizontal, but can you also jump multiple steps vertically, or are you limited to vertical stepping by one?

Is there one particular starting and ending point, such as the upper-left and bottom-right corners, or can you start from any point on the upper row as long as you end up on the bottom row? Assuming it is, this problem sounds as if it would almost reduce to a standard maze problem, for which there are numerous solutions available. If the latter, then I see the problem getting much more complex and time-consuming, since you have to consider starting from each location on the top row, at which point I would start looking for a more unusual solution, such as one using a genetic algorithm or finite-state automata. (I once used the latter in solving a maze for a class-quite interesting.)

I can't think of any modules off-handedly that would help (although if you have to get into one of those more unusual solutions I mentioned, perhaps something in the AI section of CPAN or dealing with discrete finite automata might be helpful).

As to thinking-caps, the reason I asked above about multiple vertical steps was because if so, you could rotate a copy of the array around the axis between upper-left and lower-right corners to aid in scanning for vertical jump possibilities.

I don't know if that helps any, but it does sound like an interesting problem, and I do hope you have the opportunity to post more regarding the problem.

Update: I must agree with Abigail-II-can you please clairify the notation you are using for your path? I could not make sense of the path at one point, and was unsure if I was misunderstanding or if there was an error in the path. Thanks.

Update: Appologies to Abigail-II and others for introducing something more complicated than necessary for solving a problem. My reason for suggesting such things was a weakness in the arena of graph problems.

If you can start on any top row location, and finish on any bottow row location, the problems doesn't at all become much more complex and time consuming. Just add two more nodes to the maze: a start node with exits to all the valid top row locations, and a finish node, with entries from all the valid bottow row locations, and you have a "standard maze" again, with 1 start, and 1 end position.

Now, why on earth you are referring to the AI or finite automata to solve this problem is beyond me. It's a graph problem, all you want is a path from one end to the other, and if there are multiple paths, you want to find a minimal one using some measurement.

Abigail

There is also no mention of wether or not the 1's need to be adjacent..

So you seem able to do this...

1 1 0 0 0 0 0
0 0 0 0 0 1 1
0 1 1 0 0 0 0
0 0 0 0 0 1 0
0 0 1 0 1 0 0


Where the shortest path would seem to be 16263.

Update: nosbod clarified that the shortest path in the above example would rather be 26365 as you want to jump the least number of columns and not the LEFTMOST route...which would suggest the you could start anywhere on the top row..?

-----
Of all the things I've lost in my life, its my mind I miss the most.

that would be a valid route, yes

Yes, you are right, it is possible tojump horizontally multiple steps and vertically by one step.

There is no particular starting and ending point so i guess a genetic algorithm or finite-state automata would be worth looking into

The path that I gave as an example (1,3,1,1,1,1,3,4,3,1,1,1,3,1,1) is a route that uses the first 1 of each row. It is not the best route but is just an example to show a route through the matrix.

Apologies for the messy code. It is heavily commented which makes it look worse. I think this just about works but is not particularly nice. It basically loops recursively starting at the top left and working down the left hand side of the matrix. So, just using the first 4 rows as an example it would loop through the columns in this way:

1,1,1,1
1,1,1,2
1,1,1,3
1,1,1,4
......
1,1,1,21
1,1,2,1
1,1,2,2
1,1,2,3
......
1,1,3,1
1,1,3,2
.......
1,2,1,1
1,2,1,2
......
.......
21,21,21,21


It only stores the route if at every position within the observed route there are 1's

loop(0);


# the next section takes each route and counts the number of unique sn
+p's for each route

# for the num of possible routes through the matrix
for $i (0 ... $#finalroute)
{
    $number_of_unique_columns=0;
    %count=();

    
# for each step of the particular route we are looking at
    for (@{$finalroute[$i]}) 
    {
    $count{$_}++;        
    }  
# this loop counts the number of keys , therefore gives the number of 
+columns used in this route thru the matrix                      
    for (keys %count)         
    {
    $number_of_unique_columns++;                        
    }
    $route[$i]=$number_of_unique_columns;
}

#  $column_limit is user input set at the beginning and is the cut-off
+ for the num of columns used                                        
for $i ( 1 ... $column_limit )
{

#step the route array which has the number of columns used #for each r
+oute. If it equals the $i value (number of #columns) we
#are currently looking at then print out the route thru the #matrix th
+at is associated with it i.e @{$finalroute[$_]}
    for (0 ... $#route)           
    {                    
    print "@{$finalroute[$_]}\n$route[$_]\n" if  $route[$_]==$i;
    }
}






sub loop{


    my ($row,@array)=@_  ;
    
    
    for (1 ... $#number_of_columns)
    {
    push @array,$_ if $matrix[$row][$_] ==1;
    
    my $length=@array;
    my $lengthofmatrix=@matrix;

    if ($row==$lengthofmatrix)
       {
           $finalroute[$block][$y]=[@array] if                        
+$length==$lengthofmatrix;
           $y++ if $length==$lengthofmatrix;      
    }
    else
    {
        loop($row+1,$block,@array);
    }
    
    pop @array if $matrix[$row][$_]==1;
    
    }

        
}
[download]

cheers

whoops, the sub loop should be

sub loop{


    my ($row,@array)=@_  ;
    
    
    for (1 ... $#number_of_columns)
    {
    push @array,$_ if $matrix[$row][$_] ==1;
    
    my $length=@array;
    my $lengthofmatrix=@matrix;

    if ($row==$lengthofmatrix)
       {
           $finalroute[$y]=[@array] if     $length==$lengthofmatrix;
           $y++ if $length==$lengthofmatrix;      
    }
    else
    {
        loop($row+1,@array);
    }
    
    pop @array if $matrix[$row][$_]==1;
    
    }

        
}
[download]

Umm, except DFA stands for Deterministic Finite Automata. The module author got it wrong.

Abigail

ah maybe should have made that more clear. If you jump five columns to the right you would be using two columns not 5. Is Dijkstra's algorithm appropriate still?

thanks

No, I don't think you can use Dijkstra's algorithm in this case. Because in Dijkstra's algorithm, if you can go from one node to another in say, two steps, it doesn't matter which two steps you take, and furthermore, the best overall solution will not take three steps between those nodes. But that's not true in this matrix case.

In fact, this problem might even be NP-complete.

Abigail

What format are you getting the matrix in..?

If it's a file then for each line all you want to do is find the first '1' and return the position of the number.

...or have I over simplified this..?

Update: I believe Abigail-II is refering to this Dijkstra'a Shortest Path Algorithm or this

the matrix does come in the form of a file. I read each line into an array.

yeah, i'm not just looking for the leftmost vertical route down through it but the one that uses fewest columns.

use strict;

my @matrix=('111000110000010000100',
        '001111001001011110001',
            '111110111000011110100',
        '110001110000010001111',
        '110001110000100001111',
        '111111111111001111111',
        '001110001110111111010',
        '000111001110111110001',
        '001001000001010000001',
        '110111111000011111111',
        '111001110111110001111',
        '110110111111111110100',
        '000111001110001110001',
        '110111111000101111111',
        '110110111111001110100');

my (@packed, @size, %hash, @lines);

push @packed,pack('B*',$_) for (@matrix);
push @size, s/1//g for (@matrix);

$hash{$_}++ for (@size);

for my $s (sort keys %hash) {
  while ($hash{$s}) {
    for my $x (0..$#size) {
      next if $size[$x]!=$s;
      my @new_lines=();
      $hash{$s}--;
      my $flag=0;
      for my $t (@lines) {
        if (unpack('B*',($t & $packed[$x]))>0) {
          $flag=1;
          push @new_lines, ($t & $packed[$x]);
        } else {
      push @new_lines, $t;
        }
      }
      push @new_lines, $packed[$x] if (!$flag);
      @lines = (@new_lines);
    }
  }
}

my $final;

for my $row (@packed) {
  for my $line (@lines) {
    my $match=unpack('B*',($row & $line));
    my $count=1;
    if ($match>0) {
      while ($match=~s/^0//g) {$count++};
        $final.=$count;
      last;
    }
  }
}

print "$final\n";
[download]

Hope it helps
UnderMine

it works perfectly and in the blink of an eye. It depresses me greatly that you came back with this within minutes :-)

if you already have some code, why not posting it? This will give the monks something to start on. Interesting problem, though.

CU
Robartes-

If a solution use column n, then column n+1, then column n again, does that count as 3 columns or 2?

Ie. Is the winner determined by the fewest number of columns used, or the fewest number of sideways jumps?

the winner is decided by the fewest number of columns used. The number of sideways jumps is irrelevant

In that case, read in your matrix and invert it (rows become columns and vice-versa). Then convert each row to a number (bin to decimal). A complete path will be any two (or more) rows that when or'd together, consist of all 1's. (ie. with 15 columns (in your original matrix) a value of 32767).

To determine the possible routes start by or'ing the row values together in pairs, any two that result in 32767 is a solution. If you don't find a route, starting or'ing them together 3 at a time and so on.

You can pre-determine if there are any solutions at all by or'ing all the column masks together. If the result is not 32767, there is no route.

I get this output from the code below.

C:\test>215606
No 2-column solutions found
There are 1956 3-column solutions

C:\test>
[download]

The code

Read more... (2 kB)

Of course, that includes duplicates triplets, and it only tells you which columns can be combined to form solutions. not the actual solutions themselves, but it could give you a starting point.

You could also make a generic solution by converting the nested loops to a recursive solution, but it eats memory at a prodigous rate. It depends if you need all possible solutions, of just one (or all) of the shortest.

---

Okay you lot, get your wings on the left, halos on the right. It's one size fits all, and "No!", you can't have a different color.
Pick up your cloud down the end and "Yes" if you get allocated a grey one they are a bit damp under foot, but someone has to get them.
Get used to the wings fast cos its an 8 hour day...unless the Govenor calls for a cyclone or hurricane, in which case 16 hour shifts are mandatory.
Just be grateful that you arrived just as the tornado season finished. Them buggers are real work.

           Solutions found
Prob.    1st.   2nd ... last

10010    10000  10000  00010
01100    01000  01000  00100
01110    01000  01000  00010
11000    10000  01000  01000

Score      2      2      3
[download]

Put a marker at the start of each row, when the top marker is to be reset you've found all solutions.

When you find a 1 descend a row.

When you reach the end of a row, reset its marker to the start and continue solving from the above row.

When you find a 1 on the last row, score your solution and do what you want depending on the quality of your answer: save it, trash it, quit or continue solving.