### Re: Challenge: Dumping trees.

 on Oct 13, 2012 at 15:42 UTC ( #998853=note: print w/replies, xml ) Need Help??

in reply to Challenge: Dumping trees.

Done! Adapted from http://hectorcorrea.com/Blog/Drawing-a-Binary-Tree-in-Ruby, where descendents are called children :)

_____/\_____ ___________/\_ ___/\ _______________/\_ /\_ /\_ z ___/\_____ /\_____ t /\ w /\ _/\_ _/\___ n _/\_ u v x y _/\ /\ _/\ _/\_ _/\ /\ /\ c d e /\ h /\ /\_ /\ q r s a b f g i j k /\ o p l m

Naturally nodes with a width greater than 2 chars breaks it :)

Replies are listed 'Best First'.
Re^2: Challenge: Dumping trees.
by BrowserUk (Pope) on Oct 14, 2012 at 08:40 UTC
Naturally nodes with a width greater than 2 chars breaks it :)

Thank you anonymonk. That handles everything I've thrown at it -- which it a darn sight more than I can say for my attempts so far.

It occasionally produces an oddity -- see the 'wxyz' nodes in the second example and the '1' node in the last two examples -- but they are still clear enough for my purposes.

C:\test>genBiaryTree -W=1 -S=2 | junk.pl ______________________________________________________ +________________________________________________/\_ _______/\_____________________________________________________ +_____________________________________________ /\ _/\___ + _____________________________/\_ Y Z _/\ _/\_ ____________________________________ +______________/\_ /\ _/\ d /\ /\ ___________/\_____________ + /\___ W X /\ c e f g h ___/\_____ _______/\____ + H _/\_ a b /\_ _/\___ ___/\_____ __/\________________ +_______ /\ /\_ i /\ _/\ _/\ /\_ ___/\ /\ _______________ +______/\_____ I J K /\___ j k /\ n /\ q r /\ /\_ x y / /\_ + ___/\ L _/\___ l m o p s t u /\ z 1 /\____________ +___ /\_ G /\ _/\_________ v w 2 ___________ +__/\_ D /\ M N /\ _____/\ /\_________ + /\ E F O P _/\___ V 3 _______/\ +_ B C /\ _/\ /\_ +/\ Q R /\ U 4 /\___ 9 + A S T 5 _/\ /\ 8 6 7 C:\test>genBiaryTree -W=1 -S=3 | junk.pl _____________________________/\___________________________________ +___________________________________________________ _/\___________________ + ___________________________________/\ /\ _________/\_______ _________________ +______________/\_______________________________ Z a b _____/\_______ _____/\ ____/\________________ +_____ _______________/\_ _/\___ _____/\ /\_ q ___/\ _______________ +____/\_______ _____/\_ /\ /\ _/\ /\_ l m /\_ _/\_ _/ /\___ + ___/\ _______/\___ /\_________ X Y c d /\ g h /\_ n /\ _____/\ //\ 1 _/\___ + _/\_ G /\_____ _/\ P _/\_ e f i /\ o p /\___ v wyxz /\ _/\______ +_ /\ /\ H ___/\ /\ O ___/\ /\ j k r _/\ 2 3 /\ _____ +/\_ C D E F /\_ L M N _/\_ U V W /\ u 4 5 /\_ + /\ I /\ /\ /\ s t 6 /\_ + A B J K Q R S T 7 /\ 8 9 C:\test>genBiaryTree -W=1 -S=4 | junk.pl ____________________________________ +__________/\_____________________________________ ___________________________/\_______________ + _____/\_ _/\_____________________ ___________/\___________________ +_ _____________________________/\_ /\ _/\ _/\_ _/\_________ _____________ +/\_______ /\_______________________ /\_ Y Z /\ c _______/\ /\_ /\ _/\ ____/\___________ + _____/\ F _________/\___ V /\ a b ___/\_ n o /\ r s ___/\ y /\__ _________/\ + /\_ E _______/\_____ _/\ W X ___/\_ /\_ p q _/\_ x z _/\ /\_ 9 + A /\_ _/\___ ___/\_ /\ U _/\_ /\ j /\_ /\ /\ \ 2 3 /\_ + B /\ _/\ _/\_ /\_ /\ S T /\ /\ h i k /\ t u v w 1 4 /\_ + C D /\ I /\ /\ N /\ Q R d e f g l m 5 /\_ + G H J K L M O P 6 /\ 7 8 C:\test>genBiaryTree -W=1 -S=40 | junk.pl ______________________________/\________ +_ _______________/\_________ ___ +/\_______________ _/\_ _______/\_ ___/\_ + ___________/\_____ _____/\ /\_ /\___ /\_______ /\_ /\ + _/\_______ _/\_________ _/\_ g h /\___ p _/\_ u _/\_ 5 /\ 8 9 + /\ ___/\_ _/\ _______/\_________ _/\ /\_ i _/\___ /\ /\ ___/\ /\__ 6 7 + A B _/\_ /\ /\ K /\___ ___/\___ /\ c d /\ /\ _/\_ q r s t /\_ y z _/\___ + /\ /\ G H I J L _/\_ ___/\_ _/\_ a b e f j k /\ /\ v /\ \ _/\ + C D E F /\ /\ /\_ /\ /\ /\_ l m n o w x 1 /\ 4 + M N O P Q /\ T U V W X /\ 2 3 + R S Y Z C:\test>genBiaryTree -W=1 -S=400 | junk.pl _____________________________/\_____________________________ +___________________________ _______/\_______ + _________________________/\_ /\_____ ___/\_______ ______________________ +/\___________ /\_______________ a ___/\ _/\_ ___/\_ _____/\________________ + _/\_ N ___________/\_ /\_ e /\ /\ _/\_ /\_ /\_ ___/\___ + _______/\ /\_____ _/\_ /\_ b /\ f g h i /\ /\ n /\_____ u /\_ _______/\_ _/\ + /\___ F G ___/\_ /\ /\_____ W /\_ c d j k l m o _/\_ v /\ /\_____ /\ /\ 9 + A _/\_ /\_ /\_ O P Q ___/\_ X /\ _/\ /\ w x _/ _/\ 5 6 7 8 + /\ /\ H /\ K /\ /\_ /\ Y Z /\ r s t /\ _/\ 4 + B C D E I J L M R /\ U V p q y z /\ 3 + S T 1 2 C:\test>genBiaryTree -W=1 -S=400000 | junk.pl + _________________________________/\___ __________________ +________/\___________________ _/\_ _______________________________________________/\_________________ +_______ ___/\_________ /\ /\_ _/\_________________________ _________________ +______/\ ___/\_ _/\_ V W X /\ /\ ___/\___ \ _ + D ___/\_ /\ ___/\ /\ Y Z a b _____/\_ _/\_______ /\______________ +_ ___/\_ /\ M N _/\_ S T U _______/\_ /\ /\ _/\_______ 1 ___________ +/\___ _/\_ /\ K L /\ /\ ___/\_ /\_ n o p q _/\ _/\ _/\_____ + _/\ /\ /\ I J O P Q R _/\_ /\_ k /\ _/\ u ___/\ z /\ ___/\_ + /\ C E F G H /\ /\ g /\_ l m /\ t /\_ y 2 3 /\_ /\_ + A B c d e f h /\ r s v /\ 4 /\ 7 /\ i j w x 5 6 8 9 C:\test>genBiaryTree -W=1 -S=99999400000 | junk.pl _________________/\_________________ ___/\_______________ _____________/\_____ _/\_ _________/\ _/\___ ___/\_________________ +_______________________________________________ _/\ /\ ___/\_______ n /\ _/\___ /\_ + _____/\_ /\ c d e /\_ _/\ o p /\ _/\___ x /\ + ___________________/\___ /\_ a b f /\ ___/\ m q r /\ _/\ y z + ___________/\_____________ _/\ X /\ g h /\_ l s t /\ w + _____/\_____ _______/\_ /\ W Y Z i /\ u v _____ +__/\___ ___/\_ ___/\_____ /\_ U V j k _/\____ +_ _/\ /\_ /\_ /\_ _/\ R /\ ___/\ ___ +/\ /\ D E /\ H /\ K /\ _/\ Q S T _/\_ 6 /\_ + A B C F G I J L M /\ P _/\ /\ 7 /\ + N O _/\ 3 4 5 8 9 \ 2 1

