### Re^2: Challenge: Dumping trees.

by BrowserUk (Pope)
 on Oct 15, 2012 at 14:16 UTC ( #999092=note: print w/replies, xml ) Need Help??

in reply to Re: Challenge: Dumping trees.

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.

Replies are listed 'Best First'.
Re^3: Challenge: Dumping trees.
by Anonymous Monk on Oct 15, 2012 at 17:14 UTC

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

I was not able to reproduce the anomalies, I get

```      _________________/\_____________________________________________
+____
_/\_____                                                        __
+___/\___________________________________
_/\     _/\_______                    ___________________________/\_
+__                                    _/\_________
/\ c   _/\     ___/\_        _________/\_____
+_/\           _______________________/\         _/\
a b    /\ f   _/\_   /\     _/\_______      _/\_______               /
+\ B       ___/\_________________      T   _____/\ Z
d e    /\  /\ k l   _/\       _/\   _/\     ___/\_________    9
+A     ___/\_              _____/\_       /\_    Y
g h i j      /\ o   ___/\ t  /\ w   _/\_    _______/\_
+     /\_   /\         ___/\___   /\_    U  /\_
m n    /\_  s   u v    /\  /\  /\___     /\
+    C  /\ F G     ___/\_    _/\ Q  /\     V  /\
p  /\           x y z 1 2   _/\_  7 8
+      D E       _/\_   /\  /\ P   R S       W X
q r                      /\  /\
+               /\  /\ L M N O
3 4 5 6
+              H I J K

_______/\_____________________________________________________
+________________________________________________
_/\___
+                _______________________________/\_
_/\   _/\_                                  ______________________
+_______________/\___                             /\
_/\ d  /\  /\                   _____________/\_____________________
+______________    _/\_________________________  Y Z
/\ c   e f g h       ___________/\_______
+      _______/\  /\         _________________/\
a b               ___/\_____            _/\___        ________________
+_____/\___    H I J   _____/\_______________  X
/\_      _/\___      _/\   _/\   ___/\_
+        _/\_         /\_        ___________/\
i  /\   _/\   _/\   _/\ u  /\ x  /\_   /\_
+       /\  /\       K  /\_    _/\___        W
j k  /\ n  /\ q  /\ t   v w   y  /\ 2  /\_________
+      D E F G         L  /\  /\   _/\_____
l m   o p   r s             z 1   3   _______/\_
+__                      M N O P  /\     _/\
/\_
+_/\_                            Q R   _/\ V
4  /\___   /
+\  /\                                /\ U
5   _/\ 9
+A B C                               S T
/\ 8
6 7

______________________________
+_________________________________________________/\
___________________________________/\_____________________________
+______________                                    Z
_/\___________________________                  ____________________
+_____________/\_______________________________
/\                     _______/\_          _____/\_________
+                              _______________/\_
a b           _________/\_       /\_      _/\_        _____/\_________
+__                ___________/\_               /\
___/\_______   /\___  q  /\_   /\  /\_    _/\_        ______
+_/\_______      _/\_________   /\_________    X Y
___/\_    _____/\ m   _/\   r  /\ u v w  /\  /\  /\_    _/\___
+        _/\_   /\         _/\ P         _/\_
/\_   /\  /\_    l    /\ p     s t       x y z 1 2  /\  /\   _/\_
+    ___/\  /\ H I       _/\ O       ___/\  /\
c  /\ f g h  /\_      n o                           3 4 5 6  /\  /
+\  /\_  E F G         _/\ N       _/\_  U V W
d e       i  /\                                           7 8 9
+A B  /\             _/\ M        /\  /\
j k
+    C D            /\ L         Q R S T

+                  J K

________________________________________________________________
+_________/\_____________________________________
_/\___________________________
+            ___________________________________/\_
_/\                       _____/\_______________
+           /\_______________________________     /\
/\ c                     _/\_        ___________/\___________________
+          F     ___________________________/\_  Y Z
a b               _______/\  /\_    _/\_________      _______________/
+\_            _/\_________________________   /\
___/\_      n o  /\  /\         _/\   _/\_
+ /\_         /\               ___________/\ W X
___/\_   /\_        p q r s     ___/\ y  /\  /\_
+A  /\_      G H         _____/\_____      V
_/\_   /\ j  /\_                _/\_  x   z 1 2  /\___
+  B  /\_              _/\_        _/\___
/\  /\ h i   k  /\              /\  /\           3   _/\___
+    C  /\         ___/\  /\_    _/\   _/\
d e f g         l m             t u v w              /\   _/\_
+      D E        /\_  L M  /\  /\ R  /\ U
4 5  /\  /\
+                I  /\     N O P Q   S T
6 7 8 9
+                  J K

___________/\_______________________________________
___/\_______              _____________________________/
+\___
_/\_      ___/\_        ___/\_________________________
+  _/\___________
_____/\  /\   _/\_   /\   ___/\_      _____________________/\_
+ /\       _____/\___
_/\___  g h i  /\  /\ n o  /\_   /\   _/\_________________     /\
+A B   ___/\___    _/\___________
_/\   _/\       j k l m     p  /\ s t  /\       ___________/\_  8 9
+     /\_    _/\  /\     _______/\_________
/\ c  /\ f                     q r     u v     _/\_________   /\
+    C  /\  /\ H I J   _/\___          ___/\___
a b   d e                                     _/\     _____/\ 6 7
+      D E F G        /\   _/\_    ___/\_    _/\_
/\ y   _/\_    5
+                    K L  /\  /\  /\_   /\  /\  /\_
w x    /\  /\_
+                        M N O P Q  /\ T U V W X  /\
z 1 2  /\
+                                  R S           Y Z
3 4

_________________________/\___________________________
+__________________________
_____________/\_
+            _____________/\_
/\_______       /\_____________________                          ____
+___________/\_             /\_____________
a       _/\_    i         _____________/\                     ___/\___
+____         /\_____      N     _________/\___
___/\  /\_        ___/\___          u         ___________/\_
+___/\___    G   ___/\_        _/\_          _/\_
/\_  e f  /\     _/\_    _/\_____        _____/\___         /\   _/
+\_    _/\_     /\_   /\_     /\  /\_       /\  /\_
b  /\     g h    /\  /\  /\     _/\_     /\_      _/\_____  6 7  /\
+ /\  /\  /\   H  /\ K  /\   O P Q  /\___  V W X  /\
c d           j k l m n o   _/\  /\   v  /\_   /\     _/\     8 9
+A B C D E F     I J   L M         R   _/\       Y Z
/\ r s t     w  /\ z 1   _/\ 5
+                                     /\ U
p q             x y      /\ 4
+                                    S T
2 3

________________
+___________________/\_________________
_/\_______________
+________                    _________/\___
_______________________________________________/\
+    ___/\___          _____/\___        _/\___
_/\_____________________________________          1     ____________
+___/\_    _/\_____   /\___    _/\___   /\   _/\_
/\                         _____________/\_______      _/\___
+     /\  /\     _/\ K   _/\  /\   _/\ T U  /\  /\_
a b                 _______/\_                  _/\    /\   _/\___
+    C D E F   _/\ J    /\ N O P  /\ S     V W X  /\
_______/\_____   /\___            _/\ z   2 3  /\   _/\___
+             /\ I     L M       Q R             Y Z
___/\_        ___/\ o   _/\_____    _/\ y         4 5  /\   _/
+\_          G H
_/\_   /\_     /\_  n    /\     _/\  /\ x               6 7  /\
+ /\
/\  /\ g  /\_  k  /\     p q   _/\ u v w                     8 9
+A B
c d e f   h  /\   l m          /\ t
i j               r s

_______/\_____________________
+______________________
___________________________________/\_____          ______________
+_____________________/\___________
_/\___________________                  ___/\   _____/\_____________
+____________________      _______/\_
/\             _______/\_________       /\_  x  /\___    ____________
+___________________/\   _/\___     /\_
a b     _______/\_        _______/\___  u  /\   y   _/\  /\___
+                    K  /\   _/\_  R  /\___
_/\___     /\_     /\_        _/\   v w      /\ 2 3   _/\_
+                      L M  /\  /\   S   _/\_______
/\   _/\_  i  /\_  m  /\_     /\ t           z 1      /\  /\_____
+__________                N O P Q      /\       _/\
c d  /\  /\   j  /\   n  /\_  r s                     4 5 6
+_________/\___                        T U   ___/\ Z
e f g h     k l     o  /\                                   _/
+\_          _/\___                         /\_  Y
p q                                 _/\
+ /\_____   /\   _/\                       V  /\
/\ 9
+A   ___/\ F G  /\ J                         W X
7 8
+   /\_  E     H I

+  B  /\

+    C D

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.

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

I see, thanks. Nope, definitely not worth pursuing Fudgy further.

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

How do I use this? | Other CB clients
Other Users?
Others chilling in the Monastery: (5)
As of 2018-06-21 01:29 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
Should cpanminus be part of the standard Perl release?

Results (117 votes). Check out past polls.

Notices?