 No such thing as a small change PerlMonks

GP problem with tree structure using hash

by thealienz1 (Pilgrim)
 on Oct 12, 2004 at 05:17 UTC Need Help??

thealienz1 has asked for the wisdom of the Perl Monks concerning the following question:

Hello, monks... before I say anything I want to state the following question is relation to a programming project for school, so if you have any qualms about helping a student of programming - STOP READING!!!

Alright, currently what I have been working on is genetic programming - similar to genetic algorithm just with programming trees. Currently in my programming I have built a my programming tree using hashes (soemthing similar to a binary tree structure). The tree represents aither a logical operation (AND, OR, NOT) and a variable of a bit (a0, a1, d0, d1, d2, d3).

I am using genetic programming to create a tree that I hope to find a logical function that will evaluate the following truth table:

if(\$a0 eq "0" && \$a1 eq "0" && \$d0 eq "1") {return 1;} if(\$a0 eq "1" && \$a1 eq "0" && \$d1 eq "1") {return 1;} if(\$a0 eq "0" && \$a1 eq "1" && \$d2 eq "1") {return 1;} if(\$a0 eq "1" && \$a1 eq "1" && \$d3 eq "1") {return 1;} return 0;

That table is predetermined knowledge my schematic for the logical equation. I have to find a logical that follows that table for all cases from 0-63 (being the 6 bits used for a0, a1, d0, d1, d2, d3).

The following is my code for the gp solution:

