Hi oakb! The raw data does not exist as chains. I see only the csv data (in the real life a table in the database). The earlier chain numbers should be always lesser than later numbers, this is correct.

Sorry for the delayed reply on this... I've been busy, but I've been using spare gray cells to consider your situation. :)

Given the rules you have provided and implied, a solution would seem to be fairly simple and straightforward. Indeed, overthinking the issue is a distinct danger to be avoided. The one big reservation I have is that, though you have implied it, you have never explicitly stated that each number is unique to only one chain. That is to say, something like this could never happen:



123-234-339-456-567
117-234-339
131
213-339-456
372
[download]


In the sample above, I have altered the numbers so that 234, 339, and 456 each appear in at least two chains. Your data sample, which shows only a number and its predecessor in the chain, cannot adequately represent the data in this altered environment, since there now exist multiple paths in the data for determining the first number in the chain. For instance, the first number of the chain ending in 567 is now indistinguishable; using the data as it's formatted, the first number could be 123, 117, or 213 -- although, of course, the only correct answer is 123.

The reasonable assumption, then, must be to accept and rely on your implicit rule: each three-digit number can only appear in one chain.

From there, the solution is fairly easy. Since your original question did not involve how to pull in your data, I'm going to simplify my sample code by starting with the data already formatted in a way that Perl understands. I am also going to stick with built-in Perl functions, and not require any extra modules.



#!/usr/bin/perl -w

use strict;

my @data = ( [ 567, 456 ],
             [ 456, 345 ],
             [ 345, 234 ],
             [ 234, 123 ],
             [ 339, 228 ],
             [ 228, 117 ],
             [ 131, undef ],
             [ 435, 324 ],
             [ 324, 213 ],
             [ 372, undef ]
           );

sub replace {
    my ( $num_first_ref, $pred_num_ref, $num, $pred ) = @_;
    # Catch the first number in the chain
    $num_first_ref->{ $pred } = $pred;
    # Assign current $pred as possible first
    $num_first_ref->{ $num } = $pred;
    # Use reverse hash to look up later/higher numbers and update
    if ( exists( $pred_num_ref->{ $num } ) && ( my $higher_num = $pred
+_num_ref->{ $num } ) ) {
        # Reassign current $pred as possible first
        $num_first_ref->{ $higher_num } = $pred;
        replace( $num_first_ref, $pred_num_ref, $higher_num, $pred );
    }
}

my %num_first;  # Calculated data for output goes here
my %pred_num;  # 'Reverse' hash for recursive lookup

for my $nums ( @data ) {
    # Handle single values
    unless ( defined( $nums->[ 1 ] ) ) {
        $num_first{ $nums->[ 0 ] } = $nums->[ 0 ];
        next;
    }
    # Load reverse hash with predecessor as key
    $pred_num{ $nums->[ 1 ] } = $nums->[ 0 ];
    replace( \%num_first, \%pred_num, $nums->[ 0 ], $nums->[ 1 ] );
}

for my $high_num ( sort { $a <=> $b } keys %num_first ) {
    print "$high_num => $num_first{ $high_num }\n";
}


Output:
117 => 117
123 => 123
131 => 131
213 => 213
228 => 117
234 => 123
324 => 213
339 => 117
345 => 123
372 => 372
435 => 213
456 => 123
567 => 123
[download]


This uses a reverse hash, %pred_num, and a recursive subroutine, replace, to keep track of later chain numbers that have already been seen, and update them to the current possible first number. It doesn't matter how many data rows you have, or how long the chains are, this will handle any amount of data you throw at it -- as long as the data follows the rules. Boilerplate code for handling rule exceptions can always be added as desired.