Tricky sort problem

[majorbiff]

Hope you all had a good easter.

I have an interesting problem. I have a list of 38 values that need to be sorted. At this point quite simple but it gets worse.

The list is made up of pairs of values in the form 'Qx.1=zzz' and 'Qx.2=zzz' (where 'x' is a number from 1 to 20 and 'zzz' is a short string of variable length).
There are 19 items with 'Qx.1' and 19 with 'Qx.2'
Eg:

Q1.1=bla
Q1.2=qaz
Q3.1=meh
Q3.2=ehh
Q2.1=foo
Q2.2=mar

I sort the list with the x.1s and x.2s together:

Q1.1=bla
Q1.2=qaz
Q2.1=foo
Q2.2=mar
Q3.1=meh
Q3.2=ehh

The problem is there should be 20 pairs, not 19. I need to figure out which pair is missing and insert it at the right point.
For example if there is no Q19 I need to insert 'Q19.1=null' and 'Q19.2=null' into the list.


Here is a neat sort function I prepared earlier:
I plug into the sub an array that contains the data.
In the array, the pair association is correct but the pairs are out of order (see first example). Converting the array to a hash effectively takes care of the pair associations.

sub orderPartA(){
	my %orderHash = @_;
	return map {($orderHash{$_},$_)} sort {(split(/\.|Q/,$a))[1] <=> (split(/\.|Q/,$b))[1]} keys %orderHash;
}

My sort works nicely but it doesn't detect the missing pair.
I was thinking of checking the 'x' number in each hash key against an incrementing counter in a loop, but that seems highly inefficient.

Any ideas?

Alchemy is easy with Perl!
s/lead/gold/g;

 

[stevexff]

I was thinking of checking the 'x' number in each hash key against an incrementing counter in a loop, but that seems highly inefficient

Hash lookups are fast and efficient; even if you had hundreds of questions, you'd still only iterate over the list once, way quicker than the sorting you are already doing.

foreach (1 .. 20) {
   $orderHash{"Q$_.1"} = "null" unless (exists $orderHash{"Q$_.1"});
   $orderHash{"Q$_.2"} = "null" unless (exists $orderHash{"Q$_.2"});
}

Steve

[small]"Every program can be reduced by one instruction, and every program has at least one bug. Therefore, any program can be reduced to one instruction which doesn't work." (Object:erlDesignPatterns)[/small]

 

[KevinADC]

build an inital hash with all values as 'null':

my %orderHash = ();
for my $i (1..2) { 
  map {$orderHash{"Q$_.$i"}='null'} (1..20);
}

then parse your file, filling in the new values for the existing hash keys.

------------------------------------------
- Kevin, perl coder unexceptional!

 

[majorbiff]

Two great ideas. Thanks guys.

Alchemy is easy with Perl!
s/lead/gold/g;

 

[majorbiff]

I just realised that the suggestions are not going to work.
At the moment the hash is a conversion from the array, therefore the hash looks like this:

key         data
Q1.2=qaz->Q1.1=bla
Q2.2=mar->Q2.1=foo
Q3.2=ehh->Q3.1=meh

The key isn't "Qx.2" It is actually "Qx.2=zzz"
This means that I don't know the key value.
You can't put wildcards where a key value is expected so I couldn't use something like this: $orderHash{"Q$_.*"}.

After going back to the drawing board I came up with something that appears to work:
Note that there are 21 pairs not 20 as I originally stated.

sub orderPartA(){
	my %orderHash = @_;
	my %temp=();
	my @missing;
	foreach (keys %orderHash){
		m/Q(\d+).2/;
		$seen{$1} = 1;
	}

	@missing=grep(! $temp{$_}, (1..21));
	$orderHash{"Q$missing[0].2=null"} = "Q$missing[0].1=null" unless (scalar(@missing) == 0);
	return map {($orderHash{$_},$_)} sort {(split(/\.|Q/,$a))[1] <=> (split(/\.|Q/,$b))[1]} keys %orderHash;
}

Alchemy is easy with Perl!
s/lead/gold/g;

 

[majorbiff]

Sorry, that should be:

sub orderPartA(){
    my %orderHash = @_;
    my %temp=();
    my @missing;
    foreach (keys %orderHash){
        m/Q(\d+).2/;
        $temp{$1} = 1;
    }

    @missing=grep(! $temp{$_}, (1..21));
    $orderHash{"Q$missing[0].2=null"} = "Q$missing[0].1=null" unless (scalar(@missing) == 0);
    return map {($orderHash{$_},$_)} sort {(split(/\.|Q/,$a))[1] <=> (split(/\.|Q/,$b))[1]} keys %orderHash;
}

Alchemy is easy with Perl!
s/lead/gold/g;

 

[rharsh]

Just for the heck of it.

my @list = <DATA>;
chomp @list;
my @complete_list = orderPartA(\@list);
local $, = "\n";
print @complete_list;

sub orderPartA {
    my $a_ref = shift;
    my (%temp, @return);
    for (@{$a_ref}) {
        $temp{$1}->{$2} = $_ if m/Q(\d+)\.(\d+)=/i;
    }
    
    for my $i (1..21) {
        for my $j (1..2) {
            push @return, ($temp{$i}->{$j} || "Q${i}.${j}=NULL");
        }
    }
    return @return;
}

__DATA__
Q1.1=bla
Q1.2=qaz
Q3.1=meh
Q3.2=ehh
Q2.1=foo
Q2.2=mar

 

[stevexff]

I have a list of 38 values that need to be sorted.

Is this still true? Or was it just a feature of the original plan to sort them and then look for missing values? Now that you have them in a hash, is it still relevant?

Steve

[small]"Every program can be reduced by one instruction, and every program has at least one bug. Therefore, any program can be reduced to one instruction which doesn't work." (Object:erlDesignPatterns)[/small]

 

[majorbiff]

The original plan was to sort the values in an array. Due to the fact that the values were paired it made it a bit harder.

Converting the array to a hash was a side-effect of an easy solution. I had originally looked into sorting the values without needing a hash but a sort on a hash seemed the easiest option at the time.

It was only after I wrote the code that I realised that the input data wasn't what it should have been.

On second thought I could have done it without needing the hash conversion but using the hash was a neat solution.

Alchemy is easy with Perl!
s/lead/gold/g;