I'm going to try and adapt it to produce a slightly different style of output that I think results in nicer -- cleaner, more easily read -- output. Eg. Instead of:

_____/\_____ ___________/\_ ___/\ _______________/\_ /\_ /\_ z ___/\_____ /\_____ t /\ w /\ _/\_ _/\___ n _/\_ u v x y _/\ /\ _/\ _/\_ _/\ /\ /\ c d e /\ h /\ /\_ /\ q r s a b f g i j k /\ o p l m

This:

_______ ___________/ \___ ___________/ \_ _/ \ _______/ \_____ / \_ / \_ z _/ \___ / \_ t / \ w / \ _/ \_ _/ \__ n _/ \_ u v x y _/ \ / \ _/ \ _/ \ _/ \ / \ / \ c d e / \ h / \ /\_ / \ q r s a b f g i j k / \ o p l m

Also, one possibility for handling node 'names' of more than 1 or 2 chars; though I'm not sure it really works as is?:

_______ ___________/ \___ ___________/ \_ _/ \ _______/ \_____ / \_ / \_ z _/ \___ / \_ t / \ w / \ u _/ \_ _/ \__ n _/ \_ a u v h x y l _/ \ / \ _/ \ _/ \ o _/ \ / \ n n i i r a u / \ c d e / \ h / \ /\_ v / \ q r s g i c s a n a b h e c f g o i j k / \ e o p u o i o f t k y k l r a l h o o t n u i l m m s a e m e o o e e p a r t o x l e d l l i i b c p b e r r r y y h v l a t f l i i o m k e a a e o r m a o i r g e a w r r c a e o o t t

