Beefy Boxes and Bandwidth Generously Provided by pair Networks
Do you know where your variables are?
 
PerlMonks  

Re: Challenge: Dumping trees.

by Anonymous Monk
on Oct 13, 2012 at 15:42 UTC ( [id://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 (Patriarch) 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.

    RIP Neil Armstrong

Re^2: Challenge: Dumping trees.
by BrowserUk (Patriarch) 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.

    RIP Neil Armstrong

      I also finally succeeded

      neat :) it really is much easier on the eyes

      Upon further testing, the anomalies

      Hmm, weird. Using your tree generator

      from genBiaryTree
      my $root = do { our $S //= 0; srand $S if $S; my $r; my @a =( 'a'..'z', 1..9, 'A'..'Z', ); $r = int( rand $#a ), splice @a, $r, 2, [ @a[ $r, $r+1 ]] while @a + > 1; @a = @{ $a[0] }; \@a; };
      And running
      Fudgy >anomaly.txt Fudgy -S=2 >>anomaly.txt Fudgy -S=3 >>anomaly.txt Fudgy -S=4 >>anomaly.txt Fudgy -S=40 >>anomaly.txt Fudgy -S=400 >>anomaly.txt Fudgy -S=400000 >>anomaly.txt Fudgy -S=99999400000 >>anomaly.txt notepad anomaly.txt

      I was not able to reproduce the anomalies, I get

        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:

        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.

        RIP Neil Armstrong

Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: note [id://998853]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this?Last hourOther CB clients
Other Users?
Others sharing their wisdom with the Monastery: (4)
As of 2024-03-29 12:23 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found