On Wed, Feb 27, 2008 at 9:27 PM, Nobody Imparticular
<[EMAIL PROTECTED]> wrote:
> Hi any and all;
>
> I am having a heck of time getting my head around a
> little problem I have run into; I got this question
> during an interview recently and, well, failed
> miserably. Now I am crazy to figure out the answer
> since the answer seems like it would be easy, but
> isn't (to me).
>
> Lets say I have the following data in a text file;
>
> A B C D E F G
> A B C D E F H
> A B C D E F I J
> A B C D K L
> A B C D M N
> A B C D O P
> A B C D Q R
> A S T
> A S U
>
> I need to massage the data and print it out (to the
> screen or file) as follows:
>
> A
> B C D
> E F
> G
> H
> I J
> K L
> M N
> O P
> Q R
> S
> T
> U
>
> I'm really at a loss for what to do. I've tried a
> myriad of things (recursive calls to build a hash, to
> build an array, to build a string) and basically I
> could never fully get there .
>
> What am I missing?
snip
i don't know if this is the best way or not, but the easiest answer I
could come up with is a tree. The basic algorithm goes like this:
read each line
treat line like a path to a leaf in the tree (A is parent of B who
is a parent of C who is a parent of D, etc) creating nodes where they
don't exist
walk the tree joining nodes that have only one child
print out the tree depth first
#!/usr/bin/perl
use strict;
use warnings;
package Node;
sub new {
my $class = shift;
my $self = {
value => shift,
children => []
};
return bless $self, $class;
}
sub add_characters {
my $self = shift;
my $c = shift;
return unless defined $c;
if (not defined $self->{value}) {
$self->{value} = $c;
return $self->add_characters(@_);
} elsif ($self->{value} eq $c) {
return $self->add_characters(@_);
} else {
for my $child (@{$self->{children}}) {
if ($child->{value} eq $c) {
return $child->add_characters(@_);
}
}
push @{$self->{children}}, Node->new($c);
return $self->{children}[-1]->add_characters(@_);
}
}
sub condense {
my $self = shift;
while (@{$self->{children}} == 1) {
my $child = $self->{children}[0];
$self->{value} .= " $child->{value}";
@{$self->{children}} = @{$child->{children}};
}
for my $child (@{$self->{children}}) {
$child->condense;
}
}
sub to_string {
my $self = shift;
my $level = shift || 0;
my $s;
$s = (" " x $level) . "$self->{value}\n";
for my $child (@{$self->{children}}) {
$s .= $child->to_string($level + length($self->{value}));
}
return $s;
}
package main;
my $head = Node->new(undef);
while (<DATA>) {
$head->add_characters(split);
}
$head->condense;
print $head->to_string;
__DATA__
A B C D E F G
A B C D E F H
A B C D E F I J
A B C D K L
A B C D M N
A B C D O P
A B C D Q R
A S T
A S U
--
Chas. Owens
wonkden.net
The most important skill a programmer can have is the ability to read.
--
To unsubscribe, e-mail: [EMAIL PROTECTED]
For additional commands, e-mail: [EMAIL PROTECTED]
http://learn.perl.org/