With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday'
Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
"Science is about questioning the status quo. Questioning authority".
In the absence of evidence, opinion is indistinguishable from prejudice.
Re^2: Challenge: Dumping trees.
by BrowserUk (Pope) on Oct 15, 2012 at 14:16 UTC

Upon further testing, the anomalies I noted in Re^2: Challenge: Dumping trees. were actually more prevalent and distracting than I first thought; and I failed in my attempts to cure them in your code.

I also finally succeeded in getting my attempt to work properly. In part, because of a couple of things I learnt from studying your code. Thank you.

With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday'
Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
"Science is about questioning the status quo. Questioning authority".
In the absence of evidence, opinion is indistinguishable from prejudice.
I was not able to reproduce the anomalies,

Okay.

1. First problem: Your version of the generator is not -- for the same setting of srand-- producing the same randomly generated tree.

At first, I assumed this must be because you were using a different rand to me. I guessed you might be running on some flavour of *nix -- but then I noticed your use of notepad above -- which squashed that idea.

Then I thought you might be running some other flavour of windows perl -- perhaps Strawberry. So, I thought I'd re-generate the failing test cases using my version of the generator and supply you with the generated trees.

2. Second problem: my version of the generator is no longer producing the same trees for a given value of -S=nnn!

Did I change the generator between posting and now? I don't remember, but I can only assume that something in the original code I used, that used rand has changed.

Never mind: I'll reverse engineer the output I posted back to a raw tree structure and give you that.

3. Third problem: Reverse engineering this pretty form of output is extremely painstaking, laborious and painful!

But I did it!

Which fed to your dumper produces the same (malformed) dump that I originally posted:

C:\test>anonBinTreeDumper.pl _____________________________/\___________________________________ +___________________________________________________ _/\___________________ + ___________________________________/\ /\ _________/\_______ _________________ +______________/\_______________________________ Z a b _____/\_______ _____/\ ____/\________________ +_____ _______________/\_ _/\___ _____/\ /\_ q ___/\ _______________ +____/\_______ _____/\_ /\ /\ _/\ /\_ l m /\_ _/\_ _/ /\___ + ___/\ _______/\___ /\_________ X Y c d /\ g h /\_ n /\ _____/\ //\ 1 _/\___ + _/\_ G /\_____ _/\ P _/\_ e f i /\ o p /\___ v wyxz /\ _/\______ +_ /\ /\ H ___/\ /\ O ___/\ /\ j k r _/\ 2 3 /\ _____ +/\_ C D E F /\_ L M N _/\_ U V W /\ u 4 5 /\_ + /\ I /\ /\ /\ s t 6 /\_ + A B J K Q R S T 7 /\ 8 9

