Aligning Arrays Problem

monkfan has asked for the wisdom of the Perl Monks concerning the following question:

Most Revered Monks,

Here, I intend to align arrays of a HoA. Given a hash of arrays (HoA1), where size of each array is equal and fixed _within_ that particular hash. There are other HoA2 but with different number of arrays, and the size of array is different with previous one (HoA) We need to loop over them.

The comparison of all the arrays in HoA is only done with *first* hash
e.g array of: key1-key2, key1-key3, key1-key4 ..key1-key_etc

Update: 1.Rule clarified. Apologize for confusion.
2.Animator example below also holds.

The rule is as follows:

 1. For every elements in array

 2. Assign elem[0] of array in key1,key2,key3 etc to an empty array 
    (we call it: $AoA[0])
    So it'll be as many as 4 arrays (= size of array in hash)
    e.g. $AoA[0] ..$AoA[3] filled up with elem[0] of all hashes
         $AoA[0][0]="A",$AoA[1][0] ="B", $AoA[2][0]="C",$AoA[3][0]="D"

    Or if you will at this point we have @AoA = ([A],[B],[C],[D])

    Every element of arrays in first key *becomes* first element 
    of new array in @AoA

 3. Check if the elements of next array are equal
    e.g Check: elem[0]-key1 = elem[0]-key2

 4. If they are equal, store elem[0]-key2 in $AoA[0], 
    then go to next hash (elem[0]-key3)..etc

 5. If they are not equal, check if elem[0]-key1 = elem[1]-key2 ..etc 
    until elem[last]-key2 (exhaust all element of array in key2)
    If they are >1 matches, take only the *first* matching one.
    If after exhausting it, still cannot find, 
    assign '-' (dash) to $AoA[0] etc.

 6. While checking, check elem[0]-key1 ..elem[last]-key1 
    with elements of next array of key2-key4, 
    verify if elem[0]-key2 has been *used* for previous match,
    if yes then check elem[0]-key1 = elem[1]-key2, 
                                   = elem[2]-key2  ...
                                   = elem[last]-key2, 
    otherwise match it (assign elem[0]-key1 = elem[0]-key2 ).

 7. Finally we have an AoA with $AoA[1] ..$AoA[4] filled up 
    (see answers snippet below)
[download]

And the code currently I have is:

#!/usr/bin/perl -w
use strict;
use Data::Dumper;

my %hoa1 = (
             'key1' => ["A","B","C","D"],
             'key2' => ["A","C","D","B"],
             'key3' => ["C","A","D","H"],
             'key4' => ["A","B","I","C"],
         );

my %hoa2 = (
             'key1' => ["A","D"],
             'key2' => ["A","B"],
             'key3' => ["C","H"],
         );

my @answ = align_array(%hoa1);
print Dumper \@answ;

