Re: Data file from one format to another.

On Wed, Feb 27, 2008 at 9:27 PM, Nobody Imparticular
<forcrimanysakes@xxxxxxxxx> 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.
.

Relevant Pages

  • Re: runaway memory leak with LWP and Fork()ing on Windows
    ... child is immediantly given the next task as long as there are any ... sub new { ... # registers one or more callback routines with the agent ... my $self = shift() or return; ...
    (comp.lang.perl.misc)
  • problem with Tk Drag n Drop
    ... getting problem in drag n drop. ... I am creating a tree with optional scroll bar, on each child of this ... where function sub FindSite returning a Null site, ...
    (comp.lang.perl.tk)
  • subclassing HTML::Parser
    ... Someone had suggested to use HTML::TreeBuilder, ... tree instead of just returning an array reference. ... sub start { ... my $tagname = shift; ...
    (perl.beginners)
  • Re: gtk2 treeview and threads : custom sort while updating rows
    ... use vars qw; ... sub update_action ... my $tree = shift; ...
    (comp.lang.perl.misc)
  • sitemap generator for Perl
    ... I want to run the sitemap generator ... Returns the minimum number of links to traverse from the root URL of ... my $class = shift; ...
    (perl.beginners)