But that raises another problem...

4. Fourth problem: if you look at the raw tree above, you'll see it is malformed: [['y','z'],]; the x,y node is paired with a null node.

And that raises the final problem.

5. Fifth problem: Given that the raw tree is reproduced from the pretty-printer output, there is no way to determine if the tree my generator fed your dumper was malformed; or if the malformation is a result of occlusion in the dumper output?

I don't think that it is possible for the generator to produce bad trees -- but I haven't proven that.

Looking at the spacing between the 'z' and the '1' nodes, the gap is too big, which makes me think it is a artifact of the dumper.

At that point, I manually made the simplest correction to the raw tree that (I thought) would make it valid:

my \$root = [ [ ['a','b'], [ [[['c','d'],[['e','f'],'g']],[['h',['i',['j','k']]],'l']], [['m',['n',['o','p']]],'q'] ] ], [ [ [ [[[['r',[['s','t'],'u']],'v'],['w','x']],[['y','z']]], [ ['1',[['2','3'],[['4','5'],[['6',['7',['8','9']]],['A','B']]]]], [[['C','D'],['E','F']],'G'] ] ], [ [ [['H',[['I',['J','K']],'L']],[['M','N'],'O']], ['P',[[[['Q','R'],['S','T']],'U'],['V','W']]] ], ['X','Y'] ] ],'Z' ] ] ;

and re-ran the dumper. As you can see, it still produces the identical, malformed dump:

C:\test>anonBinTreeDumper.pl _____________________________/\___________________________________ +___________________________________________________ _/\___________________ + ___________________________________/\ /\ _________/\_______ _________________ +______________/\_______________________________ Z a b _____/\_______ _____/\ ____/\________________ +_____ _______________/\_ _/\___ _____/\ /\_ q ___/\ _______________ +____/\_______ _____/\_ /\ /\ _/\ /\_ l m /\_ _/\_ _/ /\___ + ___/\ _______/\___ /\_________ X Y c d /\ g h /\_ n /\ _____/\ //\ 1 _/\___ + _/\_ G /\_____ _/\ P _/\_ e f i /\ o p /\___ v wyxz /\ _/\______ +_ /\ /\ H ___/\ /\ O ___/\ /\ j k r _/\ 2 3 /\ _____ +/\_ C D E F /\_ L M N _/\_ U V W /\ u 4 5 /\_ + /\ I /\ /\ /\ s t 6 /\_ + A B J K Q R S T 7 /\ 8 9

So then I fed that corrected tree to my dumper:

C:\test>perl \perl64\site\lib\Tree\Dump.pm ____________________________________________________ +_________________________________ _____________/ + \___________________ _/ \_________ __________ +_________________________________/ \ / \ _____/ \_____ _______/ + \_______________ Z a b ___/ \_____ _/ \ _____/ \__________ +___________ ___/ \_ _/ \_ _/ \ / \_ q _/ \ ___/ + \___ _______/ \_________ / \ / \ _/ \ / \_ l m / \_ ___/ \_ _/ / \___ + _/ \ ___/ \_ / \_ X Y c d / \ g h / \_ n / \ ___/ \ / \ / \ 1 _/ \___ + _/ \_ G / \___ _/ \ P ___/ \_ e f i / \ o p / \_ v w x y z / \ _/ \__ +___ / \ / \ H _/ \ / \ O _/ \ / \ j k r _/ \ 2 3 / \ _/ + \_ C D E F / \_ L M N _/ \_ U V W / \ u 4 5 / \_ + / \ I / \ / \ / \ s t 6 / \ +_ A B J K Q R S T 7 / + \ 8 + 9

At this point, I'm kicking the ball into your court to decide if it is worth pursuing further?

With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday'
Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
"Science is about questioning the status quo. Questioning authority".
In the absence of evidence, opinion is indistinguishable from prejudice.

Create A New User
Node Status?
node history
Node Type: note [id://998853]
help
Chatterbox?
and all is quiet...

How do I use this? | Other CB clients
Other Users?
Others taking refuge in the Monastery: (2)
As of 2018-01-21 11:55 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
How did you see in the new year?

Results (228 votes). Check out past polls.

Notices?