Re^2: Looking for the first item in the chain

by vagabonding electron (Curate)
 on Aug 10, 2014 at 12:41 UTC ( #1096908=note: print w/replies, xml ) Need Help??

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.

• Comment on Re^2: Looking for the first item in the chain

Replies are listed 'Best First'.
Re^3: Looking for the first item in the chain
by oakb (Scribe) on Aug 12, 2014 at 04:26 UTC
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

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

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.

Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: note [id://1096908]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others studying the Monastery: (4)
As of 2022-12-06 00:20 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?

No recent polls found

Notices?