Tree as a tool for enumeration - CY's take on PWC#053 Task 2

This is a part of Perl Weekly Challenge(PWC) #053 and the followings are related to my solution. If you want to challenge yourself on Perl, go to https://perlweeklychallenge.org, code the latest challenges, submit codes on-time (by GitHub or email) if possible, before reading my blog post.

Do tell me if I am wrong or you strongly oppose my statements!

( The first task is simple.
Not much to say about this task.
4-3 = 1; 4-2 =2; 4-1 = 3.
(Honestly I haven't coded on it. :P) )

Here for the second task.

Somehow, it looks like those base-10 special property tasks, e.g. multiples consisting of 1's and 0's(#49), stepping numbers(#052), gapful number(#047) or colourful numbers(#051). Like those base-10 tasks, the possible brute-force way is: list out all possible combinations or permutations, and then exclude unfit candidates (equivalently, only print suitable candidates).

Given the maximum requested length is just 5, an estimation for the size of the solution set: 5×4×5×4×5 = 2000. Not really a big number, right?

However, the restriction of this task is delicate. We have more effective ways to do it.

Last time (my post on PWC#052) I used an array as it was a binary tree. Now I must have face the tree structure! Luckily there are many Perl modules on trees.

After a brief browsing on CPAN, I decided to use the module Tree for my implementation. ( Tree::DAG_Node and Tree::Node may be suitable for the challenge also.)

Before writing for the challenge, I had to play around with it a bit before calling forth on the task. I used its synopsis content on CPAN for familiarizing.

OK, time to work. My idea is like this. The value of each node is a vowel letter. Two subroutines have to be written by myself: a depth-first traverse routine which the tree node has depth N (with return values of what letters have been traversed), and a routine requests the node(s) "produce child(ren)" are needed.

It seems that it doesn't matter much whether the traversal is preorder or postorder. (?)

It turns out my code gives 107 vowel strings for N=5. (Compare it with what I said in the beginning of this post.)

---
I think it is better to provide the link for my code after the deadline. However, it makes more fun to read the blog post if there are some codes. Hence my subroutine asking the tree to grow:

# grow : traverse and force the tree nodes produce child(ren)
sub grow {
    my ($t, $d) = ($_[0], $_[1]);
 #$t is a Tree object, $d is the expected depth of tree produce_child($t); my @t_baby = $t->children; foreach (@t_baby) { grow($_, $d) if $_->depth < $d; } } # after some boo and foo... grow($vowel, 5); traverse_and_named($vowel, $N, "");

It costs me roughly 3 hours for coding. And I get the data structure trees inside my programming toolkit now!


codes: https://github.com/manwar/perlweeklychallenge-club/blob/master/challenge-053/cheok-yin-fung/perl/ch-2.pl

Leave a comment

About C.-Y. Fung

user-pic a beginner in programming; passionate in mathematics, distance running and gender issues; from Hong Kong. https://twitter.com/e7_87