#!/usr/bin/perl use strict; use List::Util qw(shuffle); #possible values the node of a tree can be my(@node_values) = ("a1","a0","d0","d1","d2","d3","AND","OR","NOT"); #probability of one of the following next genereation functions will h +appen my(@prob) = (10, #Reproduction 95, #Crossover 5);#Mutation #the minimum fitness a person must have to be considered for any nexy +genereation functions my(\$min_fitness) = 10; #defines the possible values for the truth table my(%range) = (); #will generate a logic equation and place it in a tree format #it is done recursively to a certain depth (defined in level) #this is called for intializing a population sub generate_tree() { my( \$node, \$level) = @_; unless(\$node) { \$node = {}; \$node->{left} = undef; \$node->{right} = undef; \$node->{op} = 0; } if(\$level > 0) { my(\$op) = @node_values[int(rand(\$#node_values))]; if(\$op eq "AND") { &generate_tree(\$node->{left}, \$level-1 ); &generate_tree(\$node->{right}, \$level-1 ); } if(\$op eq "OR") { &generate_tree(\$node->{left}, \$level-1 ); &generate_tree(\$node->{right}, \$level-1 ); } if(\$op eq "NOT") { &generate_tree(\$level-1, \$node->{left}); \$node->{right} = undef; } \$node->{op} = \$op; } if(\$level == 0) { \$node = {}; \$node->{left} = undef; \$node->{right} = undef; \$node->{op} = (@node_values[int(rand(6))]); } \$_ = \$node; return; } #converts a decimal number to a binary string #used to generate values for range sub dec2bin { my \$str = unpack("B32", pack("N", shift)); \$str =~ s/^0+(?=\d)//; # otherwise you'll get leading zeros return \$str; } #this initializes a population of possible solutions at a certain size sub initialize() { my(\$size) = shift; my(@people) = {}; print "Intial String:\n"; for(my \$i = 0; \$i < \$size; \$i++) { \$people[\$i]{'fitness'} = 0; &generate_tree(\$people[\$i]->{'tree'}, int(rand(6))+1 ); print &string_tree(\$people[\$i]->{'tree'}) . "\n"; } #the following generates the truth table #the equation be looked for needs to match for(my \$i = 0; \$i < 64; \$i++) { my \$value = &dec2bin(\$i); my(\$a0,\$a1,\$d0,\$d1,\$d2,\$d3) = split(//,\$value); \$range{\$value} = 0; if(\$a0 eq "0" && \$a1 eq "0" && \$d0 eq "1") {\$range{\$value} = 1 +;} if(\$a0 eq "1" && \$a1 eq "0" && \$d1 eq "1") {\$range{\$value} = 1 +;} if(\$a0 eq "0" && \$a1 eq "1" && \$d2 eq "1") {\$range{\$value} = 1 +;} if(\$a0 eq "1" && \$a1 eq "1" && \$d3 eq "1") {\$range{\$value} = 1 +;} } return(@people); } #takes a tree and evaluates it into an actual logical equation sub eval_tree() { my(\$tree) = shift; my(\$value) = shift; if(\$tree->{op} eq "AND") {return(&eval_tree(\$tree->{left},\$value) +& &eval_tree(\$tree->{right}, \$value));} if(\$tree->{op} eq "OR") {return(&eval_tree(\$tree->{left},\$value) | + &eval_tree(\$tree->{right}, \$value));} if(\$tree->{op} eq "NOT") {return(!(&eval_tree(\$tree->{left},\$value +)));} if(\$tree->{op} eq "a0") {return(substr(\$value,0));} if(\$tree->{op} eq "a1") {return(substr(\$value,1));} if(\$tree->{op} eq "d0") {return(substr(\$value,2));} if(\$tree->{op} eq "d1") {return(substr(\$value,3));} if(\$tree->{op} eq "d2") {return(substr(\$value,4));} if(\$tree->{op} eq "d3") {return(substr(\$value,5));} } sub calc_fitness() { my(@people) = @_; for(my \$i = 0; \$i < \$#people; \$i++) { \$people[\$i]{'fitness'} = 0; foreach my \$value (keys %range) { if(&eval_tree(\$people[\$i]{'tree'}, \$value) == \$range{\$valu +e}) {\$people[\$i]{'fitness'}++;} } } return(@people); } #takes a tree and converts it into a string sub string_tree() { my(\$tree) = shift; my(\$value) = shift; if(\$tree->{op} eq "AND") {return("(" . &string_tree(\$tree->{left}, +\$value) . " AND " . &string_tree(\$tree->{right}, \$value) . ")");} if(\$tree->{op} eq "OR") {return("(" . &string_tree(\$tree->{left},\$ +value) . " OR " . &string_tree(\$tree->{right}, \$value) . ")");} if(\$tree->{op} eq "NOT") {return("(NOT " . (&string_tree(\$tree->{l +eft},\$value)) . ")");} if(\$tree->{op} eq "a0") {return("a0");} if(\$tree->{op} eq "a1") {return("a1");} if(\$tree->{op} eq "d0") {return("d0");} if(\$tree->{op} eq "d1") {return("d1");} if(\$tree->{op} eq "d2") {return("d2");} if(\$tree->{op} eq "d3") {return("d3");} } sub found_solution() { my(@people) = @_; for(my \$i = 0; \$i < \$#people; \$i++) { if(\$people[\$i]->{'fitness'} == 64) { print "Solution Found:\n"; print &string_tree(\$people[\$i]->{'tree'}); return(1); } } return(0); } sub get_all_Descendents() { my(\$node) = shift; my(@children) = (); if(\$node->{left} ne undef) {push(@children, &get_all_Descendents(\$ +node->{left}));} push(@children, \\$node); if(\$node->{right} ne undef) {push(@children, &get_all_Descendents( +\$node->{right}));} return(@children); } for(my \$size = 100; \$size < 101; \$size++) { print "Size: \$size\n"; my(@population) = &initialize(\$size); my(\$generation) = 0; my \$quit = 0; while(\$quit == 0){ @population = &calc_fitness(@population); if(&found_solution(@population)) { print "\tFinal Generation: \$generation\n"; \$quit = 1; } else{ my(@children) = (); my(\$children_size) = 0; while(\$children_size < \$size) { my(\$choice) = int(rand(100) + 1); if((\$choice >= 1) && (\$choice <= \$prob)) { #Reproduction my(\$person_a) = int(rand(\$size)); while(\$population[\$person_a]->{'fitness'} < \$min_f +itness) {\$person_a = int(rand(\$size));} push(@children,\$population[\$person_a]); \$children_size++; } if((\$choice > \$prob) && (\$choice <= \$prob)) { #Crossover my(\$person_a)= int(rand(\$size)); my(\$person_b)= int(rand(\$size)); while(\$population[\$person_a]->{'fitness'} < \$min_f +itness && \$population[\$person_b]->{'fitness'} < \$min_fitness) { \$person_a = int(rand(\$size)); \$person_b = int(rand(\$size)); } print "Person A: "; print &string_tree(\$population[\$person_a]{'tree'}) + . "\n"; my(\$child_a) = (shuffle &get_all_Descendents(\$popu +lation[\$person_a]->{'tree'})); my(\$child_b) = (shuffle &get_all_Descendents(\$popu +lation[\$person_b]->{'tree'})); (\$child_a, \$child_b) = (\$child_b, \$child_a); print "Child A: " . &string_tree(\$population[\$pers +on_a]->{'tree'}) . "\n"; push(@children,\$population[\$person_a]); push(@children,\$population[\$person_b]); \$children_size+=2; } if((\$choice > \$prob) && (\$choice <= 100)) { #Mutations my(\$person_a) = int(rand(\$size)); while(\$population[\$person_a]->{'fitness'} < \$min_f +itness) {\$person_a = int(rand(\$size));} my(\$child_a) = (shuffle &get_all_Descendents(\$popu +lation[\$person_a]->{'tree'})); &generate_tree(\$child_a, int(rand(3))+1); push(@children,\$population[\$person_a]); \$children_size++; } } \$generation++; @population = @children; } } }

