in reply to The Matrix

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?

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.

Replies are listed 'Best First'.
Re: Re: The Matrix
by nosbod (Scribe) on Nov 25, 2002 at 16:47 UTC
    the winner is decided by the fewest number of columns used. The number of sideways jumps is irrelevant
[reply]

      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.

[reply]
[d/l]
[select]
        yes, I like this. In this instance I don't actually need the solution itself I just need to know which columns provide the solution.

        It does have to be a generic solution and the one that I worked on did indeed hammer memory but came out with all solutions up to a max number of the columns set by the user as an arguement (or it should have done). I think a generic version of your solution would work better though

[reply]

In Section Seekers of Perl Wisdom