Could you please specify exactly what transformations you have to work with, and correct your diagrams so that the transformations pictured are the ones that happened? For instance where you say, swap rows 0 and 1 I'm having no luck understanding what transformation is supposed to have happened.

Apologies for the lack of clarity. I neglected to mention that after swapping the rows I also reordered the columns so that they were in ascending order of the bitwise representation of their stars. So before:

  . . . x * * * (row 2, bit value 4) 
  . . . * * * * (row 1, bit value 2)
  . * * . . . * (row 0, bit value 1)

  0 1 1 2 6 6 7 (bitwise column values)
[download]

after swapping rows 0 and 1:

  . . . x * * * (still row 2)
  . * * . . . * (was row 0, now row 1)
  . . . * * * * (was row 1, now row 0)

  0 2 2 1 5 5 7 (new bitwise column values)
[download]

and after reordering columns:

  . x . . * * *
  . . * * . . *
  . * . . * * *

  0 1 2 2 5 5 7 (new bitwise column values)
[download]

Similarly the second swap gives columns (0, 1, 4, 4, 3, 3, 7), and reordering the columns gives (0, 1, 3, 3, 4, 4, 7).

Does that make it any clearer?

Hugo

That makes it a lot clearer - for a start I realize that you're counting rows from the bottom up, not the top down!

I tried the idea of converting the args into a 2D array of 0/1s with unpack, then inverting it. That way you can perform the swapping of bits on all the rows in one go (swapping anonymous arrays around). You then reinvert and pack back to ints before finally sorting and returning.

It works, but it's certainly not quicker.

I also built a lookup table for the specific case. 3-bits gives an table with 7 elements (x-column value if 0..6. 7 is impossible because it leaves no place for the 'x'). Each of the 7 first level elements has the potential for 3 sets of swaps (one for each combination of x-column value * position of the x).

Of the 21 possible combinations, 9 are impossible and 2 require no swaps (they are correctly ordered on input). For each of the 10 remaining you need either 1 or 2 pairs of column indexes that require swapping, that need to be applied to each of the args.

## 3-bit case only.
my %reorder = (
    0 => [ undef        , [[0,1]], [[0,1],[1,2]] ],
    1 => [ undef        , [[0,1]], [[0,2]]       ],
    2 => [ [[0,1]]      , undef  , [[0,1],[1,2]] ],
    3 => [ undef        , undef  , undef         ],
    4 => [ [[1,2],[0,1]], [[0,2]], []            ],
    5 => [ undef        , [[1,2]], undef         ],
    6 => [ [[0,1],[1,2]], undef  , undef         ],
);

sub reorder {
    my( $dim, $height, $v, $args ) = @_;
    my $xforms = $reorder{ $args->[ $v ] }[ $height ];
    return $args unless $xforms;
    
    for my $arg ( @$args ) {
        swapBits( $arg, @$_ ) for @$xforms;
    }
    return $args
}
[download]

That's not working code (swapBits() is undefined) but it gives feel for the notion. The problem then would be building the lookup tables, would become quite large depending upon the maximum dimensions you are hoping to handle. But if speed is the issue, and your current sub works, then using it to build the lookup once and storing it would allow runtime to be a bit quicker I think.

ADDENDUM: Having typed that in, I realise that there is no need to store the pairs of indexes. You may as well store the xformed values instead. It saves one level of depth in the lookup at the expense of the lower level having 2**n-bits values. Which is probably much of a muchness space-wise, but it avoids the need for swapBits().

You just lookup the correct array of xforms, then lookup each args value in that and replace it with the contents indexed. That would be much quicker. At the cost of the memory.

Yes, the lookup certainly would be an improvement: since the memoization is also $dim-dependent, I've written the rest of the code to assume a series of calculations with $dim fixed, so I'd only need to set up the table once per run.