I believe it to logically work, but am having trouble with one section of my code. I have represented the data of the tree using a hash based on some code found. I know my tree structure is working correctly because I can tranverse the tree and evaluate correctly, but my problem lies in the fact that crossover and mutation.

Crossover and mutation are fundamental in the process of genetic algorithm or programming, but with the tree hash structure I am having a bit of a problem. Crossover is when two individuals exchange nodes of their tree and mutation is when a random node of an individual is changed in value. Well the problem I having is selecting that random node, since my tree is a hash within a hash (ie \$tree->{left}{left}{right} = "AND") I do not know how to select that random node.

Currently, I have created a function that tranverses a tree and is supposed to genereate a array of hash references - as seen in sub get_all_Descendents, but it does not appear to work for my purposes. I will admit this is because of a lack of understanding on my part.

I'd appreciate any insight into this problem. I posted all my code on here, so people could tinker with it if they wanted too.

Regards,
JT Archie

Replies are listed 'Best First'.
Re: GP problem with tree structure using hash
by BrowserUk (Pope) on Oct 12, 2004 at 06:41 UTC

If you add -w or use warnings to the top of your code you will get a whole heap of warning messages. Fixing these will get you a lot closer to seeing what is wrong with your code.

A few hints:

In your dec2bin sub, you are stripping leading zeros, but then relying upon having exactly 6 '1's or '0's when you later split the return value.

Instead, us substr to return just the part of the string you want:

sub dec2bin { my \$str = unpack("B32", pack("N", shift)); # \$str =~ s/^0+(?=\d)//; # otherwise you'll get leading zeros return substr( \$str, -6 ); }

That will rid you of a couple of hundred runtime warnings.

There are a couple of places where you are trying to test a value for being undef using:

if( \$value eq undef ) { ...

That is much better done as

if( defined \$value ) { ...

You are building your %range hash in a sub, but the hash is defined outside. Effectively a global which generally a frowned upon practice.

The logic of your truth table is that values 8 .. 15, and 49, 51, 53, 55, 57, 59, 61, 63 are set to 1 and the rest 0. You may or may not see a way to use this information to do the initialisation in a better way?

When iterating over a simple range of integers in Perl, it's generally considered more readable and easier to code that as:

for my \$i ( 0 .. 63 ) { ... }

but it's ultimately a personal preference thing.

To select a random node you could use:

\$tree->{ ('left', 'right')[ rand 2 ] } { ('left', 'right')[ rand 2 ] } { ('left', 'right')[ rand 2 ] } = 'AND';;

Again, you may see a better way to code that.

Examine what is said, not who speaks.
"Efficiency is intelligent laziness." -David Dunham
"Think for yourself!" - Abigail
"Memory, processor, disk in that order on the hardware side. Algorithm, algorithm, algorithm on the code side." - tachyon
Re: GP problem with tree structure using hash
by kvale (Monsignor) on Oct 12, 2004 at 06:22 UTC
For a tree represented as a recursive hash, the crossover and mutation operators are fairly simple.

It looks like you have only binomial operators, so a binary tree. To arrive at a random node, start at the root, \$tree, and pick a random key, "left" or right". Then ,e.g., \$tree->{left} becomes the new root and pick another random key, etc. Continue walking the hash until you get to a terminal, which you can recognize as a non-reference. Alter that terminal to get a one-point mutation.

For a crossover, each node on the tree is a ref, so you can just exchange references:

\$temp = \$tree->{right}{left}; \$tree->{right}{left} = \$tree->{right}{right}; \$tree->{right}{right} = temp;
For Boolean expression chromosomes, you will want to make sure that mutations and crossovers generate a syntatctically valid expression (I haven't checked your code for this).

That is the general idea. The implementation is left as an exercise :)

-Mark

Re: GP problem with tree structure using hash
by tilly (Archbishop) on Oct 12, 2004 at 06:37 UTC
In addition to the bug that kvale pointed out, you need to make deep copies in the reproduction step. A shallow copy (like you're making) means that when you modify one copy you also modify the other.
Re: GP problem with tree structure using hash
by thealienz1 (Pilgrim) on Oct 12, 2004 at 17:36 UTC

As per your suggestions, the following is the updated code, but as of now it gives me an error of "Out of memory!" after running for a while. It might that I am testing it out on a school system with several people online, or that I am just using too much memory with \$hashes. I will let you know the results when I get home.

#!/usr/bin/perl use strict; use warnings; #possible values the node of a tree can be my(@node_values) = ("a1","a0","d0","d1","d2","d3","AND","OR","NOT"); #probability of one of the following next genereation functions will h +appen my(@prob) = (10, #Reproduction 95, #Crossover 5);#Mutation #the minimum fitness a person must have to be considered for any nexy +genereation functions my(\$min_fitness) = 10; #defines the possible values for the truth table my(%range) = (); #will generate a logic equation and place it in a tree format #it is done recursively to a certain depth (defined in level) #this is called for intializing a population sub generate_tree() { my( \$node, \$level) = @_; unless(\$node) { \$node = {}; \$node->{left} = undef; \$node->{right} = undef; \$node->{op} = 0; } if(\$level > 0) { my(\$op) = @node_values[int(rand(\$#node_values))]; if(\$op eq "AND") { &generate_tree(\$node->{left}, \$level-1 ); &generate_tree(\$node->{right}, \$level-1 ); } if(\$op eq "OR") { &generate_tree(\$node->{left}, \$level-1 ); &generate_tree(\$node->{right}, \$level-1 ); } if(\$op eq "NOT") { &generate_tree(\$level-1, \$node->{left}); \$node->{right} = undef; } \$node->{op} = \$op; } if(\$level == 0) { \$node = {}; \$node->{left} = undef; \$node->{right} = undef; \$node->{op} = (@node_values[int(rand(6))]); } \$_ = \$node; return; } #converts a decimal number to a binary string #used to generate values for range sub dec2bin { my \$str = unpack("B32", pack("N", shift)); \$str =~ s/^0+(?=\d)//; # otherwise you'll get leading zeros return substr(\$str, -6); } #this initializes a population of possible solutions at a certain size sub initialize() { my(\$size) = shift; my(@people) = {}; print "Intial String:\n"; for(my \$i = 0; \$i < \$size; \$i++) { \$people[\$i]{'fitness'} = 0; &generate_tree(\$people[\$i]->{'tree'}, int(rand(6))+1 ); print &string_tree(\$people[\$i]->{'tree'}) . "\n"; } #the following generates the truth table #the equation be looked for needs to match for(my \$i = 0; \$i < 64; \$i++) { my \$value = &dec2bin(\$i); my(\$a0,\$a1,\$d0,\$d1,\$d2,\$d3) = split(//,\$value); \$range{\$value} = 0; if(\$a0 eq "0" && \$a1 eq "0" && \$d0 eq "1") {\$range{\$value} = 1 +;} if(\$a0 eq "1" && \$a1 eq "0" && \$d1 eq "1") {\$range{\$value} = 1 +;} if(\$a0 eq "0" && \$a1 eq "1" && \$d2 eq "1") {\$range{\$value} = 1 +;} if(\$a0 eq "1" && \$a1 eq "1" && \$d3 eq "1") {\$range{\$value} = 1 +;} } return(@people); } #takes a tree and evaluates it into an actual logical equation sub eval_tree() { my(\$tree) = shift; my(\$value) = shift; if(\$tree->{op} eq "AND") {return(&eval_tree(\$tree->{left},\$value) +& &eval_tree(\$tree->{right}, \$value));} if(\$tree->{op} eq "OR") {return(&eval_tree(\$tree->{left},\$value) | + &eval_tree(\$tree->{right}, \$value));} if(\$tree->{op} eq "NOT") {return(!(&eval_tree(\$tree->{left},\$value +)));} if(\$tree->{op} eq "a0") {return(substr(\$value,0));} if(\$tree->{op} eq "a1") {return(substr(\$value,1));} if(\$tree->{op} eq "d0") {return(substr(\$value,2));} if(\$tree->{op} eq "d1") {return(substr(\$value,3));} if(\$tree->{op} eq "d2") {return(substr(\$value,4));} if(\$tree->{op} eq "d3") {return(substr(\$value,5));} } sub calc_fitness() { my(@people) = @_; for(my \$i = 0; \$i < \$#people; \$i++) { \$people[\$i]{'fitness'} = 0; foreach my \$value (keys %range) { if(&eval_tree(\$people[\$i]{'tree'}, \$value) == \$range{\$valu +e}) {\$people[\$i]{'fitness'}++;} } } return(@people); } #takes a tree and converts it into a string sub string_tree() { my(\$tree) = shift; my(\$value) = shift; if(\$tree->{op} eq "AND") {return("(" . &string_tree(\$tree->{left}, +\$value) . " AND " . &string_tree(\$tree->{right}, \$value) . ")");} if(\$tree->{op} eq "OR") {return("(" . &string_tree(\$tree->{left},\$ +value) . " OR " . &string_tree(\$tree->{right}, \$value) . ")");} if(\$tree->{op} eq "NOT") {return("(NOT " . (&string_tree(\$tree->{l +eft},\$value)) . ")");} if(\$tree->{op} eq "a0") {return("a0");} if(\$tree->{op} eq "a1") {return("a1");} if(\$tree->{op} eq "d0") {return("d0");} if(\$tree->{op} eq "d1") {return("d1");} if(\$tree->{op} eq "d2") {return("d2");} if(\$tree->{op} eq "d3") {return("d3");} } sub found_solution() { my(@people) = @_; for(my \$i = 0; \$i < \$#people; \$i++) { if(\$people[\$i]->{'fitness'} == 64) { print "Solution Found:\n"; print &string_tree(\$people[\$i]->{'tree'}); return(1); } } return(0); } sub get_random_node() { my(\$tree) = shift; my(\$prob) = int(rand(100)); if(\$prob < 40 && defined (\$tree->{left})) {return(get_random_node( +\$tree->{left}));} if(\$prob > 60 && defined (\$tree->{right})) {return(get_random_node +(\$tree->{right}));} return(\$tree); } sub replace_node() { my(\$tree,\$a,\$b) = @_; if(\$tree == \$a) { \$tree = \$b; } else{ if(defined(\$tree->{left})) {&replace_node(\$tree->{left},\$a,\$b) +;} if(defined(\$tree->{right})) {&replace_node(\$tree->{right},\$a,\$ +b);} } \$_ = \$tree; return; } sub crossover() { my(\$tree_a, \$tree_b) = @_; my(\$node_a) = &get_random_node(\$tree_a); my(\$node_b) = &get_random_node(\$tree_b); &replace_node(\$tree_a, \$node_a, \$node_b); &replace_node(\$tree_b, \$node_b, \$node_a); return(\$tree_a, \$tree_b); } sub mutation() { my(\$tree) = shift; my(\$node_a) = &get_random_node(\$tree); my(\$node_b) = {}; &generate_tree(\$node_b, int(rand(3))+1 ); &replace_node(\$tree, \$node_a, \$node_b); return(\$tree); } for(my \$size = 100; \$size < 101; \$size++) { print "Size: \$size\n"; my(@population) = &initialize(\$size); my(\$generation) = 0; my \$quit = 0; while(\$quit == 0){ @population = &calc_fitness(@population); if(&found_solution(@population)) { print "\tFinal Generation: \$generation\n"; \$quit = 1; } else{ my(@children) = (); my(\$children_size) = 0; while(\$children_size < \$size) { my(\$choice) = int(rand(100) + 1); if((\$choice >= 1) && (\$choice <= \$prob)) { #Reproduction my(\$person_a) = int(rand(\$size)); while(\$population[\$person_a]->{'fitness'} < \$min_f +itness) {\$person_a = int(rand(\$size));} push(@children,\$population[\$person_a]); \$children_size++; } if((\$choice > \$prob) && (\$choice <= \$prob)) { #Crossover my(\$person_a)= int(rand(\$size)); my(\$person_b)= int(rand(\$size)); while(\$population[\$person_a]->{'fitness'} < \$min_f +itness && \$population[\$person_b]->{'fitness'} < \$min_fitness && \$pers +on_a != \$person_b) { \$person_a = int(rand(\$size)); \$person_b = int(rand(\$size)); } my(\$child_a, \$child_b) = {}; #print "A : " . &string_tree(\$population[\$person_a +]->{'tree'}) . "\n"; (\$child_a->{'tree'},\$child_b->{'tree'}) = &crossov +er(\$population[\$person_a]->{'tree'},\$population[\$person_b]->{'tree'}) +; #print "CA : " . &string_tree(\$child_a->{'tree'}) +. "\n"; push(@children,\$child_a); push(@children,\$child_b); \$children_size+=2; } if((\$choice > \$prob) && (\$choice <= 100)) { #Mutations my(\$person_a) = int(rand(\$size)); while(\$population[\$person_a]->{'fitness'} < \$min_f +itness) {\$person_a = int(rand(\$size));} my(\$child_a) = {}; #print "MA : " . &string_tree(\$population[\$person_ +a]->{'tree'}) . "\n"; (\$child_a->{'tree'}) = (&mutation(\$population[\$per +son_a]->{'tree'})); #print "MA1 : " . &string_tree(\$child_a->{'tree'}) + . "\n"; push(@children,\$child_a); \$children_size++; } } \$generation++; @population = @children; } } }

Thanks for the help.

Your modified code is still producing a large number of warnings. This is because of the "trim leading zeros" substitution in your dec2bin() routine. You added the substr, but left the s///, which means that the return value is often devoid of the leading zeros you require.

sub dec2bin { my \$str = unpack("B32", pack("N", shift)); return substr(\$str, -6); }

After that, the memory problem occurs because your crossover() routine is going into deep recursion. Ie. Once it starts recursing, it never stops. Part of the problem for this is your using empty brackets after the sunroutine names. This is called an "empty prototype" and has a very particular meaning in Perl. The explanation is long and difficult. For now, remove them; from all of your routines. You do not need them and they are having a totally different effect than you think thay are.

Once you remove the "()" from after the subroutine names (eg. sub mutation() { becomes sub mutation { ), the program operates somewhat differently. It still goes into deep recursion, but this time:

Deep recursion on subroutine "main::replace_node" at P:\test\398622.pl + line 155.

Looking at that routine

sub replace_node { my(\$tree,\$a,\$b) = @_; if(\$tree == \$a) { \$tree = \$b; } else{ if(defined(\$tree->{left})) { &replace_node(\$tree->{left},\$a,\$b); } if(defined(\$tree->{right})) { &replace_node(\$tree->{right},\$a,\$b); } } \$_ = \$tree; return; }

The first thing I noticed is that you are using '&' on the front of your calls to subroutines. Again, this has a very specific meaning in Perl, and it does something special in some circumstances that you almost certainly don't want. So remove them--all of them.

That also makes you code run differently. The explaination of what and how I frankly haven't analysed, and you probably wouldn't be interested in the detail if I had. For now, don't use prototypes or '&'s. At least until you have discovered the reason why you might want to use them on some, rare occasions.

The other thing I noticed in the routine above is:

\$_ = \$tree; return;

What do you think that this code is doing? I ask, because it almost certainly isn't doing what you think it is doing.

The upshot is that it seems fairly likely that you have started out with a program written in some langauge other than Perl, and are trying to adapt it to Perl. The problem with that is that Perl uses some syntax that looks vaguely similar to syntax found in other langauges, but uses it in quite different ways, which breaks horribly if you use them incorrectly.

It is clear that you are not testing your routines individually before trying to combine them together into a large and complicated program. That makes debugging extremely hard as you will often see the effects of several bugs combine to produce situations that no one single change will correct. That leaves you trying something, no apparent change occurs so you back the change out and try something else, when what is required is that first change plus one (or two or three) others to make thing better. It's a sole destroying way to debug code.

Try constructing a simple tree, just a parent node and two children, and then test each of your routines on that individually. Once you get one routine working correctly, move onto the next. Once you have them all working on the simple case, manually construct a slightly more complex tree and try them again. If they still work, you stand a chance that when youstart putting them together, they will cooperatively work also.

That may sound laborious but it is a simple piece of math. If you have 10 routines each with one bug, and you fix them one at a time, you will need 10 changes.

If you try to fix them in combination, you may have to go through 10! (3,628,800) combinations of changes before you find the right one. You decide which is laborious:)

Finally, when you are developing and testing a program that uses rand to generate test data, or control program flow in a random fashion, stick an

srand(1);
at the top of the program. The program will still generate random data, and follow a random path, but by initilaise the PRNG with a constant, it will be the same random data, and the same random path for each run of the program (until you change the constant or remove the statement).

It makes it a lot easier if you encounter the same bugs in the same order. When you make changes, you will see the effects of thse changes and not just the effects of processing a different set of random data.

As I have already made all the changes I've mentioned above, I'm going to post the version I have to save you a little time. You'll find that all your comments have been removed. I use an automated process to reformat other peoples code into a "standard format" which I find easier to read, but it strips the comments. Sorry.

Still, if you do the right thing and compare this version line-by-line with your own, you will see lots of places where you are using unnecessary extra syntax (brackets etc.) that just complicate things. Anyway, I hope this helps you to get started on debugging this:

Examine what is said, not who speaks.
"Efficiency is intelligent laziness." -David Dunham
"Think for yourself!" - Abigail
"Memory, processor, disk in that order on the hardware side. Algorithm, algorithm, algorithm on the code side." - tachyon
Re: GP problem with tree structure using hash
by Anonymous Monk on Oct 12, 2004 at 21:58 UTC
Hello, monks... before I say anything I want to state the following question is relation to a programming project for school, so if you have any qualms about helping a student of programming - STOP READING!!!
What monks have problem with is students asking someone to do their homework for them. Thats not the case here. OK!!!

I just meant the fact that it is for a project I did not want anyone to imply that I was cheating or anything.

Create A New User
Node Status?
node history
Node Type: perlquestion [id://398370]
Approved by davido
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others cooling their heels in the Monastery: (9)
As of 2019-10-14 23:07 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
In 2019 the site I miss most is:

Results (36 votes). Check out past polls.

Notices?