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>
The code
#! perl -slw use strict; my @cols=(0x15); while (<DATA>) { my @c = split' '; $cols[$_] |= ($c[$_]<<($.-1)) for 0..$#c; } my $test = 0; $test |= $_ for @cols; print "There is no solution\n" and exit if $test != 32767; my @found; # look for 2 column solutions... for my $first (0..$#cols) { for my $second (0..$#cols) { next if $first == $second; push @found, [$first,$second] # and print "Columns $first & $second is a solution" if (($cols[$first] | $cols[$second]) == 32767); } } if (@found) { print 'There are ', scalar @found, ' 2-column solutions'; exit; } else { print 'No 2-column solutions found'; } # look for 3 column solutions... for my $first (0..$#cols) { for my $second (0..$#cols) { for my $third (0..$#cols) { next if $first == $second or $first == $third or $second = += $third; my $route = $cols[$first] | $cols[$second] | $cols[$third] +; push @found, [$first, $second, $third] # and print "Columns $first & $second & $third is a soluti +on" if $route == 32767; } } } if (@found) { print 'There are ', scalar @found, ' 3-column solutions'; exit; } else { print 'No 3-column solutions found\n'; } __DATA__ 1 1 1 0 0 0 1 1 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 1 1 1 0 0 1 0 0 1 0 1 1 1 1 0 0 0 1 1 1 1 1 1 0 1 1 1 0 0 0 0 1 1 1 1 0 1 0 0 1 1 0 0 0 1 1 1 0 0 0 0 0 1 0 0 0 1 1 1 1 1 1 0 0 0 1 1 1 0 0 0 0 1 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 1 1 1 1 1 1 1 0 0 1 1 1 0 0 0 1 1 1 0 1 1 1 1 1 1 0 1 0 0 0 0 1 1 1 0 0 1 1 1 0 1 1 1 1 1 0 0 0 1 0 0 1 0 0 1 0 0 0 0 0 1 0 1 0 0 0 0 0 0 1 1 1 0 1 1 1 1 1 1 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 0 0 1 1 1 0 1 1 1 1 1 0 0 0 1 1 1 1 1 1 0 1 1 0 1 1 1 1 1 1 1 1 1 1 1 0 1 0 0 0 0 0 1 1 1 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 1 1 1 1 1 1 0 0 0 1 0 1 1 1 1 1 1 1 1 1 0 1 1 0 1 1 1 1 1 1 0 0 1 1 1 0 1 0 0
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.
In reply to Re: Re: Re: The Matrix
by BrowserUk
in thread The Matrix
by nosbod
| For: | Use: | ||
| & | & | ||
| < | < | ||
| > | > | ||
| [ | [ | ||
| ] | ] |