P is for Practical PerlMonks

### comment on

 Need Help??
Here goes, interesting little problem ... my solution is non-recursive, can handle loops and allows to write my @order = demangle(\%replace);.

Update After sleeping over it I've greatly simplified the algoritm, now I think it's elegant. You have to decide yourself if this algorithm is nicer than the rather elegant recursive solution.

```sub demangle {
my \$r = shift;
my %illegal;
@illegal{%\$r} = ();

my @chains;

LOOP:
while (my(\$k,\$v) = each %\$r) {
for my \$c (@chains) {
if (\$c->[-1] eq \$k) {   # append to end of chain
push @\$c, \$v;
next LOOP;
};
if (\$c->[0] eq \$v) {    # prepend to start of chain
unshift @\$c, \$k;
next LOOP;
}
}
push @chains, [\$k, \$v];     # create new chain
}

# fix circular replacements
for my \$c (@chains) {
if (\$c->[0] eq \$c->[-1]) {  # we have a circle
my \$new_key;
do {
\$new_key = join '', map { ('a'..'z')[rand 26] } 1..8;
} while exists \$illegal{\$new_key};
\$illegal{\$new_key}++;

unshift @\$c, \$new_key;
push @\$c, \$new_key;
}
}

my @order;

while (@chains) {
push @order, { map { \$_->[-2] => pop @\$_ } @chains };
@chains = grep @\$_ > 1, @chains;
}

return @order;
}

-- Hofmator

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post; it's "PerlMonks-approved HTML":

• Are you posting in the right place? Check out Where do I post X? to know for sure.
• Posts may use any of the Perl Monks Approved HTML tags. Currently these include the following:
<code> <a> <b> <big> <blockquote> <br /> <dd> <dl> <dt> <em> <font> <h1> <h2> <h3> <h4> <h5> <h6> <hr /> <i> <li> <nbsp> <ol> <p> <small> <strike> <strong> <sub> <sup> <table> <td> <th> <tr> <tt> <u> <ul>
• Snippets of code should be wrapped in <code> tags not <pre> tags. In fact, <pre> tags should generally be avoided. If they must be used, extreme care should be taken to ensure that their contents do not have long lines (<70 chars), in order to prevent horizontal scrolling (and possible janitor intervention).
• Want more info? How to link or or How to display code and escape characters are good places to start.

Create A New User
Domain Nodelet?
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others browsing the Monastery: (3)
As of 2021-08-01 07:09 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?

No recent polls found

Notices?