Beefy Boxes and Bandwidth Generously Provided by pair Networks
Perl: the Markov chain saw
 
PerlMonks  

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

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


in reply to Re: Looking for the first item in the chain
in thread Looking for the first item in the chain

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.

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.

Log In?
Username:
Password:

What's my password?
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?Last hourOther CB clients
Other Users?
Others lurking in the Monastery: (4)
As of 2024-03-29 07:08 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found