sub align_array
{
    my %hoa = @_;
    my @AoA;
    my @keys = sort keys %hoa;

    foreach my $id ( -1 .. $#keys-1  )
    {

       for  ( 0 .. $#{$hoa{$keys[$id]}}  )
       {
           #Here I get point No.2 done
           $AoA[$_][0] = $hoa{$keys[0]}[$_];

           # I'm totally stuck here, in attempt to do point No.3 to 7
           # How can I evaluate elements of array of varying size
           # dynamically?
          
           if ( $AoA[$_][0] =  $hoa{$keys[$id+1]}[$_] )
           {
               $AoA[$_][$_+2] = $hoa{$keys[$id+1]}[$_];
           }
           elsif ( $AoA[$_][0] =  $hoa{$keys[$id+3]}[$_] )
           {
            $AoA[$_][$_+2] = $hoa{$keys[$id+3]}[$_];
           }
           else
           {
               $AoA[$_+1][$_+2] = "-";
           }

      }

    }                               # -----  end foreach  -----

        return @AoA ;
}
[download]

My questions:
1. How can I create a scheme that can handle hashes with varying number of arrays (values)?
2. I also have difficulty in implementing point 6 above. Don't know what's the construct to build.

The intended answers are:

# For @answ_hoa1, note that 2nd elem of 4th array is "-" and not "D"
# because elem[last] in 2nd array ("B") has been *used* before

my @answ_hoa1 = (
                  ["A","A","A","A"],
                  ["B","B","-","B"],
                  ["C","-","-","C"],
                  ["D","-","D","-"],
               );

my @answ_hoa2 = (
                 ["A","A","-"],
                 ["D","-","-"],
               );
[download]

Desperately in need of your enlightenments. Thanks beforehand.

Regards,
Edward

Comment on Aligning Arrays Problem Select or Download Code

Replies are listed 'Best First'.
Re: Aligning Arrays Problem by tlm (Prior) on May 03, 2005 at 10:22 UTC
The code below gives the correct results, although I'm mystified by the specs. If I understand them correctly, the sort order of the keys determines which array is to be consider the reference array, as well as the flow of the rest of the algorithm, which sounds strange to me. I suspect that `align_arrays` should really operate on AoAs, not HoAs. Read more... (2 kB) the lowliest monk	[reply] [d/l]
Re: Aligning Arrays Problem by Animator (Hermit) on May 03, 2005 at 10:46 UTC
Let's take another approach: What are you trying to achieve? You want to know in what rows the letters (of the first row) occur? (although that's not quite correct) or ...? As in, `$answ_hoa1[1] (["B","B","-","B"])` tells you that the first row, the second row and the fourth row has the letter 'B' But this is only true for `$answ_hoa1[0]` and `$answ_hoa1[1]`... But not for `$answ_hoa1[3]` and `$answ_hoa1[4]` probably because of rule 6, is this view correct? Unless: if the match for the next letter may only start where the last one ended: example: it matches the B in the key2-array at the end, which means that it should start looking for the C and the D after the B (which is impossible since B is the end of the array) Is the following input possible?: `'key1' => ["A","B","C","D"], 'key2' => ["A","C","B","C"], 'key3' => ["C","A","D","H"], 'key4' => ["A","B","I","C"],` [download] And more important, what should the output of it be? Should it be this?: `[ "A", "A", "A", "A" ], [ "B", "B", "-", "B" ], [ "C", "C", "-", "C" ], [ "D", "-", "D", "-" ],` [download] Updated after reading tlm's code Update2: code. This code does basiclly the same as tlm's code, except that his code modifies the hash (that is the arrays in the hash), and mine doesn't. Read more... (829 Bytes)	[reply] [d/l] [select]
Re: Aligning Arrays Problem by Animator (Hermit) on May 03, 2005 at 09:05 UTC
Just to make sure, %hoa2 is just another example? or is there a relationship between %hoa1 and %hoa2? And to make sure aswell: you use `elem[1]` to refer to index 0? as in `elem[1] = $array[0]`? Re-reading it helped a bit, but not quite as much as I hoped... this in particular confuses me: Point 5: 'check if `elem[1]-key1 = elem[2]-key2` ..etc until `elem[last]-key2`.' Point 6: 'For checking `elem[2]-key1 ..elem[last]-key2`' Point 5 says `elem[1]-key1`, point 6 says `elem[2]-key1`, is this correct? and what do you mean by ..etc, there are too many possibilities to continue comparing... (so please add another one) And, any particular reason why you are sorting the elements in `$HoA1{key1}`? or is this done only to be able to compare it easily? (This post has been updated several times, since I misread it first)	[reply] [d/l] [select]
Re^2: Aligning Arrays Problem by monkfan (Curate) on May 03, 2005 at 10:24 UTC
Just to make sure, %hoa2 is just another example? or is there a relationship between %hoa1 and %hoa2? Yes, it's just another example. No relationship. Regards, Edward	[reply]
Re: Aligning Arrays Problem by eibwen (Friar) on May 03, 2005 at 09:36 UTC
Unfortunately I don't have the time to refractor your ruleset into code at the moment, however I may be able to answer some of your questions. 1. How can I create a scheme that can handle hashes with varying number of arrays (values)? To determine the number of rows and columns contained in a given matrix, find the number of hash keys and the number of referenced array elements respectively. `scalar keys %hash; # rows scalar @{ $hash{'element'} }; # columns` [download] 2. I also have difficulty in implementing point 6 above. Don't know what's the construct to build. This is by no means a definitive answer, but one possibility is to create a lookup "table" of the same dimensions. If a match is made, place a flag in the lookup, therefore reducing checking for prior matches to a mere lookup.	[reply] [d/l]
Re: Aligning Arrays Problem by blazar (Canon) on May 03, 2005 at 09:10 UTC
I must say that it seems to me that indeed you did spend some efforts trying ro prepare a minimal example and to pose your question in a clear way. Still, your post seems at best confusing to me. Care to rephrase it?	[reply]