In general (though I haven't benchmarked it recently[0]) I believe that @$args[ @mapping ] should be very fast, so I think either calculating the mapping array from the lookup table or (memory permitting) replacing the lookup-of-bitswaps with a lookup-of-mappings would be preferable to doing sequences of individual swaps within the array.

(I hadn't mentioned it, but the $args arrayref needs to be preserved, so serial swapping would need to be preceded by a copy.)

Hmm, of course each bitswap could be replaced by a mapping array - that way only $dim * ($dim + 1) / 2 mappings would need to be stored, rather than O($dim * (2 ^ $dim) / 2), at the cost of applying multiple mappings in some cases.

Hugo

[0] bad optimizer, no cookie

Your main task is to transform the column with the x in it, so concentrate on that first. To transform to the pattern you have in mind, I would first recode the elements in the column.

First, I would assign each element a number corresponding to its row: 0,.., $dim-1. Then I would add $dim to each element if it was equal to 'x' and 2*$dim if it was equal to '*'.

With this recoding, your transforms amount to a descending sort, and you can recover the permutation needed to create that sort by modding each element with $dim ($ele % $dim).

Now that you have the permutation, simply map all the other columns using the permutation. If you have many columns, I'd suggest creating a lookup table for the mapping. You are done.

I do not know how it compares to your code, but I would think the algorithm above is efficient. Recoding is O($dim), sorting is O($dim log $dim), and mapping is O(2**$dim). I expect that the mapping will dominate for large $dim, but the mapping copies each bit just once, which is about the minimum.

In the broader picture, your transformations induce an automorphism (permutation) on the array of bits, which by projection down to your $args array, induce an automorphism of the $args array itself. An interesting exercise would be to act directly on the $args array itself, skipping the bitwise sorting entirely.

I'm not sure I fully understood your suggestions here, perhaps again because of my own difficulties explaining the problem in the first place.

First, I would assign each element a number corresponding to its row: 0,.., $dim-1. Then I would add $dim to each element if it was equal to 'x' and 2*$dim if it was equal to '*'.

Hmm, so something like:

  my @bits = (0 .. $dim - 1);
  for (0 .. $dim - 1) {
    $bits[$_] += 2 * $dim if $v & (1 << $_);
  }
  $bits[$height] += $dim;
  my @bitmap = map $_ % $dim, sort { $b <=> $a } @bits;
[download]

If I understand this correctly, this should produce the same @bitmap that my current code calculates. I'm not sure about the efficiency: the dominant order of my current code for that calculation is O($dim), but I suspect replacing many O($dim) perl opcodes with an O($dim log $dim) C-coded sort will probably win on the constants. And the resulting code is certainly a lot clearer than I had.

Now that you have the permutation, simply map all the other columns using the permutation. If you have many columns, I'd suggest creating a lookup table for the mapping. You are done.

This bit I don't understand. Having built the mapping of bits (rows), I then applied it with this code:

  # we now know what row should go where, so build and return the mapp
+ed result
  my @invmap = sort { $bitmap[$a] <=> $bitmap[$b] } 0 .. $dim - 1;
  my @vmap = (0);
  for (0 .. $dim - 1) { 
    my $mapped = 1 << $invmap[$_];
    push @vmap, map $_ + $mapped, @vmap;
  } 
  return ($bitmap[$height], [ @$args[ @vmap ] ]);
[download]

This first inverts the mapping with a sort, then uses the inverse mapping of bits to construct a mapping for each of the 2 ^ $dim bit patterns, then applies that map to the current $args arrayref. Is that significantly different from what you're suggesting here?

In the broader picture, your transformations induce an automorphism (permutation) on the array of bits, which by projection down to your $args array, induce an automorphism of the $args array itself. An interesting exercise would be to act directly on the $args array itself, skipping the bitwise sorting entirely.

I'm not sure I understand this either: are you suggesting removing the need for the rearrangement by recoding the rest of the program to work on the array in place, eg using an auxiliary array to describe the bit-order? That might be interesting, but the primary benefit of the rearrangement is to make logically equivalent arglists identical so that memoization can short-circuit the calculations. If I don't do the actual rearrangement, I still need to identify a signature for the arglist that encapsulates the same rearrangement for the memoization to work, and I suspect that means doing the work of the actual rearrangement in all but name.

Apologies if I've wildly misunderstood any of the things you were trying to say.

Hugo

I think we are mostly on the same page.

The first code snippet in your post is precisely what I was suggesting: recode the elements of the bit array in the 'x' column to easily discover the set of transformations (resulting in a permutation of the rows)) needed to rearrange the 'x' column in the desired form.

I think your second snippet of code executes what I was suggesting: take the permutation computed in the first snippet and apply it to every column of your bit array. I'm sorry for not making more effort to understand your code; my comments may very well be redundant.

My 'broader picture' comment was just suggesting that explicit twiddling of the bit array might be able to be bypassed. If I understand your $args array correctly, a value z at index i means that you have z columns with bitstring i. The permutation converts each bitstring into another bitstring, which has the effect of shuffling the elements of $args. For instance transposing bit rows 1 and 2 would turn bit pattern '3' into bit pattern '5', so if $args3 = z, then after the transposition $args5 = z. In effect z has been permuted from the '3' postion in the $args array to the '5' position. The same thing happens for all the other elements of $args. Thus permuting the bit rows in the bit array is tantamount to permuting the elements of $args. Mathematically, one would say that the automorphism of the bit array induces an automorphism the $args.

Whether manipulating the $args directly is faster than the bit twiddling depends on how slow the bit row copying is and, as you mention, speedups like memoization. I mostly made the comment for mathematical interest.

-Mark

It's one part of my attempt to write a reasonably efficient function to calculate f(a, b), the number of full-spectrum rook's walks on an a x b board. (The integer sequence A096121 handles the specific case of a = 2, but I wish to extend to the more general case.)

I'd be kinda surprised if there were already a CPAN module for this, though I suspect an understanding of PDL might help.

Hugo

This sounds like a graph theory problem. (Though, given that I've been using Graph a bunch, and even submitted patches to it, recently, everything's been looking kinda like a nail right now.)

Here's what I mean

1. Create an undirected graph of X x Y vertices, presumably labeled a1, a2, b1, etc.
2. Create edges between all the squares that are connected to one another by means of how a rook can move. So, a1 has an edge to both a2 and b1, but a2 and b1 don't have an edge between them.
3. Put all the vertex names into a hash to mark if you've been there or not.
4. Pick a starting point. Mark it as being seen.
5. Find all the neighbors.
6. Iterate through them, recursively calling this function until you have touched every square.

The problem statement (as I read it) doesn't make mention of going back and forth between two squares (though it would be a valid variation upon a given walk), so you could probably prune a bunch of possibilities because you've already been there.

I would look at writing a better problem statement. Basically, are you only counting walks that minimize the number of squares touched? I would add the stipulation that you can only touch any square a maximum of two times. (One could add the once-per-square stipulation, but that may eliminate desired outcomes. I don't know enough about the problem domain to say with any certainty.)

The reason I suggest this option is because it sounds like you're not happy with your data structure which, in turn, is causing serious headaches with your algorithm.

------
We are the carpenters and bricklayers of the Information Age.

Then there are Damian modules.... *sigh* ... that's not about being less-lazy -- that's about being on some really good drugs -- you know, there is no spoon. - flyingmoose

I shouldn't have to say this, but any code, unless otherwise stated, is untested