Re^2: Challenge: Perl 5: lazy sameFinge()?

[Laurent_R]

Beautiful.

I made a first try to traverse the tree recursively and then figured out that it does not work for comparing two trees, it seems impossible (or at least very complicated) to recurse on two data structures simultaneously.

So, I figured out that I probably needed an iterator (well actually two iterator functions) to return the leaves on demand, leading to a solution quite similar (at least in spirit) to yours, but, since I have done that only once or twice before, and quite some time ago, I had to go back to Mark-Jason Dominus' Higher Order Perl book to figure out how to do that. My iterators now seem to work more or less properly (although they are somewhat clumsy compared to yours), so that I am almost there (the main loop is not very complicated), but you did it before (and better).

Your code definitely looks much better than what I have so far, so that, unless I come with a brilliant new idea (unlikely), I will not submit mine;

Congratulations, roboticus. Beautiful work.

To LanX: using iterators is what is needed to make the process lazy (there may be other solutions, but this is a good one), or to make it possible to have it lazy. roboticus did not really make it completely lazy (the program is counting the number of differences, rather than exiting at the first difference), but it only takes a minor change to make it truly lazy (if we have the same understanding of lazyness).

BTW, roboticus, it would be good to publish your solution on the Rosetta Stone site: when you see solutions in some languages taking 200 lines of code or more, and a solution like yours taking more than 10 times less code, you get a certain picture of the amount of effort to get something done in various languages. ADA or Java, just to name two, are very powerful languages, no doubt, but need a lot of efforts to do something simple. In contrast, languages like Perl, Python, Haskell or Lisp (just a few examples) have much more expressive power. And, even thougn IT managers usually don't really understand the difference, they do if you tell them: "well this I can do in two weeks with XYZ super-duper object language , and in 2 days in Perl or Haskel (or Lisp, or whatever).

[roboticus]

Laurent_R:

Don't worry about it, post your solution--One of the fun things about programming is seeing how other people do things, and then learning their techniques! Not only that someone might offer a suggestion to you that could lead in a different and better direction. As LanX mentioned, mine's computationally expensive. That's not a real problem in this case. But if someone needed to compute as many fringes per second as possible, then a faster solution would be helpful. I can't help but feel that there's an even nicer way to do it, but I haven't thought of it yet.

Also, the code above wasn't my first shot at it. It was an interesting problem, so I spent a bit of time on it. I went through six iterations to get it as simple as it is now. Once I had some functional code, I thought that there was just too much special-case handling code. So I tried to rearrange things to remove the special cases. It's pretty simple in the final version, but I didn't see the simple version at first--I seem to have a habit of seeing the trees before noticing the forest.

It took me six iterations to get to the version I posted. My first version was this:

sub tree_iterator {
    return undef unless @stack;
    my $tos = pop @stack;
    return $tos unless ref $tos eq 'ARRAY';
    my ($L, $R) = @$tos;
    print "ENTER ($L, $R)\n";
    while (1) {
        print "LOOP: ($L, $R)\n";
        push @stack, $R if defined $R;
        if (defined $L) {
            return $L if ref $L ne 'ARRAY';
            ($L, $R) = @$L;
            redo;
        }
        else {
            ($L, $R) = @{pop @stack};
        }
    }
}

(This is before I wrapped up the stack in a closure to make the iterator useful.) As you can see, there are just too many special cases in there. Each time I removed one special case, it gave me an idea for the next one. I'm pretty happy with the version I ultimately wound up with, even though I suspect that it could be better yet. It would be pretty nice if I could think up a nice simple way to do it and reduce the array rebuilds, too. I tried to switch back to the push/pop, as I think that would be more efficient, but most of the special cases were due to my use of push/pop at the start. Switching to shift/unshift allowed me to remove one or two odd bits.

I think I have a rosetta code login at work, so I'll try to remember to post it there on Monday.

And, even though IT managers usually don't really understand the difference, they do if you tell them: "well this I can do in two weeks with XYZ super-duper object language , and in 2 days in Perl or Haskel (or Lisp, or whatever).

I wish the people at $work were susceptible to that argument. I used this very argument at work the other day. They needed a file generated, so I quoted a day in Perl or a week in .Net or PL/SQL. Also, I mentioned that due to time pressures on the current project, I could just squeeze the Perl version into my schedule. There's little Perl expertise at $work, and they're fearful enough of it, that they opted to do it in PL/SQL. 10 days later and it works. Luckily, due to the time pressures, *I* didn't have to do the task. But I'm frequently surprised when it's "rush rush rush!" but when you want to do it with a tool they're uncomfortable with, saving all the time in the world wouldn't be enough for them. ...sigh...

...roboticus

When your only tool is a hammer, all problems look like your thumb.

[Laurent_R]

Don't worry about it, post your solution.

Well, thank you for your answer. After I wrote my previous message, I found that my iterator was not working properly (it worked on my initial test tree, but not on a more complicated tree). I thought I was going to have trouble using a closure, because I don't do that very often, but that turned out to be easy, my problem was to traverse properly the tree without doing stupid mistakes: in some cases I did not get all the leaves, in others I got some duplicate leaves. I *think* that I have it right now. I posted my solution below.

[LanX]

> As LanX mentioned, mine's computationally expensive.

actually LanX didn't realize that it's only meant for binary trees! =)

So your solution shouldn't be more expensive than e.g. hdbs.

(Perl's arrays are almost as efficient as linked lists, shift and unshift often just change internal pointers w/o expensive allocations)

[roboticus]

Laurent_R:

As I mentioned yesterday, seeing what other people do can give you inspiration. Case in point: I just reviewed the solution hdb posted, and got the hint I needed to make mine better: Rather than using just a stack, hdb uses a stack and a reference to the current (sub)tree being worked on. By using the same I idea, I was able to come up with a new version of get_tree_iterator that I like even better:

sub get_tree_iterator {
    my @rtrees=(shift);
    my $tree;
    return sub {
        $tree=pop @rtrees;
        ($tree, $rtrees[@rtrees]) = @$tree while ref $tree;
        return $tree;
    }
}

This version still descends down the left tree until it hits a leaf, but it uses much less manipulation of the @stack array, and uses the right hand side of the array, which is (I expect) more efficient than the left side. (Editing the right side of the array may cause an expansion of the array, but I'm thinking that expanding the left side of the array may cause unnecessary array copies.)

When I look at this version, I don't feel like I'm missing anything. (Not to say that I'm not--It's amazing how often one can make significant improvements to "optimized" code.)

...roboticus

When your only tool is a hammer, all problems look like your thumb.